# Generalized Pattern Avoidance Condition for the Wreath Product of Cyclic Groups with Symmetric Groups

Authors: Sergey Kitaev; Jeffrey Remmel; Manda Riehl
Journal: ISRN Combinatorics
 (2013)

---

## Abstract

We continue the study of the generalized pattern avoidance condition forCk≀Sn, the wreath product of the cyclic group Ck with the symmetric group Sn, initiated in the work by Kitaev et al., In press. Among our results, there are a number of (multivariable) generating functions both for consecutive and nonconsecutive patterns, as well as a bijective proof for a new sequence counted by the Catalan numbers.


---

## Body

## 1. Introduction

The goal of this paper is to continue the study of pattern-matching conditions on the wreath productCk≀Sn of the cyclic group Ck and the symmetric group Sn initiated in [1]. Ck≀Sn is the group of  knn! signed permutations where there are  k signs,  1=ω0, ω, ω2,…, ωk-1, where ω is a primitive kth root of unity. We can think of the elements Ck≀Sn as pairs γ=(σ,ϵ)  where  σ=σ1⋯σn∈Sn  and  ϵ=ϵ1⋯ϵn∈{1,ω,…,ωk-1}n. For ease of notation, if ϵ=(ωw1,ωw2,…,ωwn) where wi∈{0,…,k-1} for  i=1,…,n, then we simply write γ=(σ,w) where w=w1w2⋯wn. Moreover, we think of the elements of w=w1w2⋯wn as thecolors of the corresponding elements of the underlying permutation σ.We define a concept for matchings in words over a finite alphabet[k]={0,1,…,k-1}. Given a word w=w1⋯wn∈[k]n,  let red(w) be the word found by replacing the ith largest integer that appears in w by i-1. For example, if w=27247, then red(w)=02012. Given a word u∈[k]j such that red(u)=u, we say that a word  w∈[k]n has a u-match starting at positioni  provided  red(wi⋯wi+j-1)=u. Let u-mch(w) be the number of u-matches in the word w. Similarly, we say that uoccurs in a word w if there exist  1≤i1<⋯<ij≤n such that  red(wi1⋯wij)=u.  We say that  wavoidsu if there are no occurrences of u in w.There are a number of papers on pattern matching and pattern avoidance inCk≀Sn  [2–5]. We now present a selection of the previously studied definitions for pattern matching and avoidance, so that the reader may see how ours differs from and/or extends those in the literature. For example, the following pattern matching condition was studied in [3–5].Definition 1.
Let(τ,u)∈Ck≀Sj,  Υ be a subset of  Ck≀Sj, and  (σ,w)∈Ck≀Sn. (1)
One says that(σ,w) has an exact occurrence of  (τ,u) (resp., Υ)  if there are 1≤i1<i2<⋯<ij≤n  such that  (red(σi1⋯σij),wi1⋯wij)=(τ,u) (resp.,  (red(σi1⋯σij),wi1⋯wij)∈Υ).(2)
One says that(σ,w)∈Ck≀Sn   avoids an exact occurrence of(τ,u) (resp., Υ) if there are no exact occurrences of (τ,u) (resp., Υ) in (σ,w).(3)
One says that there is anexact(τ,u)-match in(σ,w)starting at positioni (resp., exactΥ-match in(σ,w)starting at positioni) if (red(σiσi+1⋯σi+j-1),wiwi+1⋯wi+j-1)=(τ,u) (resp., (red(σiσi+1⋯σi+j-1),wiwi+1⋯wi+j-1)∈Υ).
That is, an exact occurrence or an exact match of(τ,u)∈Ck≀Sj in an element (σ,w)∈Ck≀Sn is just an ordinary occurrence or match of τ in σ where the corresponding signs agree exactly. For example, Mansour [4] proved via recursion that, for any (τ,u)∈Ck≀S2, the number of elements in  Ck≀Sn which avoid exact occurrences of (τ,u)  is  ∑j=0n‍j!(k-1)j(nj)2. This generalized a result of Simion [6] who proved the same result for the hyperoctahedral group  C2≀Sn. Similarly, Mansour and West [5] determined the number of permutations in  C2≀Sn  that avoid all possible exact occurrences of 2 or 3 element sets of patterns from C2≀S2. For example, let Kn1 be the number of (σ,ϵ)∈C2≀Sn that avoid all exact occurrences of the patterns in the set {(12,00),(12,01),(21,10)},  Kn2 the number of  (σ,ϵ)∈C2≀Sn  that avoid all exact occurrences of the patterns in the set  {(12,01),(12,10),(21,01)}, and  Kn3 the number of  (σ,ϵ)∈C2≀Sn that avoid all exact occurrences of the patterns in the set {(12,00),(12,01),(21,00)}. Then Mansour and West [5] proved that
(1)Kn1=F2n+1,Kn2=n!∑j=0n‍(nj)-1,Kn3=n!+n!∑j=1n‍1j,
where Fn is the nth Fibonacci number.An alternative matching condition arises when we drop the requirement of the exact matching of signs and replace it by the condition that the two sequences of signs match in the sense of words described above. That is, we shall consider the following matching conditions.Definition 2.
Let(τ,u)∈Ck≀Sj  where red(u)=u, Υ a subset of Ck≀Sj where for all (τ,u)∈Υ, red(u)=u,  and (σ,w)∈Ck≀Sn. (1)
One says that(σ,w) has an occurrence of  (τ,u) (resp., Υ) if there are 1≤i1<i2< ⋯<ij≤n  such that (red(σi1⋯σij), red(wi1⋯wij))=(τ,u) (resp., (red(σi1⋯σij),red(wi1⋯wij))∈Υ).(2)
One says that(σ,w)∈Ck≀Sn    avoids(τ,u) (rep., Υ) if there are no occurrences of (τ,u) (resp., Υ) in (σ,w).(3)
One says that there is a(τ,u)-match in(σ,w)  starting at positioni (resp., Υ-match in(σ,w)   starting at positioni) if (red(σiσi+1⋯σi+j-1),red(wiwi+1⋯wi+j-1))=(τ,u) (resp., (red(σiσi+1⋯σi+j-1),red(wiwi+1⋯wi+j-1))∈Υ).For example, suppose that(τ,u)=(12,00) and (σ,w)=(1324,1222). Then there are no exact occurrences or exact matches of (τ,u) in (σ,w). However, there are two occurrences of  (τ,u), one in positions 2 and 4 and one in positions 3 and 4. Thus there are two occurrences of  (τ,u) in (σ,w) and there is a (τ,u)-match in  (σ,w) starting at position 3.Finally, a more general-matching condition which generalizes both occurrences and matches and exact occurrences and exact matches inCk≀Sn  was introduced in [1].Definition 3.
Let(τ,u,A→)∈Ck≀Sj, Υ be a subset of Ck≀Sj,  A→=(A1,…,Aj) be a sequence of subsets of [k], and  (σ,w)∈Ck≀Sn. (1)
One says that(σ,w) has an  occurrence of  (τ,u,A→) (resp., (Υ,A→)) if there are 1≤i1<i2<⋯<ij≤n such that  (red(σi1⋯σij),red(wi1⋯wij))=(τ,red(u)) (resp., (red(σi1⋯σij),red(wi1⋯wij))  is equal to (τ,red(u)) for some  (τ,u) in  Υ) and  wis∈As  for  s=1,…,j.(2)
One says that(σ,w)∈Ck≀Sn    avoids(τ,u,A→) (resp., (Υ,A→)) if there are no occurrences of (τ,u) (resp., Υ) in (σ,w).(3)
One says that there is a(τ,u,A→)-match in(σ,w)starting at positioni (resp., (Υ,A→)-match in(σ,w)starting at positioni) if (red(σiσi+1⋯σi+j-1),  red(wiwi+1⋯wi+j-1))=(τ,red(u))  (resp., (red(σiσi+1⋯σi+j-1),red(wiwi+1⋯wi+j-1)) is equal to (τ,red(u)) for some (τ,u) in Υ) and wi+s∈As+1 for s=0,…,j-1.Thus a(τ,u,A→)-occurrence (or a (τ,u,A→)-match) where u=u1⋯uj and A→=({u1},…,{uj}) is just an exact occurrence (resp., an exact match) of (τ,u). Similarly, a (τ,u,A→)-occurrence (or a (τ,u,A→)-match) where u=u1⋯uj, red(u)=u, and A→=(A1,…,Aj)  such that  Ai=[k]  for i=1,…,j  is just an occurrence (or match) of (τ,u).Suppose we are given(τ,u)∈Ck≀Sj, Υ⊆Ck≀Sj,  A→=(A1,…,Aj) where Ai⊆[k] for i=1,…,j, and (σ,w)∈Ck≀Sn. We let (τ,u)-mch((σ,w)) (resp., (τ,u)-Emch((σ,w))) denote the number of (τ,u)-matches (resp., exact (τ,u)-matches) in (σ,w). We let Υ-mch((σ,w)) (resp., Υ-Emch((σ,w))) denote the number Υ-matches (resp., exact Υ-matches) in (σ,w). We let  (τ,u,A→)-mch((σ,w)) be the number of (τ,u,A→)-matches in (σ,w) and (Υ,A→)-mch((σ,w)) the number of  (Υ,A→)-matches in  (σ,w).The main result of [1] was to derive a generating function for the distribution of (τ,u,A→)-matches where (τ,u)∈Ck is any element of Ck≀S2. To state the main result of [1], we need to define some notation. First we define the p,q-analogues of  n, n!, (nk), and (na1,…,am) by
(2)[n]p,q=pn-qnp-q=pn-1+pn-2q+⋯+pqn-2+qn-1,[n]p,q!=[n]p,q[n-1]p,q⋯[2]p,q[1]p,q,[nk]p,q=[n]p,q![k]p,q![n-k]p,q!,[na1,…,am]p,q=[n]p,q![a1]p,q!⋯[am]p,q!,
respectively. We define the q-analogs of n,  n!,  (nk),  and (na1,…,am) by [n]1,q,  [n]1,q!,  [nk]1,q,   and [na1,…,am]1,q,  respectively.Next suppose thatΥ⊆Ck≀S2 and A→=(A1,A2) where A1,A2⊆[k]. Then we will say that (σ,w)∈Ck≀Sn is a maximum packing for (Υ,A→) if (σ,w) has (Υ,A→)-matches starting at positions 1,2,…,n-1. We let ℳ𝒫(Υ,A→),n denote the set (σ,w)∈Ck≀Sn of maximum packings for (Υ,A→). Given any word w=w1⋯wn∈[k]n,  we let  z(w)=∏i=1n‍zwi. For any σ=σ1⋯σn∈Sn, we let inv(σ) (resp., coinv(σ)) equal the number of pairs (i,j) such that 1≤i<j≤n and σi>σj (resp., σi<σj). We then define
(3)mp(Υ,A→),n(p,q;z0,…,zk-1)=∑(σ,w)∈ℳ𝒫(Υ,A→),n‍pcoinv(σ)qinv(σ)z(w).
We will also be interested in the specializations
(4)mp(Υ,A→),n(p,q;1,…,1)=∑(σ,w)∈ℳ𝒫(Υ,A→),n‍pcoinv(σ)qinv(σ),mp(ΥA→),n(p,q;1,r,…,rk-1)=∑(σ,w)∈ℳ𝒫(Υ,A→),n‍pcoinv(σ)qinv(σ)r||w||,
where for any word  w=w1⋯wn∈[k]n,  ||w||=w1+⋯+wn. In the special case where Υ={(τ,u)} where (τ,u)∈Ck≀S2, we shall denote mp(Υ,A→),n(p,q;z0,…,zk-1) as mp(τ,u,A→),n(p,q,z0,…,zk-1).Then Kitaev et al. [1] proved that, for any Υ⊆Ck≀S2 and  A→=(A1,A2) where A1,A2⊆[k],
(5)∑n≥0‍tn[n]p,q!∑(σ,w)∈Ck≀Sn‍pcoinv(σ)qinv(σ)x(Υ,A→)-mch((σ,w))z(w)=(1-((z0+⋯+zk-1)t+∑n≥2‍tn[n]p,q!(x-1)n-1mp(Υ,A→),n(p,q;z0,…,zk-1)∑n≥2‍tn[n]p,q!(x-1)n-1))-1.Duane and Remmel [7] gave the generating function for the number of (τ,u)-matches and exact (τ,u)-matches for a certain collection of (τ,u)∈Cj≀Sn where j≥3 are called  minimal overlapping patterns. Given a word u∈{0,1,…,k-1}j such that red(u)=u and τ∈Sj, Duane and Remmel say that (τ,u) has the Ck≀Sn-minimal overlapping property if the smallest i such that there exists a  (σ,w)∈Ck≀Si with (τ,u)-mch((σ,w))=2 is 2j-1. This means that in a k-colored permutation (σ,w), two (τ,u)-matches can share at most one pair of letters, and this pair of letters must occur at the end of the first (τ,u)-match and at the start of the second (τ,u)-match. Similarly, we say that (τ,u) has the Ck≀Sn-exact match minimal overlapping property if the smallest i such that there exists a (σ,w)∈Ck≀Si with (τ,u)-Emch((σ,w))=2 is 2j-1. Now if (τ,u) has the Ck≀Sn-minimal overlapping property, then the shortest k-colored permutations (σ,w), such that (τ,u)-mch((σ,w))=n have length n(j-1)+1. We let  ℳ𝒫(τ,u),n(j-1)+1k equal the set of k-colored permutations, (σ,w)∈Ck≀Sn(j-1)+1, such that (τ,u)-mch(σ,w)=n. We refer to the k-colored permutations in  ℳ𝒫(τ,u),n(j-1)+1k  as maximum packings for (τ,u). We let
(6)mp(τ,u),n(j-1)+1k=|ℳ𝒫(τ,u),n(j-1)+1k|,mp(τ,u),n(j-1)+1k(p,q,r)=∑(σ,w)∈ℳ𝒫(τ,u),n(j-1)+1k‍pcoinv(σ)qinv(σ)r∑‍w,mp(τ,u),n(j-1)+1k(p,q;z0,…,zk-1)=∑(σ,w)∈ℳ𝒫(τ,u),n(j-1)+1k‍pcoinv(σ)qinv(σ)z(w).
Similarly, we let  ℰℳ𝒫(τ,u),n(j-1)+1k denote the set of k-colored permutations,  (σ,w)∈Ck≀Sn(j-1)+1, such that (τ,u)-Emch(σ,w)=n, and refer to the k-colored permutations in ℰℳ𝒫(τ,u),n(j-1)+1k  as exact match maximum packings for  (τ,u). We let
(7)emp(τ,u),n(j-1)+1k=|ℰℳ𝒫(τ,u),n(j-1)+1k|,emp(τ,u),n(j-1)+1k(p,q,r)=∑(σ,w)∈ℰℳ𝒫(τ,u),n(j-1)+1k‍pcoinv(σ)qinv(σ)r∑‍w,emp(τ,u),n(j-1)+1k(p,q;z0,…,zk-1)=∑(σ,w)∈ℰℳ𝒫(τ,u),n(j-1)+1k‍pcoinv(σ)qinv(σ)z(w).
Duane and Remmel [7] proved that (I) if  red(u)=u and  (τ,u) has the Ck≀Sn-minimal overlapping property, then
(8)∑n≥0‍tnn!∑(σ,w)∈Ck≀Sn‍x(τ,u)-mch(σ,u)pcoinv(σ)qinv(σ)z(w)=1/(×emp(τ,u),n(j-1)+1k(p,q;z0,…,zk-1)1-(×emp(τ,u),n(j-1)+1k(p,q;z0,…,zk-1)(z0+⋯+zk-1)t+∑n≥1‍tn(j-1)+1[n(j-1)+1]p,q!(x-1)n×mp(τ,u),n(j-1)+1k(p,q;z0,…,zk-1))),
and (II) if  (τ,u)∈Ck≀Sj has the  Ck≀Sn-exact match minimal overlapping property, then
(9)∑n≥0‍tnn!∑(σ,w)∈Ck≀Sn‍x(τ,u)-Emch(σ,u)pcoinv(σ)qinv(σ)z(w)=1/(×emp(τ,u),n(j-1)+1k(p,q,z0,…,zk-1)1-(×emp(τ,u),n(j-1)+1k(p,q,z0,…,zk-1)(z0+⋯+zk-1)t+∑n≥1‍tn(j-1)+1[n(j-1)+1]q!(x-1)n×emp(τ,u),n(j-1)+1k(p,q,z0,…,zk-1))).
Duane and Remmel's proof of (I) and (II) works equally well for (Υ,A→)-matches.The main goal of this paper is to prove a number of results on the number of(τ,u,A→)-avoiding elements of Ck≀Sn and to find a generating function for the number of (τ,u,A→)-matches for certain patterns which do not have the minimal overlapping property. That is, in Section 2, we shall prove a number of results about the number of (τ,u,A→)-avoiding elements of  Ck≀Sn where  (τ,u)∈Ck≀S2. In Section 3, we prove a number of results on the number of (Υ,A→)-avoiding elements of  Ck≀Sn and for certain subsets  Υ of  Ck≀S2. Finally, in Section 4, we will prove an analog of a theorem of Mendes and Remmel which gave a generating function by the number of descents for the set of elements of Sn that had no (j(j-1)⋯1)-matches.


## 2.(τ,u,A→)-Avoiding Patterns

Given(τ,u)∈Ck≀Sj and  A→=(A1,…,Aj) where Ai⊆[k] for i=1,…,j,  let Av(τ,u,A→) denote the number of (σ,w)∈Ck≀Sn which avoid (τ,u,A→). In the special case where Ai=[k] for i=1,…,j, we shall denote Av(τ,u,A→) as simply Av(τ,u). Thus Av(τ,u) is the number (σ,w)∈Ck≀Sn which avoid (τ,u).  In this case, we shall find formulas for Av(τ,u,A→) or Av(τ,u) where (τ,u)∈Ck≀S2.There are a number of natural maps for which the distribution of(τ,u,A→)-occurrences and (τ,u,A→)-matches remain invariant. That is, for any σ=σ1⋯σn∈Sn, we define the reverse of  σ,  σr and the complement of  σ,  σc, respectively, by
(10)σr=σnσn-1⋯σ1,σc=(n+1-σ1)⋯(n+1-σn).
If w=w1⋯wn∈[k]n, then we define the reverse of  w,  wr and the complement of w relative to [k],  w(c,k), by
(11)wr=wnwn-1⋯w1,w(c,k)=(k-1-w1)⋯(k-1-wn).
If A={a1,…,as}⊆[k], then we define A(c,k)={k-1-a1,…,k-1-as}. Then if A→=(A1,…,Aj)  where Ai⊆[k], for i=1,…,j, then we define
(12)A→r=(Aj,Aj-1,…,A1),A→(c,k)=(A1c,k,…,Ajc,k).
Then consider the maps ϕa,b:Ck≀Sn→Ck≀Sn where ϕa,b((σ,w))=(σa,wb) for a,b∈{i,r,c} and b∈{i,r,(c,k)} where i is the identity map; that is, σi=σ for all σ∈Sn, wi=w  for all w∈[k]n, and A→i=A→  for all  A→=(A1,…,An)  with Ai⊆[k] for  i=1,…,n. It is easy to see that a (σ,τ) has a (τ,w,A→)-match or (τ,w,A→)-occurrence if and only if (σa,wb) has a (τa,ub,A→b)-occurrence or (τa,ub,A→b)-match.It follows that ifred(u)=u and  (τ,u)∈Ck≀S2, then we need only to compute Av(τ,u) for two patterns; namely,  (τ,u)=(12,00) and  (τ,u)=(12,01).We start by considering the pattern(12,00).Lemma 4.
The number of elements inCk≀Sn  avoiding (12,00) is given by
(13)∑i1+⋯+ik=ni1≥0,…,ik≥0‍(ni1,…,ik)2.Proof.
We first observe that elements of different colors are independent in permutations avoiding(12,00), meaning that no two elements with different colors can form a prohibited configuration. Thus assuming we have ij+1 elements of color j,  j=0,…,k-1, we can choose how to place these colors to form a word w in (ni1,…,ik) ways. Then we can choose the sets of elements C0,…,Ck-1 from {1,…,n} which will correspond to the colors 0,…,k-1 in σ in (ni1,…,ik) ways. Finally, in order to construct a (σ,w) which avoids the prohibited pattern, we must place the elements of Ci in the positions which are colored by i in decreasing order.The proof of Lemma4 suggests an obvious generalization for patterns of the form (τ,0j) where τ∈Sj.Theorem 5.
Letτ∈Sj. Then the number of elements in  Ck≀Sn avoiding (τ,0j) is given by
(14)∑i1+⋯+ik=ni1≥0,…,ik≥0‍Ai1Ai2⋯Aik(ni1,…,ik)2,
where An is the number of permutations in Sn avoiding τ.Proof.
The proof here is essentially the same as the proof of Theorem 4, except that we can placei elements of a permutation in  Ck≀Sn  of the same color in any of Ai ways.It is well known that the number ofn-permutations avoiding any pattern of length 3 is given by the nthCatalan numberCn=(1/(n+1))(2nn). As a corollary to Theorem 5, we have that, for any pattern τ∈S3, the number of permutations in  Ck≀Sn avoiding (τ,000) is given by(15)∑i1+⋯+ik=ni1≥0,…,ik≥0‍(2i1i1)(2i2i2)⋯(2ikik)(i1+1)(i2+1)⋯(ik+1)(ni1,…,ik)2.One can generalize  Theorems 4  and5 even further, by considering the distribution of patterns. Indeed, assuming that we know the number Ai,m of  i-permutations containing m occurrences of a pattern τ∈Sj, we can write down the number of permutations in Ck≀Sn with m occurrences of (τ,0j) as
(16)∑i1+⋯+ik=nm1+⋯+mk=mi1≥0,…,ik≥0m1≥0,…,mk≥0‍Ai1,m1Ai2,m2⋯Aik,mk(ni1,…,ik)2.
For example, the distribution of the occurrences of the pattern 12 is the same as the distribution of coinversions in permutations, so one can extract the numbers Ai,m as the coefficients to  qm  in  ∏s=1i‍(1+q+⋯+qs-1) and substitute them in the last formula to get the distribution of the number of occurrences of  (12,00) in Ck≀Sn.Next we consider the pattern(12,01) in the case where k=2.The number of permutations inC2≀Sn avoiding (12,01) is shown in [6, page 19] to be equal to  ∑j=0n‍j!(nj)2. However, in Theorem 6 below we provide an independent derivation of the exponential generating function in this case.Theorem 6.
The exponential generating function for the number of elements inC2≀Sn  avoiding the pattern  (12,01) is given by
(17)A(t)=et/(1-t)1-t.Proof.
LetAn=Av(12,01) and
(18)A(t)=∑n≥0‍Antnn!.
If  (σ,w)∈C2≀Sn+1 contains the element 1 colored by the color 1, then there are no restrictions for placing this element, thereby giving  (n+1)An possibilities. On the other hand, if (σ,w) contains the element 1 colored by the color 0 in position  i+1  and (σ,w) is to avoid (12,01), it must be the case that every element to the right of 1 is colored with the color 0 and these elements can be arranged in any of (n-i)!  ways. Moreover, it immediately follows that no instance of occurrence of (12,01) exists where the first element is to the left of 1 and the second is to the right of 1. Thus it follows that (σ,w) avoids (12,01) if and only if there is no occurrence of (12,01) in (σ1⋯σi,w1⋯wi). Then in the case where 1 is colored by 0 and is in position i+1, we have (n-i)!(ni)Ai=n!Ai/i! possibilities where the binomial coefficient is responsible for choosing the elements to the left of 1 and placing the remaining elements to the right of 1. To summarize, we obtain
(19)An+1=(n+1)An+n!∑i=0n‍Aii!.
Multiplying both parts of the equation above by  tn/n! and summing over all  n≥0, we have
(20)∑n≥0‍An+1tnn!=∑n≥0‍Antnn!+∑n≥1‍nAntnn!+∑n≥0‍tn∑i=0n‍Aii!
so that
(21)A′(t)=A(t)+tA′(t)+A(t)1-t.
It follows that
(22)ddtln(A(t))=A′(t)A(t)=11-t+1(1-t)2.
Integrating and using the fact that A(0)=1, we see that
(23)ln(A(t))=-ln(1-t)+11-t-1=-ln(1-t)+t1-t
which implies that
(24)A(t)=et/(1-t)1-t.This type of argument can be generalized. That is, we have the following theorem.Theorem 7.
Let1≤r≤s≤k-1 and A→r,s,k=({0,…,r-1},{s,…,k-1}), where k≥2. Let A(n,r,s,k)=Av(12,01,Ar,s,k) denote the number of (σ,w)∈Ck≀Sn which avoid (12,01,A→r,s,k),  and
(25)Ar,s,k(t)=∑n≥0‍A(n,r,s,k)tnn!.
Then if  k-r≠s,
(26)Ar,s,k(t)=11-(k-r)t(1-st1-(k-r)t)r/(k-r-s).
If  k-r=s, then
(27)Ar,k-r,k(t)=ert/(1-(k-r)t)1-(k-r)t.Proof.
Note that if(σ,w)∈Ck≀Sn+1 contains the element 1 colored with a color from {r,…,k-1}, then there are no restrictions for placing this element, thereby giving (n+1)A(n,r,s,k) possibilities. On the other hand, if (σ,w) contains the element 1 colored by the color a in position i+1 where a∈{0,…,r-1}, then if (σ,w) is to avoid (12,01,A→), it must be the case that every element to the right of 1 must be colored with a color from {0,…,s-1} and these elements can be arranged in any (n-i)! ways. Moreover, it immediately follows that no instance of a occurrence of (12,01,A→r,s,k) exists where the first element is to the left of 1 and the second is to the right of 1. Then it follows that (σ,w) avoids (12,01,A→r,s,k)  if and only if there is no occurrence of (12,01,A→r,s,k) in (σ1⋯σi,w1⋯wi). Thus in the case where 1 is colored by a color from {0,…,r-1} and is in position i+1, we have sn-i(n-i)!(ni)A(i,r,s,k)=n!jn-iA(i,r,s,k)/i! possibilities where the binomial coefficient is responsible for choosing the elements to the left of 1 and placing the remaining elements to the right of 1. Hence
(28)A(n+1,r,s,k)=(k-r)(n+1)A(n,r,s,k)+rn!∑i=0n‍A(i,r,s,k)i!sn-i.
Multiplying both parts of the equation above by  tn/n!  and summing over all n≥0, we have
(29)∑n≥0‍A(n+1,r,s,k)tnn!=(k-r)∑n≥0‍A(n,r,s,k)tnn!+(k-r)∑n≥1‍nA(n,r,s,k)tnn!+r∑m≥0‍tn∑i=0n‍A(i,r,s,k)i!sn-i,
so that for all  k≥2,
(30)Ar,s,k′(t)=(k-r)Ar,s,k(t)+(k-r)tAr,s,k′(t)+rAr,s,k(t)1-st.
It follows that
(31)ddtln(Ar,s,k(t))=Ar,s,k′(t)Ar,s,k(t)=k-r1-(k-r)t+r(1-(k-r)t)(1-st).
Now suppose thatk-r≠s. Then integrating (31) and using the fact that  A(0,r,s,k)=1 and the fact that  (d/dt)(ln(1-xt)-ln(1-yt))=(y-x)/(1-xt)(1-yt), we see that
(32)ln(Ar,s,k(t))=-ln(1-(k-r)t)+r(k-r-s)×(ln(1-st)-ln(1-(k-r)t)),
which implies that
(33)Ar,s,k(t)=11-(k-r)t(1-st1-(k-r)t)r/(k-r-s)
which proves (26).
Next suppose thatk-r=s. Then (31) becomes
(34)ddtln(Ar,k-r,k(t))=Ar,k-r,k′(t)Ar,k-r,k(t)=j1-(k-r)t+r(1-(k-r)t)2.
Integrating (34) and using the fact that A(0,r,k-r,k)=1, we see that
(35)ln(Ar,k-r,k(t))=-ln(1-(k-r)t)+rk-r(11-(k-r)t-1)=-ln(1-(k-r)t)+rt1-(k-r)t.
Thus
(36)Ar,k-r,k(t)=ert/(1-(k-r)t)1-(k-r)t
which proves (27).Next consider the special case where2r=k and r=s so A→r,s,k=({0,…,r-1},{r,…,2r-2}).  Then clearly,
(37)Ar,r,2r(t)=ert/(1-rt)1-rt,A1,1,2(t)=et/(1-t)1-t.
It follows from the form of these generating functions that A(n,r,r,2r)=rnA(n,1,1,2). Moreover, in the case where k=2, it is easy to see that our definitions imply that the number of (σ,w)∈C2≀Sn which avoid ((12,01),({0},{1})) is the same as the number of (σ,w)∈C2≀Sn which avoid (12,01). Then A(n,r,r,2r)=rnAn where An is the number of (σ,w)∈C2≀Sn avoiding (12,01). This is also easy to see combinatorially. Namely, if (σ,w)∈C2r≀Sn which avoids ((12,01),({0,…r-1},{r,…,2r-1})), then if w′ is the result of replacing each occurrence of 0,…,r-1 in w by 0 and each occurrence of r,…,2r-1 in w by 1, then (σ,w′) will be an element of C2≀Sn which avoids (12,01). Vice versa, if (σ,w′)∈C2≀Sn avoids (12,01) and w arises from w′ by replacing each 0 by some element from {0,…,r-1} and each 1 by some element from {r,…,2j-1}, then (σ,w) will avoid ((12,01),({0,…,r-1},{r-1,…,2r-1})). In fact, if we are in the case where  r=s so that A→r,s,k=({0,…,r-1},{r-1,…,k}), then by the same argument, we can get an arbitrary (σ,w)∈Ck≀Sn which avoids ((12,01),A→r,s,k) by starting out with an (σ,w′)∈C2≀Sn which avoids (12,01) and replacing each 0 by some element from {0,…,r-1} and each 1 by some element from  {r-1,…,k-1}. Considering the form of the generating function for  Ar,r,k(t) when  r≠k,
(38)Ar,r,k(t)=11-(k-r)t(1-rt1-(k-r)t)r/(k-2r),
this suggests the following theorem which can easily be proved by the same method as we used to prove Theorem 7.Theorem 8.
Given(σ,w)∈C2≀Sn, let pos(σ,w) equal the number of  0's in w and neg(σ,w) equal the number of 1’s in w.  Let 𝔸n(12,01) denote the set of  (σ,w)∈C2≀Sn which avoids (12,01). Then
(39)A(t,y,z)=∑n≥0‍tnn!∑(σ,w)∈𝔸n(12,01)‍ypos(σ,w)zneg(σ,w)=11-zt(1-yt1-zt)y/(z-y).


## 3. Avoidance for Sets of Patterns

In this section, we shall prove a variety of results for the number of elements ofCk≀Sn that avoid certain sets of patterns of length 2.IfΥ⊆Sj is a set of permutations of Sj, we let
(40)ϕΥ(t)=∑n≥0‍AvnΥtnn!,
where AvnΥ is the number of permutations σ∈Sn such that σ avoids Υ. If Υ⊆Ck≀Sj and A→=(A1,A2,…,Aj) where Ai⊆[k] for i=1,…,j, then we let Avn,k(Υ,A→) denote the number of (σ,w)∈Ck≀Sn which avoid (Υ,A→). We then let
(41)θk(Υ,A→)(t)=∑n≥0‍Avn,k(Υ,A→)tnn!.
In the special case where for all (σ,u)∈Υ, red(u)=u and Ai=[k] for i=1,…,j, we shall write Avn,kΥ instead of Avn,k(Υ,A→). That is, Avn,kΥ is the number of  (σ,w)∈Ck≀Sn which avoid Υ. Then we let
(42)θkΥ(t)=∑n≥0‍Avn,kΥtnn!.We start with a few simple results on sets of patternsΥ where the avoidance of Υ forces certain natural conditions on the possible sets of signs for elements of  Ck≀Sn.Lemma 9.
(1) IfΥ1={(12,00),(21,00)},  then  Avn,kΥ1=(kn)n!2  for all  n≥1 and k≥1.
(2) IfΥ2={(12,10),(21,10)},  then Avn,kΥ2=(n+k-1n)n!  for all n≥1 and k≥1.
(3) IfΥ3={(12,00),(12,10), (21,00), (21,10)},  then Avn,kΥ3=(kn)n!  for all n≥1 and k≥1.
(4) IfΥ4={(12,01),(12,10), (21,01), (21,10)}, then Avn,kΥ3=kn! for all n≥1 and k≥1.Proof.
For (1), it is easy to see that(σ,w)∈Ck≀Sn avoids Υ1 if and only if all the signs are pairwise distinct. Therefore, there are (kn) ways to pick the n signs, and then you have n! ways to arrange those n signs and n! ways to pick σ.
For (2), it is easy to see that(σ,w)∈Ck≀Sn avoids Υ2  if and only if 0≤w1≤⋯≤wn≤k-1. Therefore, there are (n+k-1n) ways to pick the n signs in this case and there are n! ways to pick σ.
For (3), it is easy to see that(σ,w)∈Ck≀Sn  avoids Υ2  if and only if  0≤w1<⋯<wn≤k-1. Therefore, there are (kn) ways to pick the n signs in this case and there are n! ways to pick σ.
For (4), it is easy to see that(σ,w)∈Ck≀Sn  avoids Υ2  if and only if  0≤w1=⋯=wn≤k-1. Therefore, there are k ways to pick the n signs in this case and there are n! ways to pick σ.ForΥ⊂S-J, we let
(43)Υ0={(σ,0j):σ∈Υ}.
Then we have the following.Theorem 10.
LetΥ⊆Sj  be any set of permutations of Sj. Then if  Γ=Υ0∪{(12,10),(21,10)},
(44)θkΓ(t)=(ϕΥ(t))k,
for all k≥1.Proof.
It is easy to see that if(σ,u)∈Ck≀Sn and (σ,u) avoids  {(12,10),(21,10)}, then it must be the case that 0≤u1≤u2≤⋯≤un≤k-1. So suppose that w=0a11a2⋯(k-1)ak where a1+⋯+ak=n. Then clearly the number of σ∈Sn such that (σ,w) avoids Υ0 is
(45)(na1,…,ak)Ava1Υ⋯AvakΥ.
That is, the binomial coefficient allows us to choose the elements Ci of {1,…,n} that correspond to the constant segment  iai+1 in w. Then we only have to arrange the elements of Ci so that it avoids Υ which can be done in Avai+1Υ ways. Thus it follows that
(46)Avn,kΓ=∑a1+⋯+ak=nai≥0‍(na1,…,ak)Ava1Υ⋯AvakΥ,
or, equivalently, that
(47)Avn,kΓn!=∑a1+⋯+ak=nai≥0‍∏i=1k‍AvaiΥai!,
which implies (44).We immediately have the following corollary.Corollary 11.
For anyk≥1, the number of elements of Ck≀Sn which avoid Γ1={(12,00),(12,10),(21,10)}  or  Γ2={(21,00),(12,10),(21,10)} is kn.Proof.
LetΥ1={12} and Υ2={21}. Then clearly, AvnΥi=1 for i=1,2 so that ϕnΥi(t)=et for i=1,2. But then by Theorem 10,  θn,kΓi(t)=(et)k=ekt so that Avn,kΓi=kn for i=1,2.We can derive theorems analogous to Theorem10 for the other sign conditions in Lemma 9. That is, suppose that Υ is any set of patterns from Sj. Then we let
(48)Υi={(τ,01⋯(j-1)):τ∈Υ},Υd={(τ,u):τ∈Υ,u∈Dj},
where Dj is the set of all permutations of  {0,1,…,j-1}. Then we have the following.Theorem 12.
For anyΥ⊂Sj, let
(49)Γ1=Υ0∪{(12,01),(12,10),(21,01),(21,10)},Γ2=Υi∪{(12,10),(12,00),(21,10),(21,00)},Γ3=Υd∪{(12,00),(21,00)}.
Then, for all k≥1,  (1)
Avn,kΓ1=kAvnΥ for all n≥1,(2)
Avn,kΓ2=(kn)AvnΥ for all n≥1,(3)
Avn,kΓ3=(kn)n!AvnΥ for all n≥1.Proof.
For (1), note that for(σ,w)∈Ck≀Sn to avoid {(12,01),(12,10),(21,01),(21,10)}, we must have w=in for some i∈{0,…,k-1}. Then (σ,in)∈Ck≀Sn avoids Υ0 if and only if σ avoids Υ. Thus Avn,kΓ1=kAvnΥ.
For (2), note that for(σ,w)∈Ck≀Sn to avoid {(12,10),(12,00),(21,10),(21,00)}, we must have  w=w1⋯wn  where w1<⋯<wn. Then for any of the (kn) strictly increasing words w∈{0,…,k-1}, (σ,w)∈Ck≀Sn avoids Υi if and only if σ avoids Υ. Thus Avn,kΓ2=(kn)AvnΥ.
For (3), note that, for(σ,w)∈Ck≀Sn to avoid {(12,00),(21,00)}, we must have w=w1⋯wn where the letters of w are pairwise distinct. Then for any of the (kn)n! words w∈{0,…,k-1} which have pairwise distinct letters, (σ,w)∈Ck≀Sn avoids Υd if and only if σ avoids Υ. Thus  Avn,kΓ3=(kn)n!AvnΥ.Next we will prove two more results aboutAvn,kΥ for other sets of patterns Υ that contain {(12,10),(21,10)}.Theorem 13.
Let(50)Υ1={(12,01),(12,10),(21,10)},Υ2={(12,01),(12,10),(21,10),(21,00)}.
Then  (1)
Avn,kΥ1=∑a1+⋯+ak=nai≥0‍a1!⋯ak! for all n≥1 and k≥1,(2)
Avn,kΥ1=(n+k-1k-1) for all n≥1 and k≥1.Proof.
For (1), note that as in the proof of Theorem10, if  (σ,u)∈Ck≀Sn and (σ,u) avoids {(12,10),(21,10)}, then it must be the case that  0≤u1≤u2≤⋯≤un≤k-1.
Now suppose thatw=0a11a2⋯(k-1)ak where  a1+⋯+ak=n. Assume that (σ,w) also avoids (12,01) and Ci is the set of elements of σ that correspond to the signs (i-1)ai in w. Then it follows that all the elements of C1 must be larger than all the elements of C2, all the elements of C2 must be larger than all the elements of C3, and so forth. Thus C1 consists of the a1 largest elements of {1,…,n},C2 consists of next a2 largest elements of {1,…,n}, and so forth. Then we can arrange the elements of Ci in any order in the positions corresponding to (i-1)ai in w to produce a (σ,w) which avoids Υ. Hence there are a1!⋯ak! elements of the form (σ,w) which avoid Υ in Ck≀Sn. Therefore (1) immediately follows.
For (2), observe that if in addition such(σ,w) also avoids (21,00), then we must place the elements of Ci in increasing order. Hence Avn,kΥ2 is the number of solutions of a1+⋯+ak=n with ai≥0 which is well known to be  (n+k-1k-1).Theorem 14.
LetΥ={(12,01),(12,10),(21,00)}. Then for n≥1,
(51)Avn,1Υ=1,Avn,2Υ=2n,Avn,kΥ=k+∑j=2k-1‍(k)↓j(nj)fork≥3,
where (k)↓0=1 and (k)↓n=k(k-1)⋯(k-n+1) for n≥1.Proof.
We shall classify the elements(σ,w)∈Ck≀Sn which avoid Υ by the number of elements s which follow n in σ. Now if s=0 so that σ ends in n, the fact that (σ,w) avoids both (12,01) and (12,10) means that all the signs must be the same. That is, w must be of the form in for some i∈[k]. But since (σ,w) must also avoid (21,00), σ=12…n must be the identity. Thus there are k choices for such (σ,w).
Now suppose there ares elements following n in σ. Then again the fact that (σ,w) avoids both (12,01) and (12,10) means that all the signs in w corresponding to σ1⋯σn-s (where σn-s=n) must be the same, say that sign is i. The fact that (σ,w) avoids (21,00) means that (i) σ1⋯σn-s must be in increasing order and (ii) all the signs corresponding to σn-s+1⋯σn must be different from i. But then it follows from the fact that (σ,w) avoids both (12,01) and (12,10) that all the elements in  σ1⋯σn-s must be greater than all the elements in σn-s+1⋯σn. Hence there are  kAvs,k-1Υ such elements if  k≥2 and there are no such elements if k=1. Thus from (ii) it follows that  Avn,1Υ=1 since (12⋯n,0n) is the only element of  Ck≀Sn which avoids Υ. For  k≥2, we have
(52)Avn,kΥ=k+∑s=1n-1‍kAvs,k-1Υ.
In the casek=2, (52) becomes
(53)Avn,2Υ=2+∑s=1n-1‍2=2n,
and in the case  k=3, (52) becomes
(54)Avn,3Υ=3+∑s=1n-1‍3(2s)=3+(3·2)(n2).
In general, assuming that
(55)Avn,kΥ=k+∑j=2k-1‍(k)↓j(nj),
it follows that
(56)Avn,k+1Υ=k+1+∑s=1n-1‍(k+1)Avs,kΥ=k+1+∑s=1n-1‍(k+1)(k+∑j=2k-1‍(k)↓j(sj))=k+1+(∑s=1n-1‍(k+1)k)+∑j=2k-1‍(k+1)(k)↓j∑s=1n-1‍(sj)=k+1+(k+1)↓2(n2)+∑j=3k‍(k+1)↓j(nj).We next consider simultaneous avoidance of the patterns(12,10) and (12,01).Theorem 15.
LetΥ={(12,10),(12,01)},  AkΥ(t)=∑n≥0‍Avn,kΥtn  and  C(t)=∑n≥1‍n!tn. Then
(57)AkΥ(t)=1+C(t)1-(k-1)C(t).Proof.
Fixk and suppose that (σ,w) is an element of Ck≀Sn which avoids both (12,10) and (12,01). Now if w=in is constant, then clearly σ can be arbitrary so that there are n! such elements.Next assume thatw is not constant so there is an s≥2 such that w=i1a1i2a2⋯isas where ar≥1 for r=1,…,s and ir≠ir+1 for r=1,…,s-1. We claim that σ1⋯σa1 must be the a1 largest elements of {1,…,n}. If not, then let n-r be the largest element which is not in σ1⋯σa1. Thus r<a1-1 and there must be at least one σt with t≤s such that σt<n-r. Now it cannot be σa1+1=n-r since otherwise (σtσa1+1,i1i2) would be an occurrence of either (12,10) or (12,01). Hence it must be the case that σa1+1<n-r and σp=n-r for some p>a1+1. But then no matter what color we choose for wp, either (σtσp,i1wp) or (σa1+1σp,i2wp) would be an occurrence of either (12,10) or (12,01). We can continue this reasoning to show that for any 1≤p<q≤s, the elements of σ corresponding to the block ipap in w must be strictly larger than the elements of σ corresponding to the block iqaq in w. This given, it follows that we can arrange the elements of σ corresponding to a block  ipap in w in any way that we want and we will always produce a pair (σ,w) that avoids both (12,10) and (12,01). Thus for such a w, we have k(k-1)s-1 ways to choose the colors i1,…,is and a1!a2!⋯ak! ways to choose the permutation σ. It follows that
(58)Avn,kΥ=kn!+∑s=2n-1‍×∑a1+⋯+as=nai>0‍k(k-1)s-1a1!a2!⋯as!,
which is equivalent to (57).Next we want to consider the problem of avoiding(Υ,B→) where Υ={(12,00),(12,01)} and B→=([k],{k-1}). If σ=σ1⋯σn∈Sn, then we say that σj is a left-to-right minimum of σ if σi>σj for all i<j and we let lrmin(σ) denote the number of left-to-right minima of σ. Let 𝔹n,k denote the set of all (σ,w)∈Ck≀Sn which avoid (Υ,B→). Then we let
(59)Bk(x,t)=∑n≥0‍tnn!∑(σ,w)∈𝔹n,k‍xlrmin(σ).Then we have the following theorem.Theorem 16.
ForΥ={(12,00),(12,01)}  and B→=([k],{k-1}), one has
(60)Bk(x,t)=(11-(k-1)t)kx/(k-1).Proof.
LetBn,k(x)=∑(σ,w)∈𝔹n,k‍xlrmin(σ). If (σ,w) contains the element 1 colored by the color a in position i+1 where a∈{0,…,k-1}, then if (σ,w) is to avoid  (Υ,B→), it must be the case that every element to the right of 1 must be colored with a color from {0,…,k-2} and these elements can be arranged in any of (n-i)! ways. Moreover, it immediately follows that no instance of an occurrence of (Υ,B→) exists where the first element is to the left of 1 and the second is to the right of 1. Thus it follows that (σ,w) avoids (Υ,B→) if and only if there is no occurrence of (Υ,B→) in (σ1⋯σi,w1⋯wi). Thus it follows that
(61)∑(σ,w)∈𝔹n,k,σi+1=1‍xlrmin(σ)=x(k-1)n-i×(n-i)!(ni)Bi,k(x)=n!x(k-1)n-iBi,k(x)i!.
Here the binomial coefficient is responsible for choosing the elements to the left of 1 and placing the remaining elements to the right of 1 and the factor of x accounts for the fact that 1 is always a left-to-right minimum in σ and none of the elements following 1 can be a left-to-right minimum of σ. This shows that
(62)Bn+1,k(x)=kxn!∑i=0n‍Bi,k(x)i!(k-1)n-i.
Multiplying both parts of the equation above by tn/n! and summing over all n≥1, we have
(63)∑n≥0‍Bn+1,k(x)tnn!=kx∑m≥0‍tn∑i=0n‍Bi,k(x)i!(k-1)n-i,
so that, for all k≥2,
(64)∂∂tBk(t,x)=kxBk(t,x)1-(k-1)t.
It follows that
(65)∂∂tln(Bk(x,t))=kx1-(k-1)t.
Integrating and using the fact that Bk(x,0)=1, we see that
(66)(Bk(x,t))=-kxk-1ln(1-(k-1)t),
and hence,
(67)Bk(x,t)=(11-(k-1)t)kx/(k-1).Using the fact that(68)1(1-z)a=∑n≥0‍a(a+1)⋯(a+n-1)znn!,
we see that
(69)Bn,k(x)=(kxk-1)(kxk-1+1)⋯(kxk-1+n-1)(k-1)n=(kx)(kx+(k-1))⋯(kx+(n-1)(k-1)).
In particular,
(70)Avn,k({(12,00),(12,01)},([k],{k-1}))=k(2k-1)(3k-2)⋯(nk-(n-1)).
We note that, by our symmetry maps where we apply the identity map to σ and the composition of complement and reverse to w and A→, one can show that
(71)Avn,k({(12,00),(12,01)},([k],{k-1}))=Avn,k({(12,k-1k-1),(12,k-2k-1)},({0},[k])).
It is easy to see that our definitions imply that
(72)Avn,k({(12,00),(12,01)},({0},[k]))=Avn,k({(12,k-1k-1),(12,k-2k-1)},({0},[k])),
so that
(73)Avn,k({(12,00),(12,01)},({0},[k]))=k(2k-1)(3k-2)⋯(nk-(n-1)).Next we consider the case where1<j<k,  C→j=({0,…,j-1},{j-1,…,k-1}), and  Υ={(12,00),(12,01)}.Theorem 17.
LetC→j=({0,…,j-1},{j-1,…,k-1}) where k≥3 and 1<j<k, and Υ={(12,00),(12,01)}. Then if k-j≠j-1,
(74)θk(Υ,C→j)(t)=11-(k-j)t(1-(j-1)t1-(k-j)t)j/(k-2j+1).
If k-j=j-1,  then k=2j-1 and
(75)θ2j-1(Υ,C→j)(t)=ejt/(1-(j-1)t)1-(j-1)t.Proof.
LetC(n,k,j)=Avn,k(Υ,C→j)  so that
(76)Ck,j(t)=∑n≥0‍C(n,k,j)tnn!=θk(Υ,C→j)(t).
Now suppose that(σ,w)∈Ck≀Sn contains the element 1 colored by a color from {j,…,k-1}. Then there are no restrictions for placing this element, thus giving (n+1) possibilities. On the other hand, if (σ,w) contains the element 1 colored by the color a in position i+1 where a∈{0,…,j-1}, then if (σ,w) is to avoid (Υ,C→j), it must be the case that every element to the right of 1 must be colored with a color from {0,…,j-2} and these elements can be arranged in any of (n-i)! ways. Moreover, it immediately follows that no instance of an occurrence of (Υ,C→j) exists where the first element is to the left of 1 and the second is to the right of 1. Then it follows that (σ,w) avoids (Υ,C→j) if and only if there is no occurrence of (Υ,C→j) in (σ1⋯σi,w1⋯wi). So in the case where 1 is colored by a color from {0,…,j-1} and is in position i+1, we have (j-1)n-i(n-i)!(ni)C(i,k,j)=n!(j-1)n-iC(i,k,j)/i! possibilities where the binomial coefficient is responsible for choosing the elements to the left of 1 and placing the remaining elements to the right of 1. Thus
(77)C(n+1,k,j)=(k-j)(n+1)C(n,k,j)+jn!∑i=0n‍C(i,k,j)i!(j-1)n-i.
Multiplying both parts of the equation above by tn/n! and summing over all n≥1, we have
(78)∑n≥0‍C(n+1,k,j)tnn!=(k-j)∑n≥0‍C(n,k,j)tnn!+(k-j)∑n≥1‍nC(n,k,j)tnn!+j∑m≥0‍tn∑i=0n‍C(i,k,j)i!(j-1)n-i,
so that, for all k≥3 and 1<j<k,
(79)Ck,j′(t)=(k-j)Ck,j(t)+(k-j)tCk,j′(t)+jCk,j(t)1-(j-1)t.
It follows that
(80)ddtln(Ck,j(t))=Ck,j′(t)Ck,j(t)=11-(k-j)t+j(1-(k-j)t)(1-(j-1)t).
Now suppose thatk-j≠j-1. Then integrating (80) and using the fact that C(0,k,j)=1 and that  (d/dt)(ln(1-xt)-ln(1-yt))=(y-x)/(1-xt)(1-yt), we see that
(81)ln(Ck,j(t))=-ln(1-(k-j)t)+j(k-j)-(j-1)×(ln(1-jt)-ln(1-(k-j)t))
which implies that
(82)Ck,j(t)=11-(k-j)t(1-(j-1)t1-(k-j)t)j/(k-2j+1)
and proves (74).
Now ifk-j=j-1. Then k=2j-1 and (80) becomes
(83)ddtln(C2j-1,j(t))=C2j-1,j′(t)C2j-1,j(t)=j-11-(j-1)t+j(1-(j-1)t)2.
Integrating (83) and using the fact that C(0,2j-1,j)=1, we see that
(84)ln(C2j-1,j(t))=-ln(1-(j-1)t)+jj-1(11-(j-1)t-1)=-ln(1-(j-1)t)+jt1-(j-1)t.
Thus
(85)C2j-1,j(t)=ejt/(1-(j-1)t)1-(j-1)t,
which proves (75).Finally, we end this section by considering the elements ofCk≀Sn which avoid both (12,00) and (12,01). In this case, we only have a result for the case when  k=2.Theorem 18.
The number of permutations inC2≀Sn simultaneously avoiding (12,00) and (12,01) is given by the (n+1)-th Catalan number  Cn+1=(1/(n+2))(2n+2n+1).Proof.
We prove the statement by establishing a bijection between the objects in question of lengthn and the Dyck paths of semilength (n+1) known to be counted by the Catalan numbers (a Dyck path of semi-length n is a lattice path from (0,0) to (2n,0) with steps (1,1) and (1,-1) that never goes below the x-axis; Figure 4).
Suppose(σ,w)∈C2≀Sn. Note that σ must avoid the pattern 123, as in an occurrence of such a pattern in σ, there are two letters of the same color leading to an occurrence of (12,00). Thus the structure of σ, as it is well known, is two decreasing sequences shuffled.
Subdivideσ into the so-called reverse irreducible components. A reverse irreducible component is a factor F of σ of minimal length such that everything to the left (resp., right) of F is greater (resp., smaller) than any element of F. For example, the subdivision of σ=6574312 is σ=657-4-3-12. The blocks of size 1 are called singletons. In the example above, 4 and 3 are singletons. It is easy to see that any singleton element in σ can have any color (either 0 or 1). We will now show that the color of each element of a nonsingleton block is uniquely determined.
Indeed, irreducibility of a single block means that two decreasing sequences in the structure of(123)-avoiding permutations are the block's sequence of left-to-right minima and the block's sequence of right-to-left maxima which do not overlap. Thus for any left-to-right minimal element x (except possibly the last element), one has an element y greater than x to the right of it inside the same block and vice versa, from which we conclude that x must receive color 1, whereas y must receive color 0 (otherwise a prohibited pattern will occur).
We are ready to describe our bijection. For a given(σ,w)∈C2≀Sn, consider a matrix representation of σ, that is, an integer grid with the opposite corners in (0,0) and (n,n) and with a dot in position (i-1/2,σi-(1/2)) for  i=1,2,…,n. We will give a description of a path P (corresponding to (σ,w)) from (0,n+1) to (n+1,0) involving only steps (0,-1) and (1,0) that never goes above the line y=-x+n+1. Clearly, P can be transformed to a Dyck path of length (n+1) by taking a mirror image with respect to the line y=-x+n+1, rotating 45 degrees counterclockwise and making a parallel shift.
To buildP, set i:=0 and j:=n+1, and do the following steps, letting P begin at (i,j). Clearly, each reverse irreducible block of σ defines a square on the grid which is a matrix representation of the block. We call the reverse irreducible block of σ with the left-top corner at (i,j) the current block.
Step1. If the current block is not a singleton, go to Step 2. If the color of the element with x-coordinate equal to i+1/2 is 0 (resp., 1) travel around the current block counterclockwise (resp., clockwise) to get to the point (i+1,j-1). Note that P touches the line y=-x+n+1 if the color is 1. Set i:=i+1 and j:=j-1, and proceed with Step 3.
Step2. In Step 2 we follow a standard bijection between (123)-avoiding permutations and Dyck paths that can be described as follows. Let (k,ℓ) be the point of the current block opposite to (i,j). Start going down from (i,j) until the y-coordinate of the current node gets 1/2 less than the y-coordinate of the dot with x-coordinate equal i+1/2. Start moving horizontally to the right and go as long as possible making sure that none of the dots are below the part of P constructed so far and i≤k and j≤ℓ. Suppose (i1,j1) is the last point the procedure above can be done (i.e., we were traveling on the line y=j1 and either i1=k and j1=ℓ or there is a dot with x-coordinate i1+(1/2) having y-coordinate less than j1). If i∶=k and j∶=ℓ, proceed with Step 3; otherwise set i∶=i1 and  j:=j1 and go to Step 2. Note that in Step 2   P never touches the line y=-x+n+1.
Step3. If j=0, make as many as it takes horizontal steps to get to the point (n+1,0) and terminate; otherwise go to Step 1.
Returning to our example,σ=(6574312,1101010), we have given the matrix diagram in Figure 1. We have outlined the reverse irreducible blocks in Figure 2. We start our path at (0,8). We travel down until we reach (0,6), when we are 1/2 less than the y-coordinate of our first point (1/2,6(1/2)). We then continue traveling right and down as described in Step 2. We travel clockwise around our singleton colored 1 and counterclockwise around our singleton colored 0. Then we continue to the final reverse irreducible block and finish our path, given in Figure 3.Figure 1
Matrix representation ofσ=(6574312,1101010).Figure 2
Matrix representation ofσ=(6574312,1101010) with reverse irreducible blocks outlined.Figure 3
The Dyck path corresponding toσ=(6574312,1101010) added to Figure 2.Figure 4
The Dyck path corresponding toσ=(6574312,1101010). Note that the path only touches the line y=-x+n+1 after a singleton colored 1.


## 4. Pattern Matching Results for Pairs of Length≥2

Goulden and Jackson [8] proved the following theorem.Theorem 19 (see [8]).
Ifτ=j⋯21,  where j≥2, then
(86)∑n=0∞‍tnn!|{σ∈Sn:τ-mch(σ)=0}|=(∑n=0∞‍tjn(jn)!-∑n=0∞‍tjn+1(jn+1)!)-1.Later Mendes and Remmel [9] refined this result by proving the following.Theorem 20.
Whenτ=j⋯21,
(87)∑n=0∞‍tnn!∑σ∈Snτ-mch(σ)=0‍xdes(σ)=11+∑n=1∞tn/n!∑i≥0(-1)iℛn-1,i,j-1xi,
where  ℛn,i,j is the number of rearrangements of  i  zeroes and  n-i ones such that j zeroes never appear consecutively.The reason that Theorem20 is a refinement of Theorem 19 is that Mendes and Remmel [9] proved that
(88)∑i≥0‍(-1)iℛn,i,j-1={(-1)nifjdividesn,(-1)n+1ifjdividesn+1,0otherwise,
so that setting  x=1 in (87) yields (86).The main goal of this section is to generalize Theorem20. That is, let τ(j)=j(j-1)⋯1 where j≥3. Then we shall consider three sets of patterns for Ck≀Sn:(a)
(τ(j),0j),(b)
(τ(j),j-1j-2⋯10),(c)
Υ which equals the set of all  (τ(j),w) such that  w∈{0,…,k-1}j, w is weakly decreasing, and red(w)=w. In [1], Kitaev et al. defined three different types of descents. That is, for elements (σ,w)∈Ck≀Sn, they defined
(89)Des((σ,w))={i:σi>σi+1,wi≥wi+1},des((σ,w))=|Des((σ,w))|,WDes((σ,w))={i:σi>σi+1,wi=wi+1},wdes((σ,w))=|WDes((σ,w))|,SDes((σ,w))={i:σi>σi+1,wi>wi+1},sdes((σ,w))=|SDes((σ,w))|.
We shall refer to Des((σ,w)) as the  descent set of (σ,w), WDes((σ,w)) as the  weak descent set of  (σ,w), and  SDes((σ,w)) as the  strict descent set of (σ,w).Theorem 21.
Letτ(j)=j⋯21 where j≥3.  (1)
Ifu=0j, then
(90)∑n=0∞‍tnn!∑(σ,w)∈Ck≀Sn(τ,u)-mch((σ,w))=0‍xwdes((σ,w))=(1+∑n=1∞‍tnn!k∑i≥0‍(-1)iℛn-1,i,j-1xi)-1.(2)
Ifu=j-1j-2⋯21, then
(91)∑n=0∞‍tnn!∑(σ,w)∈Ck≀Sn(τ,u)-mch((σ,w))=0‍xsdes((σ,w))=(1+∑n=1∞‍tnn!(kn)∑i≥0‍(-1)iℛn-1,i,j-1xi)-1.
(3) IfΥ equals the set of all (τ(j),w) such that w∈{0,…,k-1}j, w is weakly decreasing, and  red(w)=w, then
(92)∑n=0∞‍tnn!∑(σ,w)∈Ck≀SnΥ-mch((σ,w))=0‍xdes((σ,w))=(1+∑n=1∞‍tnn!(k+n-1n)∑i≥0‍(-1)iℛn-1,i,j-1xi)-1.Proof.
Our proof is an adaptation of the proof that Mendes and Remmel [9] used to prove Theorem 20. The basic idea is to show that (90), (91), and (92) arise by applying appropriate ring homomorphisms, defined on the ring Λ of symmetric functions over infinitely many variables x1,x2,…, to a simple symmetric function identity.
Thenth elementary symmetric function, en, and the nth homogenous symmetric function, hn, are defined by the generating functions
(93)E(t)=∑n≥0‍entn=∏i‍(1+xit),H(t)=∑n≥0‍hntn=∏i‍11-xit.
Clearly,
(94)H(t)=1E(-t).
Letλ=(λ1,…,λℓ) be an integer partition; that is, λ is a finite sequence of weakly increasing positive integers. Let ℓ(λ)=ℓ denote the number of parts of λ. If the sum of these integers is n, we say that λ is a partition of n and write λ⊢n. For any partition λ=(λ1,…,λℓ), let eλ=eλ1⋯eλℓ. The well-known fundamental theorem of symmetric functions says that {eλ:isapartition} is a basis for Λ or that {e0,e1,…} is an algebraically independent set of generators for Λ. Similarly, if we define hλ=hλ1⋯hλℓ, then {hλ:isapartition} is also a basis for Λ.
Since the elementary symmetric functionseλ and the homogeneous symmetric functions hλ are both bases for Λ, it makes sense to talk about the coefficient of the homogeneous symmetric functions when written in terms of the elementary symmetric function basis. These coefficients have been shown to equal the sizes of certain sets of combinatorial objects up to a sign. A brick tabloid of shape (n) and type λ=(λ1,…,λk) is a filling of a row of n squares of cells with bricks of lengths λ1,…,λk such that bricks do not overlap. One brick tabloid of shape (12) and type (1,1,2,3,5)  is displayed In Figure 5.
Letℬλ,n denote the set of all λ-brick tabloids of shape (n) and let Bλ,n=|ℬλ,n|. Through simple recursions stemming from (94), Eğecioğlu and Remmel [10] proved that
(95)hn=∑λ⊢n‍(-1)n-ℓ(λ)Bλ,neλ.
We now consider three different ring homomorphisms which mapΛ to ℚ[x] where ℚ is the field of rational numbers. Since e0,e1,… is an algebraically independent set of generators for Λ, we can define a ring homomorphism by simply specifying its value on en for all n≥0. For n≥1, define
(96)Γ1(en)=(-1)nn!k∑i≥0‍(-1)n-iℛn-1,i,j-1xi,Γ2(en)=(-1)nn!(kn)∑i≥0‍(-1)n-iℛn-1,i,j-1xi,Γ3(en)=(-1)nn!(k+n-1n)∑i≥0‍(-1)n-iℛn-1,i,j-1xi.
Our first goal is to prove the following facts.(A)
Ifu=0j, then
(97)n!Γ1(hn)=∑(σ,w)∈Ck≀Sn(τ,u)-mch((σ,w))=0‍xwdes((σ,w)).(B)
Ifu=j-1j-2⋯10, then
(98)n!Γ2(hn)=∑(σ,w)∈Ck≀Sn(τ,u)-mch((σ,w))=0‍xsdes((σ,w)).(C)
IfΥ consists of the set of all (τ(j),w) such w∈{0,…,k-1}j, w is weakly decreasing, and  red(w)=w, then
(99)n!Γ3(hn)=∑(σ,w)∈Ck≀SnΥ-mch((σ,w))=0‍xdes((σ,w)).
Letf(1,n)=k, f(2,n)=(kn), and f(3,n)=(k+n-1n). Then for i∈{1,2,3},
(100)n!Γi(hn)=n!∑λ⊢n‍(-1)n-ℓ(λ)Bλ,nΓi(eλ)=n!∑λ⊢n‍(-1)n-ℓ(λ)Bλ,n∏m=1ℓ(λ)‍(-1)λmλm!×f(i,λm)(∑i≥0‍(-1)λm-iℛλm-1,i,j-1xi)=∑λ⊢n‍∑B=(b1,…,bℓ(λ))∈ℬλ,n‍(nb1,…,bℓ(λ))(-1)ℓ(λ)×∏m=1ℓ(λ)‍f(i,bm)(∑i≥0‍(-1)bm-iℛbm-1,i,j-1xi).
We wish to give a combinatorial interpretation of right-hand side of (100). First we select a partition λ⊢n and then we select a brick tabloid B=(b1,…,bℓ(λ))∈ℬλ,n. Next we interpret the multinomial coefficient (nb1,…,bℓ(λ)) as the number of ways to pick sets S1,…,Sℓ(λ) of sizes b1,…,bℓ(λ), respectively, which partition {1,…,n}. We then place these elements in Sm in the bottom of the cells of the brick bm in decreasing order reading from left to right. Next if i=1, then f(1,bm)=k which we interpret as the ways of picking an element i∈{0,…,k-1} and placing i at the top of each cell of bm. If i=2, then f(2,bm)=(kbm) which we interpret as the ways of picking a strictly decreasing sequence s=s1>⋯>sbm from {0,…,k-1} and placing sj on top of the jth cell of bm. If  i=3, then f(3,bm)=(k+bm-1bm) which we interpret as the ways of picking a weakly decreasing sequence s=s1≥⋯≥sbi from {0,…,k-1} and placing sj on top of the jth cell of bi. Finally, we interpret the term (∑i≥0‍(-1)bm-iℛbm-1,i,j-1xi) as follows. First, we pick a sequence t=t1⋯tbm-1 which consists of i   x's and bm-i-10's for some i such that there is no consecutive sequence of j-1x′s in t. Then if ts=x, we label the sth cell of bm with x, and if ts=0, we label the sth cell of bm with -1. Finally, we label the last cell of bm with -1. Thus for any given i, we will have bm-i cells labeled with -1 which accounts for the sign (-1)bi-1. The only term in (100) that we have not accounted for is the term (-1)ℓ(λ) which we use to change that last cell of each brick from -1 to 1. We shall call an object created in this way a filled labeled brick tabloid and we let ℱn,i denote the set of all filled labeled brick tabloids that arise in this way for interpreting n!Γi(hn). Thus a C∈ℱn,i consists of a brick tabloid T, a permutation σ∈Sn, a sequence w∈{0,…,k-1}n, and a labeling L of the cells of T with elements from {x,1,-1} such that the following conditions hold.  (a)
σ is strictly decreasing in each brick.(b)
(1)
Ifi=1, then w is constant in each brick.(2)
Ifi=2, then w is strictly decreasing in each brick.(3)
Ifi=3, then w is weakly decreasing in each brick.(c)
The final cell of each brick is labeled with 1.(d)
Each cell which is not a final cell of a brick is labeled withx or  -1 and there is no consecutive string of cells of length j-1 labeled x within a brick. We then define the weight w(C) of C to be the product of all the x labels in L and the sign sgn(C) of C to be the product of all the -1 labels in L.
For example, ifn=12, k=6, j=4, and T=(5,2,5), then Figure 6 pictures a filled labeled brick tabloid C∈ℱ12,1 at the top, a a filled labeled brick tabloid C∈ℱ12,2 in the middle, and a filled labeled brick tabloid C∈ℱ12,3 at the bottom. In each case, w(C)=x6 and sgn(C)=-1.
Next we define sign-reversing, weight-preserving involutionsIi on Fn,i. To define Ii(C), we scan the cells of C=(T,σ,w,L) from left to right looking for the leftmost cell t such that either (i)
t is labeled with -1,(ii)
t is at the end of a brick bj and the brick bj+1 immediately following bj has the property that σ is strictly decreasing in all the cells corresponding to bj and bj+1 and w is constant on all the cells corresponding to bj and bj+1 if i=1,w
is strictly decreasing on all the cells corresponding tobj and bj+1 if i=2,w
is weakly decreasing on all the cells corresponding tobj and bj+1 if i=3.
In case (i),Ii(C)=(T′,σ′,w′,L′) where T′ is the result of replacing the brick b in T containing t by two bricks b* and b** where b* contains the cell t plus all the cells in b to the left of t and b** contains all the cells of b to the right of t, σ=σ′, w=w′, and L′ is the labeling that results from L by changing the label of cell t from -1 to 1. In case (ii), Ii(C)=(T′,σ′,r′,L′) where T′ is the result of replacing the bricks bj and bj+1 in T by a single brick b,σ=σ′, w=w′, and L′ is the labeling that results from L by changing the label of cell t from 1 to -1. Note that since the last cell in each brick is labeled with a 1, when we combine the two bricks in case (ii), we cannot create a run of j-1 consecutive cells which are labeled x. If neither case (i) or case (ii) applies, then we let Ii(C)=C. For example, if we consider the C's in ℱ12,i pictured in Figure 6, then their corresponding images Ii(C) are pictured in Figure 7.
It is easy to see thatIi is a weight-preserving, sign-reversing involution, and hence Ii shows that
(101)n!Γi(hn)=∑C∈ℱn,i,Ii(C)=C‍sgn(C)w(C).
Thus we must examine the fixed pointsC=(T,σ,w,L) of Ii. First there can be no -1 labels in L so that sgn(C)=1. Moreover, if bj and bj+1 are two consecutive bricks in T and t is the last cell of bj, then  (1)
Ifi=1, it cannot be the case that σt>σt+1 and wt=wt+1 since otherwise we could combine bj and bj+1,(2)
ifi=2, it cannot be the case that σt>σt+1 and wt>wt+1 since otherwise we could combine bj and bj+1, and(3)
ifi=3, it cannot be the case that σt>σt+1 and wt≥wt+1 since otherwise we could combine bj and bj+1.Thus if s is the last cell of a brick, then s∉WDes(σ,w) if  i=1,  s∉SDes(σ,w) if i=2, and s∉Des(σ,w) if i=3. However, the label on a cell t of any brick bj must be x if t is not the last cell of the brick and must be 1 if t is the last cell of a brick. Moreover, if t is not the last cell of a brick, then σt>σt+1 and wt=wt+1 if i=1, wt>wt+1 if i=2, wt≥wt+1 if i=3. Thus if t is not the last cell of a brick, then t∈WDes(σ,w) if i=1, t∈SDes(σ,w) if i=2, and t∈Des(σ,w) if i=3. It follows that sgn(C)=1 and w(C)=wdes((σ,w)) if i=1, w(C)=sdes((σ,w)) if i=2, and w(C)=wdes((σ,w)) if i=3. Then
(102)n!Γ1(hn)=∑(σ,w)∈Ck≀Sn(τ,u)-mch((σ,w))=0‍xwdes((σ,w))ifi=1,n!Γ2(hn)=∑(σ,w)∈Ck≀Sn(τ,u)-mch((σ,w))=0‍xsdes((σ,w))ifi=2,n!Γ3(hn)=∑(σ,w)∈Ck≀Sn(τ,u)-mch((σ,w))=0‍xdes((σ,w))ifi=3.
Therefore (A), (B), and (C) hold.
We can now prove (90) by applying Γ1 to (94). That is, we have u=0j and τ=jj-1⋯21, and then
(103)∑n=0∞‍tnn!∑(σ,w)∈Ck≀Sn(τ,u)-mch(=)0‍xwdes((σ,w))=Γ1(∑n=0∞‍hntn)=1Γ1(∑n=0∞en(-t)n)=1(1+∑n=1∞(-t)nk(-1)n/n!∑i≥0(-1)n-iℛn-1,i,j-1xi)-1=1(1+∑n=1∞ktn/n!∑i≥0(-1)n-iℛn-1,i,j-1xi)-1.
Similarly, (91) can be proved by applying Γ2 to (94) and (92) can be proved by applying Γ3 to (94).Figure 5
A brick tabloid of shape(12) and type (1,1,2,3,5).Figure 6
Filled labeled brick tabloids inF12,i.Figure 7
I
i
(
C
) for the Cs in Figure 6.In fact, we can calculateRn,i,j in several cases. For instance, routine combinatorial techniques are able to show that Rn-1,i,2 is (n-ii) whenever  0≤i≤⌊n/2⌋. When j=3, we find that
(104)Rn-1,i,3=∑p=0⌊i/2⌋‍(n+1-ip,i-2p,n+12i+p).We can also find a generating function forRn,i,j by considering the following argument. Take a rearrangement that is counted by Rn,i,j. Now remove the final number of the rearrangement. Either(a)
we have removed a0,(b)
we have removed a1.In case (a), we can count the number of such rearrangements byRn-1,i-1,j, except that we have overcounted by those rearrangements counted by Rn-1,i-1,j which end in j-1 zeroes. We can correct this by considering removing the last j-1 zeroes of the over-counted rearrangements, leaving those of length n-j with i-j zeros ending in a 1, of which there are Rn-j-1,i-j,j. In case (b), we can count the number of such sequences by Rn-1,i,j. Thus we obtain the following relationship:
(105)Rn,i,j=Rn-1,i-1,j-Rn-j-1,i-j,j+Rn-1,i,j.Next, we multiply byqixn and sum over all n, from which we obtain a generating function with a finite sum of small R values in the numerator and a quotient of  1-xq-x+qixj+1.



---

*Source: 806583-2013-01-17.xml*