# Cyclic Pattern Containment and Avoidance

Rachel Domagalski
Department of Mathematics, Michigan State University,
East Lansing, MI 48824-1027, USA<EMAIL_ADDRESS>
Jinting Liang
Department of Mathematics, Michigan State University,
East Lansing, MI 48824-1027, USA<EMAIL_ADDRESS>
Quinn Minnich
Department of Mathematics, Michigan State University,
East Lansing, MI 48824-1027, USA<EMAIL_ADDRESS>
Bruce E. Sagan
Department of Mathematics, Michigan State University,
East Lansing, MI 48824-1027, USA<EMAIL_ADDRESS>
Jamie Schmidt
Department of Mathematics, Michigan State University,
East Lansing, MI 48824-1027, USA<EMAIL_ADDRESS>
Alexander Sietsema
Department of Mathematics, Michigan State University,
East Lansing, MI 48824-1027, USA<EMAIL_ADDRESS>
(
Key Words: cyclic descent, cyclic permutation, Erdős-Szekeres Theorem, pattern
avoidance, pattern containment
AMS subject classification (2010): 05A05 (Primary) 05A15, 05A19 (Secondary) )

###### Abstract

The study of pattern containment and avoidance for linear permutations is a
well-established area of enumerative combinatorics. A cyclic permutation is
the set of all rotations of a linear permutation. Callan initiated the study
of permutation avoidance in cyclic permutations and characterized the
avoidance classes for all single permutations of length $4$. We continue this
work. In particular, we establish a cyclic variant of the Erdős-Szekeres
Theorem that any linear permutation of length $mn+1$ must contain either the
increasing pattern of length $m+1$ or the decreasing pattern of length $n+1$.
We then derive results about avoidance of multiple patterns of length $4$. We
also determine generating functions for the cyclic descent statistic on these
classes. Finally, we end with various open questions and avenues for future
research.

##  1 Introduction

We first review some notions from the well-studied theory of patterns in
(linear) permutations. More information on this topic can be found in the
texts of Bóna [Bón04], Sagan [Sag20], or Stanley [Sta97, Sta99]. Let
${\mathbb{N}}$ be the nonnegative integers. If $m,n\in{\mathbb{N}}$ then we
define $[m,n]=\\{m,m+1,\ldots,n\\}$ which we abbreviate to $[n]=[1,n]$ when
$m=1$. Consider the symmetric group ${\mathfrak{S}}_{n}$ of all permutations
$\pi=\pi_{1}\pi_{2}\ldots\pi_{n}$ of $[n]$ written in one-line notation. We
call $n$ the length of $\pi$ and write $|\pi|=n$. We will sometimes put commas
between the elements of $\pi$ for readability. We say that two sequences of
distinct integers $\pi=\pi_{1}\ldots\pi_{k}$ and
$\sigma=\sigma_{1}\ldots\sigma_{k}$ are order isomorphic, written
$\pi\cong\sigma$, whenever $\pi_{i}<\pi_{j}$ if and only if
$\sigma_{i}<\sigma_{j}$. If $\sigma\in{\mathfrak{S}}_{n}$ and
$\pi\in{\mathfrak{S}}_{k}$ then $\sigma$ contains $\pi$ as a pattern if there
is a subsequence $\sigma^{\prime}$ of $\sigma$ with $|\sigma^{\prime}|=k$ and
$\sigma^{\prime}\cong\pi$. If no such subsequence exists then $\sigma$ avoids
$\pi$. We use the notation

$\operatorname{Av}_{n}(\pi)=\\{\sigma\in{\mathfrak{S}}_{n}\mid\text{$\sigma$
avoids $\pi$}\\}$

for the avoidance class of $\pi$. For example $\sigma=42351$ contains the
pattern $\pi=3241$ because of the subsequence $4251$ among others. But it
avoids $1234$ because it has no increasing subsequence of length $4$. One can
extend this notion to sets of permutations $\Pi$ by letting

$\operatorname{Av}_{n}(\Pi)=\\{\sigma\in{\mathfrak{S}}_{n}\mid\text{$\sigma$
avoids all $\pi\in\Pi$}\\}=\bigcap_{\pi\in\Pi}\operatorname{Av}_{n}(\pi).$

A famous theorem of Erdős and Szekeres [ES35] can be stated in terms of
pattern containment and avoidance. Let

$\iota_{n}=12\ldots n$

and

$\delta_{n}=n\ldots 21$

be the increasing and decreasing permutations of length $n$, respectively.

######  Theorem 1.1 ([ES35]).

Suppose $m,n\in{\mathbb{N}}$. Then any $\sigma\in{\mathfrak{S}}_{mn+1}$
contains either $\iota_{m+1}$ or $\delta_{n+1}$. This is the best possible in
that there exist permutations in ${\mathfrak{S}}_{mn}$ which avoid both
$\iota_{m+1}$ and $\delta_{n+1}$. ∎

$1$$2$$3$$4$$5$$1$$2$$3$$4$$5$

$1$$2$$3$$4$$5$$1$$2$$3$$4$$5$

Figure 1: The graph of $42351$ on the left and of $[42351]$ on the right

The diagram of $\pi\in{\mathfrak{S}}_{n}$ is the collection of points
$(i,\pi_{i})$ in the first quadrant of the Cartesian plane. The graphical
representation of $\pi=42351$ is given on the left in Figure 1. It follows
that we can act on $\pi$ with the dihedral group of the square

$D_{4}=\\{\rho_{0},\rho_{90},\rho_{180},\rho_{270},r_{0},r_{1},r_{-1},r_{\infty}\\}$

where $\rho_{\theta}$ is rotation counterclockwise through $\theta$ degrees
and $r_{m}$ is reflection in a line of slope $m$. We wish to write some of
these rigid motions in terms of the one-line notation for
$\pi=\pi_{1}\pi_{2}\ldots\pi_{n}$. Reflection in a vertical line gives the
reversal of $\pi$ which is

$\pi^{r}=\pi_{n}\ldots\pi_{2}\pi_{1}.$

Similarly, reflection in a horizontal line results in the complement of $\pi$

$\pi^{c}=n+1-\pi_{1},\hskip 7.0ptn+1-\pi_{2},\hskip 7.0pt\ldots,\hskip
7.0ptn+1-\pi_{n}.$

Combining these two operations gives rotation by $180$ degree or reverse
complement

$\pi^{rc}=n+1-\pi_{n},\hskip 7.0pt\ldots,\hskip 7.0ptn+1-\pi_{2},\hskip
7.0ptn+1-\pi_{1}.$

We apply any of these operations to sets of permutations by applying them to
each element of the set.

We can use diagrams to inflate permutations. If we are given
$\pi=\pi_{1}\pi_{2}\ldots\pi_{n}\in{\mathfrak{S}}_{n}$ and permutations
$\sigma_{1},\sigma_{2},\ldots,\sigma_{n}$ then the inflation of $\pi$ by the
$\sigma_{i}$ is the permutation
$\pi\langle{\sigma_{1},\sigma_{2},\ldots,\sigma_{n}}\rangle$ whose diagram is
obtained from that of $\pi$ by replacing each vertex $(i,\pi_{i})$ by a copy
of $\sigma_{i}$. For example, given $\pi=132$ and
$\sigma_{1},\sigma_{2},\sigma_{3}$ then a schematic of the diagram of
$132\langle{\sigma_{1},\sigma_{2},\sigma_{3}}\rangle$ is given on the right in
Figure 2. More concretely, if $\sigma_{1}=21$, $\sigma_{2}=1$, and
$\sigma_{3}=213$ then

$132\langle{\sigma_{1},\sigma_{2},\sigma_{3}}\rangle=216435.$

We say that patterns $\pi$ and $\pi^{\prime}$ are Wilf equivalent, written
$\pi\equiv\pi^{\prime}$, if
$\\#\operatorname{Av}_{n}(\pi)=\\#\operatorname{Av}_{n}(\pi^{\prime})$ for all
$n\in{\mathbb{N}}$ where the hash symbol denotes cardinality. This definition
extends in the obvious way to sets of patterns. Note that if $\pi$ and
$\pi^{\prime}$ are Wilf equivalent then both must be in the same
${\mathfrak{S}}_{n}$. It is easy to see that if $\phi\in D_{n}$ then
$\pi\equiv\phi(\pi)$ and so these are called trivial Wilf equivalences. As is
well known, all elements of ${\mathfrak{S}}_{3}$ are Wilf equivalent.

######  Theorem 1.2.

If $\pi\in{\mathfrak{S}}_{3}$ then

$\\#\operatorname{Av}_{n}(\pi)=C_{n}$

where $C_{n}=\frac{1}{n+1}\binom{2n}{n}$ it the $n$th Catalan number. ∎

Trivial Wilf equivalence carries over to sets $\Pi$ of permutations. Simion
and Schmidt [SS85] determined all Wilf equivalences among the
$\operatorname{Av}_{n}(\Pi)$ for all $\Pi\subseteq{\mathfrak{S}}_{3}$.

A permutation statistic is a map $\operatorname{st}:\uplus_{n\geq
0}{\mathfrak{S}}_{n}\rightarrow S$ where $S$ is some set. Many statistics are
based on the descent set statistic which is

$\operatorname{Des}\pi=\\{i\mid\pi_{i}>\pi_{i+1}\\}.$

The elements $i\in\operatorname{Des}\pi$ are called descents and if
$\pi_{i}<\pi_{i+1}$ then $i$ is called an ascent. Four famous statistics
related to $\operatorname{Des}$ are the the descent number statistic

$\operatorname{des}\pi=\\#\operatorname{Des}\pi$

the major index statistic

$\operatorname{maj}\pi=\sum_{i\in\operatorname{Des}\pi}i,$

the inversion statistic

$\operatorname{inv}\pi=\\#\\{(i,j)\mid\text{$i<j$ and $\pi_{i}>\pi_{j}$}\\},$

and the excedance statistic

$\operatorname{exc}\pi=\\#\\{i\mid\pi(i)>i\\}.$

Let $\operatorname{st}$ be a statistic whose range is ${\mathbb{N}}$ and $q$
be a variable. If $\Pi$ is a set of patterns then its avoidance class has a
corresponding generating function

$F^{\operatorname{st}}_{n}(\Pi)=F^{\operatorname{st}}_{n}(\Pi;q)=\sum_{\sigma\in\operatorname{Av}_{n}(\Pi)}q^{\operatorname{st}\sigma}.$

Say that $\Pi$ and $\Pi^{\prime}$ are $\operatorname{st}$-Wilf equivalent and
write $\Pi\stackrel{{\scriptstyle\operatorname{st}}}{{\equiv}}\Pi^{\prime}$ if
$F^{\operatorname{st}}_{n}(\Pi)=F^{\operatorname{st}}_{n}(\Pi^{\prime})$ for
all $n\geq 0$. Clearly $\operatorname{st}$-Wilf equivalence implies Wilf
equivalence. The $\operatorname{maj}$\- and $\operatorname{inv}$-Wilf
equivalence classes for $\Pi\subseteq{\mathfrak{S}}_{3}$ were determined by
Dokos, Dwyer, Johnson, Sagan, and Selsor [DDJ+12].

$\sigma_{1}$$\sigma_{2}$$\sigma_{3}$

Figure 2: The diagram of $132$ (left) and
$132\langle{\sigma_{1},\sigma_{2},\sigma_{3}}\rangle$ (right)

If $\pi=\pi_{1}\pi_{2}\ldots\pi_{n}\in{\mathfrak{S}}_{n}$ then the
corresponding cyclic permutation is the set of all rotations of $\pi$, denoted

$[\pi]=\\{\pi_{1}\pi_{2}\ldots\pi_{n},\hskip
7.0pt\pi_{2}\ldots\pi_{n}\pi_{1},\hskip 7.0pt\ldots,\hskip
7.0pt\pi_{n}\pi_{1}\ldots,\pi_{n-1}\\}.$

Continuing our example from the beginning of the section,

$[42351]=\\{42351,\hskip 7.0pt23514,\hskip 7.0pt35142,\hskip 7.0pt51423,\hskip
7.0pt14235\\}.$

If necessary, we will call permutations from ${\mathfrak{S}}_{n}$ linear to
distinguish them from their cyclic cousins. We also use square brackets to
denote cyclic analogues of objects defined in the linear case. For example,
$[{\mathfrak{S}}_{n}]$ is the set of all cyclic permutations of length $n$. We
say a cyclic permutation $[\sigma]$ contains $[\pi]$ as a pattern if there is
some rotation $\sigma^{\prime}$ of $\sigma$ which contains $\pi$ linearly.
Otherwise $[\sigma]$ avoids $[\pi]$. In our perennial example, even though
$42351$ avoids $1234$ we have that $[42351]$ contains $[1234]$ since the
rotation $14235$ has the copy $1235$ of this pattern. Given a set $[\Pi]$ of
cyclic patterns the cyclic avoidance class $\operatorname{Av}_{n}[\Pi]$ is
defined as expected. Note that when using a specific set of cyclic
permutations the square brackets will be put around the permutations
themselves, for example, $\operatorname{Av}_{n}([\pi],[\pi^{\prime}])$. Callan
[Cal] determined $\\#\operatorname{Av}_{n}[\pi]$ for all
$[\pi]\in[{\mathfrak{S}}_{4}]$. Gray, Lanning, and Wang continued work in this
direction considering cyclic packing of patterns [GLW18] and patterns in
colored cyclic permutations [GLW19].

The graph of a cyclic permutation $[\pi]$ is obtained by embedding the graph
of $\pi$ on a cylinder. This is indicated on the right in Figure 1 by
identifying the two dotted arrows. Cyclic Wilf equivalence has the obvious
definition. But note that now there are fewer trivial cyclic Wilf equivalences
since we need the chosen group element to preserved the cylinder, not just the
square. So the only trivial equivalences are

$[\pi]\equiv[\pi^{r}]\equiv[\pi^{c}]\equiv[\pi^{rc}].$ (1)

Certain linear permutation statistics have obvious cyclic analogues. For
example, if $\pi\in{\mathfrak{S}}_{n}$ then its cyclic descent number is

$\operatorname{cdes}[\pi]=\\#\\{i\mid\text{$\pi_{i}>\pi_{i+1}$ where
subscripts are taken modulo $n$}\\}.$

Note that this is well defined because the cardinality does not depend on
which representative of $[\pi]$ is chosen. To illustrate, $\pi=23514$ has
cyclic descents at indices $3$ and $5$ so $\operatorname{cdes}[\pi]=2$. The
corresponding generating function $F^{\operatorname{cdes}}_{n}[\Pi]$ where
$[\Pi]$ is a set of cyclic permutations, and $\operatorname{cdes}$-Wilf
equivalence should now need no definition. Note that $\operatorname{cdes}$ is
another form of the excedance statistic on linear permutations. In particular,
if $\pi=\pi_{1}\pi_{2}\ldots\pi_{n}$ then

$\operatorname{cdes}[\pi]=\operatorname{exc}(\pi_{n},\ldots,\pi_{2},\pi_{1})$

where $(\pi_{n},\pi_{n-1}\ldots,\pi_{1})$ is cycle notation for the linear
permutation which, as a function, sends $\pi_{i}$ to $\pi_{i-1}$ for all $i$
modulo $n$.

The rest of this paper is organized as follows. In the next section we prove a
cyclic variant of the Erdős-Szekeres Theorem. This will be used in the sequel
to show that, for certain $[\Pi]$, the set $\operatorname{Av}_{n}[\Pi]$
becomes empty for large enough $n$. Section 3 will extend Callan’s work by
enumerating $\operatorname{Av}_{n}[\Pi]$ for
$[\Pi]\subset[{\mathfrak{S}}_{4}]$ consisting of two patterns. One of our
principle proof techniques will be the use of generating trees. The following
section will consider $[\Pi]$ with three or more patterns. In Section 5 we
will compute the cyclic descent generating functions for
$[\Pi]\subset[{\mathfrak{S}}_{4}]$, thus refining the previous enumerations.
We will end with a section of open problems and additional comments.

##  2 A cyclic Erdős-Szekeres Theorem

In this section we will use the linear Erdős-Szekeres Theorem to prove a
cyclic analogue. We will need a variant of the decreasing permutation
$\delta_{n}$ defined as follows. Given nonnegative integers $n$ (the length),
$d$ (the difference), and $s$ (the smallest value) define the decreasing
sequence

$\delta_{n,d,s}=s+(n-1)d,\hskip 7.0pts+(n-2)d,\hskip 7.0pt\ldots,\hskip
7.0pts+d,\hskip 7.0pts.$

For example

$\delta_{5,2,3}=11,9,7,5,3.$

$1$$1$$2$$2$$3$$3$$4$$4$$5$$5$$6$$6$$7$$7$$8$$8$$9$$9$$10$$10$$11$$11$$12$$12$$13$$13$$14$$14$$15$$15$$16$$16$
Figure 3: The graph of $[\sigma]$ when $m=5$ and $n=3$

######  Theorem 2.1.

Suppose $m,n\in{\mathbb{N}}$. Then any $[\sigma]\in[{\mathfrak{S}}_{mn+2}]$
contains either $[\iota_{m+2}]$ or $[\delta_{n+2}]$. This is the best possible
in that there exist permutations in $[{\mathfrak{S}}_{mn+1}]$ which avoid both
$[\iota_{m+2}]$ and $[\delta_{n+2}]$.

###### Proof.

To prove the first statement we can assume, by rotating $\pi$ if necessary,
that

$\sigma=\sigma_{1},\sigma_{2},\ldots,\sigma_{mn+1},mn+2.$

So
$\sigma^{\prime}=\sigma_{1}\sigma_{2}\ldots\sigma_{mn+1}\in{\mathfrak{S}}_{mn+1}$
and, by Theorem 1.1, contains a copy $\kappa$ of either $\iota_{m+1}$ or
$\delta_{n+1}$. In the first case, the concatenation $\kappa,mn+1$ is a copy
of $[\iota_{m+2}]$ in $[\pi]$. In the second case, we have that $mn+1,\kappa$
is a copy of $[\delta_{n+2}]$ in $[\sigma]$.

To prove the second statement, consider the concatenation

$\sigma=1,\hskip 3.0pt\delta_{n,m,2},\hskip 3.0pt\delta_{n,m,3},\hskip
3.0pt\ldots,\hskip 3.0pt\delta_{n,m,m+1}.$

For example, when $m=5$ and $n=3$ then

$[\sigma]=[1,12,7,2,13,8,3,14,9,4,15,10,5,16,11,6]$

whose graph is shown in Figure 3. Define $\sigma^{\prime}$ by
$\sigma=1\sigma^{\prime}$ and note that $\sigma^{\prime}$ can be written
either as a disjoint union of $m$ decreasing subsequences of length $n$, or of
$n$ increasing subsequences of length $m$. In a linear permutation, any
increasing subsequence can intersect any decreasing subsequence at most once.
So any increasing subsequence of $\sigma^{\prime}$ has length at most $m$, and
any decreasing subsequence has length at most $n$. Now let $[\pi]$ be a
subsequence of $[\sigma]$. We consider two cases.

Suppose first that $[\pi]$ contains $1$. If $[\pi]$ is increasing then rotate,
if necessary, until $\pi=1\pi^{\prime}$ for some $\pi^{\prime}$ which is a
subsequence of $\sigma^{\prime}$. But from the previous paragraph,
$|\pi^{\prime}|\leq m$ which implies $|\pi|\leq m+1$ as desired. If $[\pi]$ is
decreasing then we pick a representative $\pi=\pi^{\prime}1$ and proceed as in
the increasing case to get $|\pi|\leq n+1$.

Now consider the possibility that $[\pi]$ does not contain $1$. Again, we
start with the subcase when $[\pi]$ is increasing. Suppose, for simplicity,
that $\pi$ contains an element of $x\in\delta_{n,m,2}$ as the proof will be
similar for the other deltas. As before, $\pi$ can contain at most one element
of each of $\delta_{n,m,3}$ through $\delta_{n,m,m+1}$. Now $[\pi]$ can wrap
around and pick up other elements. But those elements must come before $x$.
And since $\delta_{n,m,2}$ is decreasing, at most one other element can be
added in this way. It follows that $|\pi|\leq m+1$. On the other hand, if
$[\pi]$ is decreasing then the proof is similar. The only difference is that
if one attempts to pick up elements of $\delta_{n,m,2}$ before $x$ then this
is impossible since such elements are larger than $x$ and $[\pi]$ is
decreasing. So $|\pi|\leq n$ which is an even tighter bound. This completes
the demonstration of the theorem. ∎

##  3 Pattern avoidance of doubletons

In this section we will enumerate $\operatorname{Av}_{n}[\Pi]$ for all
$[\Pi]\subset[{\mathfrak{S}}_{4}]$ with $\\#[\Pi]=2$. Any cyclic Wilf
equivalences stated without proof are trivial.

Let us first dispose of the simplest singleton avoidance classes where
$[\pi]\in[{\mathfrak{S}}_{k}]$ for $k<4$. In $[{\mathfrak{S}}_{2}]$ there is
only one cyclic permutation $[12]$ and it is easy to see that every $[\sigma]$
of length at least $2$ contains it. In $[{\mathfrak{S}}_{3}]$ there are only
the patterns $[123]$ and $[321]$, and these are only avoided by $[\delta_{n}]$
and $[\iota_{n}]$, respectively.

Callan [Cal] enumerated $\operatorname{Av}_{n}[\pi]$ for any given
$[\pi]\in[{\mathfrak{S}}_{4}]$. Recall the version of the Fibonacci numbers
defined by $F_{1}=F_{2}=1$ and $F_{n}=F_{n-1}+F_{n-2}$ for $n\geq 3$. Unlike
the case of linear permutations in ${\mathfrak{S}}_{3}$, there are no
nontrivial Wilf equivalences.

######  Theorem 3.1 ([Cal]).

For $n\geq 2$ we have

$\displaystyle\\#Av_{n}[1234]=\\#Av_{n}[1432]$
$\displaystyle=2^{n}+1-2n-\binom{n}{3},$
$\displaystyle\\#Av_{n}[1243]=\\#Av_{n}[1342]$ $\displaystyle=2^{n-1}-n+1,$
$\displaystyle\rule{130.0pt}{0.0pt}\\#Av_{n}[1324]=\\#Av_{n}[1423]$
$\displaystyle=F_{2n-3}.\rule{130.0pt}{0.0pt}\qed$

In presenting the enumerations for doubletons, we make the following
conventions to facilitate locating a given result. All cyclic patterns will be
listed starting with $1$. And all sets of cyclic patterns will be given in
lexicographic order. We will also use terms like “just before” or “just after”
in $[\sigma]$ to refer the left-to-right order on the cylinder of a cyclic
permutation in the form of Figure 1. For example, in $[\sigma]=[42351]$ the
$5$ comes just before $1$ and the $4$ just after. We also say that an element
$x$ is between $y$ and $z$ if it is in the subsequence of $[\sigma]$ traversed
going left-to-right around the cylinder from $y$ to $z$. Continuing our
example, between $2$ and $5$ we have $3$, while between $5$ and $2$ we have
$1$ and $4$.

One of our tools will be generating trees. To the best of our knowledge, these
trees were introduced by Chung, Grahamm, Hoggatt, and Kleiman [CGHK78] for
studying Baxter permutations. Since then, they have become an integral
technique in the theory of pattern avoidance [BBMD+02, BM03, Kre00, Wes95,
Wes96]. The generating tree for an avoidance class $\operatorname{Av}[\Pi]$,
denoted $T[\Pi]$, has as its root the permutation $[12]$. The children of any
$[\sigma]\in\operatorname{Av}_{n}[\Pi]$ are all the
$[\sigma^{\prime}]\in\operatorname{Av}_{n+1}[\Pi]$ which can be formed by
inserting $n+1$ into one of the spaces of $[\sigma]$. A space, also called a
site, where insertion of $n+1$ produces a permutation of the avoidance class
is called active while the other spaces are inactive. A useful observation is
that if a space is inactive it must be because inserting $n+1$ there results
in copy of a forbidden pattern $[\pi]$ where $n+1$ plays the role of the
largest element of $\pi$. Once we have picked a representative
$\sigma=\sigma_{1}\sigma_{2}\ldots\sigma_{n}$ for $[\sigma]$ we will label the
spaces as $1,2,\ldots,n$ left to right where space $i$ comes between
$\sigma_{i}$ and $\sigma_{i+1}$. The nodes for $\operatorname{Av}_{n}[\Pi]$
will be said to be at level $n$ in $T[\Pi]$. We call the number of children of
a vertex its degree which is denoted $\deg[\sigma]$. Given $d\in{\mathbb{N}}$,
suppose that every cyclic permutation with $\deg[\sigma]=d$ has children of
degrees $c_{1},c_{2},\ldots,c_{d}$. Then this is denoted by the production
rule

$(d)\rightarrow(c_{1})(c_{2})\ldots(c_{d}).$

There may be other nodes having some special characteristic $X$ which always
produces nodes having characteristics $Y_{1},Y_{2},\ldots,Y_{d}$ which
correspond to a production rule

$(X)\rightarrow(Y_{1})(Y_{2})\ldots(Y_{d}).$

In particular, the characteristic of being the root of the tree is denote in a
production rule by $(*)$. We can also have production rules which mix numbers
for degrees and letters for characteristics. If $T[\pi]$ can be characterized
by production rules, these can often be used to calculate
$\\#\operatorname{Av}_{n}[\Pi]$.

######  Theorem 3.2.

We have

$\\{[1234],[1243]\\}\equiv\\{[1234],[1342]\\}\equiv\\{[1243],[1432]\\}\equiv\\{[1342],[1432]\\}.$

And for $n\geq 3$

$\\#\operatorname{Av}_{n}([1234],[1342])=2(n-2).$

###### Proof.

We claim that $T=T([1234],[1342])$ has the following production rules

$\displaystyle(*)$ $\displaystyle\rightarrow(2)(2),$ $\displaystyle(1)$
$\displaystyle\rightarrow(1),$ $\displaystyle(2)$
$\displaystyle\rightarrow(1)(2).$

Once these are proved then the enumeration follows easily since one can
inductively show that, for $n\geq 3$, level $n$ consists of two nodes of
degree $2$ and $2(n-3)$ nodes of degree $1$.

It is easy to check the production rule at levels $n=2$ and $3$, so we assume
that $n\geq 4$ and also that
$[\sigma]\in\operatorname{Av}_{n}([1234],[1342])$. First of all, note that the
site before $n$ is always active. For if it were not then the result
$[\sigma^{\prime}]$ of inserting $n+1$ would have a copy $\kappa$ of one of
the patterns containing $n+1$. But $n$ can not be in $\kappa$ since neither of
the patterns have $4$ followed immediately in the cycle by $3$. So replacing
$n+1$ by $n$ in $\kappa$ would give a forbidden pattern in $[\sigma]$ which is
a contradiction. Thus every $[\sigma]$ at has at least one child. Also
$\sigma$ has at most two children. For suppose

$\sigma^{\prime}=n+1,\rho,n,\tau$

is the result of inserting $n+1$ in $\sigma$. It follows that $|\rho|\leq 1$
since if $\rho\geq 2$ then $[\sigma^{\prime}]$ has a copy of either $[4123]$
or $[4213]$. Thus $n+1$ must be inserted either directly before $n$ or two
elements before $n$.

Now consider

$\delta=n,n-1,\ldots,3,2,1,\quad\mbox{and}\quad\epsilon=n,n-1,\ldots,3,1,2.$
(2)

It is easy to check that both sites $n$ and $n-1$ are active in these
permutations and so both have degree $2$. It is also obvious that if one
inserts $n+1$ in site $n$ in either permutation then one gets another
permutation of the same form.

From what we have done, we can finish the proof if we show that
$\deg[\sigma]=2$ implies $[\sigma]=[\delta]$ or $[\sigma]=[\epsilon]$. Write

$\sigma=n\rho m$

where $m$ is the last element of $\sigma$ and $\rho$ is everything between $n$
and $m$. Since $\deg[\sigma]=2$, site $n-1$ is active and inserting $n+1$
there yields

$\sigma^{\prime}=n,\rho,n+1,m.$

Then $m\leq 2$ since otherwise $[\sigma]$ contains a copy of $[4123]$ or
$[4213]$ since $n\geq 4$. In the case $m=1$ we must have $\rho$ decreasing.
For if there is an ascent $x<y$ in $\rho$ then $[\sigma^{\prime}]$ contains
$[x,y,n+1,1]$ which is a copy of $[2341]$, a contradiction. So in this case
$\rho$ is decreasing and $\sigma=\delta$. The other possibility is that $m=2$.
This forces the last element of $\rho$ to be $1$. For if $1$ is elsewhere and
$x$ is the last element of $\rho$ then then $[\sigma^{\prime}]$ contains
$[1,x,n+1,2]$ which is contradictory copy of $[1342]$. Similarly to the first
case, one can now show that $\rho$ is decreasing and so $\sigma=\epsilon$ as
desired. ∎

Comparing our next result with the previous one will provide our first
nontrivial Wilf equivalence.

######  Theorem 3.3.

We have

$\\{[1234],[1324]\\}\equiv\\{[1423],[1432]\\}.$

And for $n\geq 3$

$\\#\operatorname{Av}_{n}([1234],[1324])=2(n-2).$

###### Proof.

Let $D$ stand for the decreasing permutation and $E$ for the decreasing
permutation with its largest two elements swapped. We consider the root $[12]$
to be of type $D$. We will show that $T=T([1234],[1324])$ has production rules

$\displaystyle(1)$ $\displaystyle\rightarrow(1),$ $\displaystyle(D)$
$\displaystyle\rightarrow(D)(E),$ $\displaystyle(E)$
$\displaystyle\rightarrow(1)(1).$

It follows by induction that level $n\geq 3$ of $T$ has a $D$, an $E$, and
$2(n-3)$ nodes of degree one, proving the theorem.

The same demonstration as in the previous theorem shows that the site before
$n$ in any $[\sigma]\in\operatorname{Av}_{n}([1234],[1324])$ is active. So
again, every such permutation has at least one child. Also, every $[\sigma]$
has at most two children. Indeed, write

$\sigma=1\sigma_{2}\ldots\sigma_{n}$ (3)

and put $n+1$ in site $i\geq 3$. Then $1,\sigma_{2},\sigma_{3},n+1$ is a copy
of either $1234$ or $1324$, another contradiction.

Now consider permutations corresponding to $D$ and $E$ at level $n$

$\delta=1,n,n-1,n-2,n-3,\ldots,2\quad\mbox{and}\quad\epsilon=1,n-1,n,n-2,n-3,\ldots,2.$
(4)

It is easy to check that both sites $1$ and $2$ are active in $\delta$,
$\epsilon$. So, by the previous paragraph, they both have degree $2$.
Furthermore, the two children of $\delta$ have the form $D$ and $E$.

We will be done if we can show that $[\sigma]$ having two children implies
$[\sigma]=[\delta]$ or $[\epsilon]$. Write $\sigma$ as in (3). Since the
active sites must be $1$ and $2$, and the site before $n$ must be active,
either $\sigma_{2}=n$ or $\sigma_{3}=n$. If $\sigma_{2}=n$ and there is an
ascent $x<y$ in the rest of the permutation, then after inserting $n+1$ in
position $2$ we have $[x,y,n,n+1]$ which is a copy of $[1234]$, a
contradiction. So in this case $[\sigma]=[\delta]$. Alternatively, suppose
$\sigma_{3}=n$. This forces $\sigma_{2}=n-1$, since if $\sigma_{2}=x<n-1$ then
$n-1$ comes after $n$. But inserting $n+1$ in position $1$ gives
$[x,n,n-1,n+1]$ which is a copy of $[1324]$. And similarly to the first case
we see that the rest of $\sigma$ is decreasing. The result is that
$[\sigma]=[\epsilon]$. This completes the proof. ∎

######  Theorem 3.4.

We have

$\\{[1234],[1423]\\}\equiv\\{[1324],[1432]\\}.$

And for $n\geq 1$

$\\#\operatorname{Av}_{n}([1234],[1423])=1+\binom{n-1}{2}.$

###### Proof.

Suppose $[\sigma]\in\operatorname{Av}_{n}([1234],[1423])$ and write

$\sigma=1\rho n\tau$ (5)

where $\rho$ and $\tau$ are the subsequences between $1$ and $n$, and between
$n$ and $1$, respectively. Now $\rho$ and $\tau$ must be decreasing since
$[\sigma]$ avoids $[1234]$ and $[1423]$, respectively. Furthermore, $\rho$
must consist of consecutive integers since, if not, then we have $x<y<z$ such
that $1zxny$ is a subsequence of $\sigma$. So $[xnyz]$ is a copy of $[1423]$
in $[\sigma]$, which is a contradiction. Conversely, it is easy to check that
if $\sigma$ has the form (5) with $\rho$ and $\tau$ decreasing and $\rho$
consecutive then $[\sigma]\in\operatorname{Av}_{n}([1234],[1423])$. So we have
characterized the elements of this class.

To finish the enumeration, if $\rho=\emptyset$ there is one corresponding
$\sigma$. But if $\rho\neq\emptyset$ then choosing the smallest and largest
element of $\rho$ from the elements $2,3,\ldots,n-1$ completely determines
$\sigma$. Since these two elements could be equal, we are choosing $2$
elements from $n-2$ elements with repetition which is counted by
$\binom{n-1}{2}$. ∎

The following result follows immediately from Theorem 2.1

######  Theorem 3.5.

We have

$\\#\operatorname{Av}_{n}([1234],[1432])=0$

for $n\geq 6$. ∎

We now have, by comparison with Theorem 3.4, another nontrivial Wilf
equivalence.

######  Theorem 3.6.

We have

$\\{[1243],[1324]\\}\equiv\\{[1243],[1423]\\}\equiv\\{[1324],[1342]\\}\equiv\\{[1342],[1423]\\}.$

And for $n\geq 1$

$\\#\operatorname{Av}_{n}([1324],[1342])=1+\binom{n-1}{2}.$

###### Proof.

Take $[\sigma]\in\operatorname{Av}_{n}([1324],[1342])$ and write $\sigma$ as
in (5). Then $\rho$ is increasing since $[\sigma]$ avoids $[1324]$. And every
element of $\rho$ is smaller than every element of $\tau$ since $[\sigma]$
avoids $[1342]$. To avoid a copy of one of the forbidden patterns containing
the $1$ of $\sigma$ we must have that $\tau$ avoids $213$ and $231$. And to
avoid a copy of $[1324]$ where $n$ plays the role of $4$, it must be that
$\tau$ avoids $132$. The $\tau$ which avoid these three pattern are exactly
those which are inflations of the form
$\tau=21\langle{\delta_{k},\iota_{l}}\rangle$ for some $k,l\geq 0$ (see the
chart on page 2773 of [DDJ+12]). Absorbing the $1$ and $n$ of $\sigma$ into
$\rho$ and $\tau$, respectively, we see that

$\sigma=132\langle{\iota_{j},\delta_{k},\iota_{l}}\rangle$ (6)

where $j,k\geq 1$ and $l\geq 0$. Again, it is not hard to check that for every
$\sigma$ of this form we have
$[\sigma]\in\operatorname{Av}_{n}([1324],[1342])$.

To enumerate these $\sigma$, we distinguish two cases. If $l\geq 2$ then
picking the smallest and largest elements of the copy of $\iota_{l}$ from
$2,3,\ldots,n-1$ completely determines $\sigma$ . So in this case there are
$\binom{n-2}{2}$ choices. If $l\leq 1$ then the copy of $\iota_{l}$ can be
appended to the copy of $\delta_{k}$ so that
$\sigma=12[\iota_{j},\delta_{n-j}]$. Since we must have $1$ and $n$ in the
ascending and decreasing subsequences, there are now $n-1$ choices. Adding the
two counts given the desired result. ∎

######  Theorem 3.7.

For $n\geq 4$ we have

$\\#\operatorname{Av}_{n}([1243],[1342])=4.$

###### Proof.

Take $[\sigma]\in\operatorname{Av}_{n}([1243],[1342])$ and write $\sigma$ as
in (5). Then $\rho$ and $\tau$ can not both be nonempty. For if $x\in\rho$ and
$y\in\tau$ then $1xny$ is a copy of either $1243$ or $1342$.

Assume first that $\rho=\emptyset$ so that

$\sigma=1n\tau.$ (7)

Then $\tau$ must be increasing or decreasing. For suppose it was neither. Then
it would contain a copy of one of the patterns $132$, $231$, $213$, or $312$.
In the first two cases this would give, together with the $1$, a copy of
$1243$ or $1342$ in $\sigma$. And in the last two cases, prepending $n$ gives
a copy of $4213$ or $4312$. Conversely, if $\sigma$ is given by (7) with
$\tau$ increasing or decreasing then it is easy to verify that
$[\sigma]\in\operatorname{Av}_{n}([1243],[1342])$.

Using the same ideas, one can also show that if $\tau=\emptyset$ then one gets
exactly two elements of $\operatorname{Av}_{n}([1243],[1342])$, of the form
$\sigma=1\rho n$ where $\rho$ is either increasing or decreasing. Thus there
are a total of four elements in the avoidance class. ∎

######  Theorem 3.8.

For $n\geq 3$ we have

$\\#\operatorname{Av}_{n}([1324],[1423])=2^{n-2}.$

###### Proof.

Take $[\sigma]\in\operatorname{Av}_{n}([1324],[1423])$ and write

$\sigma=n,\rho,n-1,\tau.$

Similar to the previous proof, one of $\rho$ or $\tau$ must be empty since
otherwise $4132$ or $4231$ is a pattern in $\sigma$. If $\rho=\emptyset$ then
one shows similarly that $n-2$ either begins or ends $\tau$. Continuing in
this manner, we see that there are $2$ choices for the positions of
$n-1,n-2,\ldots,2$. Checking, as usual, that all such permutations are
actually in the avoidance set, the enumeration follows. ∎

##  4 Three or more patterns

We will now compute $\\#\operatorname{Av}_{n}[\Pi]$ for
$\Pi\subseteq{\mathfrak{S}}_{n}$ having $\\#\Pi\geq 3$. Will will not consider
those $[\Pi]$ containing both $[1234]$ and $[1432]$ since for such classes
$\\#\operatorname{Av}_{n}[\Pi]=0$ for $n\geq 6$ as in Theorem 3.5.

######  Theorem 4.1.

We have

$\\{[1234],[1243],[1324]\\}\equiv\\{[1234],[1324],[1342]\\}\equiv\\{[1243],[1423],[1432]\\}\equiv\\{[1342],[1423],[1432]\\}.$

And for $n\geq 4$

$\\#\operatorname{Av}_{n}([1234],[1324],[1342])=3.$

###### Proof.

If $[\sigma]\in\operatorname{Av}_{n}([1234],[1324],[1342])$ then $[\sigma]$
avoids $[1324]$ and $[1342]$. So, by the proof of Theorem 3.6, we can write
$\sigma$ in the form (6) for $j,k,l\geq 1$. But since $[\sigma]$ also avoids
$[1234]$ we must have $j+l\leq 3$. For the same reason, $j\leq 2$ since if
$j=3$ then the copy of $\iota_{3}$ and one element of the copy of $\delta_{k}$
would form a $[1234]$. Thus the only possibilities are $(j,l)=(1,1)$, $(1,2)$,
or $(2,1)$ which proves the result. ∎

######  Theorem 4.2.

We have

$\\{[1234],[1243],[1342]\\}\equiv\\{[1243],[1342],[1432]\\}.$

And for $n\geq 5$

$\\#\operatorname{Av}_{n}([1234],[1243],[1342])=2.$

###### Proof.

If $[\sigma]\in\operatorname{Av}_{n}([1234],[1243],[1342])$ then $[\sigma]$
avoids $[1243]$ and $[1342]$. So, by the proof of Theorem 3.7, we can write

$\sigma=xy\rho$ (8)

where $\\{x,y\\}=\\{1,n\\}$ and $\rho$ is either increasing or decreasing.
Since $n\geq 5$ we have $|\rho|\geq 3$. But $[\sigma]$ also avoides $[1234]$
and this forces $\rho$ to be decreasing. So there are two choices for
$[\sigma]$ depending on the values of $x$ and $y$. ∎

######  Theorem 4.3.

We have

$\\{[1234],[1243],[1423]\\}\equiv\\{[1234],[1342],[1423]\\}\equiv\\{[1243],[1324],[1432]\\}\equiv\\{[1324],[1342],[1432]\\}.$

And for $n\geq 2$

$\\#\operatorname{Av}_{n}([1234],[1342],[1423])=n-1.$

###### Proof.

We will show that $T=T([1234],[1342],[1423])$ has production rules

$\displaystyle(*)$ $\displaystyle\rightarrow(1)(2),$ $\displaystyle(1)$
$\displaystyle\rightarrow(1),$ $\displaystyle(2)$
$\displaystyle\rightarrow(1)(2).$

Then, by induction, level $n\geq 2$ of $T$ will contain one node of degree $2$
and $n-2$ nodes of degree $1$. Checking the root is easy, so assume $n\geq 3$.

By Theorem 3.2, $T$ is a subtree of $T([1234],[1342])$. So we just need to
check which nodes of that tree also avoid $[1423]$. As in the proof of that
theorem, the site before $n$ in $[\sigma]$ at level $n$ in $T$ is still active
since $4$ is not followed immediately by $3$ in $[1423]$. Thus it suffices to
show that both sites of $\delta$ remain active, but only one in $\epsilon$
where $\delta,\epsilon$ are defined by (2). Indeed, the two sites of $\delta$
give rise to copies of $\delta$ and $\epsilon$ at level $n+1$ of $T$. But site
$n-1$ of delta which was active in the larger tree is now inactive since
inserting $n+1$ there gives the copy $[1,n+1,2,n]$ of $[1423]$. This completes
the proof. ∎

We now have, in comparison with the previous theorem, a nontrivial Wilf
equivalence.

######  Theorem 4.4.

We have

$\\{[1234],[1324],[1423]\\}\equiv\\{[1324],[1423],[1432]\\}.$

And for $n\geq 2$

$\\#\operatorname{Av}_{n}([1234],[1324],[1423])=n-1.$

###### Proof.

It suffices to show that $T=T([1234],[1324],[1423])$ satisfies the same
production rules as in the previous theorem. Now $T$ is a subtree of
$T([1234],[1324])$ which was constructed in the proof of Theorem 3.3. And we
see in the usual way that the site before $n$ in any $[\sigma]$ remains active
in $T$ because $4$ is not immediately followed by $3$ in $[1423]$.

So it suffices to show, with $\delta$ and $\epsilon$ as in (4), that site $1$
remains active in $\delta$, but not in $\epsilon$. Indeed, inserting $n+1$ in
this site of $\delta$ just produces another descending sequence. But in
$\epsilon$ such a placement gives the copy $[1,n+1,n-1,n]$ of $[1423]$. ∎

We now have another nontrivial Wilf equivalence with Theorem 4.1.

######  Theorem 4.5.

We have

$\\{[1243],[1324],[1342]\\}\equiv\\{[1243],[1342],[1423]\\}.$

And for $n\geq 4$

$\\#\operatorname{Av}_{n}([1243],[1324],[1342])=3.$

###### Proof.

By Theorem 3.7, we just need to show that exactly $3$ of the $4$ permutations
$[\sigma]$ avoiding $\\{[1243],[1342]\\}$ also avoid $[1324]$. These
permutations are described in equation (8). If $x=n$ and $y=1$ then $[\sigma]$
contains the copy $[n132]$ of this pattern. It is also easy to check that the
other three avoid it. ∎

We now have our last nontrivial Wilf equivalence for triples.

######  Theorem 4.6.

We have

$\\{[1243],[1324],[1423]\\}\equiv\\{[1324],[1342],[1423]\\}.$

And for $n\geq 2$

$\\#\operatorname{Av}_{n}([1324],[1342],[1423])=n-1.$

###### Proof.

Comparing the description of $\operatorname{Av}_{n}([1324],[1342])$ in the
proof of Theorem 3.6 and that of $\operatorname{Av}_{n}([1324],[1423])$ in the
proof of Theorem 3.8, we see that any
$[\sigma]\in\operatorname{Av}_{n}([1324],[1342],[1423])$ can be put in the
form

$\sigma=21[\delta_{k},\iota_{n-k}]$

with $k\geq 1$. Also, $k=n-1$ and $k=n$ yield the same permutation. So there
are $n-1$ choices for $k$ and we are done. ∎

When $\\#[\Pi]\geq 4$ where $[\Pi]\subset[{\mathfrak{S}}_{4}]$, the size of
$\operatorname{Av}_{n}[\Pi]$ becomes constant for $n\geq 5$. And this size is
trivial to calculate for $n\leq 4$. Furthermore, the description of the
surviving permutations for large $n$ is easy to obtain given our previous
proofs. So we content ourselves with a listing of the equivalence classes and
associated constants in Table 1. Classes are separated by double horizontal
line. As usual, we do not consider classes containing both the increasing and
decreasing permutations because of the cyclic Erdős-Szekeres Theorem.

$\begin{array}[]{l|c}[\Pi]&\\#\operatorname{Av}_{n}[\Pi]\\\
\hline\cr\hline\cr\\{[1234],[1243],[1324],[1342]\\}&1\\\
\\{[1243],[1342],[1423],[1432]\\}&\\\
\hline\cr\hline\cr\\{[1234],[1243],[1324],[1423]\\}&2\\\
\\{[1234],[1243],[1342],[1423]\\}&\\\ \\{[1234],[1324],[1342],[1423]\\}&\\\
\\{[1243],[1324],[1342],[1423]\\}&\\\ \\{[1243],[1324],[1342],[1432]\\}&\\\
\\{[1243],[1324],[1423],[1432]\\}&\\\ \\{[1324],[1342],[1423],[1432]\\}&\\\
\hline\cr\hline\cr\\{[1234],[1243],[1324],[1342],[1423]\\}&1\\\
\\{[1243],[1324],[1342],[1423],[1432]\\}&\\\ \hline\cr\hline\cr\end{array}$
Table 1: Wilf equivalence classes and cardinalities of
$\operatorname{Av}_{n}[\Pi]$ for certain $[\Pi]$ and $n\geq 5$

##  5 Cyclic descent generating functions

We will now consider the generating function for the number of cyclic descents
over various avoidance classes $[\Pi]\subset[{\mathfrak{S}}_{4}]$, starting
with those defined by a single element. We will sometimes use the
characterizations given by Callan [Cal] for these classes to facilitate our
work, and use the abbreviation

$D_{n}([\Pi])=D_{n}([\Pi];q)=\sum_{\sigma\in\operatorname{Av}_{n}[\Pi]}q^{\operatorname{cdes}\sigma}$

for the generating function.

To begin, we have a lemma showing that trivial Wilf equivalences also give
simple relationships between the corresponding generating functions.

######  Lemma 5.1.

For any $[\Pi]$ We have

$D_{n}([\Pi]^{r};q)=D_{n}([\Pi]^{c};q)=q^{n}D_{n}([\pi];1/q)$

and

$D_{n}([\Pi]^{rc};q)=D_{n}([\Pi];q).$

###### Proof.

Reversing or complementing a permutation turns all cyclic descents into cyclic
ascents and vice-versa. Translating this into generating functions gives the
first displayed equalities. And the second displayed equation follows from the
the previous display. ∎

Now consider the possible $D_{n}([\pi])$ for $[\pi]\in[{\mathfrak{S}}_{4}]$.
We begin with the simplest case.

######  Theorem 5.2.

We have $D_{n}([1423];q)=q^{n}D_{n}([1324];1/q)$ where, for $n\geq 2$,

$D_{n}([1324];q)=\sum_{k=1}^{n-1}\binom{n+k-3}{n-k-1}q^{k}.$

###### Proof.

We use Callan’s characterization of this avoidance class to obtain a recursion
for $D_{n}([1324])$. If $[\sigma]\in\operatorname{Av}_{n}([1324])$ and $n\geq
3$ then write $\sigma=\sigma_{1}\sigma_{2}\ldots\sigma_{n-1}n$. Let $k$ be the
index such that $\sigma_{k}=n-1$. There are two cases.

If $k=n-1$ then $\sigma=\tau,n-1,n$ where
$[\tau,n-1]\in\operatorname{Av}_{n-1}([1324])$ and this is a bijection. Since
$\operatorname{cdes}[\sigma]=\operatorname{cdes}[\tau,n-1]$, this case
contributes $D_{n-1}([1324])$ to the recursion.

If $1\leq k\leq n-2$ then this forces

$\sigma=2314[\iota_{k-1},1,\tau,1]$

for some $\tau$ such that $[\tau n]$ avoids $[1324]$. Because of the extra
descent caused by $n-1$ we have
$\operatorname{cdes}[\sigma]=1+\operatorname{cdes}[\tau n]$. So this case
gives a contribution of $\sum_{k=1}^{n-2}qD_{n-k}([1324])$.

Putting everything together, we have

$D_{n}([1324])=D_{n-1}([1324])+\sum_{k=1}^{n-2}qD_{n-k}([1324]).$

for $n\geq 3$ and $D_{2}([1324])=q$. It is now a simple manner of manipulating
binomial coefficients to show that the formula given in the theorem satisfies
this initial value problem. ∎

For the next case, we will use a characterization of the class different from
the one found by Callan. This will permit us to avoid the use of a recurrence.

######  Lemma 5.3.

Suppose $[\sigma]\in[{\mathfrak{S}}_{n}]$ and write $\sigma=1\rho n\tau$. We
have $[\sigma]\in\operatorname{Av}_{n}([1342])$ if and only if the following
three conditions are satsified:

  1. (a)

$\rho$ and $\tau$ both avoid $\\{213,231\\}$,

  2. (b)

$\max\rho<\min\tau$,

  3. (c)

there is not both a descent in $\rho$ and an ascent in $\tau$.

###### Proof.

For the forward direction, suppose $[\sigma]\in\operatorname{Av}_{n}([1342])$.
Condition (a) is true since if either $\rho$ or $\tau$ contains $213$ then,
together with $n$, we have that $[\sigma]$ contains $[2134]$. Similarly, if
either contains $231$ then $[\sigma]$ contains the forbidden pattern by
prepending the $1$. As far as (b), if there is $y>x$ with $y\in\rho$ and
$x\in\tau$ then $[1ynx]$ is a copy of $[1342]$. Finally for (c), if there were
a descent in $\rho$ and an ascent in $\tau$ then, because of (b), putting them
together would again give a copy of the pattern to avoid.

The converse is similar where one assumes that a copy of $[1342]$ exists and
then considers all the different intersections it could have with $1$, $\rho$,
$n$, and $\tau$. We leave the details to the reader. ∎

In order to use this lemma, we will need a result about the ordinary descent
statistic on linear permutations avoiding $\\{123,231\\}$. The next result is
a specialization of Proposition 5.2 of the paper of Dokos, Dwyer, Johnson,
Sagan, and Selsor [DDJ+12] and so the proof is ommited.

######  Lemma 5.4 ([DDJ+12]).

We have

${\color[rgb]{1,1,1}\definecolor[named]{pgfstrokecolor}{rgb}{1,1,1}\pgfsys@color@gray@stroke{1}\pgfsys@color@gray@fill{1}\qed}\hfill{\displaystyle\sum_{\sigma\in\operatorname{Av}_{n}(213,231)}q^{\operatorname{des}\sigma}=(1+q)^{n-1}.}\hfill\qed$

We need one last well-known definition. Call a polynomial
$f(q)=\sum_{k=0}^{n}a_{k}q^{k}$ of degree $n$ symmetric if $a_{k}=a_{n-k}$ for
all $0\leq k\leq n$. Note that $f(q)$ of degree $n$ is symmetric if and only
if

$q^{n}f(1/q)=f(q).$ (9)

######  Theorem 5.5.

We have $D_{n}([1243];q)=D_{n}([1342];q)$ where, for $n\geq 2$,

$D_{n}([1342];q)=2q(1+q)^{n-2}-q\cdot\frac{1-q^{n-1}}{1-q}$

is symmetric.

###### Proof.

It is easy to prove from the explicit form of $D_{n}([1342])$ that it
satisfies equation (9) and so is symmetric. So once this is proved, the
equality of the two generating functions follows from Lemma 5.1.

We adopt the notation of Lemma 5.3 and let $\sigma_{k}=n$ where $2\leq k\leq
n$. We will consider cases depending on whether $\rho$ or $\tau$ is empty. If
$\rho=\emptyset$ then by Lemma 5.3 (a) and Lemma 5.4 we have that the
generating function for the possible linear $\tau$ is $(1+q)^{n-3}$. Also,
$\operatorname{cdes}[\sigma]=2+\operatorname{des}\tau$ by the form of
$\sigma$, so the contribution of such $[\sigma]$ to $D_{n}([1342])$ is
$q^{2}(1+q)^{n-3}$. In an analogous way, we see that those $[\sigma]$ with
$\tau=\emptyset$ yield $q(1+q)^{n-3}$. Adding these, we have a total of
$q(1+q)^{n-2}$ so far.

We now assume that $\rho,\tau$ are both nonempty so that $3\leq k\leq n-1$. By
parts (b) and (c) of Lemma 5.3, either $\rho$ must be an increasing
subsequence of consecutive integers or $\tau$ must be a decreasing one. Using
Lemma 5.4 again, we see that in the first subcase a contribution of
$q^{2}(1+q)^{n-k-1}$ is obtained. And in the second, taking into account the
descents in $\rho$, the contribution is $q^{n-k+1}(1+q)^{k-3}$. However, these
two subcases overlap when $\rho$ is increasing and $\tau$ is decreasing. So we
must subtract $q^{n-k+1}$.

Thus we get a grand total of

$D_{n}([1342])=q(1+q)^{n-2}+\sum_{k=3}^{n-1}[q^{2}(1+q)^{n-k-1}+q^{n-k+1}(1+q)^{k-3}-q^{n-k+1}].$

Summing the geometric series and simplifying completes the proof. ∎

For the avoidance class of the increasing (or decreasing) pattern in
$[{\mathfrak{S}}_{4}]$, we will need another concept. Given sequences $\rho$
and $\tau$ of distinct integers, their shuffle set is

$\rho\shuffle\tau=\\{\sigma\ :\ \text{$|\sigma|=|\rho|+|\tau|$ and both
$\rho,\tau$ are subsequences of $\sigma$}\\}.$

For example,

$12\shuffle 34=\\{1234,1324,1342,3124,3142,3412\\}.$

In the statement of the next result we make the usual convention that
$\binom{n}{k}=0$ if $k>n$.

######  Theorem 5.6.

We have $D_{n}([1234];q)=q^{n}D_{n}([1432];1/q)$ where, for $n\geq 2$,

$D_{n}([1432];q)=q+(2^{n-1}-n)q^{2}+\sum_{j\geq 3}\binom{n}{2j-1}q^{j}.$

###### Proof.

We use Callan’s description of the avoidance for $[1234]$ translated by
complementation to apply to $[1432]$. We are going to derive a recursion for
$D_{n}([1432];q)$. If $[\sigma]\in{\mathfrak{S}}_{n}[1432]$ then suppose
$\sigma_{n}=1$ and $\sigma_{k}=2$ for some $1\leq k\leq n-1$. There are three
cases.

If $k=1$ then there is a bijection between such $[\sigma]$ and
$\operatorname{Av}_{n-1}[1432]$ obtained by removing $1$ and taking the order
isomorphic cyclic permutation on $[n-1]$. Since $2$ immediately follows $1$
cyclically in $[\sigma]$, the descent into $1$ remains a descent after
applying the map. So the contribution of this case is $D_{n-1}([1432];q)$.

Now suppose that $2\leq k\leq n-1$ and write

$\sigma=\rho 2\tau 1.$

where $|\rho|=k-1$, $|\tau|=n-k-1$. As Callan proves, $\rho$ must be
increasing. So there are two more cases depending upon whether the elements of
$\rho$ are consecutive or not. Suppose first that they are not consecutive. In
this case, $\tau$ must also be increasing so $\operatorname{cdes}[\sigma]=2$.
To compute the number of such $\sigma$, note that once the elements of $\rho$
have been picked from $[3,n]$, all of $\sigma$ is determined. The total number
of nonempty subsets of this interval is $2^{n-2}-1$. And those which consist
of consecutive integers are determined by their minimum and maximum element,
which could be equal. So there are $\binom{n-1}{2}$ subsets to exclude. The
contribuion of this case is then

$\left(2^{n-2}-\binom{n-1}{2}-1\right)q^{2}.$

Finally we consider the case when $\rho\neq\emptyset$ is consecutive (and
still increasing), say with minimum $m+1$ and maximum $M-1$. Note that if
$l=|\tau|$ then $0\leq l\leq n-3$. Callan shows that the possible $\tau$ are
the elements of $(34\ldots m)\shuffle(M,M+1,\ldots,n)$. Since a permutation
can be written as a shuffle in many ways, the same shuffle could occur for
different $\rho$. So it will be convenient to color the elements of the second
sequence by marking them with a hat. Thus the $\sigma$ in this case are in
bijection with colored shuffles $(34\ldots
m)\shuffle(\widehat{M},\widehat{M+1},\ldots,\widehat{n})$. It will also be
convenient to consider these as corresponding to the sequences $2\tau$ by
prepending a $2$ to each shuffle and considering $2$ as an uncolored element.
Set $S$ be the set of such sequences $s=2s_{2}s_{3}\ldots s_{l+1}$ where
$l,m,M$ are allowed to vary over all possible values. Note that if $s$
corresponds to $\sigma$ then $\operatorname{des}\sigma=2+\operatorname{des}s$.
To compute $\operatorname{des}s$, we consider the transition indices

$\operatorname{Tr}s=\\{i\mid\text{$s_{i}$ is colored and $s_{i+1}$ is not, or
vice-versa}\\}.$

For example, if $s=23\widehat{6}45\widehat{7}\widehat{8}$ then
$\operatorname{Tr}s=\\{2,3,5\\}$. It is easy to see that the map
$\operatorname{Tr}:S\rightarrow 2^{[l]}$, the range being all subsets of
$[l]$, is a bijection. Also, every other transition index of $s$ starting with
the second corresponds to a descent. So, using the round down function,
$\operatorname{des}s=\lfloor\\#\operatorname{Tr}s/2\rfloor$. We can now
complete this case using $i=\\#\operatorname{Tr}s$ to see that the
contribution is

$\displaystyle\sum_{l=0}^{n-3}\sum_{i=0}^{l}\binom{l}{i}q^{\lfloor
i/2\rfloor+2}$ $\displaystyle=\sum_{i=0}^{n-3}q^{\lfloor
i/2\rfloor+2}\sum_{l=i}^{n-3}\binom{l}{i}$
$\displaystyle=\sum_{i=0}^{n-3}\binom{n-2}{i+1}q^{\lfloor i/2\rfloor+2}$
$\displaystyle=q^{2}\sum_{j\geq
0}\left[\binom{n-2}{2j+1}+\binom{n-2}{2j+2}\right]q^{j}$
$\displaystyle=q^{2}\sum_{j\geq 0}\binom{n-1}{2j+2}q^{j}.$

Putting all the cases together we have

$D_{n}([1432];q)=D_{n-1}([1432];q)+q^{2}\left[2^{n-2}-\binom{n-1}{2}-1+\sum_{j\geq
0}\binom{n-1}{2j+2}q^{j}\right].$

As usual, the routine verification that our desired formula satisfies this
recursion and the initial condition is left to the reader. ∎

We now turn to the cyclic descent polynomials for pairs in
$[{\mathfrak{S}}_{4}]$. To simplify notation, for any polynomial $f(q)$ and
$n\in{\mathbb{N}}$ we let

$f^{(n)}(q)=q^{n}f(1/q).$

######  Theorem 5.7.

We have the following descent polynomials.

  1. (a)

We have

$D_{n}([1234],[1243])=D_{n}([1342],[1432])=D_{n}^{(n)}([1243],[1432])=D_{n}^{(n)}([1234],[1342]).$

And for $n\geq 3$

$D_{n}([1234],[1342];q)=(2n-5)q^{n-2}+q^{n-1}.$

  2. (b)

We have

$D_{n}([1423],[1432])=D_{n}^{(n)}([1234],[1324]).$

And for $n\geq 3$

$D_{n}([1234],[1324];q)=(2n-5)q^{n-2}+q^{n-1}.$

  3. (c)

We have

$D_{n}([1324],[1432])=D_{n}^{(n)}([1234],[1423]).$

And for $n\geq 1$

$D_{n}([1234],[1423];q)=q^{n-1}+\binom{n-1}{2}q^{n-2}.$

  4. (d)

We have

$D_{n}([1243],[1423])=D_{n}([1342],[1423])=D_{n}^{(n)}([1243],[1324])=D_{n}^{(n)}([1324],[1342]).$

And for $n\geq 1$

$D_{n}([1324],[1342];q)=q+\sum_{k=2}^{n-1}(n-k)q^{k}.$

  5. (e)

For $n\geq 4$ we have

$D_{n}([1243],[1342];q)=q+q^{2}+q^{n-1}+q^{n-2}.$

  6. (f)

For $n\geq 3$ we have

$D_{n}([1324],[1423];q)=q(1+q)^{n-2}.$

###### Proof.

We will only prove (a) as the others follow easily in a similar fashion from
the descriptions of the avoidance classes in Section 3. We adopt the notation
of the proof of Theorem 3.2.

We will use the description of the generating tree to obtain a recursion for
$D_{n+1}[1243],[1432])$. Note that if $n+1$ is inserted in site $i$ of
$\sigma$ to form $\sigma^{\prime}$ then

$\operatorname{cdes}[\sigma^{\prime}]=\left\\{\begin{array}[]{ll}\operatorname{cdes}[\sigma]&\mbox{if
$i$ is a cyclic descent,}\\\ \operatorname{cdes}[\sigma]+1&\mbox{if $i$ is a
cyclic ascent.}\end{array}\right.$

Since the site before $n$ is always active, these children will give a
contribution of $qD_{n}([1243],[1432])$ because such a site is a cyclic
ascent. In $\delta$ and $\epsilon$, insertion in the other active site gives
permutations with $n-1$ descents. So

$D_{n+1}[1243],[1432])=2q^{n-1}+qD_{n}([1243],[1432]).$

It is now easy to check that the formula in (a) satisfies this recursion and
is also valid at $n=3$, completing the proof. ∎

For classes avoiding $3$ or more patterns, we will only write down the results
for those which are not eventually constant. The interested reader can easily
compute the polynomials for the remaining classes. We also content ourselves
with stating the polynomial for one member of every trivial Wilf equivalence
class since the rest can be computed from Lemma 5.1.

######  Theorem 5.8.

We have the descent polynomials

$D_{n}([1234],[1342],[1423];q)=D_{n}([1234],[1324],[1423];q)=(n-2)q^{n-2}+q^{n-1}$

and

$D_{n}([1324],[1342],[1423];q)=q\cdot\frac{1-q^{n-1}}{1-q}$

for $n\geq 2$. ∎

##  6 Open problems and concluding remarks

We collect here various areas for future research in the hopes that the reader
will be interested in pursuing this work.

###  6.1 Longer patterns

There has been very little work about containment and avoidance for cyclic
patterns of length longer than $4$. Of course, the cyclic Erdős-Szekeres
Theorem, Theorem 2.1 above, is one such result. There is also a paper of Gray,
Lanning and Wang [GLW18] where the authors consider cyclic packing (maximizing
the number of copies of a given pattern among all the permutations
$[\sigma]\in[{\mathfrak{S}}_{n}]$ for some $n$) and superpatterns
(permutations containing all the patterns $[\pi]\in[{\mathfrak{S}}_{k}]$ for
some $k$). It would be interesting to see if there are nice enumerative
formulas for classes consisting of cyclic patterns of length $5$ and up.

###  6.2 Other statistics

One could study other cyclic statistics. For example, the peak set of a linear
permutation is

$\operatorname{Pk}\pi=\\{i\mid\pi_{i-1}<\pi_{i}>\pi_{i+1}\\}$

with corresponding peak number

$\operatorname{pk}\pi=\\#\operatorname{Pk}\pi.$

Peaks are an important part of Stembridge’s theory of enriched $P$-partitions
[Ste97] where $P$ is a partially ordered set. On the enumerative side, the
study of permutations which have a given peak set has been a subject of
current interest [BBPS15, BBS13, BFT16, CVDLO+17, DLHIO17a, DLHIO17b,
DLHIPL17]. Now define the cyclic peak number to be

$\operatorname{cpk}[\pi]=\\#\\{i\mid\text{$\pi_{i-1}<\pi_{i}>\pi_{i+1}$ where
subscripts are taken modulo $n$}\\}.$

As with $\operatorname{cdes}$, this is well defined since it is independent of
the choice of representative of $[\pi]$. There should be interesting
generating functions for the distribution of $\operatorname{cpk}$ over
avoidance classes, or even for the joint distribution of $\operatorname{cdes}$
and $\operatorname{cpk}$. As evidence, we prove one such result.

######  Theorem 6.1.

For $n\geq 3$

$\sum_{[\sigma]\in\operatorname{Av}_{n}([1234],[1342])}q^{\operatorname{cdes}[\sigma]}t^{\operatorname{cpk}[\sigma]}=q^{n-2}t+(2n-6)q^{n-2}t^{2}+q^{n-1}t.$

###### Proof.

Let $F_{n}(q,t)$ denote the desired generating function. We proceed as in the
proof of Theorem 5.7 (a) to find a recursion for $F_{n+1}(q,t)$. Since the
largest element of $[\sigma]$ is always a cyclic peak, inserting $n+1$ before
$n$ does not change $\operatorname{cpk}$. So this contributes $qF_{n}(q,t)$ to
the recursion. For $\delta$ and $\epsilon$, inserting $n+1$ in the other
active site increases the number of peaks to $2$. So the contribution from
these cases is $2q^{n-1}t^{2}$. In summary

$F_{n+1}(q,t)=2q^{n-1}t^{2}+qF_{n}(q,t)$

and the desired polynomial is easily seen to be the solution. ∎

In a recent paper Adin, Gessel, Reiner, and Roichman [AGRR20] defined a cyclic
analogue of the Hopf algebra of quasisymmetric functions. In this context the
cyclic descent set of a linear permutation arises naturally in the description
of the product in this algebra. They also raise the following intriguing
question.

######  Question 6.2.

Find an analogue of the major index for cyclic permutations that has nice
properties, such as a generating function over $[{\mathfrak{S}}_{n}]$ which
factors nicely as does the generating function for the ordinary major index
over ${\mathfrak{S}}_{n}$.

###  6.3 Vincular patterns

The study of vincular patterns was originated by Babson and Steingrímsson
[BS00] and has since become a mainstay of the pattern field. We consider $\pi$
as a vincular pattern if one only counts occurrences in $\sigma$ where certain
adjacent elements of $\pi$ must also be adjacent in the copy in $\sigma$. Such
adjacent elements are overlined in $\pi$. For example, $\sigma=24513$ contains
two copies of $\pi=132$, namely $243$ and $253$. But only $243$ is a copy of
$\overline{13}2$. Avoidance and Wilf equivalence are defined in the obvious
way. These notions and the corresponding notation carry over to cyclic
patterns without change. There are undoubtedly nice results which can be
proven about vincular cyclic patterns. As an example, we show how one vincular
class is enumerated by the Catalan numbers.

######  Theorem 6.3.

We have

$[13\overline{24}]\equiv[1\overline{42}3]\equiv[\overline{13}24]\equiv[2\overline{31}4].$

And for $n\geq 1$

$\\#\operatorname{Av}_{n}[13\overline{24}]=C_{n-1}.$

###### Proof.

The Wilf equivalences are trivial. To prove the Catalan formula, suppose that
$[\sigma]\in\operatorname{Av}_{n}[13\overline{24}]$ for $n\geq 2$ and write
$\sigma$ so that $\sigma_{n}=n$ and $\sigma_{n-1}=m$ for some $m\in[n-1]$.
First notice that $\sigma=\rho\tau mn$ where $\rho$ and $\tau$ are
permutations of $[m+1,n-1]$ and $[m-1]$, respectively. For if there are
$x<m<y<n$ with $x$ before $y$ in $\sigma$ then $[xymn]$ is a copy of
$[13\overline{24}]$. Furthermore, it is clear that $[m\rho]$ and $[\tau m]$
must avoid the forbidden pattern.

We claim the if $\sigma=\rho\tau mn$ where $\rho$ and $\tau$ obey the
restrictions of the previous paragraph then $[\sigma]$ avoids
$[13\overline{24}]$. Suppose, towards a contradiciton, that a copy
$[\kappa]=[wyxz]$ exists with $wyxz$ order isomorphic to $13\overline{24}$.
Consider the elements $x$ and $z$ which play the roles of $2$ and $4$. The
possibility that they are $m$ and $n$, respectively, is ruled out by the fact
that every element of $\rho$ is larger than every element of $\tau$. If
$z\in\tau m$ then all of $\kappa$ must be in this subsequence since $z$ is the
largest element of the copy. But this is impossible since $[\tau m]$ avoids
the bad pattern. Finally, suppose $z\in\rho$. This forces $x\in\rho$ since it
is comes cyclically just before $z$, and $n$ is too large to be $x$. We must
also have $y\in\rho$ since $x<y<z$. But now there is no possible choice for
$w$. Indeed, if $w\in[m\rho]$ then $[\kappa]$ is in this subsequence,
contradicting our assumption. And if $w\in\tau$ then it could be replaced by
$m$ since $x,y,z>m$, yielding the same contradiction as before.

From the first two paragraphs we immediately get the recursion

$\\#\operatorname{Av}_{n}[13\overline{24}]=\sum_{m=1}^{n-1}\\#\operatorname{Av}_{m}[13\overline{24}]\cdot\\#\operatorname{Av}_{n-m}[13\overline{24}].$

From this the Catalan enumeration follows by induction. ∎

It appears that sometimes rather than trying to find the size of the avoidance
class directly, it may be easier to use exponential generating functions.
Given a set of (possibly vincular) patterns $[\Pi]$, let

$E[\Pi]=\sum_{n\geq 0}\\#\operatorname{Av}_{n}[\Pi]\frac{x^{n}}{n!}.$

We have the following conjectures for two vincular avoidance classes. Once the
corresponding differential equation is proved, an explicit solution can easily
found using separation of variables.

######  Conjecture 6.4.

We have the following.

  1. 1.

If $E=E[\overline{123}]$ then

$E^{\prime}=E^{2}-E+1.$

  2. 2.

If $E=E[\overline{213}]$ then

$E^{\prime}=e^{E-\frac{x^{2}}{2}}.$

## References

  * [AGRR20] Ron M. Adin, Ira M. Gessel, Victor Reiner, and Yuval Roichman.  Cyclic quasi-symmetric functions.  Sém. Lothar. Combin., 82B:Art. 67, 12, 2020.
  * [BBMD+02] Cyril Banderier, Mireille Bousquet-Mélou, Alain Denise, Philippe Flajolet, Danièle Gardy, and Dominique Gouyou-Beauchamps.  Generating functions for generating trees.  volume 246, pages 29–55. 2002.  Formal power series and algebraic combinatorics (Barcelona, 1999).
  * [BBPS15] Sara Billey, Krzysztof Burdzy, Soumik Pal, and Bruce E. Sagan.  On meteors, earthworms and WIMPs.  Ann. Appl. Probab., 25(4):1729–1779, 2015.
  * [BBS13] Sara Billey, Krzysztof Burdzy, and Bruce E. Sagan.  Permutations with given peak set.  J. Integer Seq., 16(6):Article 13.6.1, 18, 2013.
  * [BFT16] Sara Billey, Matthew Fahrbach, and Alan Talmage.  Coefficients and roots of peak polynomials.  Exp. Math., 25(2):165–175, 2016.
  * [BM03] Mireille Bousquet-Mélou.  Four classes of pattern-avoiding permutations under one roof: generating trees with two labels.  volume 9, pages Research paper 19, 31. 2002/03.  Permutation patterns (Otago, 2003).
  * [Bón04] Miklós Bóna.  Combinatorics of permutations.  Discrete Mathematics and its Applications (Boca Raton). Chapman & Hall/CRC, Boca Raton, FL, 2004.
  * [BS00] Eric Babson and Einar Steingrímsson.  Generalized permutation patterns and a classification of the Mahonian statistics.  Sém. Lothar. Combin., 44:Art. B44b, 18, 2000.
  * [Cal] David Callan.  Pattern avoidance in circular permutations.  Preprint arXiv:0210014.
  * [CGHK78] F. R. K. Chung, R. L. Graham, V. E. Hoggatt, Jr., and M. Kleiman.  The number of Baxter permutations.  J. Combin. Theory Ser. A, 24(3):382–394, 1978.
  * [CVDLO+17] Francis Castro-Velez, Alexander Diaz-Lopez, Rosa Orellana, José Pastrana, and Rita Zevallos.  The number of permutations with the same peak set for signed permutations.  J. Comb., 8(4):631–652, 2017.
  * [DDJ+12] Theodore Dokos, Tim Dwyer, Bryan P. Johnson, Bruce E. Sagan, and Kimberly Selsor.  Permutation patterns and statistics.  Discrete Math., 312(18):2760–2775, 2012.
  * [DLHIO17a] Alexander Diaz-Lopez, Pamela E. Harris, Erik Insko, and Mohamed Omar.  A proof of the peak polynomial positivity.  Sém. Lothar. Combin., 78B:Art. 6, 9, 2017.
  * [DLHIO17b] Alexander Diaz-Lopez, Pamela E. Harris, Erik Insko, and Mohamed Omar.  A proof of the peak polynomial positivity conjecture.  J. Combin. Theory Ser. A, 149:21–29, 2017.
  * [DLHIPL17] Alexander Diaz-Lopez, Pamela E. Harris, Erik Insko, and Darleen Perez-Lavin.  Peak sets of classical Coxeter groups.  Involve, 10(2):263–290, 2017.
  * [ES35] P. Erdös and G. Szekeres.  A combinatorial problem in geometry.  Compositio Math., 2:463–470, 1935.
  * [GLW18] Daniel Gray, Charles Lanning, and Hua Wang.  Pattern containment in circular permutations.  Integers, 18B:Paper No. A4, 13, 2018.
  * [GLW19] Daniel Gray, Charles Lanning, and Hua Wang.  Patterns in colored circular permutations.  Involve, 12(1):157–169, 2019.
  * [Kre00] Darla Kremer.  Permutations with forbidden subsequences and a generalized Schröder number.  Discrete Math., 218(1-3):121–130, 2000.
  * [Sag20] Bruce E. Sagan.  Combinatorics: The art of counting, volume 210 of Graduate Studies in Mathematics.  American Mathematical Society, Providence, RI, 2020.
  * [SS85] Rodica Simion and Frank W. Schmidt.  Restricted permutations.  European J. Combin., 6(4):383–406, 1985.
  * [Sta97] Richard P. Stanley.  Enumerative Combinatorics. Vol. 1, volume 49 of Cambridge Studies in Advanced Mathematics.  Cambridge University Press, Cambridge, 1997.  With a foreword by Gian-Carlo Rota, Corrected reprint of the 1986 original.
  * [Sta99] Richard P. Stanley.  Enumerative Combinatorics. Vol. 2, volume 62 of Cambridge Studies in Advanced Mathematics.  Cambridge University Press, Cambridge, 1999.  With a foreword by Gian-Carlo Rota and appendix 1 by Sergey Fomin.
  * [Ste97] John R. Stembridge.  Enriched $P$-partitions.  Trans. Amer. Math. Soc., 349(2):763–788, 1997.
  * [Wes95] Julian West.  Generating trees and the Catalan and Schröder numbers.  Discrete Math., 146(1-3):247–262, 1995.
  * [Wes96] Julian West.  Generating trees and forbidden subsequences.  In Proceedings of the 6th Conference on Formal Power Series and Algebraic Combinatorics (New Brunswick, NJ, 1994), volume 157, pages 363–374, 1996.


# The porous envelope and circumstellar wind matter of the closest carbon
star, CW Leonis

Hyosun Kim1 Ho-Gyu Lee1 Youichi Ohyama2 Ji Hoon Kim3 Peter Scicluna4 You-Hua
Chu2 Nicolas Mauron5 Toshiya Ueta6 1Korea Astronomy and Space Science
Institute, 776, Daedeokdae-ro, Yuseong-gu, Daejeon 34055, Republic of Korea
2Institute of Astronomy and Astrophysics, Academia Sinica, 11F of Astronomy-
Mathematics Building, AS/NTU, No.1, Sec. 4, Roosevelt Rd, Taipei 10617,
Taiwan, R.O.C.
3SNU Astronomy Research Center, Department of Physics and Astronomy, Seoul
National University, 1 Gwanak-ro, Gwanak-gu, Seoul 08826, Korea
4European Southern Observatory, Alonso de Cordova 3107, Santiago RM, Chile
5Laboratoire Univers et Particules, Universite de Montpellier and CNRS,
Batiment 13, CC072, Place Bataillon, F-34095 Montpellier, France
6Department of Physics and Astronomy, University of Denver, 2112 E Wesley
Ave., Denver, CO 80208, USA

(2022)

###### Abstract

Recent abrupt changes of CW Leonis may indicate that we are witnessing the
moment that the central carbon star is evolving off the Asymptotic Giant
Branch (AGB) and entering into the pre-planetary nebula (PPN) phase. The
recent appearance of a red compact peak at the predicted stellar position is
possibly an unveiling event of the star, and the radial beams emerging from
the stellar position resemble the feature of the PPN Egg Nebula. The increase
of light curve over two decades is also extraordinary, and it is possibly
related to the phase transition. Decadal-period variations are further found
in the residuals of light curves, in the relative brightness of radial beams,
and in the extended halo brightness distribution. Further monitoring of the
recent dramatic and decadal-scale changes of this most well-known carbon star
CW Leonis at the tip of AGB is still highly essential, and will help us gain a
more concrete understanding on the conditions for transition between the late
stellar evolutionary phases.

###### keywords:

stars: AGB and post-AGB, (stars:) binaries: general, stars: carbon, (stars:)
circumstellar matter, stars: evolution, stars: individual (CW Leonis), stars:
late-type, stars: mass loss, stars: winds, outflows

††volume: 370††journal: Winds of Stars and Exoplanets††editors: A. A. Vidotto,
L. Fossati & J. Vink, eds.

##  1 Introduction

Many pre-planetary nebulae (PPN) consist of newly-formed inner
bipolar/multipolar lobes and outer spirals/rings/arcs that are the fossil
records of stellar wind matter accumulated during the asymptotic giant branch
(AGB) phase. The coexistence of two such morphologically distinct
circumstellar structures is a mystery; however, it is widely believed that
binaries play a key role. The most direct clue to resolving the mystery of the
shape transition along stellar phase evolution may be offered by catching the
moment when an AGB star is evolving off the current phase toward the PPN
phase. Recent dramatic changes of CW Leonis likely indicate that we are
witnessing the moment of transition between these late stellar evolutionary
phases.

##  2 Previous Views on CW Leonis

CW Leonis is the closest (distance of about 123 pc; Groenewegen et al., 2012)
and the most well-studied carbon-rich AGB star (or carbon star). Multi-
wavelength observations suggest that CW Leonis is likely a binary system
(e.g., Jeffers et al., 2014; Decin et al., 2015). Its non-concentric ring-like
pattern over 200 arcsec is remarkable (Mauron & Huggins, 2000), which can be
modeled by a spiral-shell structure introduced by an eccentric orbit binary at
the center (e.g., Cernicharo et al., 2015). However, neither the carbon star
nor the companion has been identified because of obscuration by the dense
circumstellar matter ejected from this extreme carbon star at the tip of AGB.

Several near-infrared observations were executed with adaptive optics and
speckle interferometry in 1995–2003 (Tuthill et al., 2000; Osterbart et al.,
2000; Weigelt et al., 2002; Murakawa et al., 2005) achieving high-resolutions
($<0.1$ arcsec) but losing stellar positional information at the cost of field
sizes; several clumps were revealed, but their relationship with the central
star was unclear. The vigorous debate about which clump corresponds to the
carbon star ended in vain through a monitoring study over 2000–2008 showing
that the clumps faded out around 2005 (Stewart et al., 2016).

In the optical, before 2011, the core region exhibited an extended bipolar
nebula without any distinct point source (Haniff & Buscher, 1998; Skinner et
al., 1998; Leão et al., 2006), from which this object was thought to have an
invisible star residing in a dusty disk lying perpendicular to the bipolar
structure. The bipolar-like structure, however, disappeared in the latest
Hubble Space Telescope images taken in 2011 and 2016 (Kim et al., 2015, 2021),
suggesting a completely different view for CW Leonis.

##  3 Recent Dramatic Changes and Porous Envelope Scenario

Figure 1:  Temporal change of brightness in the central 1.5 arcsec region of
CW Leonis. The star symbol indicates the proper-motion-corrected position of
the star at each epoch, denoted at the top of each panel. The bipolar-like
structure (black line) before 2011, which had likely given a misleading
impression for the origin and evolutionary phase of CW Leonis, disappeared in
the 2011 and 2016 epochs. From left to right, the Hubble Space Telescope
images are taken with the F606W filter ($\sim 0.6\rm\,\mu m$) at the epochs of
1998-03-30 (Prop. ID: 6856, PI: J. Trauger), 2001-01-07 (Prop. ID: 8601, PI:
P. Seitzer), 2011-06-04 (Prop. ID: 12205, PI: T. Ueta), and 2016-05-17 (Prop.
ID: 14501, PI: H. Kim).

Surprisingly, the latest optical images of CW Leonis, taken using Hubble Space
Telescope, in 2011 and 2016 revealed dramatic changes in the core region of
the circumstellar envelope from those taken about 10-year earlier in 1998 and
2001 (Figure 1). Besides the disappearance of the long-believed bipolar-like
nebula, several important features are identified and become evidences for a
porous envelope of the central star (Kim et al., 2021).

Figure 2:  The Hubble Space Telescope image of CW Leonis taken with the F814W
filter ($\sim 0.8\rm\,\mu m$) in 2016 (bottom right), compared to the 2011
epoch image (bottom left). The radial beams and multiple rings appearing
prominent in the central 5 arcsec region are the intriguing features (top
right). The color map for central 1 arcsec region shows the reddest spot
coincides with the stellar position, marked by black contours of the F814W
brightness (top left) same as the image in the top middle panel. The color
bars range the F814W brightness in logarithmic scales, but for the color map
in the top left panel being in linear scales for the magnitude difference
between the F606W and F814W images.

In contrast to its absence at the previous epochs, a local brightness peak
appears exactly at the expected stellar position (Figure 2, top middle) and it
is identified as the reddest spot in the color map (Figure 2, top left). It is
compact; its full width at half maximum above the adjacent diffuse emission is
slightly larger than the standard point-spread function. This red compact spot
at a local peak is interpreted as the direct starlight, escaping through one
of the gaps in the clumpy envelopes shrouding the star. This radial beam may
pulsate around the line of sight with a small angle and be coincidentally
aligned with the line of sight at the observed epoch in 2016.

The outer part of the observed image exhibits eight straight lines of
brightness that are radially stretched from the central star (Figure 2, top
right). In the context of the porous envelope scenario, these searchlight
beams indicate the trajectories of starlight penetrating the holes in the
inner envelopes, along which adjacent dust particles in the circumstellar
envelopes are illuminated. Any other interpretation for their origin is
precluded because of the straightness of these beams regardless of the
considerably fast stellar proper motion.

The extended halo brightness distribution becomes fairly symmetric about the
central star in the 2016 image, compared to the elongated distribution to the
northwest in the 2011 image (Figure 2, bottom panels). This change is again
beyond the scope of dynamics of matter that would require a very long time to
move the whole halo with an extremely large extent. It is speculated that one
of the radial beams, that is related to the new emergence of central red
compact brightness peak, alters its angle toward the line of sight in 2016
from a slightly misaligned angle pointing toward the northwestern direction in
2011, explaining the redistribution of the halo brightness.

Figure 3:  Searchlight beams of CW Leonis are fixed in the relative positions
with respect to the proper-motion-corrected stellar position and their
relative brightnesses are varying with time. The snapshots are taken from an
animation in the Research Gallery of http://hubblesite.org. Image credit:
ESA/Hubble, NASA, Toshiya Ueta (Univ. of Denver), Hyosun Kim (KASI).

The radial beams appearing in the plane of the sky do not seem to shift their
positions much with time (Figure 3). Their position angles with respect to the
predicted stellar positions at the individual epochs are almost fixed.
Therefore, it is natural that we assume the precession angle for the radial
beam relevant to the extended brightness distribution is small. In order to
verify this scenario, another epoch imaging observations with the same setup
is anticipated.

In contrast, the relative brightnesses of the radial beams significantly
change and the period seems to be about 10 years (Figure 3). The brightest
beams are toward north in the 2001 and 2011 epochs (downward in the figure)
while toward south in the 2016 epoch (upward). Indeed, besides the stellar
pulsation of 640-day period, a decadal variation has been suggested based on
near-infrared and optical photometric data (Dyck et al., 1991; Kim et al.,
2021). In particular, the increases of $K$-band flux and the point source
contribution in it during 1980–1990 are quite similar to the event found in
2016. To assess whether the variations are indeed periodic, more frequent
longer-term monitoring observations are desired.

##  4 Anisotropic Wind Expansion induced by an Eccentric Binary

Figure 4:  (Left) the expansion velocities in 36 sectors derived from
differential proper motion of recurrent ring-like pattern of CW Leonis (Kim et
al., 2021); (right) the correspondance in an eccentric-orbit binary model with
the pericenter of the mass-losing star to the north (at the position angle of
0∘), viewed at three different inclination angles 0∘ (blue, solid line,
hatched area), 45∘ (green, dotted line, star-filled area), and 90∘ (red,
dashed line, horizontally lined area), respectively (Kim, 2022).

The multiple shell pattern wrapping around the star is one of the most
intriguing features of CW Leonis. Our analysis using differential proper
motion of the pattern indicates expansion of shells of ejected material from
the star. The derived speeds of the expanding shells depend on the direction
(Figure 4, left). The expansion speeds vary not only across different position
angles within the Hubble Space Telescope image (about 7 km s-1 faster to the
south), but their average speed in the plane of the sky was also about 2 km
s-1 slower than the wind speed along the line of sight that is derived from
molecular line observations in radio wavelengths. This variation of measured
speeds indicates an overall nonspherical geometry of the wind matter. We
further find that these observations (Figure 4, left panel) are compatible
with a binary model having an eccentric orbit (see the right panel of Figure
4, from Kim, 2022).

We regard, however, the velocity measurement was somewhat uncertain. The 2016
image was not as deep as the 2011 image, reducing the number of rings used in
the analysis. Another obstacle was the relatively small expansion length (the
average of positional difference of individual rings between the 2011 and 2016
epochs) due to the short 5-year interval, which was only slightly larger than
the size of point-spread function. With these reasons, high-resolution high-
sensitivity imaging monitoring is further needed.

##  5 Conclusion

The recent drastic changes in optical images suggest that the previously-seen
bipolar-like structure could not be a concrete structure but could possibly be
parts of searchlight beams with varying relative brightnesses along time.
These radial beams reveal the pathways of starlight illuminating dusty
material after escaping through the gaps in the clumpy envelope enshrouding
the star. The appearance of a distinct brightness peak exactly at the
predicted stellar position and the abnormal shift of large halo distribution
both can be explained by a hypothesized radial beam toward us that is slowly
precessing with a small angle and aligned with the line of sight at the latest
observation epoch.

Although the complexity of CW Leonis has been well known since its discovery,
the three dimensional morphology of its central core and evolving beams is
uniquely revealed with recent Hubble Space Telescope optical monitoring of the
core images. It also allows to trace the expansion velocity of shells and
clumps as seen in the evolving light of the central star. Furthermore, on-
going efforts on three dimensional hydrodynamic models fitting the data likely
suggests a small inclination of the orbit (close to face-on) with the
pericenter of the mass-losing star at North. Further systematic monitoring of
this canonical high mass-loss carbon star is mandatory to strengthen our
interpretation coupled with our modelling. Hubble Space Telescope allows us to
be very near of establishing a robust understanding of the mass loss of this
strategic but mysterious AGB (or soon post-AGB) star.

###### Acknowledgements.

HK acknowledges support by the National Research Foundation of Korea (NRF)
grant (No. 2021R1A2C1008928) and Korea Astronomy and Space Science Institute
(KASI) grant (Project No. 2022-1-840-05), both funded by the Korea Government
(MSIT).

## References

  * Cernicharo et al. (2015) Cernicharo, J., Marcelino, N., Agúndez, M., & Guélin, M. 2015, A&A, 575, A91
  * Decin et al. (2015) Decin, L., Richards, A. M. S., Neufeld, D., et al. 2015, A&A, 574, AA5
  * Dyck et al. (1991) Dyck, H. M., Benson, J. A., Howell, R. R., et al. 1991, AJ, 102, 200
  * Groenewegen et al. (2012) Groenewegen, M. A. T., Barlow, M. J., Blommaert, J. A. D. L., et al. 2012, A&A, 543, L8
  * Haniff & Buscher (1998) Haniff, C. A., & Buscher, D. F. 1998, A&A, 334, L5
  * Jeffers et al. (2014) Jeffers, S. V., Min, M., Waters, L. B. F. M., et al. 2014, A&A, 572, AA3
  * Kim (2022) Kim, H. 2022, in prep.
  * Kim et al. (2015) Kim, H., Lee, H.-G., Mauron, N., & Chu, Y.-H. 2015, ApJ Letters, 804, L10
  * Kim et al. (2021) Kim, H., Lee, H.-G., Ohyama, Y., et al. 2021, ApJ, 914, 35
  * Leão et al. (2006) Leão, I. C., de Laverny, P., Mékarnia, D., de Medeiros, J. R., & Vandame, B. 2006, A&A, 455, 187
  * Mauron & Huggins (2000) Mauron, N., & Huggins, P. J. 2000, A&A, 359, 707
  * Menten et al. (2012) Menten, K. M., Reid, M. J., Kamiński, T., & Claussen, M. J. 2012, A&A, 543, AA73
  * Murakawa et al. (2005) Murakawa, K., Suto, H., Oya, S., et al. 2005, A&A, 436, 601
  * Osterbart et al. (2000) Osterbart, R., Balega, Y. Y., Blöcker, T., Men’shchikov, A. B., & Weigelt, G. 2000, A&A, 357, 169
  * Skinner et al. (1998) Skinner, C. J., Meixner, M., & Bobrowsky, M. 1998, MNRAS, 300, L29
  * Stewart et al. (2016) Stewart, P. N., Tuthill, P. G., Monnier, J. D., et al. 2016, MNRAS, 455, 3102
  * Tuthill et al. (2000) Tuthill, P. G., Monnier, J. D., Danchi, W. C., & Lopez, B. 2000, ApJ, 543, 284
  * Weigelt et al. (2002) Weigelt, G., Balega, Y. Y., Blöcker, T., et al. 2002, A&A, 392, 131