SIMULTANEOUS MAJ STATISTICS

Dongsu Kim and Dennis Stanton

Abstract. The generating function for words with several simultaneous maj weights is given. New maj-like Mahonian statistics result. Some applications to integer partitions are given.

1. Introduction.

The usual maj statistic [2] on words w is defined by adding the location of the descents of the word w,

maj(w) = ∑_{i:w_{i}>w_{i+1}} i.

This definition presumes that the alphabet for the letters of w have been linearly ordered, for example 2 > 1 > 0,

maj(1102201) = 2 + 5 = 7 = maj_{210}(1102201).

However a similar definition can be made assuming any linear ordering σ; here we take 1 > 2 > 0, σ = 120, and 2 > 0 > 1, σ = 201

maj_{120}(1102201) = 2 + 5 = 7, maj_{201}(1102201) = 5 + 6 = 11.

In this paper we consider the generating function for several such simultaneous maj statistics (see Corollary 1). A more general generating function is given (Theorem 3), and some applications to Mahonian statistics (Corollary 2) and integer partitions (Theorem 4) are stated.

We first give a 3 letter theorem, which motivates the general result (Theorem 3). Let W (m, n, k) be the set of words of length m + n + k with m 0’s, n 1’s and k 2’s.

The first author is partially supported by KOSEF: 971–0106–038–2.

Theorem 1. For any non-negative integers m, n, and k we have

∑_{w∈W (m,n,k)}x^{maj_{120}(w)}y^{maj_{201}(w)}z^{maj_{012}(w)} = x^{n+k}y^{k} [ \begin{matrix}m + n + k − 1 \\ m − 1, n, k \end{matrix} ]_{xyz} +

y^{k+m}z^{m} [ \begin{matrix}m + n + k − 1 \\ m, n − 1, k \end{matrix} ]_{xyz} + z^{m+n}x^{n} [ \begin{matrix}m + n + k − 1 \\ m, n, k − 1 \end{matrix} ]_{xyz} .

Proof. We prove a stronger statement, that the three terms in Theorem 1 are the generating functions for the words in W (m, n, k) ending in 0, 1, and 2 respectively.

We proceed by induction on m + n + k. If w ends in a 0, the penultimate letter must be either 0, 1 or 2. Using induction we must verify that

x^{n+k}y^{k} [ \begin{matrix}m + n + k − 1 \\ m − 1, n, k \end{matrix} ]_{xyz} = x^{n+k}y^{k} [ \begin{matrix}m + n + k − 2 \\ m − 2, n, k \end{matrix} ]_{xyz} +

x^{m+n+k−1}y^{m+k−1}z^{m−1} [ \begin{matrix}m + n + k − 2 \\ m − 1, n − 1, k \end{matrix} ]_{xyz} +

(xy)^{m+n+k−1}z^{m+n−1}x^{n} [ \begin{matrix}m + n + k − 2 \\ m − 1, n, k − 1 \end{matrix} ]_{xyz} ,

which is the well-known recurrence formula [1] for the xyz-trinomial coefficient.

The other two cases are verified similarly. □

It should be noted that if any two of x, y, z are set equal to 1, then the usual maj generating function as a q-trinomial coefficient results.

2. A 7-variable theorem.

Theorem 1 contains three free variables, x, y and z. In this section we generalize Theorem 1 to Theorem 2, which contains seven free variables. Then we indicate how to specialize Theorem 2 to obtain new explicit classes of Mahonian statistics on words of 0’s, 1’s, and 2’s.

Suppose that the weights of the various possible ascents and descents in position m + n + k − 1 of a word w of m 0’s, n 1’s, and k 2’s are given by

(wt10) a_{0}^{m−1}a_{1}^{n}a_{2}^{k} for a descent 10, (wt21) b_{0}^{m}b_{1}^{n−1}b_{2}^{k} for a descent 21, (wt20) c_{0}^{m−1}c_{1}^{n}c_{2}^{k} for a descent 20, (wt01) d_{0}^{m}d_{1}^{n−1}d_{2}^{k} for an ascent 01, (wt12) e_{0}^{m}e_{1}^{n}e_{2}^{k−1} for an ascent 12, (wt02) f_{0}^{m}f_{1}^{n}f_{2}^{k−1} for an ascent 02.

Also suppose that the generating function for all such words w has the form

p_{0}(n, k)[\begin{matrix}m + n + k − 1 \\ m − 1, n, k \end{matrix}]_{B}+p_{1}(k, m)[\begin{matrix}m + n + k − 1 \\ m, n − 1, k \end{matrix}]_{B}

+ p_{2}(m, n)[\begin{matrix}m + n + k − 1 \\ m, n, k − 1 \end{matrix}]_{B} (2.1)

for some base B, and p_{0}(n, k) = p_{01}^{n}p_{02}^{k}, p_{1}(k, m) = p_{11}^{k}p_{12}^{m}, p_{2}(m, n) = p_{21}^{m}p_{22}^{n}. We also assume that the three terms in (2.1) correspond to the w which end in 0, 1, and 2 respectively.

Thus we have 25 free variables

∪_{i=0}^{2}{a_{i}, b_{i}, c_{i}, d_{i}, e_{i}, f_{i}, p_{i1}, p_{i2}} ∪ {B}.

These 25 variables are related by the three equations which we require by induction

p_{0}(n, k) [ \begin{matrix}m + n + k − 1 \\ m − 1, n, k \end{matrix} ]_{B} = p_{0}(n, k) [ \begin{matrix}m + n + k − 2 \\ m − 2, n, k \end{matrix} ]_{B}
+a_{0}^{m−1}a_{1}^{n}a_{2}^{k} p_{1}(k, m − 1) [ \begin{matrix}m + n + k − 2 \\ m − 1, n − 1, k \end{matrix} ]_{B}
(2.2a)  +c_{0}^{m−1}c_{1}^{n}c_{2}^{k} p_{2}(m − 1, n) [ \begin{matrix}m + n + k − 2 \\ m − 1, n, k − 1 \end{matrix} ]_{B} ,

p_{1}(k, m) [ \begin{matrix}m + n + k − 1 \\ m, n − 1, k \end{matrix} ]_{B} = p_{1}(k, m) [ \begin{matrix}m + n + k − 2 \\ m, n − 2, k \end{matrix} ]_{B}
+b_{0}^{m}b_{1}^{n−1}b_{2}^{k} p_{2}(m, n − 1) [ \begin{matrix}m + n + k − 2 \\ m, n − 1, k − 1 \end{matrix} ]_{B}
(2.2b)  +d_{0}^{m}d_{1}^{n−1}d_{2}^{k} p_{0}(n − 1, k) [ \begin{matrix}m + n + k − 2 \\ m − 1, n − 1, k \end{matrix} ]_{B} ,

p_{2}(m, n) [ \begin{matrix}m + n + k − 1 \\ m, n, k − 1 \end{matrix} ]_{B} = p_{2}(m, n) [ \begin{matrix}m + n + k − 2 \\ m, n, k − 2 \end{matrix} ]_{B}
+f_{0}^{m}f_{1}^{n}f_{2}^{k−1} p_{0}(n, k − 1) [ \begin{matrix}m + n + k − 2 \\ m − 1, n, k − 1 \end{matrix} ]_{B}
(2.2c)  +e_{0}^{m}e_{1}^{n}e_{2}^{k−1} p_{1}(k − 1, m) [ \begin{matrix}m + n + k − 2 \\ m, n − 1, k − 1 \end{matrix} ]_{B} .

We do not know the general solution to the equations (2.2a-c). However, we will give the general solution to (2.2a-c) if we make another assumption. If we specify that the coefficient of the second term on the the right side of (2.2a) is B^{m−1} times the coefficient of the first term, and the coefficient of the third term is B^{m+n−1} times the coefficient of the first term, then the B-trinomial recurrence relation verifies (2.2a). These two equations are

(2.3a)  \begin{matrix}a_{0}^{m−1}a_{1}^{n}a_{2}^{k}p_{11}^{k}p_{12}^{m−1} = & B^{m−1}p_{01}^{n}p_{02}^{k}, \\ c_{0}^{m−1}c_{1}^{n}c_{2}^{k}p_{21}^{m−1}p_{22}^{n} = & B^{m+n−1}p_{01}^{n}p_{02}^{k}. \end{matrix}

Similarly, we assume the B-trinomial recurrence for (2.2b) and (2.2c), which become

(2.3b)  \begin{matrix}b_{0}^{m}b_{1}^{n−1}b_{2}^{k}p_{21}^{m}p_{22}^{n−1} = & B^{n−1}p_{11}^{k}p_{12}^{m}, \\ d_{0}^{m}d_{1}^{n−1}d_{2}^{k}p_{01}^{n−1}p_{02}^{k} = & B^{n+k−1}p_{11}^{k}p_{12}^{m}. \end{matrix}

and

(2.3c)  \begin{matrix}f_{0}^{m}f_{1}^{n}f_{2}^{k−1}p_{01}^{n}p_{02}^{k−1} = & B^{k−1}p_{21}^{m}p_{22}^{n}, \\ e_{0}^{m}e_{1}^{n}e_{2}^{k−1}p_{11}^{k−1}p_{12}^{m} = & B^{k+m−1}p_{21}^{m}p_{22}^{n}. \end{matrix}

Since these equations should hold for all m, n and k, each of these 6 equations contains 3 equations (one each in m, n, and k). Thus we have 18 equations in the 25 free variables, which are written in a matrix form, where the first column comes from the equations in (2.3a):

( \begin{matrix}p_{12}a_{0} & p_{21}b_{0} & f_{0} \\ a_{1} & p_{22}b_{1} & p_{01}f_{1} \\ p_{11}a_{2} & b_{2} & p_{02}f_{2} \\ p_{21}c_{0} & d_{0} & p_{12}e_{0} \\ p_{22}c_{1} & p_{01}d_{1} & e_{1} \\ c_{2} & p_{02}d_{2} & p_{11}e_{2} \end{matrix} ) = ( \begin{matrix}B & p_{12} & p_{21} \\ p_{01} & B & p_{22} \\ p_{02} & p_{11} & B \\ B & p_{12} & p_{21}B \\ p_{01}B & B & p_{22} \\ p_{02} & p_{11}B & B \end{matrix} ) .

One may find the general solution to these 18 equations, leaving 7 free variables

{a_{0}, a_{1}, a_{2}, b_{0}, b_{1}, b_{2}, B}.

The explicit solutions for the remaining 18 variables are given below. The weights (wt) become (W): (W10) a_{0}^{m−1}a_{1}^{n}a_{2}^{k} for a descent 10, (W21) b_{0}^{m}b_{1}^{n−1}b_{2}^{k} for a descent 21, (W20) (a_{0}b_{0})^{m−1}(a_{1}b_{1})^{n}(a_{2}b_{2})^{k} for a descent 20, (W01) (B/a_{0})^{m}(B/a_{1})^{n−1}(B/a_{2})^{k} for an ascent 01, (W12) (B/b_{0})^{m}(B/b_{1})^{n}(B/b_{2})^{k−1} for an ascent 12, (W02) (B/a_{0}b_{0})^{m}(B/a_{1}b_{1})^{n}(B/a_{2}b_{2})^{k−1} for an ascent 02, and

p_{0}(n, k) = a_{1}^{n}(a_{2}b_{2})^{k}, p_{1}(k, m) = b_{2}^{k}(B/a_{0})^{m},
p_{2}(m, n) = (B/a_{0}b_{0})^{m}(B/b_{1})^{n}.

Theorem 2. The generating function of all words w ∈ W (m, n, k) with weights given by (W) is

a_{1}^{n}(a_{2}b_{2})^{k} [ \begin{matrix}m + n + k − 1 \\ m − 1, n, k \end{matrix} ]_{B} + b_{2}^{k}(B/a_{0})^{m} [ \begin{matrix}m + n + k − 1 \\ m, n − 1, k \end{matrix} ]_{B} +

(B/a_{0}b_{0})^{m}(B/b_{1})^{n} [ \begin{matrix}m + n + k − 1 \\ m, n, k − 1 \end{matrix} ]_{B} .

Theorem 1 is the special case of Theorem 2 for which B = xyz, a_{0} = a_{1} = a_{2} = x, and b_{0} = b_{1} = b_{2} = y hold.

There are 7 other versions of Theorem 2. These 8 theorems arise by independently replacing the pair of factors (B^{m−1}, B^{m+n−1}) by (B^{m+k−1}, B^{m−1}) in equation (2.3a), (B^{n−1}, B^{n+k−1}) by (B^{n+m−1}, B^{n−1}) in equation (2.3b), and (B^{k−1}, B^{k+m−1}) by (B^{k+n−1}, B^{k−1}) in (2.3c). The B-trinomial recurrence still holds. For instance if we make a replacement in (2.3a),

(2.3a′)  \begin{matrix}a_{0}^{m−1}a_{1}^{n}a_{2}^{k}p_{11}^{k}p_{12}^{m−1} = & B^{m+k−1}p_{01}^{n}p_{02}^{k}, \\ c_{0}^{m−1}c_{1}^{n}c_{2}^{k}p_{21}^{m−1}p_{22}^{n} = & B^{m−1}p_{01}^{n}p_{02}^{k}, \end{matrix}

then the explicit solutions to (2.3a′) and (2.3b-c) give the weight (W′): (W′10) a_{0}^{m−1}a_{1}^{n}a_{2}^{k} for a descent 10, (W′21) b_{0}^{m}b_{1}^{n−1}b_{2}^{k} for a descent 21, (W′20) (a_{0}b_{0})^{m−1}(a_{1}b_{1}/B)^{n}(a_{2}b_{2}/B)^{k} for a descent 20, (W′01) (B/a_{0})^{m}(B/a_{1})^{n−1}(B^{2}/a_{2})^{k} for an ascent 01, (W′12) (B/b_{0})^{m}(B/b_{1})^{n}(B/b_{2})^{k−1} for an ascent 12, (W′02) (B/a_{0}b_{0})^{m}(B/a_{1}b_{1})^{n}(B^{2}/a_{2}b_{2})^{k−1} for an ascent 02, and the corresponding theorem is the following:

Theorem 2′. The generating function of all words w ∈ W (m, n, k) with weights given by (W′) is

a_{1}^{n}(a_{2}b_{2}/B)^{k} [ \begin{matrix}m + n + k − 1 \\ m − 1, n, k \end{matrix} ]_{B} + b_{2}^{k}(B/a_{0})^{m} [ \begin{matrix}m + n + k − 1 \\ m, n − 1, k \end{matrix} ]_{B} +

(B/a_{0}b_{0})^{m}(B/b_{1})^{n} [ \begin{matrix}m + n + k − 1 \\ m, n, k − 1 \end{matrix} ]_{B} .

We do not state the remaining 6 variations here.

We can find Mahonian statistics by requiring that the generating function in Theorem 2 is the B-trinomial via the B-trinomial recurrence. There are six choices for this recurrence, one for each ordering of the 3 terms. So Theorem 2 gives a total of 6 possible Mahonian statistics, one of which (maj_{012}), is found by setting a_{0} = a_{1} = a_{2} = b_{0} = b_{1} = b_{2} = 1. Theorem 2′ also gives a total of 6 possible Mahonian statistics, one of which is found by setting a_{0} = a_{1} = b_{0} = b_{1} = b_{2} = 1, a_{2} = B. Similarly there are 6 possible Mahonian statistics for each of other 6 versions of Theorem 2, for a total of 6× 8 = 48. Six of them are the six possible maj_{σ} statistics, the remaining 42 come in 7 classes of six each, and they are all variations on maj. Each class of size 6 consists of a maj variation, and 5 others which correspond to 5 non-trivial reorderings of {0, 1, 2} of that maj variation. We give below one member of each class, eight in total.

We start with an example from Theorem 2′. If we set a_{0} = a_{1} = b_{0} = b_{1} = b_{2} = 1, a_{2} = B in Theorem 2′, the weight (W′) reduces to (W′10) B^{k} for a descent 10, (W′21) 1 for a descent 21, (W′20) B^{−n} for a descent 20, (W′01) B^{m+n+k−1} for an ascent 01, (W′12) B^{m+n+k−1} for an ascent 12, (W′02) B^{m+n+k−1} for an ascent 02. Note that the above weight (W′) is a perturbation of maj_{012} involving the descents 10 and 20. We write it as maj_{012} + s_{0}, where s_{0} is defined in the following way. We define s_{0} by giving the non-zero values at adjacent letters. One then adds these values to find s_{0}. It is assumed that if w is truncated after the adjacent letters, w has m 0’s, n 1’s, and k 2’s. s_{0}(w):

(1) k for an adjacent 10,

(2) −n for an adjacent 20. For example,

s_{0}(22012110201) = −0 + 3 − 3 = 0.

It turns out (we do not write down the details here) that the eight statistics (including maj_{012}) can be defined by three independent perturbations of maj_{012}: s_{0}, s_{1}, and s_{2}. For any subset A ⊂ {0, 1, 2} put

s_{A}(w) = ∑_{i∈A} s_{i}(w).

Then the eight Mahonian statistics are maj_{012} + s_{A}. In fact the set A indicates which replacements are made in (2.3a-c). For instance the above (W′) is maj_{012} + s_{{0}} and if we make replacements, say in (2.3b) and (2.3c), then the corresponding statistics will be maj_{012} + s_{{1,2}}, and so on. We define s_{1}, s_{2} analogously by giving the non-zero values at adjacent letters. One then adds these values to find the statistic. It is assumed that if w is truncated after the adjacent letters, w has m 0’s, n 1’s, and k 2’s. s_{1}(w):

(1) m for an adjacent 21,

(2) −k for an adjacent 01. s_{2}(w):

(1) n for an adjacent 02,

(2) −m for an adjacent 12.

For example,

s_{1}(22012110201) = −2 + 1 − 4 = −5, s_{2}(22012110201) = −1 + 3 = 2.

Below is a table evaluating maj_{012}, s_{0}, s_{1}, and s_{2} at the 6 permutations of 012. Note that the maj_{012} generating function is 1 + 2B + 2B^{2} + B^{3}, which is also the generating function for maj_{012} + s_{A}, for any subset A ⊂ {0, 1, 2}.

\begin{matrix}word & maj_{012} & s_{0} & s_{1} & s_{2} \\ 012 & 3 & 0 & 0 & −1 \\ 021 & 1 & 0 & 1 & 0 \\ 102 & 2 & 0 & 0 & 1 \\ 120 & 1 & −1 & 0 & 0 \\ 201 & 2 & 0 & −1 & 0 \\ 210 & 0 & 1 & 0 & 0 \end{matrix}

We repeat that all 48 Mahonian statistics may be found from these 8 by permuting the letters 0, 1, and 2. In this case maj_{012} becomes maj_{σ}, and each s_{i} is found by applying σ to 0, 1, and 2 in the definition of s_{i}.

3. N letters.

In this section we briefly generalize Theorem 2 to words with N letters in Theorem 3. We state the N letter version of Theorem 1 in Corollary 1. There are N! 2^{N} Mahonian statistics, which come in 2^{N} families each of size N!. We explicitly give the corresponding 2^{N} Mahonian statistics in Corollary 2.

Let W (a_{0}, a_{1}, ⋯, a_{N−1}) be the set of all words w with a_{i} i’s, 0 ≤ i ≤ N − 1.

If the words w have N letters instead of 3 letters, then each adjacent pair ij, i ≠ j, could be weighted by N variables, instead of 3 variables. Also the coefficients p_{i}, 0 ≤ i ≤ N − 1 would have N − 1 variables. Together with the base B, we have a total of N(N^{2} − N) + N(N − 1) + 1 = N^{3} − N + 1 variables. Each of the N recurrences required by induction gives N(N − 1) equations in these variables. So N(N − 1) + 1 variables will be free in the multivariable version of Theorem 2.

In order to fully describe the resulting theorem, some care must be taken with notation.

The N(N − 1) + 1 free variables may be taken to be the base B along with the N weights of the adjacent pairs (i + 1)i, for i = 0, ⋯, N − 2, for which we use the variables

(x_{i0}, x_{i1}, ⋯, x_{iN−1}), 0 ≤ i ≤ N − 2.

Suppose that w ends in an adjacent pair ij, i ≠ j, and that there are n_{k} k’s preceding the last letter j of w. The weight of the pair ij is given by

(4.2)  \begin{matrix}∏_{k=0}^{N−1}(∏_{l=j}^{i−1} x_{lk})^{n_{k}}  if j < i, \\ ∏_{k=0}^{N−1}(B/ ∏_{l=i}^{j−1} x_{lk})^{n_{k}} if i < j. \end{matrix}

As usual, we multiply the weights of adjacent pairs to find the weight of the word w.

Theorem 3. The generating function of all words w ∈ W (a_{0}, a_{1}, ⋯, a_{N−1}) with weights given by (4.2) is

∑_{i=0}^{N−1} p_{i}(a_{0}, a_{1}, ⋯, a_{N−1}) [ \begin{matrix}a_{0} + ⋯ + a_{N−1} − 1 \\ a_{0}, ⋯, a_{i} − 1, ⋯, a_{N−1} \end{matrix} ]_{B}

where

p_{i}(a_{0}, a_{1}, ⋯, a_{N−1}) = (∏_{l=0}^{i−1}(B/ ∏_{k=1}^{i−l} x_{i−k,l})^{a_{l}})( ∏_{l=i+1}^{N−1}( ∏_{k=0}^{l−i−1} x_{i+k,l})^{a_{l}}).

Note that p_{i} in Theorem 3 is independent of a_{i}.

The multivariable version of Theorem 1 occurs if

x_{i0} = x_{i1} = ⋯ = x_{iN−1} = x_{i}, 0 ≤ i ≤ N − 2,

and B = x_{0}x_{1} ⋯ x_{N−1}. Then the weights (4.2) become

(x_{j} ⋯ x_{i−1})^{n_{0}+···+n_{N−1}} if j < i,
(x_{0} ⋯ x_{i−1}x_{j} ⋯ x_{N−1})^{n_{0}+···+n_{N−1}} if i < j,

and the next corollary holds.

Corollary 1. We have

∑_{w∈W (a_{0},··· ,a_{N−1})} ∏_{i=0}^{N−1} x_{i}^{maj_{i+1···(N−1)01···i}(w)} =

∑_{i=0}^{N−1} p_{i}(a_{0}, a_{1}, ⋯, a_{N−1}) [ \begin{matrix}a_{0} + ⋯ + a_{N−1} − 1 \\ a_{0}, ⋯, a_{i} − 1, ⋯, a_{N−1} \end{matrix} ]_{x_{0}···x_{N−1}}

where

p_{i}(a_{0}, a_{1}, ⋯, a_{N−1}) =(∏_{l=0}^{i−1}(x_{0} ⋯ x_{l−1}x_{i} ⋯ x_{N−1})^{a_{l}})( ∏_{l=i+1}^{N−1}(x_{i} ⋯ x_{l−1})^{a_{l}}).

We next give the 2^{N} Mahonian statistics which follow from Theorem 3. Again they may be classified by perturbations of maj_{01···N−1}. For any subset A ⊂ {0, 1, ⋯, N − 1}, define

s_{A}(w) = ∑_{i∈A} s_{i}(w).

The individual statistics s_{i}(w) only depend upon the subwords of w ending in i, as in §2. For any given i ∈ w, suppose that i is preceded by n_{j} j’s, 0 ≤ j ≤ N−1. Extend the definition of n_{j} to be periodic mod N: n_{j+N} = n_{j} for all j. If the letter preceding i is i+k, the contribution to s_{i}(w) is positive on the circular interval [i + k + 1, i − 1] and negative on the circular interval [i + 1, i + k − 1],

(3.1) (n_{i+k+1} + n_{i+k+2} + ⋯ + n_{(i−1)}) − (n_{i+1} + n_{i+2} + ⋯ + n_{i+k−1}).

We add the contributions of (3.1) over all i ∈ w to find s_{i}(w). There is no contribution if k = 0; that is, for a repeated ii. For example,

s_{1}(41241012411312301) = 0 + (−1) + (−3) + (1 − 2) + (4 − 2) + (−8) = −11.

Corollary 2. For any set A ⊂ {0, 1, ⋯, N −1}, the statistic maj_{01···N−1} + s_{A} is Mahonian on W (a_{0}, a_{1}, ⋯, a_{N−1}).

These Mahonian statistics are examples of splittable statistics [3].

One may also allow weights on the adjacent letters 00, 11, and 22 for a more general version of Theorem 3.

4. Applications to partitions.

In this section we apply Theorem 1 and Theorem 3 to integer partitions. The special case k = 0, z = 1, x = y = q of Theorem 1 is

(4.1) ∑_{w∈W (m,n,0)} q^{maj_{10}(w)+maj_{01}(w)} = [ \begin{matrix}m + n \\ m \end{matrix} ]_{q^{2}} \frac{q^{m} + q^{n}}{1 + q^{m+n}} := f(m, n, q).

MacMahon [4, p. 139] previously gave (4.1).

The following generating function (using standard notation found in [1]) follows from (4.1),

(4.2)  ∑_{m,n≥0} f(m, n, q)\frac{(xq)^{m}(yq)^{n}}{(q; q)_{m+n}} = \frac{(xyq^{2}; q^{2})_{∞}}{(xq, yq; q)_{∞}} .

One way to see (4.2) is to consider the generating function for pairs of partitions (λ, μ) with distinct parts, weighted by

x^{# of parts of λ}y^{# of parts of μ}q^{|λ|+|μ|}

which is

∏_{k=1}^{∞} (1 + \frac{xq^{k}}{1 − xq^{k}} + \frac{yq^{k}}{1 − yq^{k}} ) = \frac{(xyq^{2}; q^{2})_{∞}}{(xq, yq; q)_{∞}} .

To prove (4.1), we must find a weight preserving bijection ϕ from the set of such (λ, μ), # parts of λ = m, # parts of μ = n, to the set of ordered pairs (w, γ), where w ∈ W (m, n, 0), and γ is a partition with m + n parts.

To define w, order the m + n parts of λ ∪ μ into a partition θ, and let w_{i} = 0 if θ_{i} ∈ λ, w_{i} = 1 if θ_{i} ∈ μ. This is well defined since the parts of λ and μ are distinct. To define γ, let t_{i} be the number of descents or ascents to the right of position i in the word w. Then we let γ = θ − t. For example if

λ = 7742, μ = 88661,

then

θ = 887766421,  w = 110011001, t = 443322110,  γ = 444444311.

This correspondence is the desired bijection ϕ.

The natural analog of ϕ on triples (λ, μ, θ) without pairwise common parts produces a word w ∈ W (m, n, k) and a partition γ. The q-statistic on the word w again counts all ascents and descents of w by their positions. However, in Theorem 1, we see that the six possible ascents/descents in w are weighted differently by position:

01 by yz,
02 by z,
10 by x,
12 by xz,
20 by xy,
21 by y.

So if we choose x = q^{a}, y = q^{b}, z = q^{c}, an occurrence of 01 in positions j and j + 1 of w contributes a weight of q^{j(b+c)}. This in turn implies that the bijection ϕ must be modified so that the part in λ corresponding to w_{j} must be at least b + c larger than the part in μ corresponding to w_{j+1}. We need six different inequalities for the six possible juxtapositions of parts. Let ϕ_{a,b,c} be the modified bijection.

For example, if m = k = 2, n = 1, a = 2, b = c = 1, then the juxtaposed parts sizes must differ by

2 for λμ,
1 for λθ,
2 for μλ,
3 for μθ,
3 for θλ,
1 for θμ.

The three possible triples (λ, μ, θ) whose weight is q^{12} are given below, along with result of the bijection ϕ_{2,1,1}:

(22, 6, 11) → (10022, 31111),
(32, 5, 11) → (10022, 22111),
(43, 1, 22) → (00221, 21111).

Corollary 3. Let a, b and c be positive integers. The generating function for all triples of partitions (λ, μ, θ) without pairwise common parts, such that λ has m parts, μ has n parts, and θ has k parts, and any adjacent parts in the partition λ ∪ μ ∪ θ of type

(1) λμ differ by b + c,

(2) λθ differ by c,

(3) μλ differ by a,

(4) μθ differ by a + c,

(5) θλ differ by a + b,

(6) θμ differ by b, is given by

\frac{q^{m+n+k}}{(q; q)_{m+n+k}}(q^{a(n+k)+bk}[\begin{matrix}m + n + k − 1 \\ m − 1, n, k \end{matrix}]_{q^{a+b+c}}+

q^{b(m+k)+cm}[\begin{matrix}m + n + k − 1 \\ m, n − 1, k \end{matrix}]_{q^{a+b+c}} + q^{c(n+m)+an}[\begin{matrix}m + n + k − 1 \\ m, n, k − 1 \end{matrix}]_{q^{a+b+c}}).

In Theorem 3, if all x_{i} = q, the following theorem results. All subscripts are taken mod N.

Theorem 4. The generating function for all N-tuples of integer partitions (λ_{1}, ⋯, λ_{N}) without pairwise common parts, such that

(a) λ_{i} has a_{i} parts, 1 ≤ i ≤ N,

(b) if the partition λ_{1} ∪ λ_{2} ∪ ⋯ ∪ λ_{N} has adjacent parts bc, for b ∈ λ_{i} and c ∈ λ_{j}, then b − c ≥ (i − j) mod N, is given by

\frac{q^{f}}{(q; q)_{f}} [ \begin{matrix}a_{1} + ⋯ + a_{N} \\ a_{1}, ⋯, a_{N} \end{matrix} ]_{q^{N}} \frac{∑_{i=1}^{N} q^{e_{i}}}{∑_{i=0}^{N−1} q^{if}} ,

where f = a_{1} + a_{2} + ⋯ + a_{N}, and e_{i} = a_{i} + 2a_{i+1} + ⋯ + (N − 1)a_{i+N−2}.

5. Remarks.

MacMahon [5, §30] defined a statistic related to maj, denoted here by MAJ, which weights each descent by the amount of the descent. For example,

MAJ(20211201) = 2 ∗ 1 + 1 ∗ 3 + 2 ∗ 6 = 17,

because the descent 20 in positions 1, 6 are weighted by 2 − 0 = 2, while the descent 21 in position 3 is weighted by 2 − 1 = 1. Let MIN denote the analogous statistic using the ascents. Then MacMahon alludes [5, §40] to the following theorem for words with three letters.

Theorem 5. For any non-negative integers m, n, and k we have

∑_{w∈W (m,n,k)}x^{MAJ(w)}y^{MIN(w)} = x^{n+2k} [ \begin{matrix}m + n + k − 1 \\ n \end{matrix} ]_{xy} [ \begin{matrix}m + k − 1 \\ m − 1 \end{matrix} ]_{(xy)^{2}}

+ y^{m−k} [ \begin{matrix}m + n + k − 1 \\ n − 1 \end{matrix} ]_{xy} [ \begin{matrix}m + k \\ m \end{matrix} ]_{(xy)^{2}} \frac{(xy)^{2k} + (xy)^{m+k}}{1 + (xy)^{m+k}}

+ y^{2m+n} [ \begin{matrix}m + n + k − 1 \\ n \end{matrix} ]_{xy} [ \begin{matrix}m + k − 1 \\ m \end{matrix} ]_{(xy)^{2}} .

If x = y, y = 1 or x = 1, the three terms in Theorem 5 sum to a single product (see [5, §38, §40]). The proof of Theorem 5 is identical to the proof of Theorem 1. We do not know a multivariable version of Theorem 5.

References

1. G. Andrews, The Theory of Partitions, Addison-Wesley, Reading, 1976.

2. D. Foata and M.-P. Schützenberger, Major index and inversion number of permutations, Math. Nachr. 83 (1978), 143–158.

3. J. Galovich and D. White, Recursive statistics on words, Disc. Math. 157 (1996), 169–191.

4. P. MacMahon, Combinatory Analysis (3rd, ed.), Chelsea, New York, 1984.

5. , The indices of permutations and the derivation therefrom of functions of a single variable associated with the permutations of any assemblage of objects, Amer. J. Math. 35 (1913), 281–322.

Department of Mathematics, KAIST, Taejon 305–701, Korea

School of Mathematics, University of Minnesota, Minneapolis, MN 55455

   E-mail address: dskim@math.kaist.ac.kr stanton@math.umn.edu