# Generalized Pattern-Matching Conditions forCk≀Sn

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

---

## Abstract

We derive several multivariable generating functions for a generalized pattern-matching condition on the wreath productCk≀Sn of the cyclic group Ck and the symmetric group Sn. In particular, we derive the generating functions for the number of matches that occur in elements of Ck≀Sn for any pattern of length 2 by applying appropriate homomorphisms from the ring of symmetric functions over an infinite number of variables to simple symmetric function identities. This allows us to derive several natural analogues of the distribution of rises relative to the product order on elements of Ck≀Sn. Our research leads to connections to many known objects/structures yet to be explained combinatorially.


---

## Body

## 1. Introduction

The goal of this paper is to study pattern-matching conditions on the wreath productCk≀Sn of the cyclic group Ck and the symmetric group Sn. Ck≀Sn is the group of knn! signed permutations where we allow k signs of the form 1=ω0,ω,ω2,…,ωk-1 for some 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,1,…,k-1} for i=1,2,…,n, then we simply write γ=(σ,w) where w=w1w2⋯wn∈{0,1,…,k-1}n.Given a sequenceσ=σ1⋯σn of distinct integers, let red(σ) be the permutation found by replacing the ith largest integer that appears in σ by i. For example, if σ=2754, then red(σ)=1432. Given a permutation τ in the symmetric group Sj, we say a permutation σ=σ1⋯σn∈Sn has a τ-match starting at positioni provided red(σi⋯σi+j-1)=τ. Let τ-mch(σ) be the number of τ-matches in the permutation σ. Similarly, we say that τoccurs in σ if there exist 1≤i1<⋯<ij≤n such that red (σi1⋯σij)=τ. We say that σ  avoidsτ if there are no occurrences of τ in σ.We can define similar notions for 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 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 w  avoidsu if there are no occurrences of u in w.There are a number of papers on pattern matching and pattern avoidance inCk≀Sn  [1–4]. For example, the following pattern matching condition was studied in [2–4].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 position  i (resp.,  exact  Υ-match in  (σ,w)  starting at position  i) if
(1)(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 [3] 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 [5] who proved the same result for the hyperoctahedral group C2≀Sn. Similarly, Mansour and West [4] determined the number of permutations in C2≀Sn that avoid all possible exact occurrences of 2 or 3 element sets of patterns of elements of 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)}, let Kn2 be the number of (σ,ϵ)∈C2≀Sn that avoid all exact occurrences of the patterns in the set {(12,01),(12,10),(21,01)}, and let Kn3 be 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 [4] proved that
(2)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 will consider the following matching conditions.Definition 2.
Let(τ,u)∈Ck≀Sj where red(u)=u, Υ be 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)
We say that(σ,w)∈Ck≀Snavoids  (τ,u) (resp., Υ) 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., Υ-matchin(σ,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), 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, we will consider a more general matching condition which generalizes both occurrences and matches and exact occurrences and exact matches inCk≀Sn.Definition 3.
Let(τ,u)∈Ck≀Sj, let Υ be a subset of Ck≀Sj, and let 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,2,…,j.(2)
One says that(σ,w)∈Ck≀Snavoids  (τ,u) (resp., Υ) if there are no occurrences of (τ,u) (resp., Υ) in (σ,w).(3)
We say that there is a(τ,u)-match in  (σ,w)  starting at position  i (resp.,  Υ-match in  (σ,w)  starting at position  i) 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,1,…,j-1.Thus, a(τ,u,A→)-occurrence or (τ,u,A→)-match where u=u1⋯uj and A→=(A1,…,Aj) is such that Ai={ui} for i=1,…,j is just an exact occurrence or exact match of (τ,u). Similarly, a (τ,u,A→)-occurrence or (τ,u,A→)-match where u=u1⋯uj, red(u)=u, and A→=(A1,…,Aj) is 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 of Υ-matches (resp., exact Υ-matches) in (σ,w). We let (τ,u,A→)-mch((σ,w)) be the number of (τ,u,A→)-matches in (σ,w) and let (Υ,A→)-mch((σ,w)) be the number of (Υ,A→)-matches in (σ,w).The main result of this paper is to derive a generating function for the distribution of(τ,u,A→)-matches where (τ,u) is any element of Ck≀S2. To state our main result, we first need some notation. We define the p,q-analogues of n, n!, (nk), and (na1,…,am) by
(3)[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 theq-analogues 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 of (σ,w)∈Ck≀Sn which are 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
(4)mp(Υ,A→),n(p,q;z0,…,zk-1)=∑(σ,w)∈ℳ𝒫(Υ,A→),n‍pcoinv(σ)qinv(σ)z(w).
We shall also be interested in the specializations
(5)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 will denote mp(Υ,A→),n(p,q;z0,…,zk-1) as mp(τ,u,A→),n(p,q;z0,…,zk-1). For example, if τ=12, u=01, and A→=([k],[k]), then (σ,w)∈Ck≀Sn is a maximum packing for (τ,u,A→) if and only if σ=12⋯n is the identity permutation and w=w1⋯wn is such that 0≤w1<⋯<wn≤k-1. Thus,
(6)mp(τ,u,A→),n(p,q;z0,…,zk-1)=p(n2)(∏i=0k-1‍(1+zit))|tn,
where for any power series f(t)=∑n≥0‍fntn, we write f(t)∣tn=fn for the coefficient of tn in f(t). Then it is easy to prove that
(7)mp(τ,u,A→),n(p,q;1,…,1)=p(n2)(kn),mp(τ,u,A→),n(p,q;1,r,…,rk-1)=p(n2)r(n2)[kn]r.
If τ=12, u=00, and A→=([k],[k]), then (σ,w)∈Ck≀Sn is a maximum packing for (τ,u,A→) if and only if σ=12⋯n is the identity permutation and w=in for some 0≤i≤k-1. Thus,
(8)mp(τ,u,A→),n(p,q;z0,…,zk-1)=p(n2)∑i=0k-1‍zin.
It then follows that
(9)mp(τ,u,A→),n(p,q;1,…,1)=kp(n2),mp(τ,u,A→),n(p,q;1,r,…,rk-1)=[k]rnp(n2).
Similarly if Υ={(12,00),(12,01)} and A→=([k],[k]), then (σ,w)∈Ck≀Sn is a maximum packing for (Υ,A→) if and only if σ=12⋯n is the identity permutation and w=w1⋯wn is such that 0≤w1≤⋯≤wn≤k-1. Thus,
(10)mp(Υ,A→),n(p,q;z0,…,zk-1)=p(n2)(∏i=0k-1‍11-zit)|tn.
We shall then prove that
(11)mp(Υ,A→),n(p,q;1,…,1)=p(n2)(n+k-1n),mp(Υ,A→),n(p,q;1,r,…,rk-1)=p(n2)[n+k-1n]r.The main result of this paper is to prove the following.Theorem 4.
For anyΥ⊆Ck≀S2 and A→=(A1,A2) where A1,A2⊆[k],
(12)∑n≥0‍tn[n]p,q!∑(σ,w)∈Ck≀Sn‍pcoinv(σ)qinv(σ)x(Υ,A→)-mch((σ,w))z(w)=1×(1-((z0+⋯+zk-1)t+∑n≥2tn[n]p,q!(x-1)n-1mp(Υ,A→),n×(p,q;z0,…,zk-1)))-1.We note that (12) can be specialized to give natural analogues for generating functions of rises and descents in Ck≀Sn where we compare pairsusing the product order. That is, instead of thinking of an element of Ck≀Sn as a pair (σ1⋯σn,w1⋯wn), we can think of it as a sequence of pairs (σ1,w1)(σ2,w2)⋯(σn,wn). We then define a partial order on such pairs by the usual product order. That is, (i1,j1)≤(i2,j2) if and only if i1≤i2 and j1≤j2. Then we define the following sets and statistics for elements (σ,w)∈Ck≀Sn:
(13)Des((σ,w))={i:σi>σi+1&wi≥wi+1},des((σ,w))=|Des((σ,w))|,Ris((σ,w))={i:σi<σi+1&wi≤wi+1},ris((σ,w))=|Ris((σ,w))|,WDes((σ,w))={i:σi>σi+1&wi=wi+1},wdes((σ,w))=|WDes((σ,w))|,WRis((σ,w))={i:σi<σi+1&wi=wi+1},wris((σ,w))=|WRis((σ,w))|,SDes((σ,w))={i:σi>σi+1&wi>wi+1},sdes((σ,w))=|SDes((σ,w))|,SRis((σ,w))={i:σi<σi+1&wi<wi+1},sris((σ,w))=|SRis((σ,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). Similarly, we will refer to Ris((σ,w)) as the rise set of (σ,w), WRis((σ,w)) as the weak rise set of (σ,w), and SRis((σ,w)) as the strict rise set of (σ,w). It is easy to see that  i∈WDes((σ,w)) if and only if there is a (21,00)-match starting at position i,i∈SDes((σ,w)) if and only if there is a (21,10)-match starting at position i, andi∈Des((σ,w)) if and only if there is a Υ-match starting at position i where Υ={(21,00),(21,10)}.Similarly,i∈WRis((σ,w)) if and only if there is a (12,00)-match starting at position i,i∈SRis((σ,w)) if and only if there is a (12,01)-match starting at position i, andi∈Ris((σ,w)) if and only if there is a Υ-match starting at position i where Υ={(12,00),(12,01)}.Ifσ=σ1⋯σn∈Sn, then we define the reverse of σ, σr by σr=σn⋯σ1. Similarly, if w=w1⋯wn∈[k]n, then we define wr=wn⋯w1. It is easy to see that
(14)ris((σ,w))=des((σr,wr)),wris((σ,w))=wdes((σr,wr)),sris((σ,w))=sdes((σr,wr)).
Thus, we need to find the distributions for only one of the corresponding pairs. Substituting z0=z1=⋯=zk-1=1 into (12) in these special cases will yield the following generating functions for rises, strict rises, and weak rises in Ck≀Sn.Theorem 5.
Consider the following:(15)∑n≥0‍tnn!∑(σ,w)∈Ck≀Sn‍xris((σ,w))=1-x1-x+∑n≥1(((x-1)t)n/n!)(n+k-1n),(16)∑n≥0‍tnn!∑(σ,w)∈Ck≀Sn‍xwris((σ,w))=1-x1-x+k(e(x-1)t-1),∑n≥0‍tnn!∑(σ,w)∈Ck≀Sn‍xsris((σ,w))=1-x1-x+∑n≥1(((x-1)t)n/n!)(kn).Other distribution results for(τ,u)-matches follow from these results. For example, if σ=σ1⋯σn∈Sn, then we define the complement of σ, σc by
(17)σc=(n+1-σ1)⋯(n+1-σn).
If w=w1⋯wn∈[k]n, then we define the complement of w, wc by
(18)wc=(k-1-w1)⋯(k-1-wn).
We can then consider maps ϕa,b:Ck≀Sn→Ck≀Sn where ϕa,b((σ,w))=(σa,wb) for a,b∈{r,c}. Such maps will easily allow us to establish that the distribution of (τ,u)-matches is the same for various classes of (τ,u)’s. For example, one can use such maps to show that the distributions of (12,01)-matches, (21,01)-matches, (12,10)-matches, and (21,10)-matches are all the same.Another interesting case is when we letΥ={(12,01),(12,10)}. In this case, we have a Υ-match in (σ,w) starting at i if and only if σi<σi+1 and wi≠wi+1. In that case, (12) can be specialized to prove the following.Theorem 6.
Consider the following:(19)∑n≥0‍tnn!∑(σ,w)∈Ck≀Sn‍xΥ-mch((σ,w))=(k-1)(1-x)(k-1)(1-x)+k(e(k-1)(x-1)t-1).Substitutingzi=ri for i=0,…,k-1 into (12) will yield the following generating function:
(20)DkΥ(x,p,q,r,t)=∑n≥0‍tn[n]p,q!∑(σ,w)∈Ck≀Sn‍qinv(σ)pcoinv(σ)r∥w∥xΥ-mch((σ,w)).
Let
(21)Υr={(12,00),(12,01)},Υw={(12,00)},Υs={(12,01)},Υd={(12,01),(12,10)}.
Thus, Υr-matches correspond to rises, Υw-matches correspond to weak rises, and Υs-matches correspond to strict rises. We shall find DkΥa(x,p,q,r,t) for a∈{r,w,s} and find DkΥd(x,p,q,1,t). For example, we will show that the following generating function for the distribution of inversions, coinversions, and rises over Ck≀Sn is an immediate consequence of (12).Lemma 7.
Consider the following:(22)DkΥr(x,p,q,r,t)=∑n≥0‍tn[n]p,q!∑(σ,w)∈Ck≀Sn‍qinv(σ)pcoinv(σ)r∥w∥xris((σ,w))=1-x1-x+∑n≥1(p(n2)((x-1)t)n/[n]p,q!)[n+k-1n]r,
which reduces to (15) when one sets p=q=r=1.We shall prove (12) by applying a ring homomorphism, defined on the ring Λ of symmetric functions over infinitely many variables x1,x2,…, to a simple symmetric function identity. There has been a long line of research, [6–15], which shows that a large number of generating functions for permutation statistics can be obtained by applying homomorphisms defined on the ring of symmetric functions Λ over infinitely many variables x1,x2,… to simple symmetric function identities. For example, the nth elementary symmetric function, en, and the nth homogeneous symmetric function, hn, are defined by the generating functions
(23)E(t)=∑n≥0‍entn=∏i‍(1+xit),H(t)=∑n≥0‍hntn=∏i‍11-xit.
We let P(t)=∑n≥0‍pntn where pn=∑i‍xin is the nth power symmetric function. A partition of n is a sequence μ=(μ1,…,μk) such that 0<μ1≤⋯≤μk and μ1+⋯+μk=n. We write μ⊢n if μ is a partition of n, and we let ℓ(μ) denote the number of parts of μ. If μ⊢n, we set hμ=∏i=1ℓ(μ)‍hμi, eμ=∏i=1ℓ(μ)‍eμi, and pμ=∏i=1ℓ(μ)‍pμi. Let Λn denote the space of homogeneous symmetric functions of degree n over infinitely many variables x1,x2,… so that Λ=⨁n≥0Λn. It is well known that {eλ:λ⊢n}, {hλ:λ⊢n}, and {pλ:λ⊢n} are all bases of Λn. It follows that {e0,e1,…} is an algebraically independent set of generators for Λ and, hence, we can define a ring homomorphism ξ:Λ→R where R is a ring by simply specifying ξ(en) for all n≥0.Now it is well known that(24)H(t)=1E(-t),(25)P(t)=∑n≥1(-1)n-1nentnE(-t).
A surprisingly large number of results on generating functions for various permutation statistics in the literature and large number of new generating functions can be derived by applying homomorphisms on Λ to simple identities such as (24) and (25). We shall show that (12) can be proved by applying appropriate ring homomorphisms to identity (24).The outline of this paper is as follows. In Section2, we will provide the necessary background in symmetric functions that we will need to derive our generating functions. In Section 3, we will prove (12) and give a number of cases where we can compute mp(Υ,A→)(p,q;z0,…,zk-1) or its specializations which will prove all of the formulas in the special cases described above. We shall also show that if NM(Υ,A→),n denotes the number of (σ,w)∈Ck≀Sn such that (σ,w) has no (Υ,A→)-matches, then the sequence (NM(Υ,A→),n)n≥0 appears in the OIES [16] in several special cases. In Section 4, we will study NM(Υ,A→),n as a function of k, the size of the underlying cyclic group Ck. We will show that in several cases, NM(Υ,A→),n is a polynomial in k whose coefficients have interesting combinatorial properties. Finally, in Section 5, we will discuss some related results and directions for future research.


## 2. Symmetric Functions

In this section, we give the necessary background on symmetric functions needed for our proofs of the generating functions.LetΛ denote the ring of symmetric functions over infinitely many variables x1,x2,… with coefficients in the field of complex numbers ℂ. The nth elementary symmetric function en in the variables x1,x2,… is defined by
(26)E(t)=∑n≥0‍entn=∏i‍(1+xit),
and the nth homogeneous symmetric function hn in the variables x1,x2,… is defined by
(27)H(t)=∑n≥0‍hntn=∏i‍11-xit.
Thus,
(28)H(t)=1E(-t).
Let λ=(λ1,…,λℓ) be an integer partition, that is, λ is a finite sequence of weakly increasing positive integers. Let ℓ(λ)=l 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 {e0,e1,…} is an algebraically independent set of generators for Λ, we can specify a ring homomorphism θ on Λ by simply defining θ(en) for all n≥0.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 1.Figure 1
A brick tabloid of shape(12) and type (1,1,2,3,5).Letℬλ,n denote the set of all λ-brick tabloids of shape (n) and let Bλ,n=|ℬλ,n|. Through simple recursions stemming from (28), Eğecioğlu and Remmel proved in [17] that
(29)hn=∑λ⊢n‍(-1)n-ℓ(λ)Bλ,neλ.We end this section with two lemmas that will be needed in later sections. Both of the lemmas follow from simple codings of a basic result of Carlitz [18] that
(30)[nk]q=∑r∈ℛ(1k0n-k)‍qinv(r),
where ℛ(1k0n-k) is the number of rearrangements of k 1's and n-k 0's. We start with a lemma from [19]. Fix a brick tabloid T=(b1,…,bℓ(μ))∈ℬμ,n. Let IF(T) denote the set of all fillings of the cells of T=(b1,…,bℓ(μ)) with the numbers 1,…,n so that the numbers increase within each brick reading from left to right. We then think of each such filling as a permutation of Sn by reading the numbers from left to right in each row. For example, Figure 2 pictures an element of IF(3,6,3) whose corresponding permutation is 461215781011239.Figure 2
An element ofIF(3,6,3).Then the following lemma which is proved in [19] gives a combinatorial interpretation to p∑i=1ℓ(μ)(bi2)[nb1,…,bℓ(μ)]p,q.Lemma 8.
IfT=(b1,…,bℓ(μ)) is a brick tabloid in ℬμ,n, then
(31)p∑i=1ℓ(μ)(bi2)[nb1,…,bℓ(μ)]p,q=∑σ∈IF(T)‍qinv(σ)pcoinv(σ).Another well known combinatorial interpretation for[n+k-1k-1]q ([13]) is that it is equal to the sum of the sizes of the partitions that are contained in an n×(k-1) rectangle. Thus one has the following lemma.Lemma 9.
Consider the following:(32)∑0≤a1≤⋯≤an≤k-1‍qa1+⋯+an=[n+k-1n]q.


## 3. Generating Functions

The main goal of this section is to prove (12). That is, we will prove the following theorem.Theorem 10.
LetΥ⊆Ck≀S2 and A→=(A1,A2) where A1,A2⊆[k]. For all k≥2,
(33)∑n≥0‍tn[n]p,q!∑(σ,w)∈Ck≀Sn‍pcoinv(σ)qinv(σ)x(Υ,A→)-mch((σ,w))z(w)=1×(1-((z0+⋯+zk-1)t+∑n≥2tn[n]p,q!(x-1)n-1mp(Υ,A→),n×(p,q;z0,…,zk-1)))-1.Proof.
Define a ring homomorphismΓ:Λ→ℚ(p,q,z0,…,zk-1,x) by setting
(34)Γ(e0)=1,Γ(e1)=z0+⋯+zk-1,Γ(en)=(-1)n-1(x-1)n-11[n]p,q!mp(Υ,A→),n×(p,q;z0,…zk-1)forn≥1.
Then we claim that
(35)[n]p,q!Γ(hn)=∑(σ,w)∈Ck≀Sn‍qinv(σ)pcoinv(σ)z(w)x(Υ,A→)-mch((σ,w)),
for all n≥1. That is,
(36)[n]p,q!Γ(hn)=[n]p,q!∑μ⊢n‍(-1)n-ℓ(μ)Bμ,(n)Γ(eμ)=[n]p,q!∑μ⊢n‍(-1)n-ℓ(μ)×∑(b1,…,bℓ(μ))∈ℬμ,n‍∏j=1ℓ(μ)‍(-1)bj-1(x-1)bj-1×((z0+⋯+zk-1)χ(bj=1)+1[bj]p,q!mp(Υ,A→),bj(p,q;z0,z1,…,zk-1)×χ(bj>1))=∑μ⊢n‍∑(b1,…,bℓ(μ))∈ℬμ,n‍p∑j=1ℓ(μ)(bj2)[nb1,…,bℓ(μ)]p,q×∏j=1ℓ(μ)((z0+⋯+zk-1)χ(bj=1)‍+p-(bj2)[bj]p,q!mp(Υ,A→),bj(p,q;z0,z1,…,zk-1)×χ(bj>1)).
Next we want to give a combinatorial interpretation to (36). By Lemma 8, for each brick tabloid T=(b1,…,bℓ(μ)), we can interpret p∑j=1ℓ(μ)‍(bj2)[nb1,…,bℓ(μ)]p,q as the sum of the weights of all fillings of T with a permutation α∈Sn such that α is increasing in each brick, and we weight α with qinv(α)pcoinv(α). If bj=1 and covers cell r, then we will interpret the factor z0+⋯+zk-1 as picking an element wr∈[k] to put on top of αr. Next suppose that bj>1 and covers cells r,r+1,…,r+s. Let αr<αr+1<⋯<αr+s be the elements of α in cells r,r+1,…,r+s, respectively. Then we interpret p-(n2)mp(Υ,A→),bj(p,q;z0,…,zk-1) as the numbers of ways of picking a maximum packing (β(j),v(j))∈Ck≀Sbj for (Υ,A→) where we weight (β(j),v(j)) by p-(bj2)pcoinv(β(j))qinv(β(j))z(v(j)). We then reorder by the proper contribution after reordering which is coinv(β(j)) to the coinversion count of the resulting permutation and inv(β(j)) to the inversion count of the resulting permutation. Finally, we interpret ∏j=1ℓ(μ)‍(x-1)bj-1 as all ways of picking a label of the cells of each brick except the final cell with either an x or a -1. For completeness, we label the final cell of each brick with 1. For example, suppose that Υ={(21,00),(21,01)}, k=3, and A→=([3],[3]). Thus (σ,w) is a maximum packing for (Υ,A→) only if σ is strictly decreasing and w is a weakly increasing word over the alphabet {0,1,2}. Then at the top of Figure 3, we have pictured the brick tabloid T=(3,1,5,2) along with a permutation α which is increasing within bricks. Below that, we have picked our choices of (β(j),v(j)) for the bricks bj for j=1,3,4 and choice of 1 for brick b2 which is of length 1. These choices result in the filled brick tabloid pictured at the bottom of Figure 3. We have also specified a labeling of the cells with either x, -1, or 1 so that the last cell of each brick is labeled with 1 and the remaining cells are labeled with either x of -1. We shall call all such objects created in this way filled labeled brick tabloids, and let ℱn denote the set of all filled labeled brick tabloids that arise in this way. Thus, a C∈ℱn consists of a brick tabloid T=(b1,…,bt), an element (σ,w)∈Ck≀Sn, and a labeling L of the cells of T with elements from {x,1,-1} such that  (1)
ifbj=1 and covers cell r, then wr is an arbitrary element of [k],(2)
ifbj>1 and covers cells r,r+1,…,r+s, then (red(σrσr+1⋯σr+s),wrwr+1⋯wr+s) is an element of ℳ𝒫(Υ,A→),bj,(3)
the final cell of each brick is labeled with 1,(4)
each cell which is not a final cell of a brick is labeled withx or -1.
We then define the weightw(C) of C to be qinv(σ)pcoinv(σ)z(w) times 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, if C=(T,(σ,w),L) is the filled labeled brick tabloid pictured at the bottom of Figure 3, then w(C)=q28p27z05z14z22x4 and sgn(C)=-1. It follows that
(37)[n]p,q!Γ(hn)=∑C∈ℱn‍sgn(C)w(C).
Next we define a weight-preserving sign-reversing involutionI:ℱn→ℱn. To define I(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 or (ii) t is at the end of a brick bj, and the brick bj+1 immediately following bj has the property that if bj together with bj+1 cover cells r,r+1,…,r+s, then (red(σrσr+1⋯σr+s),wrwr+1⋯,wr+s) is a maximum packing for (Υ,A→). In case (i), I(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), I(C)=(T′,(σ′,w′),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. If neither case (i) or case (ii) applies, then we let I(C)=C. For example, if C is the element of ℱ12 pictured in Figure 3, then I(C) is pictured in Figure 4.
It is easy to see thatI is a weight-preserving sign-reversing involution and hence I shows that
(38)[n]p,q!Γ(hn)=∑C∈ℱn,I(C)=C‍sgn(C)w(C).
Thus, we must examine the fixed pointsC=(T,σ,w,L) of I. 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 it cannot be the case that there is (Υ,A→)-match starting at position t in (σ,w) since otherwise we could combine bj and bj+1. For any such fixed point, we associate an element (σ,w)∈Ck≀Sn. For example, a fixed point of I is pictured in Figure 5 where σ=5431111097682 and w=00110011202.
It follows that if cellt is at the end of a brick, then t is not the start of a (Υ,A→)-match. However, if v is a cell which is not at the end of a brick, then our definitions force v to be the start of a (Υ,A→)-match. Since each such cell v must be labeled with an x, it follows that sgn(C)w(C)=qinv(σ)pcoinv(σ)z(w)x(Υ,A→)-mch((σ,w)). Vice versa, if (σ,w)∈Ck≀Sn, then we can create a fixed point C=(T,(σ,w),L) by having the bricks in T end at cells of the form t where t is not the start of a (Υ,A→)-match, labeling each cell t which is the start of a (Υ,A→)-match with x, and labeling the remaining cells with 1. Thus, we have shown that
(39)[n]p,q!Γ(hn)=∑(σ,w)∈Ck≀Sn‍qinv(σ)pcoinv(σ)z(w)x(Υ,A→)-mch((σ,w))
as desired.
ApplyingΓ to the identity H(t)=(E(-t))-1, we get
(40)∑n≥0‍Γ(hn)tn=∑n≥0‍tn[n]p,q!×∑(σ,w)∈Ck≀Sn‍qinv(σ)pcoinv(σ)z(w)x(Υ,A→)-mch((σ,w))=11+∑n≥1(-t)nΓ(en)=1×(1+(z0+⋯+zk-1)(-t)+∑n≥1(-1)ntn×(-1)n-1(x-1)n-1[n]p,q!×mp(Υ,A→),n(p,q;z0,…,zk-1)∑n≥1(-1)ntn)-1=1×(1-((z0+⋯+zk-1)t+∑n≥2((x-1)n-1tn/[n]p,q!)×mp(Υ,A→),n(p,q;z0,…,zk-1)))-1,
which proves (33).Figure 3
A composite objectC∈ℱ12.Figure 4
I
(
C
) for C in Figure 3.Figure 5
A fixed point ofI.To be able to use Theorem10, we need to be able to compute mp(Υ,A→),n(p,q;z0,…,zk-1). In fact, this is easy to do in most cases. Thus, we end this section by giving several such examples. We will examine the cases when  (i)
Υ=Υs={(12,01)} and A→=([k],[k]),(ii)
Υ=Υr={(12,00),(12,01)} and A→=([k],[k]),(iii)
Υ=Υw={(12,00)} and A→=([k],[k]),(iv)
Υ=Υd={(12,01),(12,10)} and A→=([k],[k]),(v)
Υ={(12,ab)} and A→=({a},{b}),(vi)
Υ={(12,00),(12,01)} and A→=([k],{k-1}),(vii)
Υ={(12,00),(12,01)} and A→=([k],{k-2,k-1}),(viii)
Υ={(12,01)} and A→=([k],{k-2,k-1}).Example 11.
LetΥ=Υs={(12,01)} and A→=([k],[k]).
In this case for any(σ,w)∈Ck≀Sn, (Υ,A→)-mch((σ,w))=sris((σ,w)). It is easy to see that for n≥2, (σ,w)∈ℳ𝒫(Υ,A→),n if and only if σ=12⋯n is the identity permutation and w=w1⋯wn where 0≤w1<⋯<wn≤k-1. As we pointed out in the introduction, it follows that
(41)mp(Υ,A→),n(p,q;z0,…,zk-1)=p(n2)(∏i=0k-1‍(1+zit))|tn,mp(Υs,A→),n(p,q;1,…,1)=p(n2)(kn).
Note that if 0≤w1<⋯<wn≤k-1 and ai=wi-(i-1) for i=1,…,n, then 0≤a1≤a2≤⋯≤an≤k-n and ∑i=1n‍wi=(n2)+∑i=1n‍ai. Hence,
(42)mp(Υs,A→),n(p,q;1,r…,rk-1)=p(n2)∑0≤w1<⋯<wn≤k-1‍rw1+⋯+wn=p(n2)r(n2)∑0≤a1≤⋯≤an≤k-n‍r∑i=1nai=p(n2)r(n2)[kn]r.
Here the last equality follows from Lemma 9. Thus, it follows that for all k≥2,
(43)DkΥs(x,p,q,r,t)=∑n≥0‍tn[n]p,q!∑(σ,w)∈Ck≀Sn‍qinv(σ)pcoinv(σ)r∥w∥xsris((σ,w))=1×(1-((1+r+⋯+rk-1)t+∑n≥2(x-1)n-1tn[n]p,q!×mp(Υs,A),n(p,q;1,r,…,rk-1)))-1=1-x1-x+∑n≥1(p(n2)((x-1)t)n/[n]p,q!)r(n2)[kn]r.Example 12.
LetΥ=Υr={(12,00),(12,01)} and A→=([k],[k]).
In this case for any(σ,w)∈Ck≀Sn, (Υ,A→)-mch((σ,w))=ris((σ,w)). It is easy to see that for n≥2, (σ,w)∈ℳ𝒫(Υ,A→),n if and only if σ=12⋯n is the identity permutation and w=w1⋯wn where 0≤w1≤⋯≤wn≤k-1. As we pointed out in the introduction, it follows that
(44)mp(Υ,A→),n(p,q;z0,…,zk-1)=p(n2)(∏i=0k-1‍1(1-zit))|tn,mp(Υr,A→),n(p,q;1,r…,rk-1)=p(n2)∑0≤w1≤⋯≤wn≤k-1‍rw1+⋯+wn=p(n2)[n+k-1n]r,mp(Υr,A→),n(p,q;1,…,1)=p(n2)(n+k-1n).
Hence, for all k≥2,
(45)DkΥr(x,p,q,r,t)=∑n≥0‍tn[n]p,q!∑(σ,w)∈Ck≀Sn‍qinv(σ)pcoinv(σ)r∥w∥xris((σ,w))=1×(1-((1+r+⋯+rk-1)t+∑n≥2(x-1)n-1tn[n]p,q!mp(Υr,A),n×(p,q;1,r,…,rk-1)))-1=1-x1-x+∑n≥1(p(n2)((x-1)t)n/[n]p,q!)[n+k-1n]r.Example 13.
LetΥ=Υw={(12,00)} and A→=([k],[k]).
In this case for any(σ,w)∈Ck≀Sn, (Υ,A→)-mch((σ,w))=wris((σ,w)). It is easy to see that for n≥2, (σ,w)∈ℳ𝒫(Υ,A→),n if and only if σ=12⋯n is the identity permutation and w=w1⋯wn where 0≤w1=⋯=wn≤k-1. As we pointed out in the introduction, it follows that
(46)mp(Υ,A→),n(p,q;z0,…,zk-1)=p(n2)∑i=0k-1‍zin.
Hence,
(47)mp(Υw,A→),n(p,q;1,…,1)=kp(n2),mp(Υw,A→),n(p,q;1,r,…,rk-1)=p(n2)=p(n2)[k]rn.
Thus, for all k≥2,
(48)DkΥw(x,p,q,r,t)=∑n≥0‍tn[n]p,q!∑(σ,w)∈Ck≀Sn‍qinv(σ)pcoinv(σ)r∥w∥xwris((σ,w))=1×(1-((1+r+⋯+rk-1)t+∑n≥2(x-1)n-1tn[n]p,q!mp(Υr,A),n×(p,q;1,r,…,rk-1)))-1=1-x1-x+∑n≥1(p(n2)((x-1)t)n/[n]p,q!)[k]rn.Example 14.
LetΥ=Υd={(12,01),(12,10)} and A→=([k],[k]).
In this case, it is easy to see that forn≥2, (σ,w)∈ℳ𝒫(Υ,A→),n if and only if σ=12⋯n and w=w1⋯wn where wi≠wi+1 for i=1,…,n. In this case, one cannot find simple compact expressions for mp(Υr,A),n(p,q;z0,…,zk-1) or mp(Υr,A),n(p,q;1,r,…,rk-1). However, it is clear that mp(Υr,A),n(p,q;1,…,1)=k(k-1)n-1. Thus, it follows that, for all k≥2,
(49)DkΥd(x,p,q,t)=∑n≥0‍tn[n]p,q!∑(σ,w)∈Ck≀Sn‍qinv(σ)pcoinv(σ)xwris((σ,w))=1×(1-(kt+∑n≥2(x-1)n-1tn[n]p,q!×mp(Υd,A),n(p,q;1,1,…,1)∑n≥2((x-1)n-1tn/[n]p,q!))∑n≥2((x-1)n-1tn/[n]p,q!))-1=1-x1-x+∑n≥1(p(n2)((x-1)t)n/[n]p,q!)k(k-1)n-1.Example 15.
LetΥ={(12,ab)} and A→=({a},{b}).
In this case, (Υ,A→)-mch((σ,w))=(τ, u)-Emch((σ,w)) where (τ,u)=(12,ab). There are two cases that we have to consider depending on whether a equals b or not. If a=b, then for n≥2, (σ,w)∈Ck≀Sn is an element of ℳ𝒫(Υ,A→),n if and only if σ=12⋯n and w=an. Thus, mp(Υ,A→),n(p,q;z0,…,zk-1)=p(n2)zan. It follows that if (τ,u)=(12,aa), then
(50)∑n≥0‍tn[n]p,q!∑(σ,w)∈Ck≀Sn‍qinv(σ)pcoinv(σ)z(w)x(τ,u)-Emch((σ,w))=1×(∑n≥2((x-1)n-1tn/[n]p,q!)p(n2)zan1-(∑n≥2((x-1)n-1tn/[n]p,q!)p(n2)zan(z0+⋯+zk-1)t+∑n≥2(x-1)n-1tn[n]p,q!p(n2)zan))-1.
In particular,
(51)∑n≥0‍tn[n]p,q!∑(σ,w)∈Ck≀Sn‍qinv(σ)pcoinv(σ)x(τ,u)-Emch((σ,w))=1-x1-x+k(x-1)t+∑n≥2(p(n2)((x-1)t)n/[n]p,q!).
Ifa≠b, then the only possible maximum packings for (12,ab) are when n=2 in which case (σ,w)∈Ck≀S2 is an element of ℳ𝒫(Υ,A→),n if and only if (σ,w)=(12,ab). Thus, mp(Υ,A→),2(p,q;z0,…,zk-1)=pzazb. It follows that if (τ,u)=(12,ab) with a≠b, then
(52)∑n≥0‍tn[n]p,q!∑(σ,w)∈Ck≀Sn‍qinv(σ)pcoinv(σ)z(w)x(τ,u)-Emch((σ,w))=11-((z0+⋯+zk-1)t+((x-1)t2/[2]p,q!)pzazb).
In particular,
(53)∑n≥0‍tn[n]p,q!∑(σ,w)∈Ck≀Sn‍qinv(σ)pcoinv(σ)x(τ,u)-Emch((σ,w))=1-x1-x+k(x-1)t+(p(x-1)2t2/[2]p,q!).Example 16.
LetΥ={(12,00),(12,01)} and A→=([k],{k-1}).
In this case, it is easy to see that for alln≥2, (σ,w)∈ℳ𝒫(Υ,A→),n if and only if σ=12⋯n and w=a(k-1)n-1 where a∈[k]. It follows that for all n≥2,
(54)mp(Υ,A→),n(p,q;z0,…,zk-1)=p(n2)(z0+⋯+zk-1)zk-1n-1.
Hence,
(55)∑n≥0‍tn[n]p,q!∑(σ,w)∈Ck≀Sn‍qinv(σ)pcoinv(σ)z(w)x(Υ,A→)-mch((σ,w))=1×(1-(p(n2)(z0+⋯+zk-1)zk-1n-1(z0+⋯+zk-1)t+∑n≥2(x-1)n-1tn[n]p,q!×p(n2)(z0+⋯+zk-1)zk-1n-1))-1.
Setting p=q=z0=⋯=zk-1=1 in (55), we obtain that
(56)∑n≥0‍tn[n]p,q!∑(σ,w)∈Ck≀Sn‍x(Υ,A→)-mch((σ,w))=11-k∑n≥1((x-1)n-1tn/n!)=1-x1-x+k∑n≥1(((x-1)t)n/n!)=1-x1-x+k(e(x-1)t-1)=1-x1-k-x+ke(x-1)t.
Let NM({(12,00),(12,01)},([k],{k-1})),n denote the number of σ∈Ck≀Sn that have no ({(12,00),(12,01)},([k],{k-1}))-matches. Then setting x=0 in (56), we see that
(57)∑n≥0‍tnn!NM({(12,00),(12,01)},([k],{k-1})),n=11-k+ke-t=etk-(k-1)et.
One can easily calculate that the sequence (NM({(12,00),(12,01)},({0,1},{1})),n)n≥0 starts out with
(58)1,2,6,26,150,1082,9366,94586,1091670,…
which is sequence A000629 in the OEIS and which also counts the number of necklaces of partitions of n+1 labeled beads. Similarly, the sequence (NM({(12,00),(12,01)},({0,1,2},{2})),n)n≥0 starts out with
(59)1,3,15,111,1095,13503,199815,3449631,68062695,…,
and the sequence (NM({(12,00),(12,01)},({0,1,2,3},{3})),n)n≥0 starts out with
(60)1,4,28,292,4060,70564,1471708,35810212,995827420,….
Neither of these two sequences appear in the OEIS.Example 17.
LetΥ={(12,00),(12,01)} and A→=([k],{k-2,k-1}).
In this case, it is easy to see that for allk≥2 and n≥2, (σ,w)∈ℳ𝒫(Υ,A→),n if and only if σ=12⋯n and w is either of the form w=a(k-2)i(k-1)j where 0≤a≤k-3 and i+j=n-1 or w=(k-2)r(k-1)s where r+s=n. Hence, for all n≥2,
(61)mp(Υ,A→),n(p,q;1,…,1)=((k-1)n+1)p(n2).
It follows that
(62)∑n≥0‍tn[n]p,q!∑(σ,w)∈Ck≀Sn‍qinv(σ)pcoinv(σ)x(Υ,A→)-mch((σ,w))=1×(1-(((k-1)n+1)p(n2)(z0+⋯+zk-1)t+∑n≥2(x-1)n-1tn[n]p,q!×((k-1)n+1)p(n2)))-1.
Setting p=q=1 in (62), we obtain that
(63)∑n≥0‍tn[n]p,q!∑(σ,w)∈Ck≀Sn‍x(Υ,A→)-mch((σ,w))=11-∑n≥1((k-1)n+1)((x-1)n-1tn/n!)=1-x1-x+∑n≥1((k-1)n+1)(((x-1)t)n/n!)=1-x(∑n≥1(((x-1)t)n-1/(n-1)!)1-x+(k-1)(x-1)t×(∑n≥1((x-1)t)n-1(n-1)!)+∑n≥1((x-1)t)nn!)-1=1-x1-x+(k-1)(x-1)te(x-1)t+e(x-1)t-1=1-x-x+(1+(k-1)(x-1)t)e(x-1)t.
Let NM({(12,00),(12,01)},([k],{k-2,k-1})),n denote the number of σ∈Ck≀Sn that have no ({(12,00),(12,01)},([k],{k-2,k-1}))-matches. Then setting x=0 in (63), we see that
(64)∑n≥0‍tnn!NM({(12,00),(12,01)},([k],{k-2,k-1})),n=1(1-(k-1)t)e-t=et1-(k-1)t.
Note that it follows that for n≥1,
(65)NM({(12,00),(12,01)},([k],{k-2,k-1})),n=n!∑j=0n‍(k-1)j(n-j)!=1+n!∑j=1n‍(k-1)j(n-j)!=1+(k-1)n((n-1)!∑i=0n-1‍(k-1)i(n-1-i)!)=1+(k-1)nNM({12,00),(12,01)},([k],{k-2,k-1}),n-1.
It would be interesting to find a direct combinatorial proof of this recursion, which we leave as an open problem.
One can easily calculate that the sequence(NM({(12,00),(12,01)},({0,1},{0,1})),n)n≥0 starts out with
(66)1,2,5,16,65,326,1957,13700,109601,986410…,
which is sequence A000522 in the OEIS having multiple combinatorial interpretations including the number of permutations σ=σ1⋯σn+1 with no 1≤i<j≤n such that σi<σj<σn+1, that is, in the Babson-Steingrimsson notation, the number of σ in Sn+1 which avoid the pattern 1-2-3] (the same pattern is denoted 123⌋ in the recently introduced notation [20]).
The sequence(NM({(12,00),(12,01)},({0,1,2},{1,2})),n)n≥0 starts out with
(67)1,3,13,79,633,6331,75973,1063623,18017969,306323443…,
which is sequence A010844 of the OEIS. This sequence does not have a combinatorial interpretation listed in the OEIS so that we have obtained a simple combinatorial interpretation of this sequence. However, if a(n) is the nth term of this sequence where a(0)=1, then a(n) is equal to 2n times the permanent of the n×n matrix with 3/2 on the main diagonal and 1s everywhere else.
The sequence(NM({(12,00),(12,01)},({0,1,2,3},{2,3})),n)n≥0 starts out with
(68)1,4,25,226,2713,40696,732529,15383110,369194641,9968255308,…
is sequence A010844 of the OEIS. This sequence does not have a combinatorial interpretation listed in the OEIS. Thus, we have obtained a new combinatorial interpretation of this sequence. In this case, if a(n) is the nth term of the sequence where a(0)=1, then a(n) is equal to 3n times the permanent of the n×n matrix with 4/3 on the main diagonal and 1's everywhere else.
Similarly, the sequences(NM({(12,00),(12,01)},([k],{k-2,k-1})),n)n≥0 for k=5,6, and 7 appear in the OEIS as sequences as A056545, A056546, and A056547, respectively.Example 18.
LetΥ={(12,01)} and A→=([k],{k-2,k-1}).
In this case, it is easy to see thatℳ𝒫(Υ,A→),n=∅ for k>3. That is, for (σ,w)∈ℳ𝒫(Υ,A→),n, we must have σ=12⋯n and w=w1⋯wn where 0≤w1<⋯<wn≤k-1 and wi∈{k-2,k-1} for i>1. Now if n=2, our choices for w are either a(k-2) or a(k-1) where a∈{0,…,k-3} or w=(k-2)(k-1) so that mp(Υ,A→),2(p,q;1,…,1)=p(2(k-2)+1)=p(2k-3). Now if n=3, our choices for w are a(k-2)(k-1) where a∈{0,…,k-3}, so that mp(Υ,A→),3(p,q;1,…,1)=p3(k-2).
It follows that(69)∑n≥0‍tn[n]p,q!∑(σ,w)∈Ck≀Sn‍qinv(σ)pcoinv(σ)x(Υ,A→)-mch((σ,w))=1×(1-(kt+p(2k-3)(x-1)t2[2]p,q!+p3(x-1)2(k-2)t3[3]p,q!))-1.
Setting p=q=1 in (69), we obtain that for k≥2(70)∑n≥0‍tn[n]p,q!∑(σ,w)∈Ck≀Sn‍x(Υ,A→)-mch((σ,w))=1×(1-(kt+(2k-3)(x-1)(t22)+(x-1)2(k-2)(t36)(t22))(t36))-1.
Let NM(12,01),([k],{k-2,k-1}),n denote the number of σ∈Ck≀Sn that have no ((12,01),([k],{k-2,k-1}))-matches. Then setting x=0 in (70), we see that
(71)∑n≥0‍tnn!NM(12,01),([k],{k-2,k-1}),n=11-kt+(2k-3)(t2/2)-(k-2)(t3/6).
One can easily calculate the initial terms of the sequences(NM(12,01),([k],{k-2,k-1}),n)n≥0. For example, the sequence (NM(12,01),([2],{0,1}),n)n≥0 starts out
(72)1,2,7,36,246,2100,21150,257040,3510360,53933040,….
The sequence (NM(12,01),([3],{1,2}),n)n≥0 starts out
(73)1,3,15,109,1050,12630,182270,3068730,59046120,1278133080,….
The sequence (NM(12,01),([4],{2,3}),n)n≥0 starts out
(74)1,4,27,266,3478,56800,1112990,25443180,664724760,19537301289,….
However, none of these sequences appear in the OEIS.


## 4. Expressions forNM(Υ,A→),n as Polynomials in k and Connections to Other Objects

Recall that for anyΥ⊆Ck≀S2 and A→=(A1,A2) where Ai⊆[k], NM(Υ,A→),n is the number of (σ,w)∈Ck≀Sn such that (σ,w) has no (Υ,A→)-matches. We start out by considering the special case where Υ⊆C2≀S2 and A→=([k],[k]). In that case, we will simply write An,kΥ for NM(Υ,A→),n. Thus, An,kΥ is the number of permutations (σ,w)∈Ck≀Sn such that (σ,w) has no Υ-matches. By setting p=q=z0=⋯=zk-1=1 in (33), we see that
(75)∑n≥0‍An,kΥtnn!=1×(1-(kt+∑n≥2mp(Υ,([k],[k])),n×(1,1;1,…,1)((-1)n-1tn/n!)∑n≥2mp(Υ,([k],[k])),n)∑n≥2mp(Υ,([k],[k])),n)-1.We can easily compute the initial sequences of values for these generating functions using any computer algebra system such as Mathematica or Maple. In this section, we will demonstrate these values in several cases.


### 4.1.NMn,kΥr

For example, ifΥ=Υr={(12,00),(12,01)}, NMn,kΥr equals the number of (σ,ϵ)∈Ck≀Sn such that ris((σ,ϵ))=0. Table 1 gives initial values of NMn,kΥr.Table 1
NM
n
,
k
Υ
r for k,n≤5.
n
=
0
n
=
1
n
=
2
n
=
3
n
=
4
n
=
5
k
=
2
1
2
5
16
65
326
k
=
3
1
3
12
64
441
3771
k
=
4
1
4
22
164
1589
19136
k
=
5
1
5
35
335
4180
64876Several of these sequences appear in the OEIS [16]. In fact, we can easily calculate NMn,kΥr as a polynomial in k. For example, we have
(76)NM0,kΥr=1,NM1,kΥr=k,NM2,kΥr=12k(3k-1),NM3,kΥr=16k(19k2-15k+2),NM4,kΥr=124k(211k3-270k2+89k-6),NM5,kΥr=1120k(3651k4-6490k3+3585k2-650k+24).We point out thatNM2,kΥr forms the familiar sequence of pentagonal numbers (A000326 in [16]). Other previously documented sequences appearing in Table 1 include the structured octagonal antiprism numbers (A100184 in [16]) for NM3,kΥr, as well as NMn,2Υr (A000522 in [16]), for which there are many known combinatorial interpretations, including the total number of arrangements of all subsets of [n].We conjecture that forn≥1 and k≥2, NMn,kΥr is always of the form (1/n!)kPn(k) where Pn(k) is a polynomial of degree n-1 whose leading coefficient is positive and such that signs of the remaining coefficients alternate. Now we can prove that NMn,kΥr is always of the form (1/n!)kPn(k) where Pn(k) is a polynomial of degree n-1 and the term of degree 1 in k is (-1)n-1(n-1)!. That is, for any k≥2, if we set p=q=z0=⋯=zk-1=1 and x=0 in the proof of Theorem 10 and use the fact that mp(Υr,([k],[k])),n(1,1;1,…,1)=(n+k-1n), we see that
(77)n!Γ-(hn)=NMn,kΥr,
where
(78)Γ-(en)=(n+k-1n)n!=(k)↑n(n!)2.
Here we let (q)↑0=1 and (q)↑n=q(q+1)⋯(q+n-1) for n≥1. But then
(79)n!Γ-(hn)=n!∑μ⊢n‍(-1)n-ℓ(μ)Bμ,nΓ-(eμ)=1n!∑μ⊢n‍(-1)n-ℓ(μ)Bμ,n(nμ1,…,μℓ(μ))2∏i=1ℓ(μ)‍(k)↑μi=1n!∑μ⊢n‍(-1)n-ℓ(μ)∑(b1,…,bℓ(μ))∈ℬμ,n‍(nb1,…,bℓ(μ))2∏i=1ℓ(μ)‍(k)↑bi.
It is easy to see that the right-hand side of (79) is a polynomial of degree n, and the lowest degree term comes from the term (-1)n-1k(k+1)⋯(k+n-1) corresponding to μ=(n) which is of the form (-1)n-1(n-1)!k+O(k2). On the other hand, the highest-degree term arises when we pick the highest power of k from the products ∏i=1ℓ(μ)‍(k)↑bi which is clearly just kn. It follows that the highest power of k in An,kΥr is just
(80)1n!∑μ⊢n‍(-1)n-ℓ(μ)∑(b1,…,bℓ(μ))∈ℬμ,n‍(nb1,…,bℓ(μ))2.We can give a combinatorial interpretation to(81)Fn=∑μ⊢n‍(-1)n-ℓ(μ)∑(b1,…,bℓ(μ))∈ℬμ,n‍(nb1,…,bℓ(μ))2.
That is, we will show that Fn counts the number of pairs of permutations (α,β)∈Sn×Sn such that if α=α1⋯αn and β=β1,…,βn, then there is no 1≤i≤n-1 such that αi<αi+1 and βi<βi+1. That is, Fn is the number of pairs (α,β)∈Sn×Sn that have no common rises. To prove our claim, we can give a combinatorial interpretation to the right-hand side of (81). That is, if we start with a brick tabloid T=(b1,…,bℓ(μ)), then by Lemma 8, we can interpret (nb1,…,bℓ(μ))2 as all ways to fill the cells of T with pairs of permutations (α,β) such that both α and β are increasing in each brick. Then we interpret (-1)n-ℓ(μ) as labeling each cell of T which is not at the end of brick with -1 and labeling each cell which is at the end of the brick with 1. We let 𝒪ℛn denote the set of all filled brick tabloids constructed in this way. For example, Figure 6 pictures a typical element of 𝒪ℛ11. If O∈𝒪ℛn, we define the sign of O, sgn(O), as the product of labels at the top of the cells of O.Figure 6
A brick tabloid of shape(12) and type (1,1,2,3,5).We now can define a sign-reversing involutionIr on 𝒪ℛn.To defineIr, suppose that O∈𝒪ℛn and α and β are the two permutations in O with α on the bottom and β on the top. Then we scan the cells of O from left to right looking for the leftmost cell t such that either (i) t is labeled with -1 or (ii) t is at the end of a brick bj, and the brick bj+1 immediately following bj has the property that both α and β are strictly increasing in all the cells corresponding to bj and bj+1. In case (i), Ir(O) is the result of replacing the brick b in O 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 changing the label of cell t from -1 to 1. In case (ii), Ir(O) is the result of replacing the bricks bj and bj+1 in T by a single brick b and changing the label of cell t from 1 to -1. If neither case (i) or case (ii) applies, then we let I(O)=O. For example, if O is the element of ℱ12 pictured in Figure 6, then Ir(O) is pictured in Figure 7.Figure 7
I
r
(
O
) for O in Figure 6.It is easy to see thatIr is a weight-preserving sign-reversing involution and, hence, Ir shows that
(82)Fn=∑O∈𝒪ℛn,Ir(O)=O‍sgn(O).Thus, we must examine the fixed pointsO of Ir. First there can be no -1 labels in O so that all bricks in O must be of size 1 and sgn(O)=1. Moreover, if bj and bj+1 are two consecutive bricks in T and t is the last cell of bj, then it cannot be the case that αt<αt+1 and βt<βt+1 where α and β are the two permutations in O since otherwise we could combine bj and bj+1. Thus, (α,β) is a pair of permutations in Sn with no common rises. Vice versa, if (α,β) is a pair of permutations in Sn with no common rises, we can create a fixed point O of Ir by having α be the bottom permutation of O, having β be the top permutation of O, and having all bricks be of size 1. For example, Figure 8 pictures a fixed point of Ir.Figure 8
A fixed point ofIr.It follows thatFn is the number of pairs (α,β)∈Sn2 with no common rises so that the leading coefficient of Ak,rΥr is Fn/n!.


### 4.2.NMn,kΥs

ForΥs={(12,01)}, NMn,kΥs equals the number of (σ,ϵ)∈Ck≀Sn such that sris((σ,ϵ))=0. Table 2 gives initial values of NMn,kΥs.Table 2
NM
n
,
k
Υ
s for k,n≤5.
n
=
0
n
=
1
n
=
2
n
=
3
n
=
4
n
=
5
k
=
2
1
2
7
36
246
2100
k
=
3
1
3
15
109
1050
12630
k
=
4
1
4
26
244
3031
47000
k
=
5
1
5
40
460
6995
132751In fact, we can easily calculateNMn,kΥs as a polynomial in k. For example, we have
(83)NM0,kΥs=1,NM1,kΥs=k,NM2,kΥs=12k(3k+1),NM3,kΥs=16k(19k2+15k+2),NM4,kΥs=124k(211k3+270k2+89k+6),NM5,kΥs=1120k(3651k4+6490k3+3585k2+650k+24).
We point out that NM2,kΥs forms the familiar sequence of the second pentagonal numbers (A005449 in [16]). None of the other rows or columns in Table 2 matched any previously known sequences in [16].We conjecture that forn≥1 and k≥2, NMn,kΥs is always of the form (1/n!)kRn(k) where Rn(k) is a polynomial of degree n-1 with positive coefficients. In fact, we see that the coefficients of Pn,k and Rn,k are the same up to a sign for all n. we can prove this. That is, for any k≥2, if we set p=q=z0=⋯=zk-1=1 and x=0 in the proof of Theorem 10 and use the fact that mp(Υs,([k],[k])),n=(kr), we see that
(84)n!Γ-s(hn)=NMn,kΥs,
where
(85)Γ-s(en)=(kn)n!=(k)↓n(n!)2.
Here we let (q)↓0=1 and (q)↓n=q(q-1)⋯(q-n+1) for n≥1. But then
(86)n!Γ-s(hn)=n!∑μ⊢n‍(-1)n-ℓ(μ)Bμ,nΓ-(eμ)=1n!∑μ⊢n‍(-1)n-ℓ(μ)Bμ,n(nμ1,…,μℓ(μ))2∏i=1ℓ(μ)‍(k)↓μi=1n!∑μ⊢n‍(-1)n-ℓ(μ)∑(b1,…,bℓ(μ))∈ℬμ,n‍(nb1,…,bℓ(μ))2∏i=1ℓ(μ)‍(k)↓bi.Since for anyn≥1, (k)↓n=(-1)n(k)↑n, it is easy to see that the right-hand side of (86) is obtained from the right-hand side of (79) by replacing k by -k and multiplying by (-1)n. Thus, conjecture that Rn(k) has positive coefficients is equivalent to the conjecture that the signs of the coefficients of Pn(k) alternate.


### 4.3.NMn,kΥw

ForΥw={(12,00)}, NMn,kΥw equals the number of (σ,ϵ)∈Ck≀Sn such that wris((σ,ϵ))=0. Table 3 gives initial values of NMn,kΥw.Table 3
NM
n
,
k
Υ
w for k,n≤5.
n
=
0
n
=
1
n
=
2
n
=
3
n
=
4
n
=
5
k
=
2
1
2
6
26
150
1082
k
=
3
1
3
15
111
1095
13503
k
=
4
1
4
28
292
4060
70564
k
=
5
1
5
45
605
10845
243005In fact, we can easily calculateNMn,kΥw as a polynomial in k. For example, we have
(87)NM0,kΥw=1,NM1,kΥw=k,NM2,kΥw=k(2k-1),NM3,kΥw=k(6k2-6k+1),NM4,kΥw=k(24k3-36k2+14k-1),NM5,kΥw=k(120k4-240k3+150k2-30k+1).
We point out that NM2,kΥw forms the familiar sequence of hexagonal numbers (A000384 in [16]). Additionally, NMn,2Υw matches the sequence counting the number of necklaces on the set of labeled beads (A000629 in [16]). In fact, in this case, we can give a completely combinatorial interpretation of the coefficients of NMn,kΥw as a polynomial in k. Let Ostpn(n) denote the set of ordered set partitions of {1,2,…,n}. For any set partition π∈Ostpn(n), let ℓ(π) denote the number of parts of π. Then we claim that
(88)NMn,kΥw=∑π∈Ostpn(n)‍(-1)n-ℓ(π)kℓ(π),
so that the coefficient of kj in NMn,kΥw is equal to (-1)n-jj!Sn,j where Sn,j is the Stirling number of the second kind which is the number of set partitions of {1,…,n} into j parts. That is, for any k≥2, if we set p=q=z0=⋯=zk-1=1 and x=0 in Theorem 10 and use the fact that mpΥw,n=k for all n≥2, then we see that
(89)n!Γ-w(hn)=NMn,kΥw,
where
(90)Γ-w(en)=kn!.
But then
(91)n!Γ-s(hn)=n!∑μ⊢n‍(-1)n-ℓ(μ)Γ-s(eμ)=n!∑μ⊢n‍(-1)n-ℓ(μ)∑(b1,…,bℓ(μ))∈ℬμ,n‍∏i=1ℓ(μ)‍kbi!=∑μ⊢n‍(-1)n-ℓ(μ)∑(b1,…,bℓ(μ))∈ℬμ,n‍(nb1,…,bℓ(μ))kℓ(μ).
Since (nb1,…,bℓ(μ)) counts the number of ordered set partitions π=(π1,…,πℓ(μ)) such that |πj|=bj, it is easy to see that the right-hand side of (91) equals the right-hand side of (88).


### 4.4.NMn,kΥd

Recall thatΥd={(12,01),(12,10)}. Table 4 gives initial values of NMn,kΥd.Table 4
NM
n
,
k
Υ
d for k,n≤5.
n
=
0
n
=
1
n
=
2
n
=
3
n
=
4
n
=
5
k
=
2
1
2
6
26
150
1082
k
=
3
1
3
12
66
480
4368
k
=
4
1
4
20
132
1140
12324
k
=
5
1
5
30
230
2280
28280In fact, we can easily calculateNMn,kΥd as a polynomial in k. For example, we have
(92)NM0,kΥd=1,NM1,kΥd=k,NM2,kΥd=k2+k,NM3,kΥd=k3+4k2+k,NM4,kΥd=k4+11k3+11k2+k,NM5,kΥd=k5+26k4+66k3+26k2+k.
In this case, we will show that NMn,kΥd is just the Eulerian polynomial
(93)NMn,kΥd=∑σ∈Sn‍xdes(σ)+1.
That is, for any k≥2, if we set p=q=z0=⋯=zk-1=1 and x=0 in the proof of Theorem 10 and the fact that mp(Υd,([k],[k])),n=k(k-1)n-1, we see that
(94)n!Γ-U(hn)=NMn,kΥd,
where
(95)Γ-U(en)=k(k-1)n-1n!.
But then
(96)n!Γ-U(hn)=n!∑μ⊢n‍(-1)n-ℓ(μ)Bu,nΓ-U(eμ)=n!∑μ⊢n‍(-1)n-ℓ(μ)∑(b1,…,bℓ(μ))∈ℬμ,n‍∏i=1ℓ(μ)‍k(k-1)bi-1bi!=∑μ⊢n‍∑(b1,…,bℓ(μ))∈ℬμ,n‍(nb1,…,bℓ(μ))∏i=1ℓ(μ)‍k(1-k)bi-1.
Next we want to give a combinatorial interpretation to (96). For any brick tabloid T=(b1,…,bℓ(μ))∈ℬμ,n, we can interpret (nb1,…,bℓ(μ)) as the set of all fillings of T with a permutation σ∈Sn such that σ is increasing in each brick. We then interpret ∏j=1ℓ(μ)‍k(1-k)bj-1 as all ways of picking a label of the cells of each brick except the final cell with either an 1 or a -k and letting the label of the last cell of each brick be k. We let 𝒟n denote the set of all filled labeled brick tabloids that arise in this way. Thus, a C∈𝒟n consists of a brick tabloid T, a permutation σ∈Sn, and a labeling L of the cells of T with elements from {k,-k,1} such that(1)
σ is strictly increasing in each brick,(2)
the final cell of each brick is labeled withk,(3)
each cell which is not a final cell of a brick is labeled with1 or -k. We then define the weight w(C) of C to be the product of all the k labels in L and the sign sgn(C) of C to be the product of all the -1 labels in L. For example, if n=12, k=4, and T=(4,3,3,2), then Figure 9 pictures such a composite object C∈𝒟12 where w(C)=k7 and sgn(C)=-1.Figure 9
A composite objectC∈𝒟12.Thus,(97)n!Γ-U(hn)=∑C∈𝒟n‍sgn(C)w(C).Next we define a weight-preserving sign-reversing involutionJ:𝒟n→𝒟n. To define J(C), we scan the cells of C=(T,σ,L) from left to right looking for the leftmost cell t such that either (i) t is labeled with -k or (ii) t is at the end of a brick bj, and the brick bj+1 immediately following bj has the property that σ is strictly increasing in all the cells corresponding to bj and bj+1. In case (i), J(C)=(T′,σ′,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, σ=σ′, and L′ is the labeling that results from L by changing the label of cell t from -k to k. In case (ii), J(C)=(T′,σ′,L′) where T′ is the result of replacing the bricks bj and bj+1 in T by a single brick b, σ=σ′, and L′ is the labeling that results from L by changing the label of cell t from k to -k. If neither case (i) or case (ii) applies, then we let J(C)=C. For example, if C is the element of 𝒟12 pictured in Figure 9, then J(C) is pictured in Figure 10.Figure 10
J
(
C
) for C in Figure 9.It is easy to see thatJ is a weight-preserving sign-reversing involution, and hence J shows that
(98)n!Γ-U(hn)=∑C∈𝒟n,J(C)=C‍sgn(C)w(C).Thus, we must examine the fixed pointsC=(T,σ,L) of J. First there can be no -k 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 it cannot be the case that σt<σt+1 since otherwise we could combine bj and bj+1. For any such fixed point, we associate an element (σ,w)∈Ck≀Sn. For example, a fixed point of I is pictured in Figure 11 where
(99)σ=234116910181257.
It follows that if cell t is at the end of a brick which is not the last brick, then σt>σt1. However, if v is a cell which is not at the end of a brick, then our definitions force σv<σv+1. Since each such cell v must be labeled with an 1, it follows that sgn(C)w(C)=kdes(σ)+1 where the +1 comes from the fact that the last cell of the last brick is also labeled with k. Vice versa, if σ∈Sn, then we can create a fixed point C=(T,σ,L) by having the bricks in T end at cells of the form t where σt>σt+1 and labeling each such cell with k, labeling the last cell with k, and labeling the remaining cells with 1. Thus, we have shown that
(100)n!Γ-U(hn)=∑σ∈Sn‍kdes(σ)+1
as desired.Figure 11
A fixed point ofJ.


### 4.5.NM(Υ,A→),n

Next we consider another case where we can show that as a polynomial ink, NM(Υ,A→),n has coefficients whose signs alternate. That is, it follows from (64) that
(101)NM({(12,00),(12,01)},([k],{k-2,k-1})),n=n!∑r=0n‍(k-1)r(n-r)!=∑r=0n‍(n)↓r(k-1)r.
We can easily calculate NM({(12,00),(12,01)},([k],{k-2mk-1})),n as a polynomial in k. For example, we have
(102)NM({(12,00),(12,01)},([k],{k-2,k-1})),0=1,NM({(12,00),(12,01)},([k],{k-2,k-1})),1=k,NM({(12,00),(12,01)},([k],{k-2,k-1})),2=2k2-2k+1,NM({(12,00),(12,01)},([k],{k-2,k-1})),3=6k3-12k2+9k-2,NM({(12,00),(12,01)},([k],{k-2,k-1})),4=24k4-72k3+84k2-44k+9,NM({(12,00),(12,01)},([k],{k-2,k-1})),5=120k5-480k4+780k3+-640k2+265k-44.Thus, we see that the signs of the polynomialNM({(12,00),(12,01)},([k],{k-2,k-1})),n seem to alternate and that the leading term seems to be n!kn. We can prove both of these facts. Taking the coefficient of ks on both sides of (101), we see that
(103)NM({(12,00),(12,01)},([k],{k-2,k-1})),n∣ks=∑r=sn‍(n)↓r(rs)(-1)r-s.Now we can give a combinatorial interpretation to the right-hand side of (103) as follows. First for each r, we interpret (n)↓r as the number of ways to pick a sequence a1⋯ar of pairwise distinct elements from [n]. Then we interpret (rs) as picking s of the elements which we indicate by putting an x above each of the s elements picked. Finally, we interpret (-1)r-s as placing -1 above the elements in the sequence. We let Mn,s,r denote the set of all labeled sequences constructed in this way. For example, if n=10, s=3, and r=6, then the following labeled sequence would be in M10,4,6:
(104)(a,L)=-1x-1-1xx6310458.
Given a labeled sequence (a,L)∈Mn,s,r, we let the sign of (a,L), sgn(a,L), be the product of the -1 labels in L. We let Mn,s=⋃r=sn‍Mn,s,r. Then it is easy to see that
(105)NM({(12,00),(12,01)},([k],{k-2,k-1})),n∣ks=∑r=sn‍(n)↓r(rs)(-1)r-s=∑(a,L)∈Mn,s‍sgn(a,L).Given a sequence(a,L)=(a1⋯ar,L1⋯Lr), we say that the minimal sequence of (a,L) is the longest string atat+1⋯ar such that for all j=t,…,r, aj=min([n]-{a1,…,aj-1}) and Li=-1 for j=t,…,r. The minimal sequence for (a,L) might be empty. For example, it could be the last label Lr=x or it could be that ar≠min([n]-{a1,…,ar-1}). We let ms(a,L) denote the length of the minimal sequence of (a,L). For example, the minimal sequence of
(106)(a,L)=-1xxx-1-16310458
is empty so that ms(a,L)=0. The minimal sequence of
(107)(a′,L′)=-1xxx-1-11310425
is 25 so that ms(a,L)=2.Now suppose that(a,L)∈Mn,s,r is such that a=a1⋯ar, L=L1⋯Lr, and its minimal sequence is empty. Let b1<⋯<bn-r be the elements of [n]-{a1,…,ar}. Then we define the minimal sequence chain of (a,L) to be (a(r),L(r)),(a(r+1),L(r+1)),…,(a(n),L(n)) where (a(r),L(r))=(a,L) and (a(r+p),L(r+p))=(a1⋯arb1⋯bp,L1⋯Lr(-1)p) for 1≤p≤n-r. Note that the signs of the elements of a minimal sequence chain of (a,L) alternate. Thus, if the minimal sequence chain of (a,L) is of even length, then ms(a(n),L(n)) is odd, and the sum of the signs of elements in the minimal sequence chain of (a,L) is 0. If the minimal sequence chain of (a,L) is of odd length, then ms(a(n),L(n)) is even, and the sum of the signs of elements in the minimal sequence chain of (a,L) is sgn(a(n),L(n)). Clearly every element of Mn,r is an element of a unique minimal sequence chain for some (a,L)∈Mn,s whose minimal sequence is empty so that
(108)∑(a,L)∈Mn,s‍sgn(a,L)=∑(a,L)∈Mn,s,n,ms(a,L)iseven‍sgn(a,L)=(-1)n-s|{(a,L)∈Mn,s,n:ms(a,L)iseven}|.
Thus, we have shown that
(109)NM({(12,00),(12,01)},([k],{k-2,k-1})),n∣ks=(-1)n-s|{(a,L)∈Mn,s,n:ms(a,L)iseven}|.
This shows that as a polynomial in k, NM({(12,00),(12,01)},([k],{k-2,k-1})),n is sign alternating starting with the leading term n!kn. That is, by (109),
(110)NM({(12,00),(12,01)},([k],{k-2,k-1})),n∣kn=|{(a,L)∈Mn,n,n:ms(a,L)iseven}|.
But the elements of Mn,n,n have no -1 labels since every element of Mn,n,n has an empty minimal sequences and, hence, |{(a,L)∈Mn,n,n:ms(a,L)iseven}|=n!.We can also compute several other coefficients ofNM({(12,00),(12,01)},([k],{k-2,k-1})),n as a polynomial in k. For example, we can explicitly compute the coefficient of kn-1 in NM({(12,00),(12,01)},([k],{k-2,k-1})),n. Note that
(111)NM({(12,00),(12,01)},([k],{k-2,k-1})),n∣kn-1=-|{(a,L)∈Mn,n-1,n:ms(a,L)iseven}|.
Now an element (a,L)∈Mn,n-1,n has exactly one label which is -1. If Ln=-1, then the last element of a is automatically its minimal sequence so that it is not counted in |{(a,L)∈Mn,n-1,n:ms(a,L)iseven}|. Thus, |{(a,L)∈Mn,n-1,n:ms(a,L)iseven}| counts all (a,L)∈Mn,n-1,n such that Ln=x which is clearly (n-1)n!.We claim that(112)NM({(12,00),(12,01)},([k],{k-2,k-1})),n∣k0=(-1)nDn,
where Dn is the number of derangements of Sn, that is, the number of permutations with no fixed points. It is well known that Dn=n!∑k=0n‍(-1)k/k! for n≥1. But by (105),
(113)NM({(12,00),(12,01)},([k],{k-2,k-1})),n∣k0=∑r=0n‍(n)↓r(-1)r=(-1)nn!∑r=0n‍(-1)n-r(n-r)!=Dn.
One can also use our combinatorial interpretation of NM({(12,00),(12,01)},([k],{k-2,k-1})),n∣k0 to give a combinatorial proof of this fact. That is, it is well known that D1=0, D2=1 for n≥2Dn+1=nDn+nDn-1. In our case, we know that
(114)NM({(12,00),(12,01)},([k],{k-2,k-1})),n∣k0=(-1)n|{(a,L)∈Mn,0,n:ms(a,L)iseven}|.
Thus, we must show that Dn=|{(a,L)∈Mn,0,n:ms(a,L)iseven}|. Now if (a,L)∈Mn,0,n, then all the labels in L are -1 so that we can identify each element (a,L)∈Mn,0,n with just a permutation a=σ=σ1⋯σn∈Sn. Now consider a σ∈Sn+1 whose minimal sequence has even length. If σ1≠1, then clearly the minimal sequence of red(σ2⋯σn+1)∈Sn has the same length as the minimal sequence of σ. Vice versa, given τ1⋯τn∈Sn, let τ(i)=iτ1*⋯τn* be the permutation of Sn+1 such that red(τ1*⋯τn*)=τ. Clearly for i=2,…,n+1, τ(i) is a permutation in Sn+1 whose minimal sequences have the same length as the minimal sequence of τ. It follows that
(115)|{(a,L)∈Mn+1,0,n+1:ms(σ,L)iseven&σ1≠1}|=n|{(a,L)∈Mn,0,n:ms(a,L)iseven}|.Next suppose thatσ∈Sn+1 is such that σ1=1, and its minimal sequence has even length. Then we claim that red(σ3⋯σn+1) has a minimal sequence whose length has the same parity as the length of the minimal sequence of σ. That is, if 1 is an element of the minimal sequence of σ, then it must be the case that σ=12⋯(n+1) is the identity so that red(σ3⋯σn+1)=1⋯n-1 has minimal sequence of length n-1. If 1 is not in the minimal sequence of σ, then it cannot be the case that σ2 is in the minimal sequence of σ so that the lengths of the minimal sequences of σ and red(σ3⋯σn+1) are the same. Vice versa, given τ1⋯τn-1∈Sn-1, let τ(1,i)=1iτ1*⋯τn-1* be the permutation of Sn+1 such that red(τ1*⋯τn-1*)=τ. Clearly for i=2,…,n+1, τ(1,i) is a permutation in Sn+1 whose lengths of the minimal sequences have the same parity as the length of the minimal sequence of τ. It follows that
(116)|{(a,L)∈Mn+1,0,n+1:ms(σ,L)iseven
andσ1=1}|=n|{(a,L)∈Mn-1,0,n-1:ms(a,L),iseven}|
Hence, |{(a,L)∈Mn+1,0,n+1:ms(σ,L)iseven| satisfies the same recursion as the recursion for Dn.Finally, it is not difficult to see that(117)NM({(12,00),(12,01)},([k],{k-2,k-1})),n∣k1=NM({(12,00),(12,01)},([k],{k-2,k-1})),n+1∣k0.
To prove this, we will construct a bijection θ:Mn,1,n→Mn+1,0,n+1 which has the property that for all (a,L)∈Mn,1,n, ms(a,L) and ms(θ(a,L)) have the same parity. Now suppose we are given an (a,L)∈Mn,1,n where a=a1⋯an and L=L1⋯Ln. Then is must be the case that there is a unique j such that Lj=x. Let θ(a,L)=(a′,L′)=(a1+1,…,aj-1+1,1,aj+1,…,an+1,(-1)n+1). That is, (a′,L′) arises from (a,L) by inserting 1 just before the element of a that is marked with x and adding 1 to all the elements of a and removing the x and replacing it with -1 and labeling 1 with -1. It is easy to see that θ is a bijection. Thus, all we need to do is to show that for all (a,L)∈Mn,1,n, ms(a,L) and ms(θ(a,L)) have the same parity. The minimal sequence of (a,L) does not contain aj. In (a′,L′), the minimal sequence does not contain aj′=aj-1+1>1 since 1=min([n+1]-{a1′,…,aj-2′}). Now if the minimal sequence of (a,L) does not contain aj+1, then it is easy to see that the minimal sequence of (a′,L′) does not contain aj+2′ which means that the lengths of the minimal sequences of (a,L) and (a′,L′) are the same. So suppose that the minimal sequence of (a,L) is aj+1⋯an. Then there are two cases. Namely, either (i) aj=min([n]-{a1,…,aj-1}) in which case the minimal sequence of (a′,L′) is 1,aj+1,aj+1+1,…,an+1 or (ii) aj≠min([n]-{a1,…,aj-1}) in which case the minimal sequence of (a′,L′) is aj+1+1,…,an+1. Hence in all cases, the lengths of the minimal sequences of (a,L) and (a′,L′) have the same parity. Thus, θ shows that
(118)|{(a,L)∈Mn,1,n:ms(σ,L)iseven}|=|{(a,L)∈Mn+1,0,n+1:ms(σ,L)iseven}|,
which by (109) establishes (117).


## 4.1.NMn,kΥr

For example, ifΥ=Υr={(12,00),(12,01)}, NMn,kΥr equals the number of (σ,ϵ)∈Ck≀Sn such that ris((σ,ϵ))=0. Table 1 gives initial values of NMn,kΥr.Table 1
NM
n
,
k
Υ
r for k,n≤5.
n
=
0
n
=
1
n
=
2
n
=
3
n
=
4
n
=
5
k
=
2
1
2
5
16
65
326
k
=
3
1
3
12
64
441
3771
k
=
4
1
4
22
164
1589
19136
k
=
5
1
5
35
335
4180
64876Several of these sequences appear in the OEIS [16]. In fact, we can easily calculate NMn,kΥr as a polynomial in k. For example, we have
(76)NM0,kΥr=1,NM1,kΥr=k,NM2,kΥr=12k(3k-1),NM3,kΥr=16k(19k2-15k+2),NM4,kΥr=124k(211k3-270k2+89k-6),NM5,kΥr=1120k(3651k4-6490k3+3585k2-650k+24).We point out thatNM2,kΥr forms the familiar sequence of pentagonal numbers (A000326 in [16]). Other previously documented sequences appearing in Table 1 include the structured octagonal antiprism numbers (A100184 in [16]) for NM3,kΥr, as well as NMn,2Υr (A000522 in [16]), for which there are many known combinatorial interpretations, including the total number of arrangements of all subsets of [n].We conjecture that forn≥1 and k≥2, NMn,kΥr is always of the form (1/n!)kPn(k) where Pn(k) is a polynomial of degree n-1 whose leading coefficient is positive and such that signs of the remaining coefficients alternate. Now we can prove that NMn,kΥr is always of the form (1/n!)kPn(k) where Pn(k) is a polynomial of degree n-1 and the term of degree 1 in k is (-1)n-1(n-1)!. That is, for any k≥2, if we set p=q=z0=⋯=zk-1=1 and x=0 in the proof of Theorem 10 and use the fact that mp(Υr,([k],[k])),n(1,1;1,…,1)=(n+k-1n), we see that
(77)n!Γ-(hn)=NMn,kΥr,
where
(78)Γ-(en)=(n+k-1n)n!=(k)↑n(n!)2.
Here we let (q)↑0=1 and (q)↑n=q(q+1)⋯(q+n-1) for n≥1. But then
(79)n!Γ-(hn)=n!∑μ⊢n‍(-1)n-ℓ(μ)Bμ,nΓ-(eμ)=1n!∑μ⊢n‍(-1)n-ℓ(μ)Bμ,n(nμ1,…,μℓ(μ))2∏i=1ℓ(μ)‍(k)↑μi=1n!∑μ⊢n‍(-1)n-ℓ(μ)∑(b1,…,bℓ(μ))∈ℬμ,n‍(nb1,…,bℓ(μ))2∏i=1ℓ(μ)‍(k)↑bi.
It is easy to see that the right-hand side of (79) is a polynomial of degree n, and the lowest degree term comes from the term (-1)n-1k(k+1)⋯(k+n-1) corresponding to μ=(n) which is of the form (-1)n-1(n-1)!k+O(k2). On the other hand, the highest-degree term arises when we pick the highest power of k from the products ∏i=1ℓ(μ)‍(k)↑bi which is clearly just kn. It follows that the highest power of k in An,kΥr is just
(80)1n!∑μ⊢n‍(-1)n-ℓ(μ)∑(b1,…,bℓ(μ))∈ℬμ,n‍(nb1,…,bℓ(μ))2.We can give a combinatorial interpretation to(81)Fn=∑μ⊢n‍(-1)n-ℓ(μ)∑(b1,…,bℓ(μ))∈ℬμ,n‍(nb1,…,bℓ(μ))2.
That is, we will show that Fn counts the number of pairs of permutations (α,β)∈Sn×Sn such that if α=α1⋯αn and β=β1,…,βn, then there is no 1≤i≤n-1 such that αi<αi+1 and βi<βi+1. That is, Fn is the number of pairs (α,β)∈Sn×Sn that have no common rises. To prove our claim, we can give a combinatorial interpretation to the right-hand side of (81). That is, if we start with a brick tabloid T=(b1,…,bℓ(μ)), then by Lemma 8, we can interpret (nb1,…,bℓ(μ))2 as all ways to fill the cells of T with pairs of permutations (α,β) such that both α and β are increasing in each brick. Then we interpret (-1)n-ℓ(μ) as labeling each cell of T which is not at the end of brick with -1 and labeling each cell which is at the end of the brick with 1. We let 𝒪ℛn denote the set of all filled brick tabloids constructed in this way. For example, Figure 6 pictures a typical element of 𝒪ℛ11. If O∈𝒪ℛn, we define the sign of O, sgn(O), as the product of labels at the top of the cells of O.Figure 6
A brick tabloid of shape(12) and type (1,1,2,3,5).We now can define a sign-reversing involutionIr on 𝒪ℛn.To defineIr, suppose that O∈𝒪ℛn and α and β are the two permutations in O with α on the bottom and β on the top. Then we scan the cells of O from left to right looking for the leftmost cell t such that either (i) t is labeled with -1 or (ii) t is at the end of a brick bj, and the brick bj+1 immediately following bj has the property that both α and β are strictly increasing in all the cells corresponding to bj and bj+1. In case (i), Ir(O) is the result of replacing the brick b in O 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 changing the label of cell t from -1 to 1. In case (ii), Ir(O) is the result of replacing the bricks bj and bj+1 in T by a single brick b and changing the label of cell t from 1 to -1. If neither case (i) or case (ii) applies, then we let I(O)=O. For example, if O is the element of ℱ12 pictured in Figure 6, then Ir(O) is pictured in Figure 7.Figure 7
I
r
(
O
) for O in Figure 6.It is easy to see thatIr is a weight-preserving sign-reversing involution and, hence, Ir shows that
(82)Fn=∑O∈𝒪ℛn,Ir(O)=O‍sgn(O).Thus, we must examine the fixed pointsO of Ir. First there can be no -1 labels in O so that all bricks in O must be of size 1 and sgn(O)=1. Moreover, if bj and bj+1 are two consecutive bricks in T and t is the last cell of bj, then it cannot be the case that αt<αt+1 and βt<βt+1 where α and β are the two permutations in O since otherwise we could combine bj and bj+1. Thus, (α,β) is a pair of permutations in Sn with no common rises. Vice versa, if (α,β) is a pair of permutations in Sn with no common rises, we can create a fixed point O of Ir by having α be the bottom permutation of O, having β be the top permutation of O, and having all bricks be of size 1. For example, Figure 8 pictures a fixed point of Ir.Figure 8
A fixed point ofIr.It follows thatFn is the number of pairs (α,β)∈Sn2 with no common rises so that the leading coefficient of Ak,rΥr is Fn/n!.


## 4.2.NMn,kΥs

ForΥs={(12,01)}, NMn,kΥs equals the number of (σ,ϵ)∈Ck≀Sn such that sris((σ,ϵ))=0. Table 2 gives initial values of NMn,kΥs.Table 2
NM
n
,
k
Υ
s for k,n≤5.
n
=
0
n
=
1
n
=
2
n
=
3
n
=
4
n
=
5
k
=
2
1
2
7
36
246
2100
k
=
3
1
3
15
109
1050
12630
k
=
4
1
4
26
244
3031
47000
k
=
5
1
5
40
460
6995
132751In fact, we can easily calculateNMn,kΥs as a polynomial in k. For example, we have
(83)NM0,kΥs=1,NM1,kΥs=k,NM2,kΥs=12k(3k+1),NM3,kΥs=16k(19k2+15k+2),NM4,kΥs=124k(211k3+270k2+89k+6),NM5,kΥs=1120k(3651k4+6490k3+3585k2+650k+24).
We point out that NM2,kΥs forms the familiar sequence of the second pentagonal numbers (A005449 in [16]). None of the other rows or columns in Table 2 matched any previously known sequences in [16].We conjecture that forn≥1 and k≥2, NMn,kΥs is always of the form (1/n!)kRn(k) where Rn(k) is a polynomial of degree n-1 with positive coefficients. In fact, we see that the coefficients of Pn,k and Rn,k are the same up to a sign for all n. we can prove this. That is, for any k≥2, if we set p=q=z0=⋯=zk-1=1 and x=0 in the proof of Theorem 10 and use the fact that mp(Υs,([k],[k])),n=(kr), we see that
(84)n!Γ-s(hn)=NMn,kΥs,
where
(85)Γ-s(en)=(kn)n!=(k)↓n(n!)2.
Here we let (q)↓0=1 and (q)↓n=q(q-1)⋯(q-n+1) for n≥1. But then
(86)n!Γ-s(hn)=n!∑μ⊢n‍(-1)n-ℓ(μ)Bμ,nΓ-(eμ)=1n!∑μ⊢n‍(-1)n-ℓ(μ)Bμ,n(nμ1,…,μℓ(μ))2∏i=1ℓ(μ)‍(k)↓μi=1n!∑μ⊢n‍(-1)n-ℓ(μ)∑(b1,…,bℓ(μ))∈ℬμ,n‍(nb1,…,bℓ(μ))2∏i=1ℓ(μ)‍(k)↓bi.Since for anyn≥1, (k)↓n=(-1)n(k)↑n, it is easy to see that the right-hand side of (86) is obtained from the right-hand side of (79) by replacing k by -k and multiplying by (-1)n. Thus, conjecture that Rn(k) has positive coefficients is equivalent to the conjecture that the signs of the coefficients of Pn(k) alternate.


## 4.3.NMn,kΥw

ForΥw={(12,00)}, NMn,kΥw equals the number of (σ,ϵ)∈Ck≀Sn such that wris((σ,ϵ))=0. Table 3 gives initial values of NMn,kΥw.Table 3
NM
n
,
k
Υ
w for k,n≤5.
n
=
0
n
=
1
n
=
2
n
=
3
n
=
4
n
=
5
k
=
2
1
2
6
26
150
1082
k
=
3
1
3
15
111
1095
13503
k
=
4
1
4
28
292
4060
70564
k
=
5
1
5
45
605
10845
243005In fact, we can easily calculateNMn,kΥw as a polynomial in k. For example, we have
(87)NM0,kΥw=1,NM1,kΥw=k,NM2,kΥw=k(2k-1),NM3,kΥw=k(6k2-6k+1),NM4,kΥw=k(24k3-36k2+14k-1),NM5,kΥw=k(120k4-240k3+150k2-30k+1).
We point out that NM2,kΥw forms the familiar sequence of hexagonal numbers (A000384 in [16]). Additionally, NMn,2Υw matches the sequence counting the number of necklaces on the set of labeled beads (A000629 in [16]). In fact, in this case, we can give a completely combinatorial interpretation of the coefficients of NMn,kΥw as a polynomial in k. Let Ostpn(n) denote the set of ordered set partitions of {1,2,…,n}. For any set partition π∈Ostpn(n), let ℓ(π) denote the number of parts of π. Then we claim that
(88)NMn,kΥw=∑π∈Ostpn(n)‍(-1)n-ℓ(π)kℓ(π),
so that the coefficient of kj in NMn,kΥw is equal to (-1)n-jj!Sn,j where Sn,j is the Stirling number of the second kind which is the number of set partitions of {1,…,n} into j parts. That is, for any k≥2, if we set p=q=z0=⋯=zk-1=1 and x=0 in Theorem 10 and use the fact that mpΥw,n=k for all n≥2, then we see that
(89)n!Γ-w(hn)=NMn,kΥw,
where
(90)Γ-w(en)=kn!.
But then
(91)n!Γ-s(hn)=n!∑μ⊢n‍(-1)n-ℓ(μ)Γ-s(eμ)=n!∑μ⊢n‍(-1)n-ℓ(μ)∑(b1,…,bℓ(μ))∈ℬμ,n‍∏i=1ℓ(μ)‍kbi!=∑μ⊢n‍(-1)n-ℓ(μ)∑(b1,…,bℓ(μ))∈ℬμ,n‍(nb1,…,bℓ(μ))kℓ(μ).
Since (nb1,…,bℓ(μ)) counts the number of ordered set partitions π=(π1,…,πℓ(μ)) such that |πj|=bj, it is easy to see that the right-hand side of (91) equals the right-hand side of (88).


## 4.4.NMn,kΥd

Recall thatΥd={(12,01),(12,10)}. Table 4 gives initial values of NMn,kΥd.Table 4
NM
n
,
k
Υ
d for k,n≤5.
n
=
0
n
=
1
n
=
2
n
=
3
n
=
4
n
=
5
k
=
2
1
2
6
26
150
1082
k
=
3
1
3
12
66
480
4368
k
=
4
1
4
20
132
1140
12324
k
=
5
1
5
30
230
2280
28280In fact, we can easily calculateNMn,kΥd as a polynomial in k. For example, we have
(92)NM0,kΥd=1,NM1,kΥd=k,NM2,kΥd=k2+k,NM3,kΥd=k3+4k2+k,NM4,kΥd=k4+11k3+11k2+k,NM5,kΥd=k5+26k4+66k3+26k2+k.
In this case, we will show that NMn,kΥd is just the Eulerian polynomial
(93)NMn,kΥd=∑σ∈Sn‍xdes(σ)+1.
That is, for any k≥2, if we set p=q=z0=⋯=zk-1=1 and x=0 in the proof of Theorem 10 and the fact that mp(Υd,([k],[k])),n=k(k-1)n-1, we see that
(94)n!Γ-U(hn)=NMn,kΥd,
where
(95)Γ-U(en)=k(k-1)n-1n!.
But then
(96)n!Γ-U(hn)=n!∑μ⊢n‍(-1)n-ℓ(μ)Bu,nΓ-U(eμ)=n!∑μ⊢n‍(-1)n-ℓ(μ)∑(b1,…,bℓ(μ))∈ℬμ,n‍∏i=1ℓ(μ)‍k(k-1)bi-1bi!=∑μ⊢n‍∑(b1,…,bℓ(μ))∈ℬμ,n‍(nb1,…,bℓ(μ))∏i=1ℓ(μ)‍k(1-k)bi-1.
Next we want to give a combinatorial interpretation to (96). For any brick tabloid T=(b1,…,bℓ(μ))∈ℬμ,n, we can interpret (nb1,…,bℓ(μ)) as the set of all fillings of T with a permutation σ∈Sn such that σ is increasing in each brick. We then interpret ∏j=1ℓ(μ)‍k(1-k)bj-1 as all ways of picking a label of the cells of each brick except the final cell with either an 1 or a -k and letting the label of the last cell of each brick be k. We let 𝒟n denote the set of all filled labeled brick tabloids that arise in this way. Thus, a C∈𝒟n consists of a brick tabloid T, a permutation σ∈Sn, and a labeling L of the cells of T with elements from {k,-k,1} such that(1)
σ is strictly increasing in each brick,(2)
the final cell of each brick is labeled withk,(3)
each cell which is not a final cell of a brick is labeled with1 or -k. We then define the weight w(C) of C to be the product of all the k labels in L and the sign sgn(C) of C to be the product of all the -1 labels in L. For example, if n=12, k=4, and T=(4,3,3,2), then Figure 9 pictures such a composite object C∈𝒟12 where w(C)=k7 and sgn(C)=-1.Figure 9
A composite objectC∈𝒟12.Thus,(97)n!Γ-U(hn)=∑C∈𝒟n‍sgn(C)w(C).Next we define a weight-preserving sign-reversing involutionJ:𝒟n→𝒟n. To define J(C), we scan the cells of C=(T,σ,L) from left to right looking for the leftmost cell t such that either (i) t is labeled with -k or (ii) t is at the end of a brick bj, and the brick bj+1 immediately following bj has the property that σ is strictly increasing in all the cells corresponding to bj and bj+1. In case (i), J(C)=(T′,σ′,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, σ=σ′, and L′ is the labeling that results from L by changing the label of cell t from -k to k. In case (ii), J(C)=(T′,σ′,L′) where T′ is the result of replacing the bricks bj and bj+1 in T by a single brick b, σ=σ′, and L′ is the labeling that results from L by changing the label of cell t from k to -k. If neither case (i) or case (ii) applies, then we let J(C)=C. For example, if C is the element of 𝒟12 pictured in Figure 9, then J(C) is pictured in Figure 10.Figure 10
J
(
C
) for C in Figure 9.It is easy to see thatJ is a weight-preserving sign-reversing involution, and hence J shows that
(98)n!Γ-U(hn)=∑C∈𝒟n,J(C)=C‍sgn(C)w(C).Thus, we must examine the fixed pointsC=(T,σ,L) of J. First there can be no -k 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 it cannot be the case that σt<σt+1 since otherwise we could combine bj and bj+1. For any such fixed point, we associate an element (σ,w)∈Ck≀Sn. For example, a fixed point of I is pictured in Figure 11 where
(99)σ=234116910181257.
It follows that if cell t is at the end of a brick which is not the last brick, then σt>σt1. However, if v is a cell which is not at the end of a brick, then our definitions force σv<σv+1. Since each such cell v must be labeled with an 1, it follows that sgn(C)w(C)=kdes(σ)+1 where the +1 comes from the fact that the last cell of the last brick is also labeled with k. Vice versa, if σ∈Sn, then we can create a fixed point C=(T,σ,L) by having the bricks in T end at cells of the form t where σt>σt+1 and labeling each such cell with k, labeling the last cell with k, and labeling the remaining cells with 1. Thus, we have shown that
(100)n!Γ-U(hn)=∑σ∈Sn‍kdes(σ)+1
as desired.Figure 11
A fixed point ofJ.


## 4.5.NM(Υ,A→),n

Next we consider another case where we can show that as a polynomial ink, NM(Υ,A→),n has coefficients whose signs alternate. That is, it follows from (64) that
(101)NM({(12,00),(12,01)},([k],{k-2,k-1})),n=n!∑r=0n‍(k-1)r(n-r)!=∑r=0n‍(n)↓r(k-1)r.
We can easily calculate NM({(12,00),(12,01)},([k],{k-2mk-1})),n as a polynomial in k. For example, we have
(102)NM({(12,00),(12,01)},([k],{k-2,k-1})),0=1,NM({(12,00),(12,01)},([k],{k-2,k-1})),1=k,NM({(12,00),(12,01)},([k],{k-2,k-1})),2=2k2-2k+1,NM({(12,00),(12,01)},([k],{k-2,k-1})),3=6k3-12k2+9k-2,NM({(12,00),(12,01)},([k],{k-2,k-1})),4=24k4-72k3+84k2-44k+9,NM({(12,00),(12,01)},([k],{k-2,k-1})),5=120k5-480k4+780k3+-640k2+265k-44.Thus, we see that the signs of the polynomialNM({(12,00),(12,01)},([k],{k-2,k-1})),n seem to alternate and that the leading term seems to be n!kn. We can prove both of these facts. Taking the coefficient of ks on both sides of (101), we see that
(103)NM({(12,00),(12,01)},([k],{k-2,k-1})),n∣ks=∑r=sn‍(n)↓r(rs)(-1)r-s.Now we can give a combinatorial interpretation to the right-hand side of (103) as follows. First for each r, we interpret (n)↓r as the number of ways to pick a sequence a1⋯ar of pairwise distinct elements from [n]. Then we interpret (rs) as picking s of the elements which we indicate by putting an x above each of the s elements picked. Finally, we interpret (-1)r-s as placing -1 above the elements in the sequence. We let Mn,s,r denote the set of all labeled sequences constructed in this way. For example, if n=10, s=3, and r=6, then the following labeled sequence would be in M10,4,6:
(104)(a,L)=-1x-1-1xx6310458.
Given a labeled sequence (a,L)∈Mn,s,r, we let the sign of (a,L), sgn(a,L), be the product of the -1 labels in L. We let Mn,s=⋃r=sn‍Mn,s,r. Then it is easy to see that
(105)NM({(12,00),(12,01)},([k],{k-2,k-1})),n∣ks=∑r=sn‍(n)↓r(rs)(-1)r-s=∑(a,L)∈Mn,s‍sgn(a,L).Given a sequence(a,L)=(a1⋯ar,L1⋯Lr), we say that the minimal sequence of (a,L) is the longest string atat+1⋯ar such that for all j=t,…,r, aj=min([n]-{a1,…,aj-1}) and Li=-1 for j=t,…,r. The minimal sequence for (a,L) might be empty. For example, it could be the last label Lr=x or it could be that ar≠min([n]-{a1,…,ar-1}). We let ms(a,L) denote the length of the minimal sequence of (a,L). For example, the minimal sequence of
(106)(a,L)=-1xxx-1-16310458
is empty so that ms(a,L)=0. The minimal sequence of
(107)(a′,L′)=-1xxx-1-11310425
is 25 so that ms(a,L)=2.Now suppose that(a,L)∈Mn,s,r is such that a=a1⋯ar, L=L1⋯Lr, and its minimal sequence is empty. Let b1<⋯<bn-r be the elements of [n]-{a1,…,ar}. Then we define the minimal sequence chain of (a,L) to be (a(r),L(r)),(a(r+1),L(r+1)),…,(a(n),L(n)) where (a(r),L(r))=(a,L) and (a(r+p),L(r+p))=(a1⋯arb1⋯bp,L1⋯Lr(-1)p) for 1≤p≤n-r. Note that the signs of the elements of a minimal sequence chain of (a,L) alternate. Thus, if the minimal sequence chain of (a,L) is of even length, then ms(a(n),L(n)) is odd, and the sum of the signs of elements in the minimal sequence chain of (a,L) is 0. If the minimal sequence chain of (a,L) is of odd length, then ms(a(n),L(n)) is even, and the sum of the signs of elements in the minimal sequence chain of (a,L) is sgn(a(n),L(n)). Clearly every element of Mn,r is an element of a unique minimal sequence chain for some (a,L)∈Mn,s whose minimal sequence is empty so that
(108)∑(a,L)∈Mn,s‍sgn(a,L)=∑(a,L)∈Mn,s,n,ms(a,L)iseven‍sgn(a,L)=(-1)n-s|{(a,L)∈Mn,s,n:ms(a,L)iseven}|.
Thus, we have shown that
(109)NM({(12,00),(12,01)},([k],{k-2,k-1})),n∣ks=(-1)n-s|{(a,L)∈Mn,s,n:ms(a,L)iseven}|.
This shows that as a polynomial in k, NM({(12,00),(12,01)},([k],{k-2,k-1})),n is sign alternating starting with the leading term n!kn. That is, by (109),
(110)NM({(12,00),(12,01)},([k],{k-2,k-1})),n∣kn=|{(a,L)∈Mn,n,n:ms(a,L)iseven}|.
But the elements of Mn,n,n have no -1 labels since every element of Mn,n,n has an empty minimal sequences and, hence, |{(a,L)∈Mn,n,n:ms(a,L)iseven}|=n!.We can also compute several other coefficients ofNM({(12,00),(12,01)},([k],{k-2,k-1})),n as a polynomial in k. For example, we can explicitly compute the coefficient of kn-1 in NM({(12,00),(12,01)},([k],{k-2,k-1})),n. Note that
(111)NM({(12,00),(12,01)},([k],{k-2,k-1})),n∣kn-1=-|{(a,L)∈Mn,n-1,n:ms(a,L)iseven}|.
Now an element (a,L)∈Mn,n-1,n has exactly one label which is -1. If Ln=-1, then the last element of a is automatically its minimal sequence so that it is not counted in |{(a,L)∈Mn,n-1,n:ms(a,L)iseven}|. Thus, |{(a,L)∈Mn,n-1,n:ms(a,L)iseven}| counts all (a,L)∈Mn,n-1,n such that Ln=x which is clearly (n-1)n!.We claim that(112)NM({(12,00),(12,01)},([k],{k-2,k-1})),n∣k0=(-1)nDn,
where Dn is the number of derangements of Sn, that is, the number of permutations with no fixed points. It is well known that Dn=n!∑k=0n‍(-1)k/k! for n≥1. But by (105),
(113)NM({(12,00),(12,01)},([k],{k-2,k-1})),n∣k0=∑r=0n‍(n)↓r(-1)r=(-1)nn!∑r=0n‍(-1)n-r(n-r)!=Dn.
One can also use our combinatorial interpretation of NM({(12,00),(12,01)},([k],{k-2,k-1})),n∣k0 to give a combinatorial proof of this fact. That is, it is well known that D1=0, D2=1 for n≥2Dn+1=nDn+nDn-1. In our case, we know that
(114)NM({(12,00),(12,01)},([k],{k-2,k-1})),n∣k0=(-1)n|{(a,L)∈Mn,0,n:ms(a,L)iseven}|.
Thus, we must show that Dn=|{(a,L)∈Mn,0,n:ms(a,L)iseven}|. Now if (a,L)∈Mn,0,n, then all the labels in L are -1 so that we can identify each element (a,L)∈Mn,0,n with just a permutation a=σ=σ1⋯σn∈Sn. Now consider a σ∈Sn+1 whose minimal sequence has even length. If σ1≠1, then clearly the minimal sequence of red(σ2⋯σn+1)∈Sn has the same length as the minimal sequence of σ. Vice versa, given τ1⋯τn∈Sn, let τ(i)=iτ1*⋯τn* be the permutation of Sn+1 such that red(τ1*⋯τn*)=τ. Clearly for i=2,…,n+1, τ(i) is a permutation in Sn+1 whose minimal sequences have the same length as the minimal sequence of τ. It follows that
(115)|{(a,L)∈Mn+1,0,n+1:ms(σ,L)iseven&σ1≠1}|=n|{(a,L)∈Mn,0,n:ms(a,L)iseven}|.Next suppose thatσ∈Sn+1 is such that σ1=1, and its minimal sequence has even length. Then we claim that red(σ3⋯σn+1) has a minimal sequence whose length has the same parity as the length of the minimal sequence of σ. That is, if 1 is an element of the minimal sequence of σ, then it must be the case that σ=12⋯(n+1) is the identity so that red(σ3⋯σn+1)=1⋯n-1 has minimal sequence of length n-1. If 1 is not in the minimal sequence of σ, then it cannot be the case that σ2 is in the minimal sequence of σ so that the lengths of the minimal sequences of σ and red(σ3⋯σn+1) are the same. Vice versa, given τ1⋯τn-1∈Sn-1, let τ(1,i)=1iτ1*⋯τn-1* be the permutation of Sn+1 such that red(τ1*⋯τn-1*)=τ. Clearly for i=2,…,n+1, τ(1,i) is a permutation in Sn+1 whose lengths of the minimal sequences have the same parity as the length of the minimal sequence of τ. It follows that
(116)|{(a,L)∈Mn+1,0,n+1:ms(σ,L)iseven
andσ1=1}|=n|{(a,L)∈Mn-1,0,n-1:ms(a,L),iseven}|
Hence, |{(a,L)∈Mn+1,0,n+1:ms(σ,L)iseven| satisfies the same recursion as the recursion for Dn.Finally, it is not difficult to see that(117)NM({(12,00),(12,01)},([k],{k-2,k-1})),n∣k1=NM({(12,00),(12,01)},([k],{k-2,k-1})),n+1∣k0.
To prove this, we will construct a bijection θ:Mn,1,n→Mn+1,0,n+1 which has the property that for all (a,L)∈Mn,1,n, ms(a,L) and ms(θ(a,L)) have the same parity. Now suppose we are given an (a,L)∈Mn,1,n where a=a1⋯an and L=L1⋯Ln. Then is must be the case that there is a unique j such that Lj=x. Let θ(a,L)=(a′,L′)=(a1+1,…,aj-1+1,1,aj+1,…,an+1,(-1)n+1). That is, (a′,L′) arises from (a,L) by inserting 1 just before the element of a that is marked with x and adding 1 to all the elements of a and removing the x and replacing it with -1 and labeling 1 with -1. It is easy to see that θ is a bijection. Thus, all we need to do is to show that for all (a,L)∈Mn,1,n, ms(a,L) and ms(θ(a,L)) have the same parity. The minimal sequence of (a,L) does not contain aj. In (a′,L′), the minimal sequence does not contain aj′=aj-1+1>1 since 1=min([n+1]-{a1′,…,aj-2′}). Now if the minimal sequence of (a,L) does not contain aj+1, then it is easy to see that the minimal sequence of (a′,L′) does not contain aj+2′ which means that the lengths of the minimal sequences of (a,L) and (a′,L′) are the same. So suppose that the minimal sequence of (a,L) is aj+1⋯an. Then there are two cases. Namely, either (i) aj=min([n]-{a1,…,aj-1}) in which case the minimal sequence of (a′,L′) is 1,aj+1,aj+1+1,…,an+1 or (ii) aj≠min([n]-{a1,…,aj-1}) in which case the minimal sequence of (a′,L′) is aj+1+1,…,an+1. Hence in all cases, the lengths of the minimal sequences of (a,L) and (a′,L′) have the same parity. Thus, θ shows that
(118)|{(a,L)∈Mn,1,n:ms(σ,L)iseven}|=|{(a,L)∈Mn+1,0,n+1:ms(σ,L)iseven}|,
which by (109) establishes (117).


## 5. Further Research

An obvious question is to ask whether the results of this paper can be extended to patterns of length≥3. There are some partial results in this direction due to Duane and Remmel [21]. 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 in (σ,w) 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
(119)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∑‍wmp(τ,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 equal 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
(120)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).
Then Duane and Remmel [21] proved that (I) if red(u)=u and (τ,u) has the Ck≀Sn-minimal overlapping property, then
(121)∑n≥0‍tnn!∑(σ,w)∈Ck≀Sn‍x(τ,u)-mch(σ,u)pcoinv(σ)qinv(σ)z(w)=1×(1-((z0+⋯+zk-1)t+∑n≥1tn(j-1)+1[n(j-1)+1]p,q!(x-1)n×mp(τ,u),n(j-1)+1k(p,q,z0,…,zk-1)))-1,(II) if(τ,u)∈Ck≀Sj has the Ck≀Sn-exact match minimal overlapping property, then
(122)∑n≥0‍tnn!∑(σ,w)∈Ck≀Sn‍x(τ,u)-Emch(σ,u)pcoinv(σ)qinv(σ)z(w)=1×(1-((z0+⋯+zk-1)t+∑n≥1tn(j-1)+1[n(j-1)+1]q!(x-1)n×emp(τ,u),n(j-1)+1k(p,q,z0,…,zk-1)))-1.
Duane and Remmel’s proof of (I) and (II) works equally well for (Υ,A→)-matches.There are, however, several examples in the literature of generating functions for the number ofτ-matches in permutations where τ does not have the minimal overlapping property, and we have found some analogues of such results for Ck≀Sn. In addition, there are many formulas in the literature for the number of permutations that avoid certain patterns in permutations. We have found several examples of such formulas for the matching conditions for Ck≀Sn discussed in this paper. Such results will appear in subsequent papers.



---

*Source: 634823-2013-02-13.xml*