Séminaire Lotharingien de Combinatoire 54A (2007), Article B54At

GENERATING FUNCTIONS FOR STATISTICS ON C_{k} ≀ S_{n}

Anthony Mendes

Department of Mathematics California Polytechnic State University San Luis Obispo, CA 93407. USA

                       aamendes@calpoly.edu

and

Jeffrey Remmel^{1}

Department of Mathematics University of California, San Diego La Jolla, CA 92093-0112. USA

                         jremmel@ucsd.edu

Dedicated to Adriano Garsia on the occasion of his 78-th Birthday.

Abstract. Foata and Han [Adv. in Appl. Math. 18 (1997), 489–509; Electron. J. Combin. 4 (1997), Article #R9] proved some remarkable generating functions for statistics on the hyperoctahedral group B_{n}. These generating functions can be specialized to give a large number of generating functions for permutation statistics appearing in the literature. In this paper, we give a new proof of Foata and Han’s result by defining a homomorphism on the ring of symmetric functions and applying it to a simple symmetric function identity. Our methods easily extend to derive several natural extensions of Foata and Han’s generating functions. In particular, we show that there exists a natural family of generating functions for permutation statistics over wreath products C_{k} ≀ S_{n} of cyclic groups C_{k} with the symmetric group S_{n} which can be viewed as generalizations of the Foata-Han generating functions. We also prove some new generating functions for the Foata-Han statistics for tuples of permutations of B_{n} or C_{k} ≀ S_{n} whose common descent set contain a final sequence of at least s or whose common descent set contain a final sequence of exactly size s.

1. Introduction and Preliminaries

Let G be a finite group and S_{n} the symmetric group on n letters. This work is the continuation of a series of papers that show how various generating functions for permutation statistics on wreath products G ≀ S_{n} can be derived by applying appropriate homomorphisms on the ring of symmetric functions to simple symmetric function identities.

1 Partially supported by NSF Grant DMS 0400507 and DMS 0502858.

This idea was first used by Brenti [Bre93]. Beck and Remmel then gave combinatorial proofs of Brenti’s results by exploiting combinatorial interpretations of the entries of the transitions matrices between bases of symmetric functions [Bec93, BR95]. This combinatorial approach allowed for q-analogues of Brenti’s results as well as generalizations of Brenti’s results for the hyperoctahedral group B_{n}. Wagner extended these results to study permutation statistics on groups of the form C_{k} ≀ S_{n} where C_{k} is the cyclic group of order k [Wag00]. Since then, there has been a series of papers that have developed these methods, see [LR06, MRa, MR06]. A systematic treatment of these ideas is currently being developed by the authors [MRb].

The goal of this paper is to show how such methods can be used to prove a remarkable generating function for permutation statistics on the hyperoctahedral group B_{n} first proved by Foata and Han [FH97a, FH97b]. Foata and Han’s generating function is significant because it can be specialized to give a large number of generating function for permutation statistics for S_{n} and B_{n}. Their paper includes a flow chart recording the many different specializations.

Our proof has a number of important features.

• It can be easily extended to give an entire family of extensions of the Foata-Han generating function to groups of the form C_{k} ≀ S_{n} for k ≥ 2 (B_{n} is isomorphic to C_{2} ≀ S_{n}).

• It allows us to define a new set of permutation statistics on B_{n} that have the same distribution as the permutation statistics that appear in the Foata-Han result.

• It provides an archetypal example of a result found in the literature with the property that the homomorphism required in our proof can be read directly from the generating function itself. Then, once one has proved the given generating function by our methods, it can immediately be generalized to give a number of new results.

• It exploits a symmetric function identity that involves a new class of symmetric functions which have properties similar to the power symmetric functions. Special cases of these symmetric functions have appeared in the work of Langley and Remmel [LR06] and Mendes and Remmel [MR06].

• Finally, as with many other cases of our method, once we have proved a given result, we can modify the combinatorics involved in the proof to prove new results. In this case, we will show that we can easily modify our proof to give generating functions for tuples of permutations in C_{k} ≀ S_{n} whose final common decreasing sequence has size at least s or exactly s for any s ≥ 2, relative to the statistics involved in our generalization of the Foata-Han result. These results are completely new even in the case where k = 2 and C_{k} ≀ S_{n} = B_{n}.

GENERATING FUNCTIONS FOR STATISTICS ON C_{k} ≀ S_{n} 3

The outline of this paper is as follows. In Section 2, we shall define the various permutation statistics for B_{n} that we shall use and state the Foata-Han result. In particular, we shall state a variation of the Foata-Han result which uses a more natural version of an inversion statistics than was originally used by Foata and Han. This result is new and does not follow from the previous results of Foata and Han. In Section 3, we shall define our new class of symmetric functions and prove a simple identity (5) involving our new class of symmetric functions to which will apply various homomorphisms defined on the ring of symmetric functions to derive our results. In Section 4, we shall define the homomorphism ξ which can be applied to the symmetric function identity (5) to yield both the Foata-Han generating function relative to their definition of inversions for signed permutations and our new generating function relative to a more natural definition of inversions for signed permutations. We shall give a very careful proof that ξ applied to (5) yields both generating functions since if one understands the proof in this case, then one can see that relatively simple variations of that proof will yield our family of extensions of these results to C_{k} ≀ S_{n} for any k ≥ 3 as well as the new generating functions for tuples of permutations in C_{k} ≀ S_{n} whose final common decreasing sequence has size at least s or exactly s for any s ≥ 2. The proof that we present in section 4 could be simplified if our goal was just to prove the results stated in section 2. However, the main goal of this paper is to prove the generalizations and extensions of the results stated in section 2 to the groups C_{k} ≀ S_{n}. The reader will see that the proof presented in section 4 is a template for the proofs of those generalizations and extensions. In Section 5, we extend our methods to give some new families of generating functions for permutation statistics on C_{k} ≀S_{n}. Some of the identities that we prove were first proved by Wagner [Wag] using the methods of Foata and Han. Finally, in Section 6, we shall use the combinatorics developed in Section 5 to prove a new class of generating functions for tuples of permutations in C_{k} ≀ S_{n} whose final common decreasing segment has size at least s or exactly s for any s ≥ 2.

2. Permutation Statistics and Generating Functions for B_{n}

Following Foata and Han, we shall think of an element of B_{n} as pair (σ, ϵ) where σ ∈ S_{n} and ϵ ∈ {x, y}^{n}. Then we define the following statistics on B_{n}.

We call i a descent of (σ, ϵ) if either

(i) ϵ(i) = ϵ(i + 1) and σ_{i} > σ_{i+1},

(ii) ϵ(i) = x and ϵ(i + 1) = y, or

(iii) i = n and ϵ(n) = x. Let Des(σ, ϵ) denote the set of descents (σ, ϵ) ∈ B_{n}.

A pair (i, j) is a FH-inversion (respectively FH-coinversion) of (σ, ϵ) if

(i) i < j, ϵ(i) = ϵ(j) and σ_{i} > σ_{j} (respectively σ_{i} < σ_{j}), or (ii) ϵ(i) = y and ϵ(j) = x, and σ_{i} > σ_{j}.

We say that a pair (i, j) is an inversion (respectively coinversion) of (σ, ϵ) if i < j and σ_{i} > σ_{j} (respectively σ_{i} < σ_{j}), i.e. we say that (i, j) is an inversion (respectively coinversion) of (σ, ϵ) if it is an inversion (respectively coinversion) of σ. In [FH97a, FH97b], Foata and Han used the term inversion and coinversion for what we are calling FH-inversion and FH-coinversion respectively. They did not consider the usual notion of inversion and coinversion as we have defined.

Next we consider the restriction of (σ, ϵ) to its x part σ_{ϵ|x}, the restriction of (σ, ϵ) to its y part σ_{ϵ|y}, and their inverses σ_{ϵ|x}^{−1} and σ_{ϵ|y}^{−1}. These are best understood with an example. Suppose

(σ, ϵ) = (6 2 7 4 3 1 5 8 9, x x y y y y x x x).

We may think of (σ, ϵ) as an array:

1 2 3 4 5 6 7 8 9
σ = 6 2 7 4 3 5 1 8 9
ϵ = x x y y y y x x x

Then σ_{ϵ|x} and σ_{ϵ|y} may be found by looking at the columns corresponding to the x’s and y’s, respectively:

\begin{aligned}& & 1 & 2 & 7 & 8 & 9 \\ σ_{ϵ|x} & = & 6 & 2 & 1 & 8 & 9 \end{aligned}  and  \begin{aligned}& & 3 & 4 & 5 & 6 \\ σ_{ϵ|y} & = & 7 & 4 & 3 & 5 \end{aligned} .

We will let ℓ(σ_{ϵ|x}) be the length of σ_{ϵ|x}. To find the inverses σ_{ϵ|x}^{−1} and σ_{ϵ|y}^{−1}, we take the arrays corresponding to σ_{ϵ|x} and σ_{ϵ|y}, interchange the numbers in each column, then reorder the columns so the numbers in the top row corresponding are increasing. In our case, the process would result in the following arrays:

\begin{aligned}& & 1 & 2 & 6 & 8 & 9 \\ σ_{ϵ|x}^{−1} & = & 7 & 2 & 1 & 8 & 9 \end{aligned}  and  \begin{aligned}& & 3 & 4 & 5 & 7 \\ σ_{ϵ|y}^{−1} & = & 5 & 4 & 6 & 3 \end{aligned} .

For any sequence τ = τ_{1} ⋯ τ_{n} of distinct integers, we define the usual notions of descents, rises, major index, comajor index, inversion and coinversions:

Des(τ) = {i < n : τ_{i} > τ_{i+1}},  Rise(τ) = {i < n : τ_{i} < τ_{i+1}},
des(τ) = |Des(τ)|,  rise(τ) = |Rise(τ)|,
maj(τ) = ∑_{i∈Des(τ)} i,  comaj(τ) = ∑_{i∈Rise(τ)} i,
inv(τ) = {(i, j) : 1 ≤ i < j ≤ n, τ_{i} > τ_{j}}, coinv(τ) = {(i, j) : 1 ≤ i < j ≤ n, τ_{i} < τ_{j}}.

In addition, we define

\overline{inv}(σ_{ϵ|x}, σ_{ϵ|y}) = |\{(i, j) : ϵ(i) = y, ϵ(j) = x, σ_{i} > σ_{j}\}|.

In our example, \overline{inv}(σ_{ϵ|x}, σ_{ϵ|y}) = 9. We can now give the following two statistics on elements (σ, ϵ) in B_{n}. Let

imaj(σ, ϵ) = maj(σ_{ϵ|x}^{−1}) + maj(σ_{ϵ|y}^{−1}) + \overline{inv}(σ_{ϵ|x}, σ_{ϵ|y}),  and
icomaj(σ, ϵ) = comaj(σ_{ϵ|x}^{−1}) + comaj(σ_{ϵ|y}^{−1}) + \overline{inv}(σ_{ϵ|x}, σ_{ϵ|y}).

Our definitions of FH-inversion, FH-coinversions, inversions and coinversions for elements (σ, ϵ) in B_{n} satisfy the following relationships:

F Hinv(σ, ϵ) = inv(σ_{ϵ|x}) + inv(σ_{ϵ|y}) + \overline{inv}(σ_{ϵ|x}, σ_{ϵ|y}),
F Hcoinv(σ, ϵ) = coinv(σ_{ϵ|x}) + coinv(σ_{ϵ|y}) + \overline{inv}(σ_{ϵ|x}, σ_{ϵ|y}),
inv(σ, ϵ) = inv(σ),  and
coinv(σ, ϵ) = coinv(σ).

We will write (σ^{(1)}, σ^{(2)}, …, σ^{(k)}; ϵ) for the sequence of elements (σ^{(1)}, ϵ), (σ^{(2)}, ϵ), …, (σ^{(k)}, ϵ) of B_{n} (the second elements of all pairs are the same). Define

Comdes((σ^{(1)}, ϵ), (σ^{(2)}, ϵ), …, (σ^{(k)}, ϵ)) = Comdes(σ^{(1)}, σ^{(2)}, …, σ^{(k)}; ϵ) = ⋂_{i} Des(σ^{(i)}, ϵ)

and

comdes((σ^{(1)}, ϵ), (σ^{(2)}, ϵ), …, (σ^{(2)}, ϵ)) = comdes(σ^{(1)}, σ^{(2)}, …, σ^{(k)}; ϵ)
= |Comdes(σ^{(1)}, σ^{(2)}, …, σ^{(k)}; ϵ)|.

Suppose we are given two sequences of variables, Q = (Q_{1}, …, Q_{L}) and q = (q_{1}, …, q_{ℓ}). We will use the following notation:

Q^{\binom{n}{2}} = Q\binom{n}{2}_{1} ⋯ Q\binom{n}{2}_{L},
(Q, Q)_{n} = ∏_{i=1}^{L}(Q_{i}, Q_{i})_{n},

(q, q)_{n} = ∏_{i=1}^{ℓ}(q_{i}, q_{i})_{n},  and

J(u, Q, q) = ∑_{n≥0} \frac{(−1)^{n}u^{n}Q^{\binom{n}{2}}}{(Q, Q)_{n} (q, q)_{n}}

where (a, q)_{0} = 1 and (a, q)_{n} = (1 − a)(1 − aq) ⋯ (1 − aq^{n−1}) for n > 0. The usual q-analogues of the factorial, binomial coefficients, and multinomial coefficients will be used:

[n]_{q} = q^{0} + ⋯ + q^{n−1} = \frac{1 − q^{n}}{1 − q} ,
[n]_{q}! = [1]_{q}[2]_{q} ⋯ [n]_{q} = \frac{(q, q)_{n}}{(1 − q)^{n}} ,
\left[{n \atop k}\right]_{q} = \frac{[n]_{q}!}{[k]_{q}![n − k]_{q}!} = \frac{(q, q)_{n}}{(q, q)_{k}(q, q)_{n−k}} ,  and

\left[{n \atop b_{1}, …, b_{k}}\right]_{q} = \frac{[n]_{q}!}{[b_{1}]_{q}! ⋯ [b_{k}]_{q}!} = \frac{(q, q)_{n}}{(q, q)_{b_{1}} ⋯ (q, q)_{b_{k}}} .

If Σ = (Σ^{(1)}, …, Σ^{(L)}) and σ = (σ^{(1)}, …, σ^{(ℓ)}) are sequences of permutations in S_{n} and ϵ ∈ {x, y}^{n}, we let

Q^{inv(Σ;ϵ)} = ∏_{i=1}^{L} Q_{i}^{inv(Σ^{(i)},ϵ)} and q^{inv(σ;ϵ)} = ∏_{i=1}^{ℓ} q_{i}^{inv(σ^{(i)},ϵ)}.  (1)

We may replace the “inv” in (1) with any other permutation statistic like “imaj”, “icomaj”, “FHinv”, etc.

If Σ = (Σ^{(1)}, …, Σ^{(L)}) and σ = (σ^{(1)}, …, σ^{(ℓ)}) are sequences in the symmetric group S_{n} and ϵ is a word of length n in the letters {x, y}, we will denote

(Σ^{(1)}, …, Σ^{(L)}, σ^{(1)}, …, σ^{(ℓ)}; ϵ)

as (Σ, σ; ϵ). The last definitions we will need to make before we can state the results of Foata and Han are as follows. Let

W_{n}^{(1)}(X, Y, t, Q, q) = ∑_{(Σ,σ;ϵ)} X^{ℓ(ϵ|x)}Y^{ℓ(ϵ|y)}t^{comdes(Σ,σ;ϵ)}Q^{F Hinv(Σ;ϵ)}q^{F Hcoinv(σ;ϵ)},
W_{n}^{(2)}(X, Y, t, Q, q) = ∑_{(Σ,σ;ϵ)} X^{ℓ(ϵ|x)}Y^{ℓ(ϵ|y)}t^{comdes(Σ,σ;ϵ)}Q^{inv(Σ;ϵ)}q^{coinv(σ;ϵ)},  and
W_{n}^{(3)}(X, Y, t, Q, q) = ∑_{(Σ,σ;ϵ)} X^{ℓ(ϵ|x)}Y^{ℓ(ϵ|y)}t^{comdes(Σ,σ;ϵ)}Q^{imaj(Σ;ϵ)}q^{icomaj(σ;ϵ)}

where the sums run over all ϵ ∈ {x, y}^{n} and all sequences (Σ^{(1)}, …, Σ^{(L)}, σ^{(1)}, …, σ^{(ℓ)}) ∈ S_{n}^{L+ℓ}. Foata and Han proved the following theorem.

Theorem 1. For i = 1 and i = 3,

∑_{n≥0} \frac{W_{n}^{(i)}(X, Y, t, Q, q)u^{n}}{(Q, Q)_{n}(q, q)_{n}} = \frac{(1 − t)J((1 − t)Xu; Q, q)}{−t + J((1 − t)uX; Q, q)J((1 − t)Y u; Q, q)}.

An immediately corollary of this theorem is that

W_{n}^{(1)}(X, Y, t, Q, q) = W_{n}^{(3)}(X, Y, t, Q, q).

Indeed, Foata and Han gave a bijection showing this fact by proving the following theorem.

Theorem 2. For all pairs of nonnegative integers L and ℓ, let Γ_{B_{n},L,ℓ} be the set of all (Σ, σ; ϵ) = (Σ^{(1)}, …, Σ^{(L)}, σ^{(1)}, …, σ^{(ℓ)}; ϵ) such that ϵ ∈ {x, y}^{n} and Σ^{(i)}, σ^{(j)} ∈ S_{n} for all i and j. Then there is a bijection Ψ_{n} : Γ_{B_{n},L,ℓ} → Γ_{B_{n},L,ℓ} such that if Ψ_{n}((Σ, σ; ϵ)) = (Σ′, σ′; ϵ′), then

ℓ(ϵ|x) = ℓ(ϵ′|x),
comdes(Σ, σ; ϵ) = comdes(Σ′, σ′; ϵ′),
imaj(Σ, ϵ) = F Hinv(Σ′; ϵ′)  and
icomaj(σ, ϵ) = F Hcoinv(σ′; ϵ′).

We shall see that the proof of Theorem 1 in section 4 can also be modified to give a proof of the following theorem which is a new result.

Theorem 3.

∑_{n≥0} \frac{W_{n}^{(2)}(X, Y, t, Q, q)u^{n}}{(Q, Q)_{n}(q, q)_{n}} = \frac{(1 − t)J((1 − t)Xu; Q, q)}{−t + J((1 − t)uX; Q, q)J((1 − t)Y u; Q, q)}.

3. Symmetric Functions

In this section, we shall give the necessary background on symmetric functions and the combinatorics of the entries of the transition matrix that we need before we can give our proofs of Theorems 1 and 3.

A symmetric polynomial p in the variables x_{1}, …, x_{N} is a polynomial over a field F of characteristic 0 with the property that

p(x_{1}, …, x_{N}) = p(x_{σ_{1}}, …, x_{σ_{N}})

Figure 1. A brick tabloid.

for all σ = σ_{1} ⋯ σ_{N} ∈ S_{N}. Let Λ^{N} be the ring of symmetric polynomials in x_{1}, …, x_{N} and Λ_{n}^{N} be the subset of Λ^{N} containing the homogeneous elements of degree n. Using the surjective ring homomorphism from Λ_{n}^{N+1} to Λ_{n}^{N} defined by taking x_{N+1} = 0, let Λ_{n} = \underleftarrow{lim}_{N} Λ_{n}^{N} for each n ≥ 0. Define Λ = ⨁_{n≥0} Λ_{n} to be the ring of symmetric functions over F. A symmetric function in the variables x_{1}, x_{2}, … may be thought of as a symmetric polynomial in an infinite number of variables.

For instance, the elementary symmetric function e_{n} = e_{n}(x_{1}, x_{2}, …) may be defined by

∑_{n≥0} e_{n}t^{n} = (1 + x_{1}t)(1 + x_{2}t) · · · .

Let λ = (λ_{1}, …, λ_{ℓ}) be an integer partition; that is, λ is a finite sequence of weakly increasing nonnegative integers. We will let ℓ(λ) denote the number of nonzero integers in λ. 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_{λ_{ℓ}}. It is well known that that {e_{λ} : λ is a partition} is a basis for Λ.

The homogeneous symmetric function h_{n} = h_{n}(x_{1}, x_{2}, …) is defined such that

∑_{n≥0} h_{n}t^{n} = \frac{1}{1 − x_{1}t} · \frac{1}{1 − x_{2}t} · · · .

Therefore,

∑_{n≥0} h_{n}t^{n} = \frac{1}{1 − x_{1}t} · \frac{1}{1 − x_{2}t} ⋯ = ((1 − x_{1}t)(1 − x_{2}t) ⋯)^{−1} = (∑_{n≥0} e_{n}(−t)^{n})^{−1} . (2)

The coefficient of the homogeneous symmetric functions when written in terms of the elementary symmetric function basis is a sum of combinatorial objects. A rectangle of height 1 and length n chopped into “bricks” of lengths found in the partition λ is known as a brick tabloid of shape (n) and type λ. One brick tabloid of shape (9) and type (1, 1, 2, 5) is displayed in Figure 1.

Let B_{λ,n} be the number of such objects. Through simple recursions stemming from (2), Eğecioğlu and Remmel proved in [ER91] that

h_{n} = ∑_{λ⊢n}(−1)^{n−ℓ(λ)}B_{λ,n}e_{λ}.  (3)

A large number of generating functions for various statistics are the result of applying an appropriate homomorphism to (3), see [Men04]. However to prove Theorems 3 and 1 and their extensions, we will need to have an increased amount of flexibility than is available in the relationship between the homogeneous and elementary symmetric functions. To this end, we define the following class of symmetric functions.

Let ν be a function which maps the set of nonnegative integers into the field F. Recursively define p_{n,ν} ∈ Λ_{n} by setting p_{0,ν} = 1 and letting

p_{n,ν} = (−1)^{n−1}ν(n)e_{n} + ∑_{k=1}^{n−1}(−1)^{k−1}e_{k}p_{n−k,ν}

for all n ≥ 1. By multiplying series, this means that

(∑_{n≥0}(−1)^{n}e_{n}t^{n}) (∑_{n≥1} p_{n,ν}t^{n}) = ∑_{n≥1} (∑_{k=0}^{n−1} p_{n−k,ν}(−1)^{k}e_{k}) t^{n} = ∑_{n≥1}(−1)^{n−1}ν(n)e_{n}t^{n},

where the last equality follows from the definition of p_{n,ν}. Therefore,

∑_{n≥1} p_{n,ν}t^{n} = \frac{∑_{n≥1}(−1)^{n−1}ν(n)e_{n}t^{n}}{∑_{n≥0}(−1)^{n}e_{n}t^{n}}  (4)

or, equivalently,

1 + ∑_{n≥1} p_{n,ν}t^{n} = \frac{1 + ∑_{n≥1}(−1)^{n}(e_{n} − ν(n)e_{n})t^{n}}{∑_{n≥0}(−1)^{n}e_{n}t^{n}} .  (5)

When taking ν(n) = 1 for all n ≥ 1, (5) becomes

1 + ∑_{n≥1} p_{n,1}t^{n} = 1 + \frac{∑_{n≥1}(−1)^{n−1}e_{n}t^{n}}{∑_{n≥0}(−1)^{n}e_{n}t^{n}} = \frac{1}{∑_{n≥0}(−1)^{n}e_{n}t^{n}} = 1 + ∑_{n≥1} h_{n}t^{n}

which implies p_{n,1} = h_{n}.

Other special cases for ν give well known generating functions. Taking ν such that ν(n) = n for n ≥ 1, p_{n,n} is the power symmetric function ∑_{i} x_{i}^{n}. Let χ(S) be equal to 1 if S is true and 0 if false for any statement S. By taking ν(n) = (−1)^{k}χ(n ≥ k + 1) for some k ≥ 1, p_{n,(−1)^{k}χ(n≥k+1)} is the Schur function corresponding to the partition (1^{k}, n).

This definition of p_{n,ν} is desirable because of its expansion in terms of elementary symmetric functions. The coefficient of e_{λ} in p_{n,ν} has a nice combinatorial interpretation similar to that of the homogeneous symmetric functions. Suppose T is a brick tabloid of shape (n) and type λ and that the final brick in T has length ℓ. Define the weight of a brick tabloid w_{ν}(T) to be ν(ℓ) and let

w_{ν}(B_{λ,n}) = ∑_{T is a brick tabloid of shape (n) and type λ} w_{ν}(T).  (6)

When ν(n) = 1 for n ≥ 1, B_{λ,n} and w_{ν}(B_{λ,n}) are the same. By the recursions found in the definition of p_{n,ν}, it may be shown that

p_{n,ν} = ∑_{λ⊢n}(−1)^{n−ℓ(λ)}w_{ν}(B_{λ,n})e_{λ}  (7)

in almost the exact same way that (3) was proved in [ER91]. A detailed proof may be found in [Men04].

We are now ready to give our proof of Theorems 3 and 1.

4. Our proof of Theorems 1 and 3

In this section, we shall prove Theorem 1 in the case where i = 1 and Theorem 3 by applying a homomorphism ξ defined on the ring of symmetric functions to the identity ((5)) for an appropriate weight function ν. The case where i = 3 of Theorem 1 will then follow by applying the bijection of Foata and Han described in Theorem 2. The remarkable fact is that we can essentially read the required homomorphism ξ and the required function ν directly from the right hand side of the statement of Theorem 3. Rewrite this expression as

\frac{(1 − t)J((1 − t)Xu; Q, q)}{1 − t + (J((1 − t)Xu; Q, q)J((1 − t)Y u; Q, q) − 1)}

= \frac{1 + ∑_{n≥1}(−1)^{n}X^{n}u^{n}(1 − t)^{n}^{\frac{Q^{\binom{n}{2}}}{(Q,Q)_{n}(q,q)_{n}}}}{1 + ∑_{n≥1}(−1)^{n}u^{n}(1 − t)^{n−1} ∑_{k=0}^{n} ^{\frac{X^{k}Q^{\binom{k}{2}}Y^{n−k}Q^{\binom{n−k}{2}}}{(Q,Q)_{k}(q,q)_{k}(Q,Q)_{n−k}(q,q)_{n−k}}}} .

This suggests that we should set

ξ(e_{n}) = (1 − t)^{n−1} ∑_{k=0}^{n} \frac{X^{k}Q^{\binom{k}{2}}Y^{n−k}Q^{\binom{n−k}{2}}}{(Q, Q)_{k}(q, q)_{k}(Q, Q)_{n−k}(q, q)_{n−k}}  (8)

and

ξ(e_{n}) − ν(n)ξ(e_{n}) = \frac{(1 − t)^{n}X^{n}Q^{\binom{n}{2}}}{(Q, Q)_{n}(q, q)_{n}} .  (9)

Solving (9) for ν(n), we see that

ν(n) = \frac{1}{ξ(e_{n})} (ξ(e_{n}) − \frac{(1 − t)^{n−1}X^{n}Q^{\binom{n}{2}}}{(Q, Q)_{n}(q, q)_{n}} + \frac{t(1 − t)^{n−1}X^{n}Q^{\binom{n}{2}}}{(Q, Q)_{n}(q, q)_{n}} ) .  (10)

Therefore, to prove Theorem 1, we need only show that

ξ(p_{n,ν}) = \frac{W_{n}^{(1)}(X, Y, t, Q, q)}{(Q, Q)_{n}(q, q)_{n}}

or, equivalently, that

(Q, Q)_{n}(q, q)_{n}ξ(p_{n,ν}) = W_{n}^{(1)}(X, Y, t, Q, q).  (11)

Similarly, to prove Theorem 3, we need only show that

ξ(p_{n,ν}) = \frac{W_{n}^{(2)}(X, Y, t, Q, q)}{(Q, Q)_{n}(q, q)_{n}}

or, equivalently, that

(Q, Q)_{n}(q, q)_{n}ξ(p_{n,ν}) = W_{n}^{(2)}(X, Y, t, Q, q).  (12)

We start by using (7) to express p_{n,ν} in terms of the elementary symmetric functions. We have

(Q, Q)_{n}(q, q)_{n}ξ(p_{n,ν}) = (Q, Q)_{n}(q, q)_{n} ∑_{μ⊢n}(−1)^{n−ℓ(μ)}w_{ν}(B_{μ,n})ξ(e_{μ})

= ∑_{μ⊢n}(−1)^{n−ℓ(μ)} ∑_{T =(b_{1},...,b_{k})∈B_{μ,n}}(Q, Q)_{n}(q, q)_{n}ν(b_{k}) ∏_{i=1}^{k} ξ(e_{b_{i}}). (13)

Focusing on the term (Q, Q)_{n}(q, q)_{n}ν(b_{k}) ∏_{i=1}^{k} ξ(e_{b_{i}}), we have for i < k,

ξ(e_{b_{i}}) = (1 − t)^{b_{i}−1} ∑_{j=0}^{k} \frac{X^{j}Q^{\binom{j}{2}}Y^{b_{i}−j}Q^{\binom{b_{i}−j}{2}}}{(Q, Q)_{j}(q, q)_{j}(Q, Q)_{b_{i}−j}(q, q)_{b_{i}−j}}

= (1 − t)^{b_{i}−1} ∑_{r_{i}+s_{i}=b_{i}} \frac{X^{r_{i}}Y^{s_{i}}Q^{\binom{r_{i}}{2}}Q^{\binom{s_{i}}{2}}}{(Q, Q)_{r_{i}}(q, q)_{r_{i}}(Q, Q)_{s_{i}}(q, q)_{s_{i}}} .

For i = k,

ξ(e_{b_{k}})ν(b_{k}) = ξ(e_{b_{k}})\frac{1}{ξ(e_{b_{k}})} (ξ(e_{b_{k}}) − \frac{(1 − t)^{b_{k}−1}X^{b_{k}}Q^{\binom{b_{k}}{2}}}{(Q, Q)_{b_{k}}(q, q)_{b_{k}}} + \frac{t(1 − t)^{b_{k}−1}X^{b_{k}}Q^{\binom{b+k}{2}}}{(Q, Q)_{b_{k}}(q, q)_{b_{k}}} )

= (1 − t)^{b_{k}−1} (∑_{j=0}^{b_{k}−1} \frac{X^{j}Q^{\binom{j}{2}}Y^{b_{k}−j}Q^{\binom{b_{k}−j}{2}}}{(Q, Q)_{j}(q, q)_{j}(Q, Q)_{b_{k}−j}(q, q)_{b_{k}−j}} )

+ \frac{t(1 − t)^{b_{k}−1}X^{b_{k}}Q^{\binom{b+k}{2}}}{(Q, Q)_{b_{k}}(q, q)_{b_{k}}}

= (1 − t)^{b_{k}−1} ( ∑_{r_{k}+s_{k}=b_{k},r_{k}≠b_{k}} \frac{X^{r_{k}}Y^{s_{k}}Q^{\binom{r_{k}}{2}}Q^{\binom{s_{k}}{2}}}{(Q, Q)_{r_{k}}(q, q)_{r_{k}}(Q, Q)_{s_{k}}(q, q)_{s_{k}}} )

+ \frac{t(1 − t)^{b_{k}−1}X^{b_{k}}Q^{\binom{b_{k}}{2}}}{(Q, Q)_{b_{k}}(q, q)_{b_{k}}} .

The net effect of taking the weight ξ(e_{b_{k}}) versus the weight ν(b_{k})ξ(e_{b_{k}}) is that the last term summand for ξ(e_{b_{k}}) is

\frac{(1 − t)^{b_{k}−1}X^{b_{k}}Q^{\binom{b_{k}}{2}}}{(Q, Q)_{b_{k}}(q, q)_{b_{k}}}

while the last term in the summand for ν(b_{k})ξ(e_{b_{k}}) has an extra factor of t,

\frac{t(1 − t)^{b_{k}−1}X^{b_{k}}Q^{\binom{b_{k}}{2}}}{(Q, Q)_{b_{k}}(q, q)_{b_{k}}} .

Thus, (13) is equal to

∑_{μ⊢n}(−1)^{n−ℓ(μ)} ∑_{T =(b_{1},...,b_{k})∈B_{μ,n}} ∑_{r_{i}+s_{i}=b_{i}}(1 − t)^{n−ℓ(μ)}X^{r_{1}+···+r_{k}}Y^{s_{1}+···+s_{k}}

× \frac{(Q, Q)_{n}}{(Q, Q)_{r_{1}}(Q, Q)_{s_{1}} ⋯ (Q, Q)_{r_{k}}(Q, Q)_{s_{k}}}

× Q^{∑ \binom{r_{i}}{2}+∑ \binom{s_{i}}{2}} \frac{(q, q)_{n}}{(q, q)_{r_{1}}(q, q)_{s_{1}} ⋯ (q, q)_{r_{k}}(q, q)_{s_{k}}} t^{χ(r_{k}=b_{k})}

= ∑_{μ⊢n}(t − 1)^{n−ℓ(μ)} ∑_{T =(b_{1},...,b_{k})∈B_{μ,n}} ∑_{r_{i}+s_{i}=b_{i}} X^{r_{1}+···+r_{k}}Y^{s_{1}+···+s_{k}}t^{χ(r_{k}=b_{k})}

× ∏_{a=1}^{L} \left[{n \atop r_{1}, s_{1}, …, r_{k}, s_{k}}\right]_{Q_{a}}Q_{a}^{∑_{i=1}^{k}(\binom{r_{i}}{2}+\binom{s_{i}}{2})} ∏_{b=1}^{ℓ} \left[{n \atop r_{1}, s_{1}, …, r_{k}, s_{k}}\right]_{q_{b}}.

Fix a brick tabloid T = (b_{1}, …, b_{k}) ∈ B_{μ,n} and fix a sequence r_{1}, s_{1}, …, r_{k}, s_{k} such that for all i = 1, …, k, r_{i} + s_{i} = b_{i}. We wish to give a combinatorial interpretation to the term

X^{r_{1}+···+r_{k}}Y^{s_{1}+···+s_{k}} ∏_{a=1}^{L} \left[{n \atop r_{1}, s_{1}, …, r_{k}, s_{k}}\right]_{Q_{a}}Q_{a}^{∑_{i=1}^{k}(\binom{r_{i}}{2}+\binom{s_{i}}{2})} ∏_{b=1}^{ℓ} \left[{n \atop r_{1}, s_{1}, …, r_{k}, s_{k}}\right]_{q_{b}}. (14)

Take the brick tabloid T = (b_{1}, …, b_{k}) and divide each brick b_{i} into two pieces, the first of size r_{i} and the second of size s_{i}. Place X’s at the top of all the cells corresponding to r_{1}, …, r_{k} and Y ’s at the top of all the cells corresponding to s_{1}, …, s_{k}. Further divide the brick tabloid T into L + ℓ rows and consider the set of all fillings F_{T,L,ℓ,r_{1},s_{1},...,r_{k},s_{k}} of T with integers such that

(1) within each row j, each brick b_{i} is filled with subsets R_{i,j}, S_{i,j} ⊆ {1, …, n} such that |R_{i,j}| = r_{i}, |S_{i,j}| = s_{i}, the numbers in R_{i,j} occupy the first r_{i} cells of row j in the brick b_{i} in decreasing order, and the numbers in S_{i,j} occupy the last s_{i} cells of row j in the brick b_{i} in decreasing order, and

(2) for each row j, ⋃_{i=1}^{k}(R_{i,j} ∪ S_{i,j}) = {1, …, n}.

If we read to numbers from left to right in the first L rows, we will obtain permutations Σ^{(1)}, … Σ^{(L)} in S_{n}. If we read to numbers from left to right in the last ℓ rows, we will obtain permutations σ^{(1)}, … σ^{(ℓ)} in S_{n}. For example, if T = (4, 5), r_{1} = s_{1} = 2, r_{2} = 2 and s_{2} = 3, and L = ℓ = 2, then and element of F_{T,L,ℓ,r_{1},s_{1},...,r_{k},s_{k}} is pictured in Figure 2

In the special case where the configuration F has only one permutation, i.e. when either L = 1 and ℓ = 0 or L = 0 and ℓ = 1, we shall denote F_{T,L,ℓ,r_{1},s_{1},...,r_{k},s_{k}} by simply F_{T,r_{1},s_{1},...,r_{k},s_{k}}.

Our goal is to interpret (14) as a weighted sum over all elements F ∈ F_{T,L,ℓ,r_{1},s_{1},...,r_{k},s_{k}}. Carlitz showed in [Car70] that the q-multinomial coefficient can be interpreted as

\left[{n \atop r_{1}, s_{1}, …, r_{k}, s_{k}}\right]_{q} = ∑_{r∈R(1^{r_{1}}2^{s_{1}}3^{r_{2}}4^{s_{2}}···(2k−1)^{r_{k}} (2k)^{s_{k}})} q^{inv(r)}.

6 8 7  5  1  6  4  9  8  3 3  5  2  7  4  1 9  2 X X  Y  Y  X X Y  Y  Y1 2 7 9 3 6 4 8 2  1  8  3  9  5  7  4 5  Σ_{1} σ_{1} σ_{1} Σ_{2} s_{1} = 2  r_{2} = 2  s_{2} = 3 r_{1} = 2  6
Figure 2. An element of F_{T,L,ℓ,r_{1},s_{1},...,r_{k},s_{k}}

where R(1^{r_{1}}2^{s_{1}}3^{r_{2}}4^{s_{2}} ⋯ (2k − 1)^{r_{k}}(2k)^{s_{k}}) is the set of all possible rearrangements of 1^{r_{1}}2^{s_{1}}3^{r_{2}}4^{s_{2}} ⋯ (2k − 1)^{r_{k}}(2k)^{s_{k}}. Similarly,

\left[{n \atop r_{1}, s_{1}, …, r_{k}, s_{k}}\right]_{q} = ∑_{r∈R(1^{r_{1}}2^{s_{1}}3^{r_{2}}4^{s_{2}}···(2k−1)^{r_{k}} (2k)^{s_{k}})} q^{coinv(r)}.

Given a rearrangement r ∈ R(1^{r_{1}}2^{s_{1}}3^{r_{2}}4^{s_{2}} ⋯ (2k − 1)^{r_{k}}(2k)^{s_{k}}), we can associate a permutation σ_{r} by labeling the 1’s from right to left with 1, …, r_{1}, labeling the 2’s from right to left with r_{1} + 1, …, r_{1} + s_{1}, etc. It is not difficult to see that inv(σ_{r}) = inv(r) + ∑_{i=1}^{k} (\binom{r_{i}}{2} + \binom{s_{i}}{2}) and that σ_{r}^{−1} consists of a list of the positions of the 1’s in r in decreasing order, followed by a list of positions of the 2’s in r in decreasing order, etc.

For instance, we consider the example where n = 9, b_{1} = 4, b_{2} = 5, r_{1} = s_{1} = 2, r_{2} = 2 and s_{2} = 3. If the rearrangement r = 1 3 4 2 1 4 3 4 2, then we would obtain

\begin{aligned}r & = & 1 & 3 & 4 & 2 & 1 & 4 & 3 & 4 & 2 , \\ σ_{r} & = & 2 & 6 & 9 & 4 & 1 & 8 & 5 & 7 & 3 , \\ σ_{r}^{−1} & = & 5 & 1 & 9 & 4 & 7 & 2 & 8 & 6 & 3 . \end{aligned}

Thus such a σ_{r}^{−1} corresponds to a legitimate filling of one of the rows of a configuration of F in F_{T,L,ℓ,r_{1},s_{1},...,r_{k},s_{k}}. Since we can reverse the labeling process, it is easy to see the map r → σ_{r}^{−1} is bijection from R(1^{r_{1}}2^{s_{1}}3^{r_{2}}4^{s_{2}} ⋯ (2k −1)^{r_{k}}(2k)^{s_{k}}) onto F_{T,r_{1},s_{1},...,r_{k},s_{k}}. Our labeling ensures that

inv(σ_{r}) = inv(r) + ∑_{i=1}^{k} \binom{r_{i}}{2} + ∑_{i=1}^{k} \binom{s_{i}}{2} and
coinv(σ_{r}) = coinv(r).

Since inv(σ_{r}) = inv(σ_{r}^{−1}) and coinv(σ_{r}) = coinv(σ_{r}^{−1}), it follows that

q^{∑_{i=1}^{k} \binom{r_{i}}{2}+∑_{i=1}^{k} \binom{s_{i}}{2}}\left[{n \atop r_{1}, s_{1}, …, r_{k}, s_{k}}\right]_{q} = ∑_{σ∈F_{T,r_{1},s_{1},...,r_{k},s_{k}}} q^{inv(σ)} and  (15)

\left[{n \atop r_{1}, s_{1}, …, r_{k}, s_{k}}\right]_{q} = ∑_{σ∈F_{T,r_{1},s_{1},...,r_{k},s_{k}}} q^{coinv(σ)}.  (16)

It follows from (15) and (16) that if we let ϵ = x^{r_{1}}y^{s_{1}} ⋯ x^{r_{k}}y^{s_{k}}, then we have the following.

Lemma 4.

X^{r_{1}+···+r_{k}}Y^{s_{1}+···+s_{k}} ∏_{a=1}^{L} \left[{n \atop r_{1}, s_{1}, …, r_{k}, s_{k}}\right]_{Q_{a}}Q_{a}^{∑_{i=1}^{k}(\binom{r_{i}}{2}+\binom{s_{i}}{2})} ∏_{b=1}^{ℓ} \left[{n \atop r_{1}, s_{1}, …, r_{k}, s_{k}}\right]_{q_{b}}

= X^{ℓ(ϵ|x)}Y^{ℓ(ϵ|y)} ∑_{F =(Σ^{(1)},...,Σ^{(L)},σ^{(1)},...,σ^{(ℓ)})∈F_{T,L,ℓ,r_{1},s_{1},...,r_{k},s_{k}}} Q^{inv(Σ^{(1)},...,Σ^{(L)};ϵ)}q^{coinv(σ^{(1)},...,σ^{(ℓ)};ϵ)}.

By slightly modify our labeling, we can get an analogue of Lemma 4 where we replace the statistics inv and coinv by F Hinv and F Hcoinv respectively. That is, it is also that case that

\left[{n \atop r_{1}, s_{1}, …, r_{k}, s_{k}}\right]_{q} = ∑_{r∈R(1^{s_{1}}2^{s_{2}}···k^{s_{k}} (k+1)^{r_{1}}(k+2)^{r_{2}}···(2k)^{r_{k}})} q^{inv(r)}.

As before, given a rearrangement r ∈ R(1^{s_{1}}2^{s_{2}} ⋯ k^{s_{k}}(k + 1)^{r_{1}}(k + 2)^{r_{2}} ⋯ (2k)^{r_{k}}), we associate a permutation σ_{r} by labeling the 1’s from right to left with 1, …, s_{1}, labeling the 2’s from right to left with s_{1} + 1, …, s_{1} + s_{2}, etc. As before, σ_{r}^{−1} consists of a list of the positions of the 1’s in r in decreasing order, followed by a list of positions of the 2’s in r in decreasing order, etc.

For example, consider the case where n = 9, b_{1} = 4, b_{2} = 5, r_{1} = 1, s_{1} = 3, r_{2} = 2 and s_{2} = 3 and where the rearrangement is r = 1 3 1 2 1 4 2 4 2. Since in the end we want the positions corresponding to the r_{i}’s weighted by X and the position of the s_{j}’s weighted by Y, we place the appropriate X and Y on top of the letters. Doing this, we would obtain

\begin{aligned}& & Y & X & Y & Y & Y & X & Y & X & Y \\ r & = & 1 & 3 & 1 & 2 & 1 & 4 & 2 & 4 & 2, \end{aligned}

\begin{aligned}& & Y & X & Y & Y & Y & X & Y & X & Y \\ σ_{r} & = & 3 & 7 & 2 & 6 & 1 & 9 & 5 & 8 & 4, \end{aligned}

and

\begin{aligned}& & Y & Y & Y & Y & Y & Y & X & X & X \\ σ_{r}^{−1} & = & 5 & 3 & 1 & 9 & 7 & 4 & 2 & 8 & 6. \end{aligned}

At this point σ_{r}^{−1} does not correspond to a legitimate filling of a configuration of F ∈ F_{T,r_{1},s_{1},...,r_{k},s_{k}} since it consists of decreasing sequences of lengths s_{1}, …, s_{k}, r_{1}, …, r_{k}, respectively. However, we can easily obtain a legitimate filling of a configuration of F ∈ F_{T,r_{1},s_{1},...,r_{k},s_{k}} by simply bringing the decreasing sequence corresponding to r_{1} in front of the decreasing sequence corresponding to s_{1}, then bringing the decreasing sequence corresponding to r_{2} immediately in front of the decreasing sequence corresponding to s_{2}, etc. Let us call the result of this rearrangement σ_{r}^{∗}. In our example,

\begin{aligned}& & X & Y & Y & Y & X & X & Y & Y & Y \\ σ_{r}^{∗} & = & 2 & 5 & 3 & 1 & 8 & 6 & 9 & 7 & 4. \end{aligned}

If we let ϵ = y^{s_{1}+···+s_{k}}x^{r_{1}+···+r_{k}} and ϵ^{∗} = x^{r_{1}}y^{s_{1}}x^{r_{2}}y^{s_{2}} ⋯ x^{r_{k}}y^{s_{k}}, then, since all the Y ’s precede all the X’s in σ_{r}^{−1}, we have

∑_{i=1}^{k} \binom{r_{i}}{2} + ∑_{i=1}^{k} \binom{s_{i}}{2} + inv(r) = inv(σ_{r}) = inv(σ_{r}^{−1})
= inv((σ_{r}^{−1})_{ϵ|x}) + inv((σ_{r}^{−1})_{ϵ|y})

+ ∑_{i,j} χ(ϵ_{i} = y, ϵ_{j} = x, (σ_{r}^{−1})_{i} > (σ_{r}^{−1})_{j}).

But clearly

inv((σ_{r}^{−1})_{ϵ|x}) + inv((σ_{r}^{−1})_{ϵ|y}) + ∑_{i,j} χ(ϵ_{i} = y, ϵ_{j} = x, & (σ_{r}^{−1})_{i} > (σ_{r}^{−1})_{j})

= inv((σ_{r}^{∗})_{ϵ^{∗}|x}) + inv((σ_{r}^{∗})_{ϵ^{∗}|y}) + ∑_{i,j} χ(ϵ_{i}^{∗} = y, ϵ_{j}^{∗} = x, & (σ_{r}^{∗})_{i} > (σ_{r}^{∗})_{j}),

which in turn is equal to F Hinv(σ_{r}^{∗}). It follows that

q^{∑_{i=1}^{k} \binom{r_{i}}{2}+∑_{i=1}^{k} \binom{s_{i}}{2}}\left[{n \atop r_{1}, s_{1}, …, r_{k}, s_{k}}\right]_{q} = ∑_{σ∈F_{T,r_{1},s_{1},...,r_{k},s_{k}}} q^{F Hinv(σ)}.  (17)

We also need to show that

\left[{n \atop r_{1}, s_{1}, …, r_{k}, s_{k}}\right]_{q} = ∑_{σ∈F_{T,r_{1},s_{1},...,r_{k},s_{k}}} q^{F Hcoinv(σ)}.  (18)

In this case, we need a slightly different labeling. That is, it is the case that

\left[{n \atop r_{1}, s_{1}, …, r_{k}, s_{k}}\right]_{q} = ∑_{r∈R(1^{r_{1}}2^{r_{2}}···k^{r_{k}} (k+1)^{s_{1}}(k+2)^{s_{2}}···(2k)^{s_{k}})} q^{coinv(r)}.

As before, given a rearrangement r ∈ R(1^{r_{1}}2^{r_{2}} ⋯ k^{r_{k}}(k + 1)^{s_{1}}(k + 2)^{s_{2}} ⋯ (2k)^{s_{k}}), we can associate a permutation σ_{r} by labeling the 1’s from right to left with 1, …, r_{1}, labeling the 2’s from right to left with r_{1} + 1, …, r_{1} + r_{2}, etc. As before σ_{r}^{−1} consists of a list of the positions of the 1’s in r in decreasing order, followed by a list of positions of the 2’s in r in decreasing order, etc.

For instance, let us return to our example where n = 9, b_{1} = 4, b_{2} = 5, r_{1} = 1, s_{1} = 3, r_{2} = 2 and s_{2} = 3. Consider the rearrangement r = 1 3 4 2 3 4 3 4 2. Since in the end we want the positions corresponding to the r_{i}’s weighted by X and the position of the s_{j}’s weighted by Y we shall again place the appropriate X and Y on top of the letters. Thus we would obtain

\begin{aligned}& & X & Y & Y & X & Y & Y & Y & Y & X \\ r & = & 1 & 3 & 4 & 2 & 3 & 4 & 3 & 4 & 2, \end{aligned}

\begin{aligned}& & X & X & Y & X & Y & X & Y & X & X \\ σ_{r} & = & 1 & 6 & 9 & 3 & 5 & 8 & 4 & 7 & 2, \end{aligned}

and

\begin{aligned}& & X & X & X & Y & Y & Y & Y & Y & Y \\ σ_{r}^{−1} & = & 1 & 9 & 4 & 7 & 5 & 2 & 8 & 6 & 3. \end{aligned}

At this point σ_{r}^{−1} does not correspond to a legitimate filling of a configuration of F ∈ F_{r_{1},s_{1},...,r_{k},s_{k}} since it consists of decreasing sequences of lengths r_{1}, …, r_{k}, s_{1}, …, s_{k}, respectively. However, we can obtain a legitimate filling of a configuration of F ∈ F_{r_{1},s_{1},...,r_{k},s_{k}} by placing the decreasing sequence corresponding to s_{1} immediately after the decreasing sequence corresponding to r_{1}, then placing the decreasing sequence corresponding to s_{2} immediately after the decreasing sequence corresponding to r_{2}, etc. Call the result of this rearrangement σ_{r}^{∗∗}. In our example,

\begin{aligned}& & X & Y & Y & Y & X & X & Y & Y & Y \\ σ_{r}^{∗∗} & = & 1 & 7 & 5 & 2 & 9 & 4 & 8 & 6 & 3. \end{aligned}

If we let ϵ′ = y^{r_{1}+···+r_{k}}x^{s_{1}+···+s_{k}} and ϵ^{∗∗} = x^{r_{1}}y^{s_{1}}x^{r_{2}}y^{s_{2}} ⋯ x^{r_{k}}y^{s_{k}}, it is easy to see that since all the X’s precede all the Y ’s in σ_{r}^{−1}, we have

coinv(r) = coinv(σ_{r}) = coinv(σ_{r}^{−1})
= coinv((σ_{r}^{−1})_{ϵ′|x}) + coinv((σ_{r}^{−1})_{ϵ′|y})

+ ∑_{i,j} χ(ϵ_{i} = y, ϵ_{j} = x, (σ_{r}^{−1})_{i} > (σ_{r}^{−1})_{j}).

Clearly,

coinv((σ_{r}^{−1})_{ϵ′|x}) + coinv((σ_{r}^{−1})_{ϵ′|y}) + ∑_{i,j} χ(ϵ_{i} = y, ϵ_{j} = x, (σ_{r}^{−1})_{i} > (σ_{r}^{−1})_{j})

= coinv((σ_{r}^{∗∗})_{ϵ^{∗∗}|x}) + inv((σ_{r}^{∗})_{ϵ^{∗∗}|y}) + ∑_{i,j} χ(ϵ_{i}^{∗∗} = y, ϵ_{j}^{∗∗} = x, (σ_{r}^{∗∗})_{i} > (σ_{r}^{∗∗})_{j}),

which in turn is equal to F Hcoinv(σ_{r}^{∗∗}). Thus, (18) is true.

Since (17) and (18) have been proved, if we let ϵ = x^{r_{1}}y^{s_{1}} ⋯ x^{r_{k}}y^{s_{k}}, then we have the following.

Lemma 5.

X^{r_{1}+···+r_{k}}Y^{s_{1}+···+s_{k}} ∏_{a=1}^{L} \left[{n \atop r_{1}, s_{1}, …, r_{k}, s_{k}}\right]_{Q_{a}}Q_{a}^{∑_{i=1}^{k}(\binom{r_{i}}{2}+\binom{s_{i}}{2})} ∏_{b=1}^{ℓ} \left[{n \atop r_{1}, s_{1}, …, r_{k}, s_{k}}\right]_{q_{b}}

= X^{ℓ(ϵ|x)}Y^{ℓ(ϵ|y)}

× ∑_{F =(Σ^{(1)},...,Σ^{(L)},σ^{(1)},...,σ^{(ℓ)})∈F_{T,L,ℓ,r_{1},s_{1},...,r_{k},s_{k}}} Q^{F Hinv(Σ^{(1)},...,Σ^{(L)};ϵ)}q^{F Hcoinv(σ^{(1)},...,σ^{(ℓ)};ϵ)}.

We are in the position to give two different combinatorial interpretations for (Q, Q)_{n}(q, q)_{n}ξ(p_{n,ν}). Recall that we have already shown that (Q, Q)_{n}(q, q)_{n}ξ(p_{n,ν}) is equal to

∑_{μ⊢n}(t − 1)^{n−ℓ(μ)} ∑_{T =(b_{1},...,b_{k})∈B_{μ,n}} ∑_{r_{i}+s_{i}=b_{i}} X^{r_{1}+···+r_{k}}Y^{s_{1}+···+s_{k}}

× ∏_{a=1}^{L} \left[{n \atop r_{1}, s_{1}, …, r_{k}, s_{k}}\right]_{Q_{a}}Q^{∑ \binom{r_{i}}{2}+∑ \binom{s_{i}}{2}} ∏_{b=1}^{ℓ} \left[{n \atop r_{1}, s_{1}, …, r_{k}, s_{k}}\right]_{q_{b}}t^{χ(r_{k}=b_{k})}.

6 8 7  5  1  6  4  9  8  3 3  5  2  7  4  1 9  2 X X  Y  Y  X X Y  Y  Y1 2 7 9 3 6 4 8 2  1  8  3  9  5  7  4 5  Σ_{1} σ_{1} σ_{1} Σ_{2} s_{1} = 2  r_{2} = 2  s_{2} = 3 r_{1} = 2 t  t −1 1 −1 t −1 t  1 6

Figure 3. A combinatorial object.

We can interpret this equation as follows. For each brick T = (b_{1}, …, b_{k}) ∈ B_{μ,n} and for each choice r_{1}, s_{1}, …, r_{k}, s_{k} from the sum ∑_{r_{i}+s_{i}=b_{i}}, the term

X^{r_{1}+···+r_{k}}Y^{s_{1}+···+s_{k}} ∏_{a=1}^{L} \left[{n \atop r_{1}, s_{1}, …, r_{k}, s_{k}}\right]_{Q_{a}}Q^{∑ \binom{r_{i}}{2}+∑ \binom{s_{i}}{2}} ∏_{b=1}^{ℓ} \left[{n \atop r_{1}, s_{1}, …, r_{k}, s_{k}}\right]_{q_{b}}

can be viewed either as the sum

X^{ℓ(ϵ|x)}Y^{ℓ(ϵ|y)} ∑_{F =(Σ^{(1)},...,Σ^{(L)},σ^{(1)},...,σ^{(ℓ)})∈F_{T,L,ℓ,r_{1},s_{1},...,r_{k},s_{k}}} Q^{inv(Σ^{(1)},...,Σ^{(L)};ϵ)}q^{coinv(σ^{(1)},...,σ^{(ℓ)};ϵ)}

or the sum

X^{ℓ(ϵ|x)}Y^{ℓ(ϵ|y)} ∑_{F =(Σ^{(1)},...,Σ^{(L)},σ^{(1)},...,σ^{(ℓ)})∈F_{T,L,ℓ,r_{1},s_{1},...,r_{k},s_{k}}} Q^{F Hinv(Σ^{(1)},...,Σ^{(L)};ϵ)}q^{F Hcoinv(σ^{(1)},...,σ^{(ℓ)};ϵ)}

where ϵ = x^{r_{1}}y^{s_{1}} ⋯ x^{r_{k}}y^{s_{k}}.

Now, if s_{k} ≠ 0, then we have a factor of (t − 1)^{n−ℓ(μ)}. For each

F = (Σ^{(1)}, …, Σ^{(L)}, σ^{(1)}, …, σ^{(ℓ)})

in F_{T,L,ℓ,r_{1},s_{1},...,r_{k},s_{k}}, we create a new set of weighted objects by placing a t or a −1 in cell of T which is not at the end of a brick and placing a 1 in each cell which at the end of the brick.

For example, if we let T = (4, 5) and r_{1} = 2, s_{1} = 2, r_{2} = 2 and s_{2} = 3, then we would obtain configuration C as pictured in Figure 3. We then let w(C) be the product of the all the −1’s, t’s, X’s and Y ’s appearing in the configuration. For the configuration appearing Figure 3, w(C) = −t^{4}X^{4}Y^{5}.

If s_{k} = 0 so that r_{k} = b_{k}, we have a factor of t(t − 1)^{n−ℓ(μ)}. As before, for each member F = (Σ^{(1)}, …, Σ^{(L)}, σ^{(1)}, …, σ^{(ℓ)}) of the set F_{T,L,ℓ,r_{1},s_{1},...,r_{k},s_{k}}, we create a new set of weighted objects by placing a t or a −1 in cell of T which is not at the end of a brick and placing a 1 in each cell which at the end of the brick which is not the final brick and placing a t in the last cell of the final brick.

For example, if we let T = (4, 5) and r_{1} = 2, s_{1} = 2, r_{2} = 5 and s_{2} = 0, then we would obtain configuration C′ as pictured in Figure 4. Let w(C′) be the product of the all the −1’s, t’s, X’s and Y ’s appearing in the configuration. For the configuration below, w(C′) = t^{5}X^{7}Y^{2}.

6 8 7  5  1  9  8  6  4  3 3  7  5  2  1 9  2 X X  Y  Y  X X X X X 1 2 7 9 3 6 4 8 2  1  8  3  9  7  6  4 5  Σ_{1} σ_{1} σ_{1} Σ_{2} s_{1} = 2 r_{1} = 2  4 r_{2} = 5  t t −1 t −1 1 t t t  5

Figure 4. A configuration similar to Figure 3 but with a slightly different labeling.

Let C_{T,L,ℓ,r_{1},s_{1},...,r_{k},s_{k}} denote the set of all configurations C as constructed from elements F = (Σ^{(1)}, …, Σ^{(L)}, σ^{(1)}, …, σ^{(ℓ)}) of the set F_{T,L,ℓ,r_{1},s_{1},...,r_{k},s_{k}} and let

C_{n} = ⋃_{μ⊢n} ⋃_{T =(b_{1},...,b_{k})∈B_{μ,n}} ⋃_{r_{i}+s_{i}=b_{i}} C_{T,L,ℓ,r_{1},s_{1},...,r_{k},s_{k}}.

Define two different weights on configurations C ∈ C_{n}. If C ∈ C_{T,L,ℓ,r_{1},s_{1},...,r_{k},s_{k}} is constructed from F = (Σ^{(1)}, …, Σ^{(L)}, σ^{(1)}, …, σ^{(ℓ)}) ∈ F_{T,r_{1},s_{1},...,r_{k},s_{k}}, let

U_{1}(C) = w(C)Q^{F Hinv(Σ^{(1)},...,Σ^{(L)};ϵ)}q^{F Hcoinv(σ^{(1)},...,σ^{(ℓ)};ϵ)} and
U_{2}(C) = w(C)Q^{inv(Σ^{(1)},...,Σ^{(L)};ϵ)}q^{coinv(σ^{(1)},...,σ^{(ℓ)};ϵ)}

where ϵ = x^{r_{1}}y^{s_{1}} ⋯ x^{r_{k}}y^{s_{k}}. It follows that

(Q, Q)_{n}(q, q)_{n}ξ(p_{n,ν}) = ∑_{C∈C_{n}} U_{1}(C) and  (19)
(Q, Q)_{n}(q, q)_{n}ξ(p_{n,ν}) = ∑_{C∈C_{n}} U_{2}(C).

It follows from (11) and (19) that to prove Theorem 1, we need to show that

∑_{C∈C_{n}} U_{1}(C) = W_{n}^{(1)}(X, Y, t, Q, q)  (20)

Similarly, to prove Theorem 3, we need to show that

∑_{C∈C_{n}} U_{2}(C) = W_{n}^{(2)}(X, Y, t, Q, q).  (21)

To prove both (20) and (21), we will define a sign-reversing weight-preserving involution I on C_{n} so that the fixed points of I will give the desired right hand side of (20) or (21). In fact, the same involution will work for both (20) or (21).

Suppose that C is constructed from

F = (Σ^{(1)}, …, Σ^{(L)}, σ^{(1)}, …, σ^{(ℓ)}) ∈ F_{T,L,ℓ,r_{1},s_{1},...,r_{k},s_{k}},

then we say that a sequence of cells in c, c + 1, …, c + k in C forms a decreasing sequence if the following three things happen:

(i) the labels at the top of the cells c, c + 1, …, c + k when read from left to right is a word of the form X^{u}Y^{v} for some u, v ≥ 0,

6 8 7  5  1  6  4  9  8  3 3  5  2  7  4  1 9  2 X X  Y  Y  X X Y  Y  Y1 2 7 9 3 6 4 8 2  1  8  3  9  5  7  4 5  Σ_{1} σ_{1} σ_{1} Σ_{2} r_{3} = 2  s_{3} = 3 r_{1} = 2 s_{1} = 2s_{2} = 1 t  t  1  1 −1 t −1 t  1 6

Figure 5. The image of Figure 3 under I.

(ii) the entries in each of the rows corresponding to Σ^{(1)}, …, Σ^{(L)}, σ^{(1)}, …, σ^{(ℓ)} are

decreasing in cells whose label is X, i.e., in cells c, c + 1, …, c + u − 1, and (iii) the entries in each of the rows corresponding to Σ^{(1)}, …, Σ^{(L)}, σ^{(1)}, …, σ^{(ℓ)} are

decreasing in cells whose label is Y, i.e., in cells c + u, c + u + 1, …, c + u + v − 1.

By definition, the cells corresponding to each brick in a configuration C ∈ C_{n} form a decreasing sequence.

We define the involution I as follows. Given C ∈ C_{n}, scan the cells of the C from left to right until either

• Case 1: there is a cell c with a −1 in which case I(C) is the result of changing the weight cell c to 1 and breaking the brick b_{i} which contains cell c into two bricks b′ and b′′ where b′ ends at cell c, or

• Case 2: we find two consecutive bricks b_{i} and b_{i+1} such that cells corresponding to b_{i} and b_{i+1} form a decreasing sequence in which case I(C) is the result of replacing bricks b_{i} and b_{i+1} by a single brick b and changing the weight of the last cell of b_{i} from 1 to −1.

If neither Case 1 or Case 2 holds, then define I(C) = C.

For example, if we consider the configuration C pictured in Figure 3, then we are Case 1 with cell c equal to cell 3 so that I(C) = C′ where C′ is pictured in Figure 5. However, C′ is in Case 2 because we can combine bricks b_{1} and b_{2} so that I(C′) is equal to C.

The definition of I is designed so that the only change is the total number of bricks. The underlying permutations (Σ^{(1)}, …, Σ^{(L)}, σ^{(1)}, …, σ^{(ℓ)}) remain unchanged. Moreover, since we do not change any of the labels at the top of the column, it follows that if cell n has an X at the top of the column, then the last brick of both C and I(C) must contain all X’s since the cells in each brick must form a decreasing sequence and hence the weight of the final cell in both C and I(C) is equal to t.

Our definitions ensure that if I(C) ≠ C, then U_{1}(C) = −U_{1}(I(C)), U_{2}(C) = −U_{2}(I(C)), and I(I(C)) = C. Let F ix_{I} = {C ∈ C_{n} : I(C) = C}. Then I shows that

∑_{C∈C_{n}} U_{1}(C) = ∑_{C∈F ix_{I}} U_{1}(C),  and
∑_{C∈C_{n}} U_{2}(C) = ∑_{C∈F ix_{I}} U_{2}(C).

Consider the fixed points of I. Suppose that C ∈ F ix_{I} and C is constructed from an element F = (Σ^{(1)}, …, Σ^{(L)}, σ^{(1)}, …, σ^{(ℓ)}) of the set F_{T,L,ℓ,r_{1},s_{1},...,r_{k},s_{k}}. No cell of C can have label −1 and the sequence of cells in any two consecutive bricks do not form a decreasing sequence. This means that if b_{i} and b_{i+1} are two consecutive bricks in C, s is last cell in b_{i}, s + 1 is the first cell of b_{i+1}, and ϵ = x^{r_{1}}y^{s_{1}} ⋯ x^{r_{k}}y^{s_{k}}, then either

• ϵ_{s} = y and ϵ_{s+1} = x,

• ϵ_{s} = x and ϵ_{s+1} = x and there is some i such that Σ^{(i)}(s) < Σ^{(i)}(s + 1) or there is

some j such that σ^{(j)}(s) < σ^{(j)}(s + 1), or

• ϵ_{s} = y and ϵ_{s+1} = y and there is some i such that Σ^{(i)}(s) < Σ^{(i)}(s + 1) or there is

some j such that σ^{(j)}(s) < σ^{(j)}(s + 1).

It follows that s is not a member of Comdes(Σ^{(1)}, …, Σ^{(L)}, σ^{(1)}, …, σ^{(ℓ)}) and that the weight of cell s is 1. If s = n, then s ∈ Comdes(Σ^{(1)}, …, Σ^{(L)}, σ^{(1)}, …, σ^{(ℓ)}) if and only if ϵ_{n} = x. Thus if ϵ_{n} = y, s is not an element of Comdes(Σ^{(1)}, …, Σ^{(L)}, σ^{(1)}, …, σ^{(ℓ)}) and the weight of cell s is 1. If ϵ_{n} = x, s ∈ Comdes(Σ^{(1)}, …, Σ^{(L)}, σ^{(1)}, …, σ^{(ℓ)}) and that the weight of cell s is t. If s is not the last cell of a brick, then our definitions ensure that s ∈ Comdes(Σ^{(1)}, …, Σ^{(L)}, σ^{(1)}, …, σ^{(ℓ)}) and that the weight of cell s is t. Therefore w(C) = t^{comdes(Σ,σ;ϵ)}. Thus if C ∈ F ix_{I} and C is constructed from a member of F_{T,L,ℓ,r_{1},s_{1},...,r_{k},s_{k}}, then

U_{1}(C) = t^{comdes(Σ,σ;ϵ)}Q^{F Hinv(Σ,σ;ϵ)}q^{F Hcoinv(Σ,σ;ϵ)},  and
U_{2}(C) = t^{comdes(Σ,σ;ϵ)}Q^{inv(Σ,σ;ϵ)}q^{coinv(Σ,σ;ϵ)}.

Finally, if we are given (Σ, σ; ϵ) = (Σ^{(1)}, …, Σ^{(L)}, σ^{(1)}, …, σ^{(ℓ)}; ϵ), then we can construct a configuration C ∈ F ix_{I} such that

U_{1}(C) = t^{comdes(Σ,σ;ϵ)}Q^{F Hinv(Σ,σ;ϵ)}q^{F Hcoinv(Σ,σ;ϵ)} and
U_{2}(C) = t^{comdes(Σ,σ;ϵ)}Q^{inv(Σ,σ;ϵ)}q^{coinv(Σ,σ;ϵ)}

as follows. Let rows of C correspond the sequence of permutations

(Σ^{(1)}, …, Σ^{(L)}, σ^{(1)}, …, σ^{(ℓ)} : ϵ)

and label the top of column i with X if ϵ_{i} = x and with Y if ϵ_{i} = y. Next, let

E = {1, …, n − 1} − Comdes(Σ^{(1)}, …, Σ^{(L)}, σ^{(1)}, …, σ^{(ℓ)}).

If E = ∅, then C has a single brick of length n and if E = {i_{1} < ⋯ < i_{k}}, then we have bricks ending at i_{1}, …, i_{k}, n. Then we label each cell i with a t if i ∈ Comdes(Σ^{(1)}, …, Σ^{(L)}, σ^{(1)}, …, σ^{(ℓ)}) and with a 1 if i ∉ Comdes(Σ^{(1)}, …, Σ^{(L)}, σ^{(1)}, …, σ^{(ℓ)}) and i ≠ n. We label the last cell with a 1 if the last cell has a Y at the top of the column and with t is the last cell has an X at the top of the column. It is then easy to check that C ∈ F ix_{I}. It follows that

∑_{C∈C_{n}} U_{1}(C) = ∑_{C∈F ix_{I}} U_{1}(C) = W_{n}^{(1)}(X, Y, t, Q, q) and
∑_{C∈C_{n}} U_{2}(C) = ∑_{C∈F ix_{I}} U_{2}(C) = W_{n}^{(2)}(X, Y, t, Q, q)

as desired. This completes the proof of Theorems 1 and 3.

In the next section, we shall show how we can modify this proof to prove a whole family of extensions of Theorem 1 and 3 to groups of the form C_{k} ≀ S_{n}.

5. Permutation Statistics and Generating Functions for C_{k} ≀ S_{n}

For the rest of the paper, assume k ≥ 2. An element of C_{k} ≀ S_{n} is a pair (σ, ϵ) where σ ∈ S_{n} and ϵ ∈ {x_{1}, …, x_{k}}^{n}. Define the following statistics on C_{k} ≀ S_{n}. For 1 ≤ d ≤ k, we call i a descent of type d of (σ, ϵ) if either

(i) ϵ(i) = ϵ(i + 1) and σ_{i} > σ_{i+1},

(ii) ϵ(i) = x_{s} and ϵ(i + 1) = x_{t} where s < t, or (iii) i = n and ϵ(n) ∈ {x_{1}, …, x_{d}}.

A pair (i, j) is a FH-inversion (respectively FH-coinversion) of (σ, ϵ) if (i) i < j, ϵ(i) = ϵ(j) and σ_{i} > σ_{j} (respectively σ_{i} < σ_{j}), or (ii) ϵ(i) = x_{t} and ϵ(j) = x_{s} where t > s and σ_{i} > σ_{j}.

A pair (i, j) is an inversion (respectively coinversion) of (σ, ϵ) if i < j and σ_{i} > σ_{j} (respectively σ_{i} < σ_{j}), i.e. we say that (i, j) is an inversion (respectively coinversion) of (σ, ϵ) if it is an inversion (respectively coinversion) of σ.

Let Des^{d}(σ, ϵ) denote the set of all descents of type d for elements (σ, ϵ) ∈ C_{k} ≀ S_{n}. The restriction of (σ, ϵ) to its x_{i} part will be denoted σ_{ϵ|x_{i}} for i = 1, …, k. The inverses

to these sequences will be denoted σ_{ϵ|x_{i}}^{−1}. These are found in the same manner as displayed in the second 2. Let

\overline{inv}(σ_{ϵ|x_{1}}, …, σ_{ϵ|x_{k}}) = |\{(i, j) : ϵ(i) = x_{t}, ϵ(j) = x_{s}, t > s, σ_{i} > σ_{j}\}|

This given, we define the following two statistics for elements (σ, ϵ) ∈ C_{k} ≀ S_{n}.

imaj(σ, ϵ) = \overline{inv}(σ_{ϵ|x_{1}}, …, σ_{ϵ|x_{k}}) + ∑_{i=1}^{k} maj((σ^{−1})_{ϵ|x_{i}})

icomaj(σ, ϵ) = \overline{inv}(σ_{ϵ|x_{1}}, …, σ_{ϵ|x_{k}}) + ∑_{i=1}^{k} comaj((σ^{−1})_{ϵ|x_{i}}).

Our definitions imply that

F Hinv(σ, ϵ) = \overline{inv}(σ_{ϵ|x_{1}}, … σ_{ϵ|x_{k}}) + ∑_{i=1}^{k} inv(σ_{ϵ|x_{i}}),

F Hcoinv(σ, ϵ) = \overline{inv}(σ_{ϵ|x_{1}}, … σ_{ϵ|x_{k}}) + ∑_{i=1}^{k} coinv(σ_{ϵ|x_{i}}),
inv(σ, ϵ) = inv(σ),  and coinv(σ, ϵ) = coinv(σ).

We will write (σ^{(1)}, σ^{(2)}, …, σ^{(k)}; ϵ) for the sequence of elements

(σ^{(1)}, ϵ), (σ^{(2)}, ϵ), …, (σ^{(k)}, ϵ)

of C_{k} ≀ S_{n}. For each 1 ≤ d ≤ k, let

Comdes^{d}((σ^{(1)}, ϵ), (σ^{(2)}, ϵ), …, (σ^{(k)}, ϵ))

= Comdes^{d}(σ^{(1)}, σ^{(2)}, …, σ^{(k)}; ϵ) = ⋂_{i} Des^{d}(σ^{(i)}, ϵ)

and

comdes^{d}((σ^{(1)}, ϵ), (σ^{(2)}, ϵ), …, (σ^{(k)}, ϵ)) = comdes^{d}(σ^{(1)}, σ^{(2)}, …, σ^{(k)}; ϵ)
= |Comdes^{d}(σ^{(1)}, σ^{(s)}, …, σ^{(k)}; ϵ)|.

We will employ the same convention as found in (1), namely, if Σ = (Σ^{(1)}, …, Σ^{(L)}) is a sequence of permutations in C_{k} ≀ S_{n}, then we let

Q^{inv(Σ;ϵ)} = ∏_{i=1}^{L} Q_{i}^{inv(Σ^{(i)},ϵ)} and q^{inv(σ;ϵ)} = ∏_{i=1}^{ℓ} q_{i}^{inv(σ^{(i)},ϵ)}

where inv may be replaced with any other statistic. If Σ = (Σ^{(1)}, …, Σ^{(L)}) and σ = (σ^{(1)}, …, σ^{(ℓ)}) are lists of elements in S_{n}, we let (Σ, σ; ϵ) = (Σ^{(1)}, …, Σ^{(L)}, σ^{(1)}, …, σ^{(ℓ)}; ϵ).

Our C_{k} ≀ S_{n} analogues of W^{(1)},W^{(2)}, and W^{(3)} are:

W_{n}^{(1,d)}(X, Y, t, Q, q) = ∑_{(Σ,σ;ϵ)} (∏_{i=1}^{k} X_{i}^{ℓ(ϵ|x_{i})}) t^{comdes^{d}(Σ,σ;ϵ)}Q^{F Hinv(Σ;ϵ)}q^{F Hcoinv(σ;ϵ)},

W_{n}^{(2,d)}(X, Y, t, Q, q) = ∑_{(Σ,σ;ϵ)} (∏_{i=1}^{k} X_{i}^{ℓ(ϵ|x_{i})}) t^{comdes^{d}(Σ,σ;ϵ)}Q^{inv(Σ;ϵ)}q^{coinv(σ;ϵ)},  and

W_{n}^{(3,d)}(X, Y, t, Q, q) = ∑_{(Σ,σ;ϵ)} ∏_{i=1}^{k} (X_{i}^{ℓ(ϵ|x_{i})}) t^{comdes^{d}(Σ,σ;ϵ)}Q^{imaj(Σ;ϵ)}q^{icomaj(σ,ϵ)}

where the sums run over all ϵ ∈ {x_{1}, …, x_{k}}^{n} and all (Σ^{(1)}, …, Σ^{(L)}, σ^{(1)}, …, σ^{(ℓ)}) ∈ (C_{k} ≀ S_{n})^{L+ℓ}. Our next theorem gives a family of generating functions which can be viewed as natural analogues of Theorem 1 for C_{k} ≀ S_{n}.

Theorem 6. For i = 1, i = 2 and d = 1, …, k,

∑_{n≥0} \frac{W_{n}^{(i,d)}(X, Y, t, Q, q)u^{n}}{(Q, Q)_{n}(q, q)_{n}} = \frac{(1 − t) ∏_{i=1}^{d} J((1 − t)X_{i}u; Q, q)}{−t + ∏_{j=1}^{k} J((1 − t)X_{j}u; Q, q)}.

The fact that W_{n}^{(1,d)}(X, Y, t, Q, q) = W_{n}^{(3,d)}(X, Y, t, Q, q) can be proved using the same bijection that Foata and Han used to prove Theorem 2, implying that Theorem 6 holds when i = 3 as well.

We will prove a more general theorem than Theorem 6 which may be specialized to give Theorem 6 for either i = 1 or i = 2. Fix nonnegative integers L_{1}, L_{2}, L, ℓ_{1}, ℓ_{2}, and ℓ such that L_{1} + L_{2} = L and ℓ_{1} + ℓ_{2} = ℓ. Let

W_{n}^{(4,d)}(X_{1}, …, X_{k}, t, Q, q) = ∑_{(Σ,σ;ϵ)} (∏_{i=1}^{k} X_{i}^{ℓ(ϵ|x_{i})}) t^{comdes^{d}(Σ,σ;ϵ)} ∏_{i=1}^{L_{1}} Q_{i}^{F Hinv(Σ^{(i)},ϵ)}

× ∏_{i=L_{1}+1}^{L} Q_{i}^{inv(Σ^{(i)},ϵ)} ∏_{i=1}^{ℓ_{1}} q_{i}^{F Hcoinv(σ^{(i)},ϵ)} ∏_{i=1+ℓ_{1}}^{ℓ} q_{i}^{coinv(σ^{(i)},ϵ)}

where the sums run over all ϵ ∈ {x_{1}, …, x_{k}}^{n} and all (Σ^{(1)}, …, Σ^{(L)}, σ^{(1)}, …, σ^{(ℓ)}) ∈ (C_{k} ≀ S_{n})^{L+ℓ}. We shall prove the following result.

Theorem 7. For d = 1, …, k,

∑_{n≥0} \frac{W_{n}^{(4,d)}(X, Y, t, Q, q)u^{n}}{(Q, Q)_{n}(q, q)_{n}} = \frac{(1 − t) ∏_{i=1}^{d} J((1 − t)X_{i}u; Q, q)}{−t + ∏_{j=1}^{k} J((1 − t)X_{j}u; Q, q)}.

Proof. Our idea is that for each d = 1, …, k the identity in the statement of the theorem should be the result of applying a homomorphism ξ_{d} to the identity found in (5) for an appropriate function ν_{d}. Indeed, there is a single homomorphism ξ that works for all d. However, the weighting function ν_{d} does vary as d varies.

As before, we can read what the required homomorphism ξ and the required function ν_{d} are from directly from the right hand side of statement of the Theorem 7. This is we can rewrite (7) as follows:

\frac{1 + ∑_{n≥1}(−1)^{n}u^{n}(1 − t)^{n} ∑_{a_{i}≥0,a_{1}+···+a_{d}=n} ∏_{i=1}^{d} ^{\frac{X_{i}^{a_{i}}Q^{\binom{a_{i}}{2}}}{(Q,Q)_{a_{i}}(q,q)_{a_{i}}}}}{1 + ∑_{n≥1}(−1)^{n}u^{n}(1 − t)^{n−1} ∑_{f_{i}≥0,f_{1}+···+f_{k}=n} ∏_{j=1}^{k} \frac{X_{i}^{f_{i}}Q^{\binom{f_{i}}{2}}}{(Q,Q)_{f_{i}}(q,q)_{f_{i}}}} .

This suggests that for d = 1, …, k, we should set

ξ(e_{n}) = (1 − t)^{n−1} ∑_{f_{j}≥0,f_{1}+···+f_{k}=n} ∏_{j=1}^{k} \frac{X^{f_{i}}Q^{\binom{f_{i}}{2}}}{(Q, Q)_{f_{i}}(q, q)_{f_{i}}}  and

ξ(e_{n}) − ν_{d}(n)ξ(e_{n}) = \frac{(1 − t)^{n} ∑_{a_{i}≥0,a_{1}+···+a_{d}=n} ∏_{i=1}^{d} X^{a_{i}}Q^{\binom{n}{2}}}{(Q, Q)_{a_{i}}(q, q)_{a_{i}}} ,

so that ν_{d}(n) is equal to

1−\frac{(1 − t)^{n−1} ∑_{a_{i}≥0,a_{1}+···+a_{d}=n} ∏_{i=1}^{d} X_{i}^{n}Q^{\binom{a_{i}}{2}}}{ξ(e_{n})(Q, Q)_{a_{i}}(q, q)_{a_{i}}} +\frac{t(1 − t)^{n−1} ∑_{a_{i}≥0,a_{1}+···+a_{d}=n} ∏_{i=1}^{d} X_{i}^{a_{i}}Q^{\binom{a_{i}}{2}}}{ξ(e_{n})(Q, Q)_{a_{i}}(q, q)_{a_{i}}}

Therefore, to prove Theorem 7, we will show that

ξ(p_{n,ν_{d}}) = \frac{W_{n}^{(4,d)}(X, Y, t, Q, q)}{(Q, Q)_{n}(q, q)_{n}}

or, equivalently,

(Q, Q)_{n}(q, q)_{n}ξ(p_{n,ν_{d}}) = W_{n}^{(4,d)}(X, Y, t, Q, q).  (22)

We begin by using (7) to express p_{n,ν_{d}} in terms of the elementary symmetric functions:

(Q, Q)_{n}(q, q)_{n}ξ(p_{n,ν_{d}}) = (Q, Q)_{n}(q, q)_{n} ∑_{μ⊢n}(−1)^{n−ℓ(μ)}w_{ν}(B_{μ,n})ξ(e_{μ})

= ∑_{μ⊢n}(−1)^{n−ℓ(μ)} ∑_{T =(b_{1},...,b_{m})∈B_{μ,n}}(Q, Q)_{n}(q, q)_{n}ν_{d}(b_{m}) ∏_{s=1}^{m} ξ(e_{b_{s}}).

Focusing on the (Q, Q)_{n}(q, q)_{n}ν_{d}(b_{m}) ∏_{s=1}^{m} ξ(e_{b_{s}}) term, we have for s < m,

ξ(e_{b_{s}}) = (1 − t)^{b_{s}−1} ∑_{f_{j}≥0,f_{1}+···+f_{k}=b_{s}} ∏_{j=1}^{k} \frac{X_{j}^{f_{j}}Q^{\binom{f_{j}}{2}}}{(Q, Q)_{f_{j}}(q, q)_{f_{j}}} .

For s = m, we have ξ(e_{b_{m}})ν_{d}(b_{m}) is equal to

ξ(e_{b_{m}})\frac{1}{ξ(e_{b_{m}})} (ξ(e_{b_{m}}) − (1 − t)^{b_{m}−1} ∑_{a_{i}≥0,a_{1}+···a_{d}=b_{m}} ∏_{i=1}^{d} \frac{X_{i}^{a_{i}}Q^{\binom{a_{i}}{2}}}{(Q, Q)_{a_{i}}(q, q)_{a_{i}}}

+t(1 − t)^{b_{m}−1} ∑_{a_{i}≥0,a_{1}+···a_{d}=b_{m}} ∏_{i=1}^{d} \frac{X^{a_{i}}Q^{\binom{a_{i}}{2}}}{(Q, Q)_{a_{i}}(q, q)_{a_{i}}} )

which in turn is equal to

(1 − t)^{b_{m}−1} ∑_{(f_{1},...,f_{k})∈A_{d}(b_{m})} ∏_{j=1}^{k} \frac{X^{f_{j}}Q^{\binom{f_{j}}{2}}}{(Q, Q)_{f_{j}}(q, q)_{f_{j}}}

+ t(1 − t)^{b_{m}−1} ∑_{(f_{1},...,f_{k})∈B_{d}(b_{m})} ∏_{j=1}^{k} \frac{X^{f_{j}}Q^{\binom{f_{j}}{2}}}{(Q, Q)_{f_{j}}(q, q)_{f_{j}}}

where

(i) A_{d}(b_{m}) is the set of k-tuples (f_{1}, …, f_{k}) such that ∑_{j=1}^{k} f_{j} = b_{m} and at least one of f_{d+1}, … f_{d} is nonzero, and

(ii) B_{d}(b_{m} − 1) is the set of all tuples (f_{1}, …, f_{k}) such that ∑_{j=1}^{k} f_{j} = b_{m} and f_{d+1} =

⋯ = f_{d} = 0. The effect of taking the weight ξ(e_{b_{m}}) versus the weight ν_{d}(b_{m})ξ(e_{b_{m}}) is that the terms

corresponding to the sequences (f_{1}, …, f_{k}) where f_{d+1} = ⋯ = f_{d} = 0 in the summand for ξ(e_{b_{m}}) are of the form

(1 − t)^{b_{m}−1} ∏_{j=1}^{k} \frac{X^{f_{j}}Q^{\binom{f_{j}}{2}}}{(Q, Q)_{f_{j}}(q, q)_{f_{j}}}

while the corresponding sequences in the summand for ν_{d}(b_{m})ξ(e_{b_{m}}) have an extra factor of t,

t(1 − t)^{b_{m}−1} ∏_{j=1}^{k} \frac{X^{f_{j}}Q^{\binom{f_{j}}{2}}}{(Q, Q)_{f_{j}}(q, q)_{f_{j}}} .

Therefore (Q, Q)_{n}(q, q)_{n}ξ(p_{n,ν}) is equal to

∑_{μ⊢n}(−1)^{n−ℓ(μ)} ∑_{T =(b_{1},...,b_{m})∈B_{μ,n}} ∑_{f_{j}^{i}≥0,f_{1}^{i}+···f_{k}^{i}=b_{i}}(1 − t)^{n−ℓ(μ)} (∏_{t=1}^{k} X_{t}^{f_{t}^{1}+···+f_{t}^{m}}) Q∑{m \atop i=1} ∑{k \atop j=1} ^{\binom{f^{i}_{j}}{2}}

× \frac{(Q, Q)_{n}}{∏_{i=1}^{m} ∏_{j=1}^{k}(Q, Q)_{f_{j}^{i}}} \frac{(q, q)_{n}}{∏_{i=1}^{m} ∏_{j=1}^{k}(q, q)_{f_{j}^{i}}} t^{χ(f_{d+1}^{m}+···+f_{k}^{m}=0)}

which in turn is equal to

∑_{μ⊢n}(t − 1)^{n−ℓ(μ)} ∑_{T =(b_{1},...,b_{m})∈B_{μ,n}} ∑_{f_{j}^{i}≥0,f_{1}^{i}+···f_{k}^{i}=b_{i}} (∏_{t=1}^{k} X_{t}^{f_{t}^{1}+···+f_{t}^{m}}) t^{χ(f_{d+1}^{m}+···+f_{k}^{m}=0)}

× ∏_{a=1}^{L} \left[{n \atop f_{1}^{1}, …, f_{k}^{1}, …, f_{1}^{m}, …, f_{k}^{m}}\right]_{Q_{a}}Q∑_{i=1}^{m} ∑_{j=1}^{k} \binom{f^{i}_{j}}{2}_{a} ∏_{b=1}^{ℓ} \left[{n \atop f_{1}^{1}, …, f_{k}^{1}, …, f_{1}^{m}, …, f_{k}^{m}}\right]_{q_{b}}.

Fix a brick tabloid T = (b_{1}, …, b_{m}) ∈ B_{μ,n} and a sequence f_{1}^{1}, …, f_{k}^{1}, …, f_{1}^{m}, …, f_{k}^{m} such that for all i = 1, …, k, f_{1}^{i} +⋯ f_{k}^{i} = b_{i}. As in our proofs of Theorem 1 and Theorem 3, the first step is to give a combinatorial interpretation to the term

∏_{i=1}^{m} X_{i}^{∑_{j=1}^{k} f_{j}^{i}} ∏_{a=1}^{L} \left[{n \atop f_{1}^{1}, …, f_{k}^{1}, …, f_{1}^{m}, …, f_{k}^{m}}\right]_{Q_{a}}Q∑_{i=1}^{m} ∑_{j=1}^{k} \binom{f^{i}_{j}}{2}_{a}

× ∏_{b=1}^{ℓ} \left[{n \atop f_{1}^{1}, …, f_{k}^{1}, …, f_{1}^{m}, …, f_{k}^{m}}\right]_{q_{b}}. (23)

Take the brick tabloid T = (b_{1}, …, b_{m}) and divide each brick b_{i} into pieces of size f_{1}^{i}, …, f_{k}^{i} reading from left to right. Place X_{j}’s at the top of all the cells corresponding to f_{j}^{1}, …, f_{j}^{m} for j = 1, … k. Further divide the brick tabloid T into L+ℓ rows and consider the set of all fillings F_{T,L,ℓ,f_{k}^{1},...,f_{1}^{m},...,f_{k}^{m}} of T with integers such that

(1) within each row s, each brick b_{i} is filled with sets R_{i,1,s}, R_{i,2,s}, …, R_{i,k,s} ⊆ {1, …, n} such that |R_{i,j,s}| = f_{j}^{i}, the numbers in R_{i,j,s} occupy the cells 1 + ∑_{t=1}^{j−1} f_{t}^{i}, …, f_{j}^{i} + ∑_{t=1}^{j−1} f_{t}^{i} within the brick b_{i} in row s and are arranged in decreasing order, and

(2) for each row s, ⋃_{i=1}^{m} ⋃_{j=1}^{k} R_{i,j,s} = {1, …, n}. If we read to numbers from left to right in the first L rows, we find permutations Σ^{(1)}, …, Σ^{(L)} in S_{n}. If we read to numbers from left to right in the last ℓ rows, we will obtain permutations σ^{(1)}, … σ^{(ℓ)} in S_{n}.

For instance, if k = 3, T = (6, 5), f_{1}^{1} = 2, f_{2}^{1} = 1, f_{3}^{1} = 3, f_{1}^{2} = 2, f_{2}^{2} = 2, f_{3}^{2} = 1, and L = ℓ = 2, then an element of F_{T,L,ℓ,f_{1}^{1},...,f_{k}^{1},...,f_{1}^{m},...,f_{k}^{m}} is found in Figure 6.

In the case where there is a single permutation, i.e., when either L = 1 and ℓ = 0 or L = 0 and ℓ = 1, we shall simply write F_{T,f_{1}^{1},...,f_{k}^{1},...,f_{1}^{m},...,f_{k}^{m}} for F_{T,L,ℓ,f_{1}^{1},...,f_{k}^{1},...,f_{1}^{m},...,f_{k}^{m}}.

Our goal is to interpret (23) as a weighted sum over all elements

F ∈ F_{T,L,ℓ,f_{1}^{1},...,f_{k}^{1},...,f_{1}^{m},...,f_{k}^{m}}.

5 6 11  5  1  9  4 10 3  8 8  11 2  4  1 10 7  6 X_{3} X_{2}  X_{3} X_{3} X_{1} X_{1} X_{2} X_{2} X_{3} 2 10 7 5 1 6 9 3 10 8  7  3 11 5  6  9 11  Σ_{1} σ_{1} σ_{1} Σ_{2} f_{1}^{2} = 2 X_{1} X_{1} 1 7  2 9  3 8  4 2f_{1}^{1} = 2 f_{2}^{1} = 1  f_{3}^{1} = 3  f_{3}^{2} = 2 f_{3}^{2} = 1 4

Figure 6. A combinatorial object arising from (23).

The q-multinomial coefficient can be interpreted as

\left[{n \atop f_{1}^{1}, …, f_{k}^{1}, …, f_{1}^{m}, …, f_{k}^{m}}\right]_{q} = ∑_{r∈R(1^{f^{1}_{1}}···k^{f^{1}_{k}}···((m−1)k+1)^{f^{m}_{1}}((m−1)k+2)^{f^{m}_{2}}···(mk)^{f^{m}_{k}})} q^{inv(r)}.

Similarly,

\left[{n \atop f_{1}^{1}, …, f_{k}^{1}, …, f_{1}^{m}, …, f_{k}^{m}}\right]_{q} = ∑_{r∈R(1^{f^{1}_{1}}···k^{f^{1}_{k}}···((m−1)k+1)^{f^{m}_{1}}((m−1)k+2)^{f^{m}_{2}}···(mk)^{f^{m}_{k}})} q^{coinv(r)}.

Given a rearrangement

r ∈ R(1^{f_{1}^{1}}2^{f_{2}^{1}} ⋯ k^{f_{k}^{1}} ⋯ ((m − 1)k + 1)^{f_{1}^{m}}((m − 1)k + 2)^{f_{2}^{m}} ⋯ (mk)^{f_{k}^{m}}),

we may associate a permutation σ_{r} by labeling the 1’s from right to left with 1, …, f_{1}^{1}, labeling the 2’s from right to left with f_{1}^{1} + 1, …, f_{1}^{1} + f_{2}^{1}, etc. Then inv(σ_{r}) = inv(r) + ∑_{i=1}^{m} ∑_{j=1}^{k} \binom{f_{j}^{i}}{2} and σ_{r}^{−1} consists of a list of the positions of the 1’s in r in decreasing order, followed by a list of positions of the 2’s in r in decreasing order, etc.

For example, suppose n = 11, b_{1} = 6, b_{2} = 5, and f_{1}^{1} = 2, f_{2}^{1} = 1, f_{3}^{1} = 3, f_{1}^{2} = 2, f_{2}^{2} = 2 and f_{3}^{2} = 1. Then if we consider the rearrangement r = 1 3 4 2 1 4 3 4 2, we find

\begin{aligned}r & = & 1 & 3 & 4 & 2 & 1 & 5 & 3 & 4 & 6 & 3 & 5 , \\ σ_{r} & = & 2 & 6 & 8 & 3 & 1 & 10 & 5 & 7 & 11 & 4 & 9 , \\ σ_{r}^{−1} & = & 5 & 1 & 4 & 10 & 7 & 2 & 8 & 3 & 11 & 6 & 9 . \end{aligned}

Such a σ_{r}^{−1} corresponds to a legitimate filling of one of the rows of a configuration of an element F of F_{T,L,ℓ,f_{1}^{1},...,f_{k}^{1},...,f_{1}^{m},...,f_{k}^{m}}. Since this labeling process can be reversed, the map r → σ_{r}^{−1} is bijection from

R(1^{f_{1}^{1}}2^{f_{2}^{1}} ⋯ k^{f_{k}^{1}} ⋯ ((m − 1)k + 1)^{f_{1}^{m}}((m − 1)k + 2)^{f_{2}^{m}} ⋯ (mk)^{f_{k}^{m}})

onto F_{T,f_{1}^{1},...,f_{k}^{1},...,f_{1}^{m},...,f_{k}^{m}}. Our labeling insures that

inv(σ_{r}) = inv(r) + ∑_{i=1}^{m} ∑_{j=1}^{k} \binom{f_{j}^{i}}{2} and coinv(σ_{r}) = coinv(r).

Since inv(σ_{r}) = inv(σ_{r}^{−1}) and coinv(σ_{r}) = coinv(σ_{r}^{−1}), it follows that

q∑{m \atop i=1} ∑{k \atop j=1} ^{\binom{f^{i}_{j}}{2}}\left[{n \atop f_{1}^{1}, …, f_{k}^{1}, …, f_{1}^{m}, …, f_{k}^{m}}\right]_{q} = ∑_{σ∈F_{T,f^{1}_{1},...,f^{1}_{k},...,f^{m}_{1},...,f^{m}_{k}}} q^{inv(σ)} and (24)

\left[{n \atop f_{1}^{1}, …, f_{k}^{1}, …, f_{1}^{m}, …, f_{k}^{m}}\right]_{q} = ∑_{σ∈F_{T,f^{1}_{1},...,f^{1}_{k},...,f^{m}_{1},...,f^{m}_{k}}} q^{coinv(σ)}.  (25)

It follows from (24) and (25) that if we let ϵ = x_{1}^{f_{1}^{1}} ⋯ x_{k}^{f_{k}^{1}} ⋯ x_{1}^{f_{m}^{1}} ⋯ x_{k}^{f_{m}^{1}}, then we have the following.

Lemma 8.

∏_{j=1}^{k} X_{j}^{f_{j}^{1}+···+f_{j}^{m}} ∏_{a=1}^{L} \left[{n \atop f_{1}^{1}, …, f_{k}^{1}, …, f_{1}^{m}, …, f_{k}^{m}}\right]_{Q_{a}}Q∑_{i=1}^{m} ∑_{j=1}^{k} \binom{f^{i}_{j}}{2}_{a}

× ∏_{b=1}^{ℓ} \left[{n \atop f_{1}^{1}, …, f_{k}^{1}, …, f_{1}^{m}, …, f_{k}^{m}}\right]_{q_{b}}

= ∏_{j=1}^{k} X_{j}^{ℓ(ϵ|x_{j})} ∑_{F =(Σ^{(1)},...,Σ^{(L)},σ^{(1)},...,σ^{(ℓ)})∈F_{T,L,ℓ,f^{1}_{1},...,f^{1}_{k},...,f^{m}_{1},...,f^{m}_{k}}} Q^{inv(Σ^{(1)},...,Σ^{(L)};ϵ)}q^{coinv(σ^{(1)},...,σ^{(ℓ)};ϵ)}.

Next we show that modifications of our labeling allows us to prove an analogue of Lemma 8 where we replace the statistics inv and coinv with F Hinv and F Hcoinv.

Given a rearrangement

r ∈ R(1^{f_{k}^{1}} ⋯ m^{f_{k}^{m}}(m + 1)^{f_{k−1}^{1}} ⋯ (2m)^{f_{k−1}^{m}} ⋯ ((k − 1)m + 1)^{f_{1}^{1}}((k − 1)m + 2)^{f_{1}^{2}} ⋯ (km)^{f_{1}^{m}}),

we can associate a permutation σ_{r} by labeling the 1’s from right to left with 1, …, f_{k}^{1}, labeling the 2’s from right to left with f_{k}^{1} + 1, …, f_{k}^{1} + f_{k}^{2}, etc. As before, σ_{r}^{−1} consists of a list of the positions of the 1’s in r in decreasing order, followed by a list of positions of the 2’s in r in decreasing order, etc.

For example, suppose that n = 11, b_{1} = 6, b_{2} = 5, and f_{1}^{1} = 2, f_{2}^{1} = 1, f_{3}^{1} = 3, f_{1}^{2} = 2, f_{2}^{2} = 2, f_{3}^{2} = 1 and we consider the rearrangement r = 6 1 5 1 2 1 4 2 5 4 6 3. Since in the end we want the positions corresponding to the f_{j}^{i}’s weighted by X_{j}, we place the X_{j} on top of all the numbers corresponding to f_{j}^{i}’s. Doing this, we would find

\begin{aligned}& & X_{1} & X_{3} & X_{1} & X_{3} & X_{2} & X_{3} & X_{2} & X_{3} & X_{1} & X_{2} & X_{1} \\ r & = & 6 & 1 & 5 & 1 & 3 & 1 & 4 & 2 & 5 & 4 & 6 \end{aligned}

\begin{aligned}& & X_{1} & X_{3} & X_{1} & X_{3} & X_{2} & X_{3} & X_{2} & X_{3} & X_{1} & X_{2} & X_{1} \\ σ_{r} & = & 11 & 3 & 9 & 2 & 5 & 1 & 7 & 4 & 9 & 6 & 10 \end{aligned}

and

\begin{aligned}& & X_{3} & X_{3} & X_{3} & X_{3} & X_{2} & X_{2} & X_{2} & X_{1} & X_{1} & X_{1} & X_{1} \\ σ_{r}^{−1} & = & 6 & 4 & 2 & 8 & 5 & 10 & 7 & 9 & 3 & 11 & 1 \end{aligned}

At this point σ_{r}^{−1} does not correspond to a legitimate filling of a configuration of an element in F_{T,f_{1}^{1},...,f_{k}^{1},...,f_{1}^{m},...,f_{k}^{m}} since it consists of decreasing sequences of lengths f_{k}^{1}, …, f_{k}^{m}, …, f_{1}^{1}, f_{1}^{2}, …, f_{1}^{k}. However, we can obtain a legitimate filling of a configuration of F ∈ F_{T,f_{1}^{1},...,f_{k}^{1},...,f_{1}^{m},...,f_{k}^{m}} by rearranging the decreasing sequences corresponding to f_{j}^{i} so that the decreasing sequences correspond to the order f_{1}^{1}, …, f_{k}^{1}, …, f_{1}^{m}, …, f_{k}^{m}. Let us call the result of this rearrangement σ_{r}^{∗}. In our example.

\begin{aligned}& & X_{1} & X_{1} & X_{2} & X_{3} & X_{3} & X_{3} & X_{1} & X_{1} & X_{2} & X_{2} & X_{3} \\ σ_{r}^{∗} & = & 9 & 3 & 5 & 6 & 4 & 2 & 11 & 1 & 10 & 7 & 8 \end{aligned}

If we let ϵ = x_{k}^{∑_{i=1}^{m} f_{k}^{i}} ⋯ x_{1}^{∑_{i=1}^{m} f_{1}^{i}} and ϵ^{∗} = x_{1}^{f_{1}^{1}} ⋯ x_{k}^{f_{k}^{1}} ⋯ x_{1}^{f_{m}^{1}} ⋯ x_{k}^{f_{m}^{1}}, it may be seen that, since in σ_{r}^{−1}, all the X_{m}’s precede all the X_{i}’s for i = 1, …, m − 1, all the X_{m−1}’s precede all the X_{i}’s for i = 1, …, m − 2, etc., we have

∑_{i=1}^{m} ∑_{j=1}^{k} \binom{f_{j}^{i}}{2} + inv(r) = inv(σ_{r})

= inv(σ_{r}^{−1})

= ∑_{j−1}^{k} inv((σ_{r}^{−1})_{ϵ|x_{j}}) + ∑_{i,j} χ(ϵ_{i} = x_{t}, ϵ_{j} = x_{s}, t > s, (σ_{r}^{−1})_{i} > (σ_{r}^{−1})_{j})

= ∑_{j=1}^{k} inv((σ_{r}^{∗})_{ϵ^{∗}|x_{j}}) + ∑_{i,j} χ(ϵ_{i} = x_{t}, ϵ_{j} = x_{s}, t > s, (σ_{r}^{∗})_{i} > (σ_{r}^{∗})_{j})

= F Hinv(σ_{r}^{∗}).

It follows that

q∑{m \atop i=1} ∑{k \atop j=1} ^{\binom{f^{i}_{j}}{2}}\left[{n \atop f_{1}^{1}, …, f_{k}^{1}, …, f_{1}^{m}, …, f_{k}^{m}}\right]_{q} = ∑_{σ∈F_{T,f^{1}_{1},...,f^{1}_{k},...,f^{m}_{1},...,f^{m}_{k}}} q^{F Hinv(σ)}.  (26)

We also need to prove that

\left[{n \atop f_{1}^{1}, …, f_{k}^{1}, …, f_{1}^{m}, …, f_{k}^{m}}\right]_{q} = ∑_{σ∈F_{T,f^{1}_{1},...,f^{1}_{k},...,f^{m}_{1},...,f^{m}_{k}}} q^{F Hcoinv(σ)}.  (27)

This case requires a slightly different labeling. Given a rearrangement

r ∈ R(1^{f_{1}^{1}} ⋯ m^{f_{1}^{m}} ⋯ ((k − 1)m + 1)^{f_{k}^{1}} ⋯ (km)^{f_{k}^{m}}),

we may associate a permutation σ_{r} by labeling the 1’s from right to left with 1, …, f_{1}^{1}, labeling the 2’s from right to left with f_{1}^{1} + 1, …, f_{1}^{1} + f_{1}^{2}, etc. As before, σ_{r}^{−1} consists of a list of the positions of the 1’s in r in decreasing order, followed by a list of positions of the 2’s in r in decreasing order, etc. For example, consider the case where n = 11, b_{1} = 6, b_{2} = 5, and f_{1}^{1} = 2, f_{2}^{1} = 1, f_{3}^{1} = 3, f_{1}^{2} = 2, f_{2}^{2} = 2, f_{3}^{2} = 1 and the rearrangement r = 1 5 6 2 2 4 3 5 4 1 5. Placing an X_{j} on top of all the numbers corresponding to f_{j}^{i}’s, we find

\begin{aligned}& & X_{1} & X_{3} & X_{3} & X_{1} & X_{1} & X_{2} & X_{2} & X_{3} & X_{2} & X_{1} & X_{3} \\ r & = & 1 & 5 & 6 & 2 & 2 & 4 & 3 & 5 & 4 & 1 & 5 \end{aligned}

\begin{aligned}& & X_{1} & X_{3} & X_{3} & X_{1} & X_{1} & X_{2} & X_{2} & X_{3} & X_{2} & X_{1} & X_{3} \\ σ_{r} & = & 2 & 10 & 11 & 4 & 3 & 7 & 5 & 9 & 6 & 1 & 8 \end{aligned}

and

\begin{aligned}& & X_{1} & X_{1} & X_{1} & X_{1} & X_{2} & X_{2} & X_{2} & X_{3} & X_{3} & X_{3} & X_{3} \\ σ_{r}^{−1} & = & 10 & 1 & 5 & 4 & 7 & 9 & 6 & 11 & 8 & 2 & 3. \end{aligned}

At this point σ_{r}^{−1} does not correspond to a legitimate filling of a configuration of a member of F_{T,f_{1}^{1},...,f_{k}^{1},...,f_{1}^{m},...,f_{k}^{m}}. To find a legitimate filling, move the decreasing sequences corresponding to f_{j}^{i} so that the decreasing sequences correspond to the order f_{1}^{1}, …, f_{k}^{1}, …, f_{1}^{m}, …, f_{k}^{m}. This rearrangement will be called σ_{r}^{∗∗}.

In our example,

\begin{aligned}& & X_{1} & X_{1} & X_{2} & X_{3} & X_{3} & X_{3} & X_{1} & X_{1} & X_{2} & X_{2} & X_{3} \\ σ_{r}^{∗∗} & = & 10 & 1 & 7 & 11 & 8 & 2 & 5 & 4 & 9 & 6 & 3 \end{aligned}

By letting ϵ = x_{1}^{∑_{i=1}^{m} f_{1}^{i}} ⋯ x_{k}^{∑_{i=1}^{m} f_{k}^{i}} and ϵ^{∗∗} = x_{1}^{f_{1}^{1}} ⋯ x_{k}^{f_{k}^{1}} ⋯ x_{1}^{f_{m}^{1}} ⋯ x_{k}^{f_{m}^{1}}, we see that coinv(r), coinv(σ_{r}), and coinv(σ_{r}^{−1}) are all equal to

∑_{j−1}^{k} coinv((σ_{r}^{−1})_{ϵ|x_{j}}) + ∑_{i,j} χ(ϵ_{i} = x_{t}, ϵ_{j} = x_{s}, t > s, (σ_{r}^{−1})_{i} > (σ_{r}^{−1})_{j}).

However, this is equal to

∑_{j=1}^{k} coinv((σ_{r}^{∗∗})_{ϵ^{∗∗}|x_{j}}) + ∑_{i,j} χ(ϵ_{i} = x_{t}, ϵ_{j} = x_{s}, t > s, (σ_{r}^{∗∗})_{i} > (σ_{r}^{∗∗})_{j}),

which in turn is equal to F Hcoinv(σ_{r}^{∗∗}). This shows that (27) holds.

Combining the results from (24), (25), (26), and (27), if we let

ϵ = x_{1}^{f_{1}^{1}} ⋯ x_{k}^{f_{k}^{1}} ⋯ x_{1}^{f_{m}^{1}} ⋯ x_{k}^{f_{m}^{1}},

L = L_{1} + L_{2}, and ℓ = ℓ_{1} + ℓ_{2}, then we arrive at the following lemma.

GENERATING FUNCTIONS FOR STATISTICS ON C_{k} ≀ S_{n} 29

Lemma 9.

∏_{j=1}^{k} X_{j}^{∑_{i=1}^{m} f_{j}^{i}} ∏_{a=1}^{L} \left[{n \atop f_{1}^{1}, …, f_{k}^{1}, …, f_{1}^{m}, …, f_{k}^{m}}\right]_{Q_{a}}Q∑_{i=1}^{m} ∑_{j=1}^{k} \binom{f^{i}_{j}}{2}_{a}

× ∏_{b=1}^{ℓ} \left[{n \atop f_{1}^{1}, …, f_{k}^{1}, …, f_{1}^{m}, …, f_{k}^{m}}\right]_{q_{b}}

= ∏_{j=1}^{k} X_{j}^{ℓ(ϵ|x_{j})} ∑_{F =(Σ^{(1)},...,Σ^{(L)},σ^{(1)},...,σ^{(ℓ)})∈F_{T,L,ℓ,f^{1}_{1},...,f^{1}_{k},...,f^{m}_{1},...,f^{m}_{k}}} ∏_{i=1}^{L_{1}} Q_{i}^{F Hinv(Σ^{(i)},ϵ)}

× ∏_{i=L_{1}+1}^{L} Q_{i}^{inv(Σ^{(i)},ϵ)} ∏_{i=1}^{ℓ_{1}} q_{i}^{F Hcoinv(σ^{(i)},ϵ)} ∏_{i=1+ℓ_{1}}^{ℓ} q_{i}^{coinv(σ^{(i)},ϵ)}.

We now are in position to give our combinatorial interpretation of (Q, Q)_{n}(q, q)_{n}ξ(p_{n,ν_{d}}). Recall that we have shown (Q, Q)_{n}(q, q)_{n}ξ(p_{n,ν_{d}}) is equal to

∑_{μ⊢n}(t − 1)^{n−ℓ(μ)} ∑_{T =(b_{1},...,b_{m})∈B_{μ,n}} ∑_{f_{j}^{i}≥0,f_{1}^{i}+···f_{k}^{i}=b_{i}} (∏_{t=1}^{k} X_{t}^{f_{t}^{1}+···+f_{t}^{m}}) t^{χ(f_{d+1}^{m}+···+f_{k}^{m}=0)}

× ∏_{a=1}^{L} \left[{n \atop f_{1}^{1}, …, f_{k}^{1}, …, f_{1}^{m}, …, f_{k}^{m}}\right]_{Q_{a}}Q∑_{i=1}^{m} ∑_{j=1}^{k} \binom{f^{i}_{j}}{2}_{a} ∏_{b=1}^{ℓ} \left[{n \atop f_{1}^{1}, …, f_{k}^{1}, …, f_{1}^{m}, …, f_{k}^{m}}\right]_{q_{b}}. (28)

We interpret (28) as follows. For each brick T = (b_{1}, …, b_{m}) ∈ B_{μ,n} and for each choice for the values of f_{1}^{1}, …, f_{k}^{1}, …, f_{1}^{m}, …, f_{k}^{m} from the sums ∑_{i=1}^{m} ∑_{f_{1}^{i}+···+f_{k}^{i}=b_{i}}, the term

∏_{j=1}^{k} X_{j}^{∑_{i=1}^{m} f_{j}^{i}} ∏_{a=1}^{L} \left[{n \atop f_{1}^{1}, …, f_{k}^{1}, …, f_{1}^{m}, …, f_{k}^{m}}\right]_{Q_{a}}Q∑_{i=1}^{m} ∑_{j=1}^{k} \binom{f^{i}_{j}}{2}_{a}

× ∏_{b=1}^{ℓ} \left[{n \atop f_{1}^{1}, …, f_{k}^{1}, …, f_{1}^{m}, …, f_{k}^{m}}\right]_{q_{b}}

can be viewed as the sum

∏_{j=1}^{k} X_{j}^{ℓ(ϵ|x_{j})} ∑_{F =(Σ^{(1)},...,Σ^{(L)},σ^{(1)},...,σ^{(ℓ)})∈F_{T,L,ℓ,f^{1}_{1},...,f^{1}_{k},...,f^{m}_{1},...,f^{m}_{k}}} ∏_{i=1}^{L_{1}} Q_{i}^{F Hinv(Σ^{(i)},ϵ)}

× ∏_{i=L_{1}+1}^{L} Q_{i}^{inv(Σ^{(i)},ϵ)} ∏_{i=1}^{ℓ_{1}} q_{i}^{F Hcoinv(σ^{(i)},ϵ)} ∏_{i=1+ℓ_{1}}^{ℓ} q_{i}^{coinv(σ^{(i)},ϵ)}

where ϵ = x_{1}^{f_{1}^{1}} ⋯ x_{k}^{f_{k}^{1}} ⋯ x_{1}^{f_{m}^{1}} ⋯ x_{k}^{f_{m}^{1}}.

If f_{d+1}^{m} + ⋯ + f_{k}^{m} ≠ 0, then we have a factor of (t − 1)^{n−ℓ(μ)}. For each F = (Σ^{(1)}, …, Σ^{(L)}, σ^{(1)}, …, σ^{(ℓ)})

5 6 11  5  1  9  4 10 3  8 8  11 2  4  1 10 7  6 X_{3} X_{2}  X_{3} X_{3} X_{1} X_{1} X_{2} X_{2} X_{3} 2 10 7 5 1 6 9 3 10 8  7  3 11 5  6  9 11  Σ_{1} σ_{1} σ_{1} Σ_{2} f_{1}^{2} = 2 X_{1} X_{1} 1 7  2 9  3 8  4 2f_{1}^{1} = 2 f_{2}^{1} = 1  f_{3}^{1} = 2  f_{3}^{2} = 2 f_{3}^{2} = 1 t  t  t −1 −1 1  t  t −1 t  1 4

Figure 7. An example of a configuration arising from (28).

in F_{T,L,ℓ,f_{1}^{1},...,f_{k}^{1},...,f_{1}^{m},...,f_{k}^{m}}, create a new set of weighted objects by placing a t or a −1 in cell of T which is not at the end of a brick and placing a 1 in each cell which at the end of the brick.

For example, if we let k = 3, d = 2, T = (6, 5) and f_{1}^{1} = 2, f_{2}^{1} = 1, f_{3}^{1} = 3, f_{1}^{2} = 2, f_{2}^{2} = 2, f_{3}^{2} = 1, then we would obtain configuration C as the one pictured in Figure 7. We then let w(C) be the product of the all the −1’s, t’s, X_{j}’s appearing in the configuration. For the configuration appearing in Figure 7, w(C) = −t^{6}X_{1}^{4}X_{2}^{3}X_{3}^{4}.

If f_{d+1}^{m} + ⋯ + f_{k}^{m} = 0, then we have a factor of t(t − 1)^{n−ℓ(μ)}. As before, for each member F = (Σ^{(1)}, …, Σ^{(L)}, σ^{(1)}, …, σ^{(ℓ)}) of the set F_{T,L,ℓ,f_{1}^{1},...,f_{k}^{1},...,f_{1}^{m},...,f_{k}^{m}}, we create a new set of weighted objects by placing a t or a −1 in cell of T which is not at the end of a brick and placing a 1 in each cell which at the end of the brick which is not the final brick and placing a t in the last cell of the final brick.

Let C_{T,L,ℓ,f_{1}^{1},...,f_{k}^{1},f_{1}^{2},...,f_{k}^{2},...,f_{1}^{m},...,f_{k}^{m}} denote the set of all configurations C constructed from one of the F = (Σ^{(1)}, …, Σ^{(L)}, σ^{(1)}, …, σ^{(ℓ)}) ∈ F_{T,L,ℓ,f_{1}^{1},...,f_{k}^{1},...,f_{1}^{m},...,f_{k}^{m}} and let

C_{n} = ⋃_{μ⊢n} ⋃_{T =(b_{1},...,b_{m})∈B_{μ,n}} ⋃_{i=1}^{m} ⋃_{f_{1}^{i}+···f_{m}^{i}=b_{i}} C_{T,L,ℓ,f_{1}^{1},...,f_{k}^{1},...,f_{1}^{m},...,f_{k}^{m}}.

If C ∈ C_{T,L,ℓ,f_{1}^{1},...,f_{k}^{1},...,f_{1}^{m},...,f_{k}^{m}} is constructed from an element

F = (Σ^{(1)}, …, Σ^{(L)}, σ^{(1)}, …, σ^{(ℓ)})

which is a member of F_{T,L,ℓ,f_{1}^{1},...,f_{k}^{1},...,f_{1}^{m},...,f_{k}^{m}}, then we let

U_{d}(C) = w(C) ∏_{i=1}^{L_{1}} Q_{i}^{F Hinv(Σ^{(i)},ϵ)} ∏_{i=1+L_{1}}^{L} Q_{i}^{inv(Σ^{(i)},ϵ)} ∏_{i=1}^{ℓ_{1}} q_{i}^{F Hcoinv(σ^{(i)},ϵ)} ∏_{i=1+ℓ_{1}}^{ℓ} q_{i}^{coinv(σ^{(i)},ϵ)}.

It follows that

(Q, Q)_{n}(q, q)_{n}ξ(p_{n,ν_{d}}) = ∑_{C∈C_{n}} U_{d}(C).  (29)

In order to use (22) and (29) to prove Theorem 7, we need to show that

∑_{C∈C_{n}} U_{d}(C) = W_{n}^{(4,d)}(X_{1}, …, X_{k}, t, Q, q).  (30)

5 6 11  5  1  9  4 10 3  8 8  11 2  4  1 10 7  6 X_{3} X_{2}  X_{3} X_{3} X_{1} X_{1} X_{2} X_{2} X_{3} 2 10 7 5 1 6 9 3 10 8  7  3 11 5  6  9 11  Σ_{1} σ_{1} σ_{1} Σ_{2} f_{1}^{3} = 2 X_{1} X_{1} 1 7  2 9  3 8  4 2f_{1}^{1} = 2 f_{2}^{1} = 1  f_{2}^{3} = 2 f_{3}^{3} = 1 t  t  t  1 −1 1  t  t −1 t  1 f_{3}^{1} = 2 f_{3}^{2} = 2  4

Figure 8. The image of Figure 7 under I

To do this, we will define a sign-reversing involution I on C_{n} so that the fixed points of I will give the desired right hand side of (30). Our involution I is essentially the same as the one we used in the proofs of Theorems 1 and 3.

To define I, we first need the concept of when a sequence of cells in C forms a decreasing sequence. Suppose C is constructed from F = (Σ^{(1)}, …, Σ^{(L)}, σ^{(1)}, …, σ^{(ℓ)}) which is a member of the set F_{T,L,ℓ,f_{1}^{1},...,f_{k}^{1},...,f_{1}^{m},...,f_{k}^{m}}. Then we say that a sequence of cells in c, …, c + k in C forms a decreasing sequence if

(i) the labels at the top of the cells c, c + 1, …, c + k when read from left to right is a word of the form X_{1}^{u_{1}} ⋯ X_{k}^{u_{k}} for some u_{i} ≥ 0 and

(ii) the entries in each of the rows corresponding to Σ^{(1)}, …, Σ^{(L)}, σ^{(1)}, …, σ^{(ℓ)} are decreasing in cells whose labels are X_{j} for j = 1, … k.

By definition, the cells corresponding to each brick in a configuration C ∈ C_{n} form a decreasing sequence. This given, we can define our involution I as follows.

Given C ∈ C_{n}, scan the cells of the C from left to right until either

• Case 1: there is a cell c with a −1 in which case I(C) is the result of changing the weight cell c to 1 and breaking the brick b_{i} which contains cell c into two bricks b′ and b′′ where b′ ends at cell c, or

• Case 2: we find two consecutive bricks b_{i} and b_{i+1} such that cells corresponding to b_{i} and b_{i+1} form a decreasing sequence in which case I(C) is the result of combining bricks b_{i} and b_{i+1} into a single brick b and changing the weight of the last cell of b_{i} from 1 to −1.

If neither Case 1 or Case 2 holds, let I(C) = C.

For example, if we consider the configuration C pictured in Figure 7, then we are Case 1 with cell c equal to cell 4 so that I(C) = C′ where C′ is pictured in Figure 8. However, C′ is in Case 2 because we can combine bricks b_{1} and b_{2} so that I(C′) is equal to C.

The definitions of I leave the permutations (Σ^{(1)}, …, Σ^{(L)}, σ^{(1)}, …, σ^{(ℓ)}) unchanged. Moreover, since we do not change any of the labels at the top of the column, it follows that if cell n has an X_{i} for some i ∈ {1, …, d} at the top of the column, then cell n of both C and I(C) must have an X_{i} for some i ∈ {1, …, d} and hence the weight of cell n in both C and I(C) is equal to t.

Our definitions ensure that if I(C) ≠ C, then U_{d}(C) = −U_{d}(I(C)) and I(I(C)) = C. Let F ix_{I} = {C ∈ C_{n} : I(C) = C}. Then I shows that

∑_{C∈C_{n}} U_{d}(C) = ∑_{C∈F ix_{I}} U_{d}(C).

What are the fixed points of I? Suppose that C ∈ F ix_{I} and C is constructed from an element F = (Σ^{(1)}, …, Σ^{(L)}, σ^{(1)}, …, σ^{(ℓ)}) of the set F_{T,L,ℓ,f_{1}^{1},...,f_{k}^{1},...,f_{1}^{m},...,f_{k}^{m}}. Then no cell of C can have label −1 and the sequence of cells in any two consecutive bricks do not form a decreasing sequence. This means that if b_{i} and b_{i+1} are two consecutive bricks in C, s is last cell in b_{i}, s + 1 is the first cell of b_{i+1}, and ϵ = x_{1}^{f_{1}^{1}}x_{2}^{f_{2}^{1}} ⋯ x_{k}^{f_{k}^{1}} ⋯ x_{1}^{f_{1}^{m}}x_{2}^{f_{2}^{m}} ⋯ x_{k}^{f_{k}^{m}}, then either

(a) ϵ_{s} = x_{i} and ϵ_{s+1} = x_{j} for some i > j, or

(b) ϵ_{s} = x_{j} and ϵ_{s+1} = x_{j} for some i = j, …, k and there is some i such that Σ^{(i)}(s) < Σ^{(i)}(s + 1) or there is some r such that σ^{(r)}(s) < σ^{(r)}(s + 1).

It follows that s ∉ Comdes^{d}(Σ^{(1)}, …, Σ^{(L)}, σ^{(1)}, …, σ^{(ℓ)}; ϵ) and that the weight of cell s is 1. For s = n, our definitions ensure that s ∈ Comdes^{d}(Σ^{(1)}, …, Σ^{(L)}, σ^{(1)}, …, σ^{(ℓ)}; ϵ) if and only if ϵ_{n} = x_{i} for some i in {1, …, d}. Thus if ϵ_{n} = x_{j} for some j ∈ {d + 1, …, k}, then n ∉ Comdes^{d}(Σ^{(1)}, …, Σ^{(L)}, σ^{(1)}, …, σ^{(ℓ)}; ϵ) and cell n has weight 1. If ϵ_{n} = x_{i} where i ∈ {1, …, d}, then n ∈ Comdes^{d}(Σ^{(1)}, …, Σ^{(L)}, σ^{(1)}, …, σ^{(ℓ)}; ϵ) and the weight of cell n is t. If s is not the last cell of a brick, then our definitions ensure that if s ∈ Comdes^{d}(Σ^{(1)}, …, Σ^{(L)}, σ^{(1)}, …, σ^{(ℓ)}; ϵ), then the weight of cell s is t. It follows that w(C) = t^{comdes^{d}(Σ,σ;ϵ)}.

Thus if C ∈ F ix_{I} and C is constructed from an element

F = (Σ^{(1)}, …, Σ^{(L)}, σ^{(1)}, …, σ^{(ℓ)}; ϵ)

of the set F_{T,L,ℓ,f_{1}^{1},...,f_{k}^{1},...,f_{1}^{m},...,f_{k}^{m}}, then

U_{d}(C) = t^{comdes^{d}(Σ,σ,ϵ)} ∏_{i=1}^{L_{1}} Q_{i}^{F Hinv(Σ^{(i)},ϵ)} ∏_{i=1+L_{1}}^{L} Q_{i}^{inv(Σ^{(i)},ϵ)} ∏_{i=1}^{ℓ_{1}} q_{i}^{F Hcoinv(σ^{(i)},ϵ)} ∏_{i=1+ℓ_{1}}^{ℓ} q_{i}^{coinv(σ^{(i)},ϵ)}.

Finally, suppose that we are given (Σ, σ, ϵ) = (Σ^{(1)}, …, Σ^{(L)}, σ^{(1)}, …, σ^{(ℓ)}; ϵ), then we can construct a configuration C ∈ F ix_{I} such that

U(C) = t^{comdes^{d}(Σ,σ,ϵ)} ∏_{i=1}^{L_{1}} Q_{i}^{F Hinv(Σ^{(i)},ϵ)} ∏_{i=1+L_{1}}^{L} Q_{i}^{inv(Σ^{(i)},ϵ)} ∏_{i=1}^{ℓ_{1}} q_{i}^{F Hcoinv(σ^{(i)},ϵ)} ∏_{i=1+ℓ_{1}}^{ℓ} q_{i}^{coinv(σ^{(i)},ϵ)}

as follows. Let the rows of C correspond to the sequence (Σ^{(1)}, …, Σ^{(L)}, σ^{(1)}, …, σ^{(ℓ)}) and label the top of column i with X_{j} if ϵ_{i} = x_{j}. Next, let

E = {1, …, n − 1} − Comdes^{d}(Σ^{(1)}, …, Σ^{(L)}, σ^{(1)}, …, σ^{(ℓ)}; ϵ).

If E = ∅, then C has a single brick of length n and if E = {i_{1} < ⋯ < i_{k}}, then we have bricks ending at i_{1}, …, i_{k}, n. Label each cell i with a t if i ∈ Comdes^{d}(Σ^{(1)}, …, Σ^{(L)}, σ^{(1)}, …, σ^{(ℓ)}) and with a 1 if i ∉ Comdes^{d}(Σ^{(1)}, …, Σ^{(L)}, σ^{(1)}, …, σ^{(ℓ)}). Then C ∈ F ix_{I}.

Therefore,

∑_{C∈C_{n}} U_{d}(C) = ∑_{C∈F ix_{I}} U_{d}(C) = W_{n}^{(4,d)}(X, Y, t, Q, q).

This completes the proof. □

6. Further generalizations of Theorem 7

Theorem 7 specializes to give all previous theorems recorded in this document. It is the most general theorem in this paper up to this point. However, there are still further generalizations which may be found using the methods we are presenting. To show that this is the case, this section extends Theorem 7 according to certain restrictions on the set of common descents. Given a tuple of permutations in C_{k} ≀ S_{n}, (Σ, σ; ϵ), we shall say that it has a final common decreasing segment of size s if {n−s+1, …, n−1} is a subset of Comdes^{d}((Σ, σ; ϵ)) and n − s ∉ Comes^{d}((Σ, σ; ϵ)). Then the goal of this section is to derive generating functions for tuples of permutations in C_{k} ≀S_{n} according to the statistics in Theorem 7 which either have a final common decreasing sequence of size at least s or size exactly s for any given s ≥ 1.

The method we used to prove Theorem 7 can be summarized as follows. First we had a desired generating function in mind. Next we rewrote that generating function in order to read the homomorphism ξ and the weighting function ν_{d}. Then we built combinatorial objects to interpret (Q, Q)_{n}(q, q)_{n}ξ(p_{n,ν_{d}}) Finally we found a weight preserving sign reversing involution to simplify this collection of objects to prove that (Q, Q)_{n}(q, q)_{n}ξ(p_{n,ν_{d}}) = W_{n}^{(4,d)}(X_{1}, …, X_{k}, t, Q, q).

In this section, we shall do something a bit different. We will not have a generating function in mind when trying to simplify a certain permutation statistic. Instead, we will take the already known homomorphism ξ and weighting function ν_{d} and alter them a bit. As a result, the combinatorial objects we constructed will be altered accordingly. Then, the same involution I will simplify things to leave a desired set of objects. In short, instead of being lead by the generating function, we will be lead by the combinatorics.

As in the previous section, let

ξ(e_{n}) = (1 − t)^{n−1} ∑_{f_{j}≥0,f_{1}+···+f_{k}=n} ∏_{j=1}^{k} \frac{X^{f_{i}}Q^{\binom{f_{i}}{2}}}{(Q, Q)_{f_{i}}(q, q)_{f_{i}}} .

Instead of keeping ν_{d} such that ν_{d}(n) is equal to

1 − \frac{(1 − t)^{n−1} ∑_{a_{i}≥0,a_{1}+···+a_{d}=n} ∏_{i=1}^{d} X_{i}^{n}Q^{\binom{a_{i}}{2}}}{ξ(e_{n})(Q, Q)_{a_{i}}(q, q)_{a_{i}}}

+ \frac{t(1 − t)^{n−1} ∑_{a_{i}≥0,a_{1}+···+a_{d}=n} ∏_{i=1}^{d} X_{i}^{a_{i}}Q^{\binom{a_{i}}{2}}}{ξ(e_{n})(Q, Q)_{a_{i}}(q, q)_{a_{i}}} ,

we make an adjustment. Let s ≥ 1 be an integer and define ν_{d,s}(n) = (t/(t − 1)^{s−1}χ(n ≥ s)ν_{d}(n) for d = 1, …, k. Thus ν_{d,s} is the function such that

ν_{d,s}(n) = \begin{cases}0 & if n < s and \\ (\frac{t}{t − 1})^{s−1} ν_{d}(n) & if n ≥ s. \end{cases}  (31)

for all n = 1, 2, . . .. Note ν_{d,1} = ν_{d}. The effect of this modification will occur in the last brick of a combinatorial object because (6) tells us that the function ν_{d,s} changes the weight on the last brick in a weighted brick tabloid.

This change is relatively easy to describe. We can proceed exactly as in the proof of Theorem 7 to show that (Q, Q)_{n}(q, q)_{n}ξ(p_{n,ν_{d,s}}) is equal to

∑_{μ⊢n}(t − 1)^{n−ℓ(μ)} ∑_{T =(b_{1},...,b_{m})∈B_{μ,n}} ∑_{i=1}^{m} ∑_{f_{1}^{i}+···+f_{k}^{i}=b_{i}} ∏_{j=1}^{k} X_{j}^{∑_{i=1}^{m} f_{j}^{i}}(t/(t − 1))^{s−1}χ(b_{m} ≥ s)

× ∏_{a=1}^{L} \left[{n \atop f_{1}^{1}, …, f_{k}^{1}, …, f_{1}^{m}, …, f_{k}^{m}}\right]_{Q_{a}}Q^{∑_{i=1}^{m} ∑_{j=1}^{k} f_{j}^{i}}

× ∏_{b=1}^{ℓ} \left[{n \atop f_{1}^{1}, …, f_{k}^{1}, …, f_{1}^{m}, …, f_{k}^{m}}\right]_{q_{b}}t^{χ(f_{d+1}^{m}+···+f_{k}^{m}=0)}. (32)

The difference in this case is the extra factor of (t/(t − 1)^{s}χ(b_{m} ≥ s) that arises from replacing ν_{d}(n) by ν_{d,s}(n). We can then interpret (32) as a sum over weighted configurations

F = (Σ^{(1)}, …, Σ^{(L)}, σ^{(1)}, …, σ^{(ℓ)}) ∈ F_{T,L,ℓ,f_{1}^{1},...,f_{k}^{1},...,f_{1}^{m},...,f_{k}^{m}}

as in the the proof of Theorem 7 with two modifications. First the factor χ(b_{m} ≥ s) has the effect of eliminating all brick tabloids T = (b_{1}, …, b_{m}) in the sum in (32) such that b_{m} < s. Thus the only configurations that we need to consider have an underlying brick tabloid T whose last brick has length greater than or equal to s. Now if (b_{1}, …, b_{m}) is such that b_{m} ≥ s, then there will be a factor of (t − 1)^{n−ℓ(μ)}(t/(t − 1)^{s−1}t^{χ(f_{d+1}^{m}+···+f_{k}^{m}=0)} which can be rewritten as t^{s−1}(t − 1)^{b_{m}−1−(s−1)}t^{χ(f_{d+1}^{m}+···+f_{k}^{m}=0)} ∏_{i=1}^{m−1}(t − 1)^{b_{i}−1}. This term then effects the weight of a configuration as follows. For each of brick b_{i} with i < m, we weight the cells as before, namely, the last cell in the brick gets weight 1 and every other cell can have weight t or −1. We use the remaining factor t^{s−1}(t − 1)^{b_{m}−1−(s−1)}t^{χ(f_{d+1}^{m}+···+f_{k}^{m}=0)} to weight the cells of the last brick of the configuration as follows. First the last cell gets weight 1 or t depending on whether the label X_{i} at the top of the last column has i ∈ {d+1, …, k} or has i ∈ {1, …, d}. We then use the factor t^{s−1} to weight the s−1 cells immediately to the left of the last cell of b_{m} with t and we use the factor (t − 1)^{b_{m}−1−(s−1)} to weight the remaining cells of b_{m} with either t or −1. As before, we let w(C) be the product of all the −1’s, t’s, and X_{i}’s appearing in the configuration.

Let C_{T,L,ℓ,f_{1}^{1},...,f_{k}^{1},f_{1}^{2},...,f_{k}^{2},...,f_{1}^{m},...,f_{k}^{m}}^{s} denote the set of all configurations C constructed from one of the F = (Σ^{(1)}, …, Σ^{(L)}, σ^{(1)}, …, σ^{(ℓ)}) ∈ F_{T,L,ℓ,f_{1}^{1},...,f_{k}^{1},...,f_{1}^{m},...,f_{k}^{m}} where b_{m} ≥ s in this manner and let

C_{n}^{s} = ⋃_{μ⊢n} ⋃_{T =(b_{1},...,b_{m}),b_{m}≥s)∈B_{μ,n}} ⋃_{i=1}^{m} ⋃_{f_{1}^{i}+···f_{m}^{i}=b_{i}} C_{T,L,ℓ,f_{1}^{1},...,f_{k}^{1},...,f_{1}^{m},...,f_{k}^{m}}^{s}.

If C ∈ C_{T,L,ℓ,f_{1}^{1},...,f_{k}^{1},...,f_{1}^{m},...,f_{k}^{m}}^{s} is constructed from an element

F = (Σ^{(1)}, …, Σ^{(L)}, σ^{(1)}, …, σ^{(ℓ)})

which is a member of F_{T,L,ℓ,f_{1}^{1},...,f_{k}^{1},...,f_{1}^{m},...,f_{k}^{m}}, then we let

U_{d,s}(C) = w(C) ∏_{i=1}^{L_{1}} Q_{i}^{F Hinv(Σ^{(i)},ϵ)} ∏_{i=1+L_{1}}^{L} Q_{i}^{inv(Σ^{(i)},ϵ)} ∏_{i=1}^{ℓ_{1}} q_{i}^{F Hcoinv(σ^{(i)},ϵ)} ∏_{i=1+ℓ_{1}}^{ℓ} q_{i}^{coinv(σ^{(i)},ϵ)}.

It follows that

(Q, Q)_{n}(q, q)_{n}ξ(p_{n,ν_{d,s}}) = ∑_{C∈C_{n}^{s}} U_{d}(C).  (33)

We can apply the same involution I to C_{n}^{s} that we used in Theorem 7. Note that since the s − 1 cells immediately to the left of last cell in each configuration are labeled with t, we will never try to split the last brick at any one of those cells and hence our involution will automatically ensure that the image of any element in C_{n}^{s} will have its last brick of size ≥ s and, hence, I maps C_{n}^{s} onto C_{n}^{s}. The fixed points of I restricted to C_{n}^{s} will be exactly the same as in Theorem 7 with the added condition that the size of the last brick is ≥ s. Thus if C ∈ F ix_{I} ∩C_{n}^{s} and C is constructed from an element F = (Σ^{(1)}, …, Σ^{(L)}, σ^{(1)}, …, σ^{(ℓ)}; ϵ) of the set F_{T,L,ℓ,f_{1}^{1},...,f_{k}^{1},...,f_{1}^{m},...,f_{k}^{m}}, then just as before we will have that

U_{d}(C) = t^{comdes^{d}(Σ,σ,ϵ)} ∏_{i=1}^{L_{1}} Q_{i}^{F Hinv(Σ^{(i)},ϵ)} ∏_{i=1+L_{1}}^{L} Q_{i}^{inv(Σ^{(i)},ϵ)} ∏_{i=1}^{ℓ_{1}} q_{i}^{F Hcoinv(σ^{(i)},ϵ)} ∏_{i=1+ℓ_{1}}^{ℓ} q_{i}^{coinv(σ^{(i)},ϵ)}.

However, since the last brick is of size at least s, then we are guaranteed that

{n − s + 1, …, n − 1} ∈ Comes^{d}((Σ^{(1)}, …, Σ^{(L)}, σ^{(1)}, …, σ^{(ℓ)}; ϵ).

Finally if F = (Σ^{(1)}, …, Σ^{(L)}, σ^{(1)}, …, σ^{(ℓ)}; ϵ) is an element of the set F_{T,L,ℓ,f_{1}^{1},...,f_{k}^{1},...,f_{1}^{m},...,f_{k}^{m}} is such that {n − s + 1, …, n − 1} ∈ Comes^{d}((Σ^{(1)}, …, Σ^{(L)}, σ^{(1)}, …, σ^{(ℓ)}; ϵ), then we can use same argument as in Theorem 7 to show that we can construct a unique C ∈ F ix_{I} ∩C_{n}^{s} whose underlying configuration is F.

Now if we let

W_{n}^{(4,d,s)}(X_{1}, …, X_{k}, t, Q, q) = ∑_{(Σ,σ;ϵ)} (∏_{i=1}^{k} X_{i}^{ℓ(ϵ|x_{i})}) t^{Comdes^{d}(Σ,σ;ϵ)} ∏_{i=1}^{L_{1}} Q_{i}^{F Hinv(Σ^{(i)},ϵ)}

× ∏_{i=1+L_{1}}^{L} Q_{i}^{inv(Σ^{(i)},ϵ)} ∏_{i=1}^{ℓ_{1}} q_{i}^{F Hcoinv(σ^{(i)},ϵ)} ∏_{i=1+ℓ_{1}}^{ℓ} q_{i}^{coinv(σ^{(i)},ϵ)}.

where the sum runs over all ϵ ∈ {x_{1}, …, x_{k}}^{n} and (Σ, σ) ∈ (C_{k} ≀ S_{n})^{L+ℓ} such that {n − s + 1, …, n − 1} is contained in Comdes^{d}((Σ, σ; ϵ)), then it follows that

(Q, Q)_{n}(q, q)_{n}ξ(p_{n,ν_{d,s}}) = W_{n}^{(4,d,s)}(X_{1}, …, X_{k}, t, Q, q).  (34)

36 ANTHONY MENDES AND JEFFREY REMMEL

Hence

∑_{n≥0} \frac{u^{n}}{(Q, Q)_{n}(q, q)_{n}} W_{n}^{(4,d,s)}(X_{1}, …, X_{k}, t, Q, q) = 1 + ∑_{n≥1} ξ(p_{n,ν_{d,s}})u^{n}

= \frac{1 + ∑_{n≥1}(−1)^{n}u^{n}(ξ(e_{n}) − ν_{d,s}(n)ξ(e_{n}))}{∑_{n≥0}(−1)^{n}u^{n}ξ(e_{n})}. (35)

Now the denominator on the right-hand side of (35) is

∑_{n≥0}(−1)^{n}u^{n}ξ(e_{n}) = ∑_{n≥0}(−1)^{n}u^{n}(1 − t)^{n−1} ∑_{b_{j}≥0,b_{1}+···+b_{k}=n} ∏_{j=1}^{k} \frac{X_{j}Q^{\binom{b_{j}}{2}}}{(Q, Q)_{b_{j}}(q, q)_{b_{j}}}

= \frac{1}{1 − t} (1 − t + ∑_{n≥1}(−1)^{n}u^{n}(1 − t)^{n} ∑_{b_{j}≥0,b_{1}+···+b_{k}=n} ∏_{j=1}^{k} \frac{X_{j}Q^{\binom{b_{j}}{2}}}{(Q, Q)_{b_{j}}(q, q)_{b_{j}}} )

= \frac{1}{1 − t} (−t + ∏_{j=1}^{k} J((1 − t)X_{j}u, Q, q)) .

The numerator on the right-hand side of (35) is

1 + ∑_{n≥1}(−1)^{n}u^{n}(ξ(e_{n}) − ν_{d,s}(n)ξ(e_{n}))

= 1 + ∑_{n≥1}(−1)^{n}u^{n}ξ(e_{n}) − ∑_{n≥s}(−1)^{n}u^{n} (\frac{t}{t − 1})^{s−1}

× (ξ(e_{n}) − (1 − t)^{n} ∑_{a_{i}≥0,a_{1}+···+a_{d}=n} ∏_{i=1}^{d} \frac{X_{i}^{a_{i}}Q^{\binom{a_{i}}{2}}}{(Q, Q)_{a_{i}}(q, q)_{a_{i}}} )

= (1 − (\frac{t}{t − 1})^{s−1}) (1 + ∑_{n≥1}(−1)^{n}u^{n}ξ(e_{n}))

+ (\frac{t}{t − 1})^{s−1} (1 + ∑_{n=1}^{s−1}(−1)^{n}u^{n}ξ(e_{n}))

+ (\frac{t}{t − 1})^{s−1} (1 + ∑_{n≥1}(−1)^{n}u^{n}(1 − t)^{n} ∑_{a_{i}≥0,a_{1}+···+a_{d}=n} ∏_{i=1}^{d} \frac{X_{i}^{a_{i}}Q^{\binom{a_{i}}{2}}}{(Q, Q)_{a_{i}}(q, q)_{a_{i}}} )

− (\frac{t}{t − 1})^{s−1} (1 + ∑_{n=1}^{s−1}(−1)^{n}u^{n}(1 − t)^{n} ∑_{a_{i}≥0,a_{1}+···+a_{d}=n} ∏_{i=1}^{d} \frac{X_{i}^{a_{i}}Q^{\binom{a_{i}}{2}}}{(Q, Q)_{a_{i}}(q, q)_{a_{i}}} )

= (1 − (\frac{t}{t − 1})^{s−1}) (\frac{1}{1 − t} (−t + ∏_{j=1}^{k} J((1 − t)X_{j}u, Q, q)))

+ (\frac{t}{t − 1})^{s−1} (∏_{i=1}^{d} J((1 − t)X_{i}u, Q, q))

+ (\frac{t}{t − 1})^{s−1} ∑_{n=1}^{s−1}(−1)^{n}u^{n}

× (ξ(e_{n}) − (1 − t)^{n} ∑_{a_{i}≥0,a_{1}+···+a_{d}=n} ∏_{i=1}^{d} \frac{X_{i}^{a_{i}}Q^{\binom{a_{i}}{2}}}{(Q, Q)_{a_{i}}(q, q)_{a_{i}}} )

= (1 − (\frac{t}{t − 1})^{s−1}) (\frac{1}{1 − t}(−t + ∏_{j=1}^{k} J((1 − t)X_{j}u, Q, q)))

+ (\frac{t}{t − 1})^{s−1} (∏_{i=1}^{d} J((1 − t)X_{i}u, Q, q))

+ (\frac{t}{t − 1})^{s−1} ∑_{n=1}^{s−1}(−1)^{n}u^{n}(1 − t)^{n−1}

× ∑_{b_{j}≥0,b_{1}+···+b_{k}=n} t^{χ(b_{d+1}+···+b_{k}=0)} ∏_{j=1}^{k} \frac{X_{j}^{b_{j}}Q^{\binom{a_{i}}{2}}}{(Q, Q)_{b_{j}}(q, q)_{b_{j}}} .

It then follows that we have the following theorem.

Theorem 10. For all k ≥ 2, d = 1, …, k, and s ≥ 1,

∑_{n≥0} \frac{u^{n}}{(Q, Q)_{n}(q, q)_{n}} W_{n}^{(4,d,s)}(X_{1}, …, X_{k}, t, Q, q)

= (1 − (\frac{t}{t − 1})^{s−1}) + (\frac{t}{t − 1})^{s−1} \frac{(1 − t) ∏_{i=1}^{d} J((1 − t)X_{i}u, Q, q)}{−t + ∏_{j=1}^{k} J((1 − t)X_{j}u, Q, q)}

+ (\frac{t}{t − 1})^{s−1} \frac{∑_{n=1}^{s−1}(−1)^{n}u^{n}(1 − t)^{n} ∑_{b_{j}≥0,b_{1}+···+b_{k}=n} t^{χ(b_{d+1}+···+b_{k}=0)} ∏_{j=1}^{k} ^{\frac{X_{j}^{b_{j}} Q^{\binom{b_{j}}{2}}}{(Q,Q)_{b_{j}} (q,q)_{b_{j}}}}}{−t + ∏_{j=1}^{k} J(u(1 − t)X_{j}, Q, q)} .

Next we present another modification which will product a generating functions for those tuples of permutations (Σ, σ; ϵ) in C_{k} ≀ S_{n} such that {n − s + 1, …, n − 1} ⊆ Comdes^{d}((Σ, σ; ϵ)) but n − s ∉ Comdes^{d}((Σ, σ; ϵ)) That is, for d = 1, …, k, define a function \overline{ν}_{d,s} such that

\overline{ν}_{d,s}(n) = \begin{cases}0 & if n < s, \\ (\frac{t}{t − 1})^{s−1} ν_{d}(n) & if n = s, and \\ (\frac{−1}{t − 1}) (\frac{t}{t − 1})^{s−1} ν_{d}(n) & if n > s. \end{cases}

for all n = 1, 2, . . .. Again the effect of this modification will occur in the last brick of a combinatorial object because (6) tells us that the function ν_{d,s} changes the weight on the last brick in a weighted brick tabloid.

5 6 11  5  1  9  4 10 3  8 8  11 2  4  1 10 7  6 X_{3} X_{2}  X_{3} X_{3} X_{1} X_{1} X_{2} X_{2} X_{3} 2 10 7 5 1 6 9 3 10 8  7  3 11 5  6  9 11  Σ_{1} σ_{1} σ_{1} Σ_{2} f_{1}^{2} = 2 X_{1} X_{1} 1 7  2 9  3 8  4 2f_{1}^{1} = 2 f_{2}^{1} = 1  f_{3}^{1} = 2  f_{3}^{2} = 2 f_{3}^{2} = 1 t  t  t −1 −1 1  −1 t  t  1 −1 These values must be −1 t t 1. 4

Figure 9. A combinatorial object coming from ξ and ν_{d,3}.

This change is also relatively easy to describe. Suppose the last brick of the underlying brick tabloid of a configuration has a length b. If b < s, then the weight assigned by \overline{ν}_{d,s} is 0 as before. If b = s, then we use the extra factor of (t/(t − 1))^{s−1} that occurs in the \overline{ν}_{d,s}(s) to ensure that the weights of each of the s − 1 cells immediately preceding the last cell of the configuration is t. If b > s, then we again we use the extra factor of (t/(t − 1))^{s−1} that occurs in the \overline{ν}_{d,s}(b) to ensure that the weights of each of the s − 1 cells immediately preceding the last cell of the configuration is t. However, in this case, we have another factor of (−1)/(t − 1) which use to ensure that the next cell to left has weight −1. That is, if b > s, we would take a combinatorial object as found in the proof of Theorem 7, erase the final s choices of either −1 or t made at the end of the last brick (the last cell in the brick will still be 1 or t). Then, the sequence −1 t t ⋯ t would be placed in the cells instead. We let \overline{C}_{n}^{s} denote the set of configurations that we can produce in this manner.

An example of a configuration in \overline{C}_{n}^{s} when s = 3 may be found in Figure 9.

The exact same involution I may be used to simplify the set of objects in \overline{C}_{n}^{s}. Note that if the last brick of a configuration C has length > s, then either we use the label −1 that is forced on cell n − s to split at cell n − s so that I(C) will have its last brick of size s or the involution either splits or combines bricks as some cell to the left of n−s in which case the labels on the cells n−s, …, n−1 are not effected. Thus our involution I maps \overline{C}_{n}^{s} onto \overline{C}_{n}^{s}. Since the fixed points of I have no cell with weight −1, it must be that all elements of F ix_{I} ∩ \overline{C}_{n}^{s} have a last brick of size s. Thus if C ∈ F ix_{I} ∩ \overline{C}_{n}^{s} and C is constructed from an element F = (Σ^{(1)}, …, Σ^{(L)}, σ^{(1)}, …, σ^{(ℓ)}; ϵ) of the set F_{T,L,ℓ,f_{1}^{1},...,f_{k}^{1},...,f_{1}^{m},...,f_{k}^{m}}, then just as before we will have that

U_{d}(C) = t^{comdes^{d}(Σ,σ,ϵ)} ∏_{i=1}^{L_{1}} Q_{i}^{F Hinv(Σ^{(i)},ϵ)} ∏_{i=1+L_{1}}^{L} Q_{i}^{inv(Σ^{(i)},ϵ)} ∏_{i=1}^{ℓ_{1}} q_{i}^{F Hcoinv(σ^{(i)},ϵ)} ∏_{i=1+ℓ_{1}}^{ℓ} q_{i}^{coinv(σ^{(i)},ϵ)}.

However, since the last brick is of size s, then we are guaranteed that

{n − s + 1, …, n − 1} ∈ Comes^{d}((Σ^{(1)}, …, Σ^{(L)}, σ^{(1)}, …, σ^{(ℓ)}; ϵ)

and n − s ∉ Comes^{d}((Σ^{(1)}, …, Σ^{(L)}, σ^{(1)}, …, σ^{(ℓ)}; ϵ). Finally by the same argument that we used in Theorem 7, we can show that if F = (Σ^{(1)}, …, Σ^{(L)}, σ^{(1)}, …, σ^{(ℓ)}; ϵ) of the set F_{T,L,ℓ,f_{1}^{1},...,f_{k}^{1},...,f_{1}^{m},...,f_{k}^{m}} is such that

{n − s + 1, …, n − 1} ∈ Comes^{d}((Σ^{(1)}, …, Σ^{(L)}, σ^{(1)}, …, σ^{(ℓ)}; ϵ) and
n − s ∉ Comes^{d}((Σ^{(1)}, …, Σ^{(L)}, σ^{(1)}, …, σ^{(ℓ)}; ϵ),

then we can construct a unique fixed C ∈ F ix_{I} ∩ \overline{C}_{n}^{s} whose underlying configuration is F. Now if we let

\overline{W} _{n}^{(4,d,s)}(X_{1}, …, X_{k}, t, Q, q) = ∑_{(Σ,σ;ϵ)} (∏_{i=1}^{k} X_{i}^{ℓ(ϵ|x_{i})}) t^{Comdes^{d}(Σ,σ;ϵ)} ∏_{i=1}^{L_{1}} Q_{i}^{F Hinv(Σ^{(i)},ϵ)}

× ∏_{i=1+L_{1}}^{L} Q_{i}^{inv(Σ^{(i)},ϵ)} ∏_{i=1}^{ℓ_{1}} q_{i}^{F Hcoinv(σ^{(i)},ϵ)} ∏_{i=1+ℓ_{1}}^{ℓ} q_{i}^{coinv(σ^{(i)},ϵ)}

where the sum runs over all ϵ ∈ {x_{1}, …, x_{k}}^{n} and (Σ, σ) ∈ (C_{k} ≀ S_{n})^{L+ℓ} such that

{n − s + 1, …, n − 1} ∈ Comes^{d}((Σ^{(1)}, …, Σ^{(L)}, σ^{(1)}, …, σ^{(ℓ)}; ϵ) and
n − s ∉ Comes^{d}((Σ^{(1)}, …, Σ^{(L)}, σ^{(1)}, …, σ^{(ℓ)}; ϵ),

then we have shown that

(Q, Q)_{n}(q, q)_{n}ξ(p_{n,\overline{ν}_{d,s}}) = \overline{W} _{n}^{(4,d,s)}(X_{1}, …, X_{k}, t, Q, q).  (35)

It follows that

∑_{n≥0} \frac{u^{n}}{(Q, Q)_{n}(q, q)_{n}} \overline{W} _{n}^{(4,d,s)}(X_{1}, …, X_{k}, t, Q, q)

= 1 + ∑_{n≥1} ξ(p_{n,\overline{ν}_{d,s}})u^{n}

= \frac{1 + ∑_{n≥1}(−1)^{n}u^{n}(ξ(e_{n}) − \overline{ν}_{d,s}(n)ξ(e_{n}))}{∑_{n≥0}(−1)^{n}u^{n}ξ(e_{n})}.  (36)

We can then carry out a computation similar to the one we used to prove Theorem 10 to prove the following theorem.

Theorem 11. For all k ≥ 2, d = 1, …, k, and s ≥ 1,

∑_{n≥0} \frac{u^{n}}{(Q, Q)_{n}(q, q)_{n}} \overline{W} _{n}^{(4,d,s)}(X_{1}, …, X_{k}, t, Q, q) = (1 + \frac{t^{s−1}}{(t − 1)^{s}} )

+ (\frac{t}{t − 1})^{s−1} \frac{∏_{i=1}^{d} J((1 − t)X_{i}u, Q, q)}{−t + ∏_{j=1}^{k} J((1 − t)X_{j}u, Q, q)}

− \frac{t^{s−1}}{(t − 1)^{s}} \frac{∑_{n=1}^{s}(−1)^{n}u^{n}(1 − t)^{n} ∑_{b_{j}≥0,b_{1}+···+b_{k}=n} t^{χ(n=s)}t^{χ(b_{d+1}+···+b_{k}=0)} ∏_{j=1}^{k} ^{\frac{X_{j}^{b_{j}} Q^{\binom{b_{j}}{2}}}{(Q,Q)_{b_{j}} (q,q)_{b_{j}}}}}{−t + ∏_{j=1}^{k} J((1 − t)X_{j}u, Q, q)} . (37)

References

[Bec93] Desiree Beck, Permutation enumeration of the symmetric and hyperoctahedral group and the combinatorics of symmetric functions, Ph.D. thesis, University of California, San Diego, 1993.

[BR95] Desiree Beck and Jeffrey Remmel, Permutation enumeration of the symmetric group and the combinatorics of symmetric functions, J. Combin. Theory Ser. A 72 (1995), no. 1, 1–49.

[Bre93] Francesco Brenti, Permutation enumeration symmetric functions, and unimodality, Pacific J. Math. 157 (1993), no. 1, 1–28.

[Car70] Leonard Carlitz, Sequences and inversions, Duke Math. J. 37 (1970), 193–198.

[ER91] Ömer Eğecioğlu and Jeffrey Remmel, Brick tabloids and the connection matrices between bases of symmetric functions, Discrete Appl. Math. 34 (1991), no. 1-3, 107–120, Combinatorics and theoretical computer science (Washington, DC, 1989). MR 92j:05179

[FH97a] Dominique Foata and Guo-Niu Han, Calcul basique des permutations signées. I. Longueur et nombre d’inversions, Adv. in Appl. Math. 18 (1997), no. 4, 489–509.

[FH97b] , Calcul basique des permutations signées. II. Analogues finis des fonctions de Bessel, Electron. J. Combin. 4 (1997), no. 2, Research Paper 9, approx. 25 pp. (electronic), The Wilf Festschrift (Philadelphia, PA, 1996).

[LR06] Thomas Langley and Jeffrey Remmel, Enumeration of m-tuples of permutations and a new class of power bases for the space of symmetric functions, Adv. Appl. Math. 36 (2006), no. 1, 30–66.

[Men04] Anthony Mendes, Building generating functions brick by brick, Ph.D. thesis, University of California, San Diego, 2004.

[MRa] Anthony Mendes and Jeffrey Remmel, Descents, inversions, and major indices in permutation groups, submitted to Discrete Math.

[MRb] , Generating functions via symmetric functions, book in preparation.

[MR06] , Permutations and words counted by consecutive patterns, Adv. Appl. Math. 37 (2006), no. 4, 443–480.

[Wag] Jennifer Wagner, Personal communication, 2001.

[Wag00] , The combinatorics of the permutation enumeration of wreath products between cyclic and symmetric groups, Ph.D. thesis, University of California, San Diego, 2000.