Séminaire Lotharingien de Combinatoire 54 (2006), Article B54a

SIGNED WORDS AND PERMUTATIONS, III;

THE MACMAHON VERFAHREN

Dominique Foata and Guo-Niu Han

Glory to Viennot, Wizard of Bordeaux, A prince in Physics, In Mathematics, Combinatorics, Even in Graphics, Sure, in Viennotics. He builds bijections, Top calculations.

No one can beat him. Only verbatim Can we follow him. He has admirers, Who have got down here. They all celebrate Such a happy fate. Sixty years have gone, He still is our don.

Dedicated to Xavier. Lucelle, April 2005.

Abstract. The MacMahon Verfahren is fully exploited to derive a five-variable generating polynomial over signed permutations, where the parameters are: “neg” (number of negative values), “fdes” (flag descent number), “fmaj” (flag major index), “ifdes” and “ifmaj” (fdes and fmaj for the inverse permutation); then a three-variable generating polynomial over signed words with given letter multiplicities, where the parameters are “neg”, “fmaj”, and “fdes”.

1. Introduction

To paraphrase Leo Carlitz [Ca56], the present paper could have been entitled “Expansions of certain products,” as we want to expand the product

(1.1) K_{∞}(u) := ∏_{i≥0,j≥0} \frac{1}{(1 − uZ_{ij}q_{1}^{i}q_{2}^{j})},

in its infinite version, and

(1.2)  K_{r,s}(u) := ∏_{0≤i≤r, 0≤j≤s} \frac{1}{(1 − uZ_{ij}q_{1}^{i}q_{2}^{j})},

in its graded version, where

Z_{ij} := \{ \begin{matrix}Z, & if i and j are both odd; \\ 1, & if i and j are both even; \\ 0, & if i and j have different parity. \end{matrix}

DOMINIQUE FOATA AND GUO-NIU HAN

The second pair under study, which depends on r variables u_{1}, …, u_{r}, reads

(1.3) L_{∞}(u_{1}, …, u_{r}) := ∏_{1≤i≤r} \frac{1}{(u_{i}; q^{2})_{∞}} \frac{1}{(u_{i}qZ; q^{2})_{∞}} ,

(1.4) L_{s}(u_{1}, …, u_{r}) := ∏_{1≤i≤r} \frac{1}{(u_{i}; q^{2})_{⌊s/2⌋+1}} \frac{1}{(u_{i}qZ; q^{2})_{⌊(s+1)/2⌋}} .

In those expressions we have used the usual notations for the qascending factorial

(1.5)  (a; q)_{n} := \{ \begin{matrix}1, & if n = 0; \\ (1 − a)(1 − aq) … (1 − aq^{n−1}), & if n ≥ 1; \end{matrix}

in its finite form and

(1.6) (a; q)_{∞} := lim_{n}(a; q)_{n} = ∏_{n≥0}(1 − aq^{n});

in its infinite form.

All those products will be the basic ingredients for deriving the distributions of various statistics attached to signed permutations and words. By signed word we understand a word w = x_{1}x_{2} … x_{m}, whose letters are integers, positive or negative. If m = (m_{1}, m_{2}, …, m_{r}) is a sequence of nonnegative integers such that m_{1} + m_{2} + ⋯ + m_{r} = m, let B_{m} be the set of rearrangements w = x_{1}x_{2} … x_{m} of the sequence 1^{m_{1}}2^{m_{2}} … r^{m_{r}}, with the convention that some letters i (1 ≤ i ≤ r) may be replaced by their opposite values −i. For typographical reasons we shall use the notation \overline{i} := −i in the sequel. When m_{1} = m_{2} = ⋯ = m_{r} = 1, the class B_{m} is simply the hyperoctahedral group B_{m} (see [Bo68], p. 252-253) of the signed permutations of order m (m = r).

Using the χ-notation that maps each statement A onto the value χ(A) = 1 or 0 depending on whether A is true or not, we recall that the usual inversion number, inv w, of each signed word w = x_{1}x_{2} … x_{n} is defined by

inv w := ∑_{1≤j≤n} ∑_{i<j} χ(x_{i} > x_{j}).

It also makes sense to introduce

\overline{inv} w := ∑_{1≤j≤n} ∑_{i<j} χ(\overline{x}_{i} > x_{j}),

and define the flag-inversion number of w by

finv w := inv w + \overline{inv} w + neg w,

where neg w := ∑_{1≤j≤n} χ(x_{j} < 0). As noted in our previous paper

[FoHa05a], the flag-inversion number coincides with the traditional length function ℓ, when applied to each signed permutation.

SIGNED WORDS AND PERMUTATIONS, III

The flag-major index “fmaj” and the flag descent number “fdes”, which were introduced by Adin and Roichman [AR01] for signed permutations, are also valid for signed words. They read

fmaj w := 2 maj w + neg w;
fdes w := 2 des w + χ(x_{1} < 0);

where maj w := ∑_{j} j χ(x_{j} > x_{j+1}) denotes the usual major index of w and des w the number of descents des w := ∑_{j} χ(x_{j} > x_{j+1}). Finally, for each signed permutation w let w^{−1} denote the inverse of w and define ifdes w := fdes w^{−1} and ifmaj := fmaj w^{−1}.

Notations. In the sequel B_{n} (resp. B_{m}) designates the hyperoctahedral group of order n (resp. the set of signed words of multiplicity m = (m_{1}, m_{2}, …, m_{r})), as defined above. Each generating polynomial for B_{n} (resp. for B_{m}) by some k-variable statistic will be denoted by B_{n}(t_{1}, …, t_{k}) (resp. B_{m}(t_{1}, …, t_{k})). When the variable t_{i} is missing in the latter expression, it means that the variable t_{i} is given the value 1.

The main two results of this paper corresponding to the two pairs of products earlier introduced can be stated as follows.

Theorem 1.1. Let

(1.7) B_{n}(t_{1}, t_{2}, q_{1}, q_{2}, Z) := ∑_{w∈B_{n}} t_{1}^{fdes w}t_{2}^{ifdes w}q_{1}^{fmaj w}q_{2}^{ifmaj w}Z^{neg w}

be the generating polynomial for the group B_{n} by the five-variable statistic (fdes, ifdes, fmaj, ifmaj, neg). Then,

(1.8) ∑_{n≥0} \frac{u^{n}}{(t_{1}^{2}; q_{1}^{2})_{n+1}(t_{2}^{2}; q_{2}^{2})_{n+1}} (1 + t_{1})(1 + t_{2})B_{n}(t_{1}, t_{2}, q_{1}, q_{2}, Z)

= ∑_{r≥0,s≥0} t_{1}^{r}t_{2}^{s} K_{r,s}(u),

where K_{r,s}(u) is defined in (1.2).

Theorem 1.2. For each sequence m = (m_{1}, …, m_{r}) let

(1.9)  B_{m}(t, q, Z) := ∑_{w∈B_{m}} t^{fdes w}q^{fmaj w}Z^{neg w}

be the generating polynomial for the class B_{m} of signed words by the three-variable statistic (fdes, fmaj, neg). Then

(1.10)  ∑_{m}(1 + t)B_{m}(t, q, Z)\frac{u_{1}^{m_{1}} ⋯ u_{r}^{m_{r}}}{(t^{2}; q^{2})_{1+|m|}} = ∑_{s≥0} t^{s}L_{s}(u_{1}, …, u_{r}),

where |m| := m_{1} + ⋯ + m_{r} and L_{s}(u_{1}, …, u_{r}) is defined in (1.4).

It is worth noticing that Reiner [Re93a] has calculated the generating polynomial for B_{n} by another 5-variable statistic involving each signed permutation and its inverse. The bibasic series he has used are normalized by products of the form (t_{1}; q_{1})_{n+1}(t_{2}; q_{2})_{n} instead of (t_{1}^{2}; q_{1}^{2})_{n+1}(t_{2}^{2}; q_{2}^{2})_{n+1}.

Using the properties of the fundamental transformation on signed words described in our first paper [FoHa05a] we obtain the following specialization of Theorem 1.1. Let

(1.11)  ^{finv}B_{n}(t, q) := ∑_{w∈B_{n}} t^{fdes w}q^{finv w}

be the generating polynomial for the group B_{n} by the pair (fdes, finv). Then, the q-factorial generating function for the polynomials ^{finv}B_{n}(t, q) (n ≥ 0) has the following form:

(1.12) ∑_{n≥0} \frac{v^{n}}{(q^{2}; q^{2})_{n}}^{finv}B_{n}(t, q)

= \frac{1 − t}{−t^{2} + (v(1 − t^{2}); q)_{∞}} (t + (v(1 − t^{2})q; q^{2})_{∞}).

From identity (1.12) we deduce the generating function for the polynomials dessB_{n}(t, q) := ∑_{w∈B_{n}} t^{dess w}q^{finv w}, where “dess” is the traditional number of descents for signed permutations defined by

dess w := des w + χ(x_{1} < 0) instead of fdes w := 2 des w + χ(x_{1} < 0)

and recover Reiner’s identity [Re93a]

(1.13) ∑_{n≥0} \frac{u^{n}}{(q^{2}; q^{2})_{n}}^{dess}B_{n}(t, q) = \frac{1 − t}{1 − t e_{q}(u(1 − t))} \frac{1}{(v(1 − t); q^{2})_{∞}} ,

where e_{q}(v(1 − t^{2})) = 1/(v(1 − t^{2}); q)_{∞} is the traditional q-exponential. This is done in section 4.

As in our second paper [FoHa05b] we make use of the MacMahon Verfahren technique to prove the two theorems, which consists of transferring the topology of the signed permutations or words measured by the various statistics, “fdes”, “fmaj”, to a set of pairs of matrices with integral entries in the case of Theorem 1.1 and a set of plain words in the case of Theorem 1.2 for which the calculation of the associated statistic is easy. Each time there is then a combinatorial bijection between signed permutations (resp. words) and pairs of matrices (resp. plain words) that has the adequate properties. This is the content of Theorem 3.1 and Theorem 4.1.

In all our results we have tried to include the variable Z that takes the number “neg” of negative letters of each signed permutation or word into account. This allows us to re-obtain the classical results on the symmetric group and sets of words.

In the next section we recall the MacMahon Verfahren technique, which was developed in our previous paper [FoHa05b] for signed permutations. Notice that Reiner [Re93a, Re93b, Re93c, Re95a, Re95b], extending Stanley’s [St72] (P, ω)-partition approach, has successfully developed a (P, ω)-partition theory for the combinatorial study of the hyperoctahedral group, which could have been used in this paper. Section 3 contains the proof of Theorem 1.1, whose specializations are given in Section 4. We end the paper with the proof of Theorem 1.2 and its specializations. Noticeably, the generating polynomial for the class B_{m} of signed words by the twovariable statistic (fdes, fmaj) is completely explicit, in the sense that we derive the factorial generating function for those polynomials and also a recurrence relation, while only the generating function given by (1.10) has a simple form when the variable Z is kept.

2. The MacMahon Verfahren

Let ℕ^{n} (resp. NIW(n)) be the set of words (resp. nonincreasing words) of length n, whose letters are nonnegative integers. As done in [FoHa05b] the MacMahon Verfahren consists of mapping each pair (b, w) ∈ NIW(n)× B_{n} onto a word c ∈ ℕ^{n} as follows. Write the signed permutation w as the linear word w = x_{1}x_{2} … x_{n}, where x_{k} is the image of the integer k (1 ≤ k ≤ n). For each k = 1, 2, …, n let z_{k} be the number of descents in the right factor x_{k}x_{k+1} … x_{n} and ϵ_{k} be equal to 0 or 1 depending on whether x_{k} is positive or negative. Next, form the words z(w) := z_{1}z_{2} … z_{n} and ϵ(w) := ϵ_{1}ϵ_{2} … ϵ_{n}.

Now, take a nonincreasing word b = b_{1}b_{2} … b_{n} and define a_{k} := b_{k} +z_{k}, c′_{k} := 2a_{k} + ϵ_{k} (1 ≤ k ≤ n), then a(b, w) := a_{1}a_{2} … a_{n} and c′(b, w) :=

c′_{1}c′_{2} … c′_{n}. Finally, form the two-row matrix ( \begin{matrix}c′_{1} & c′_{2} & … & c′_{n} \\ |x_{1}| & |x_{2}| & … & |x_{n}| \end{matrix} ). Its

bottom row is a permutation of 1 2 … n; rearrange the columns in such a way that the bottom row is precisely 1 2 … n. Then the word c(b, w) = c_{1}c_{2} … c_{n} which corresponds to the pair (b, w) is defined to be the top row in the resulting matrix.

Example. Start with the pair (b, w) below and calculate all the necessary ingredients:

\begin{aligned}b & = & 4 & 2 & 2 & 1 & 1 & 0 & 0 \\ w & = & 3 & \overline{5} & \overline{1} & 6 & 7 & \overline{4} & 2 \\ z(w) & = & 2 & 1 & 1 & 1 & 1 & 0 & 0 \\ ϵ(w) & = & 0 & 1 & 1 & 0 & 0 & 1 & 0 \\ a(b, w) & = & 6 & 3 & 3 & 2 & 2 & 0 & 0 \\ c′(b, w) & = & 12 & 7 & 7 & 4 & 4 & 1 & 0 \\ c(b, w) & = & 7 & 0 & 12 & 1 & 7 & 4 & 4 \end{aligned}

For each c = c_{1} … c_{n} ∈ ℕ^{n} and let tot c := c_{1} + ⋯ + c_{n}, max c := max{c_{1}, …, c_{n}} and let odd c denote the number of odd letters in c . The proof of the following theorem can be found in [FoHa05b, Theorem 4.1].

Theorem 2.1. For each nonnegative integer s the above mapping is a bijection (b, w) ↦ c(b, w) of the set of pairs

(b, w) = (b_{1}b_{2} … b_{n}, x_{1}x_{2} … x_{n}) ∈ NIW(n) × B_{n}

such that 2b_{1} + fdes w = s onto the set of words c = c_{1}c_{2} … c_{n} ∈ ℕ^{n} such that max c = s. Moreover,

(2.1) 2b_{1} + fdes w = max c(b, w); 2 tot b + fmaj w = tot c(b, w); neg w = odd c(b, w).

We end this section by quoting the following classical identity, where b_{1} is the first letter of b.

(2.2)  \frac{1}{(u; q)_{n+1}} = ∑_{s≥0} u^{s} ∑_{b∈NIW(n), b_{1}≤s} q^{tot b}.

3. Proof of Theorem 1.1

We apply the MacMahon Verfahren just described to the two pairs (b, w) and (β, w^{−1}), where b and β are two nonincreasing words. The pair (b, w) (resp. (β, w^{−1})) is mapped onto a word c := c(b, w) = c_{1}c_{2} … c_{n} (resp. C := c(β, w^{−1}) = C_{1}C_{2} … C_{n}) of length n, with the properties

(3.1) 2b_{1} + fdes w = max c; 2 tot b + fmaj w = tot c; (3.2) 2β_{1} + ifdes w = max C; 2 tot β + ifmaj w = tot C.

There remains to investigate the relation between the two words c and C before pursuing the calculation. Form the two-row matrix

( \begin{matrix}c′ \\ C \end{matrix} ) = ( \begin{matrix}c′_{1} & c′_{2} & … & c′_{n} \\ C_{1} & C_{2} & … & C_{n} \end{matrix} ) ,

where c′ = c′_{1}c′_{2} … c′_{n} designates the nonincreasing rearrangement of the word c. The following lemma is readily verified.

Lemma. The following properties hold:

(i) for each i = 1, 2, …, n the letters c′_{i} and C_{i} are of the same parity; (ii) if c′_{i} = c′_{i+1} is even (resp. is odd), then C_{i} ≥ C_{i+1} (resp. C_{i} ≤ C_{i+1}). (iii) if \binom{c′}{C} is a two-row matrix of length n having properties (i) and (ii), there exists one and only one signed permutation w and two nonincreasing words b, β satisfying (3.1) and (3.2).

Example. We take the same example for w as in the previous section, but we also calculate C = c(β, w^{−1}).

\begin{aligned}b & = & 4 & 2 & 2 & 1 & 1 & 0 & 0 \\ w & = & 3 & \overline{5} & \overline{1} & 6 & 7 & \overline{4} & 2 \\ z(w) & = & 2 & 1 & 1 & 1 & 1 & 0 & 0 \\ ϵ(w) & = & 0 & 1 & 1 & 0 & 0 & 1 & 0 \\ a(b, w) & = & 6 & 3 & 3 & 2 & 2 & 0 & 0 \\ c′ := c′(b, w) & = & 12 & 7 & 7 & 4 & 4 & 1 & 0 \\ c := c(b, w) & = & 7 & 0 & 12 & 1 & 7 & 4 & 4 \end{aligned}  \begin{aligned}β & = & 3 & 2 & 1 & 1 & 0 & 0 & 0 \\ w^{−1} & = & \overline{3} & 7 & 1 & \overline{6} & \overline{2} & 4 & 5 \\ z(w^{−1}) & = & 2 & 2 & 1 & 0 & 0 & 0 & 0 \\ ϵ(w^{−1}) & = & 1 & 0 & 0 & 1 & 1 & 0 & 0 \\ a(β, w^{−1}) & = & 5 & 4 & 2 & 1 & 0 & 0 & 0 \\ C′ := c′(β, w^{−1}) & = & 11 & 8 & 4 & 3 & 1 & 0 & 0 \\ C := c(β, w^{−1}) & = & 4 & 1 & 11 & 0 & 0 & 3 & 8 \end{aligned}

\binom{c′}{C} = ( \begin{matrix}12 & 7 & 7 & 4 & 4 & 1 & 0 \\ 4 & 1 & 11 & 0 & 0 & 3 & 8 \end{matrix} ) .

Let (i_{1} < i_{1} < ⋯ < i_{r}) (resp. (j_{1} < j_{2} < ⋯ < j_{s})) be the increasing sequence of the integers i (resp. the integers j) such that c′_{i} is even (resp. c′_{j} is odd). Define (“e” for “even” and “o” for “odd”)

2d^{e} = \binom{2f^{e}}{2g^{e}} := ( \begin{matrix}c′_{i_{1}} & c′_{i_{2}} & … & c′_{i_{r}} \\ C_{i_{1}} & C_{i_{2}} & … & C_{i_{r}} \end{matrix} );
2d^{o} + 1 = \binom{2f^{o} + 1}{2g^{o} + 1} := ( \begin{matrix}c′_{j_{1}} & c′_{j_{2}} & … & c′_{j_{s}} \\ C_{j_{1}} & C_{j_{2}} & … & C_{j_{s}} \end{matrix} );

so that the two two-row matrices

d^{e} = \binom{f^{e}}{g^{e}} := ( \begin{matrix}c′_{i_{1}}/2 & c′_{i_{2}}/2 & … & c′_{i_{r}}/2 \\ C_{i_{1}}/2 & C_{i_{2}}/2 & … & C_{i_{r}}/2 \end{matrix} ) ,
d^{o} = \binom{f^{o}}{g^{o}} := ( \begin{matrix}(c′_{j_{1}} − 1)/2 & (c′_{j_{2}} − 1)/2 & … & (c′_{j_{s}} − 1)/2 \\ (C_{j_{1}} − 1)/2 & (C_{j_{2}} − 1)/2 & … & (C_{j_{s}} − 1)/2 \end{matrix} ) ,

may be regarded as another expression for the two-row matrix \binom{c′}{C}. Define the integers i_{max} and j_{max} by:

i_{max} := \{ \begin{matrix}(max c − 1)/2, & if max c is odd; \\ max c/2, & if max c is even; \end{matrix}
j_{max} := \{ \begin{matrix}(max C − 1)/2, & if max C is odd; \\ max C/2, & if max C is even. \end{matrix}

Then, to the pair d^{e}, d^{o} there corresponds a pair of unique finite matrices D^{e} = (d_{ij}^{e}), D^{o} = (d_{ij}^{o}) (0 ≤ i ≤ i_{max}, 0 ≤ j ≤ j_{max}) (and no other pair of smaller dimensions), where d_{ij}^{e} (resp. d_{ij}^{o}) is equal to the number of the two-letters in d^{e} (resp. in d^{o}) that are equal to \binom{i}{j}.

On the other hand, with |f| designating the length of the word f,

tot c = tot 2f^{e} + tot(2f^{o} + 1) = 2 tot f^{e} + 2 tot f^{o} + |f^{o}|

= 2 ∑_{i,j} i d_{ij}^{e} + 2 ∑_{i,j} i d_{ij}^{o} + ∑_{i,j} d_{ij}^{o};

tot C = tot 2g^{e} + tot(2g^{o} + 1) = 2 tot g^{e} + 2 tot g^{o} + |g^{o}|

= 2 ∑_{i,j} j d_{ij}^{e} + 2 ∑_{i,j} j d_{ij}^{o} + ∑_{i,j} d_{ij}^{o}.

The following proposition follows from Theorem 2.1.

Proposition 3.1. For each pair of nonnegative integers (r, s) the map (b, β, w) ↦ (D^{e}, D^{o}) is a bijection of the triples (b, β, w) such that 2b_{1} + fdes w ≤ r, 2β_{1} + ifdes w ≤ s onto the pairs of matrices D^{e} = (d_{i,j}^{e}), D^{o} = (d_{i,j}^{o}) (0 ≤ i ≤ r, 0 ≤ j ≤ s). Moreover,

(3.3) 2 tot b + fmaj w = 2 ∑_{i,j} i d_{ij}^{e} + 2 ∑_{i,j} i d_{ij}^{o} + ∑_{i,j} d_{ij}^{o};

(3.4) 2 tot β + ifmaj w = 2 ∑_{i,j} j d_{ij}^{e} + 2 ∑_{i,j} j d_{ij}^{o} + ∑_{i,j} d_{ij}^{o};

(3.5) neg w = ∑_{i,j} d_{ij}^{o}.

(3.6) |w| = ∑_{i,j} d_{ij}^{e} + ∑_{i,j} d_{ij}^{o}.

Again work with the same example as above. To the two-row matrix

\binom{c′}{C} = ( \begin{matrix}12 & 7 & 7 & 4 & 4 & 1 & 0 \\ 4 & 1 & 11 & 0 & 0 & 3 & 8 \end{matrix} )

there corresponds the pair

d^{e} = ( \begin{matrix}6 & 2 & 2 & 0 \\ 2 & 0 & 0 & 4 \end{matrix} ) , d^{o} = ( \begin{matrix}3 & 3 & 0 \\ 0 & 5 & 1 \end{matrix} ) .

As max c = 12 is even (resp. max C = 11 is odd), we have i_{max} = 6, j_{max} = 5 and

D^{e} = ( \begin{matrix}& 0 & 1 & 2 & 3 & 4 & 5 \\ 0 & . & . & . & . & 1 & . \\ 1 & . & . & . & . & . & . \\ 2 & 2 & . & . & . & . & . \\ 3 & . & . & . & . & . & . \\ 4 & . & . & . & . & . & . \\ 5 & . & . & . & . & . & . \\ 6 & . & . & 1 & . & . & . \end{matrix} ); D^{o} = ( \begin{matrix}& 0 & 1 & 2 & 3 & 4 & 5 \\ 0 & . & 1 & . & . & & . \\ 1 & . & . & . & . & . & . \\ 2 & . & . & . & . & . & . \\ 3 & 1 & . & . & . & . & 1 \\ 4 & . & . & . & . & . & . \\ 5 & . & . & . & . & . & . \\ 6 & . & . & . & . & . & . \end{matrix} ).

Also verify that 2 tot b + fmaj w = 35 = 2 × (2 + 2 + 6) + 2 × (3 + 3) + 3; 2 tot β + ifmaj w = 27 = 2 × (2 + 4) + 2 × (1 + 5) + 3 and neg w = 3.

In the following summations b and β run over the set of nonincreasing words of length n. By using identity (2.2) we have

∑_{n≥0} \frac{u^{n}}{(t_{1}^{2}; q_{1}^{2})_{n+1}(t_{2}^{2}; q_{2}^{2})_{n+1}} (1 + t_{1})(1 + t_{2})B_{n}(t_{1}, t_{2}, q_{1}, q_{2}, Z)

= ∑_{n≥0} u^{n}(1 + t_{1})(1 + t_{2})B_{n}(t_{1}, t_{2}, q_{1}, q_{2}, Z) ∑_{{r′≥0, s′≥0 \atop b,β,b_{1}≤r′, β_{1}≤s′}} t_{1}^{2r′}t_{2}^{2s′}q_{1}^{2 tot b}q_{2}^{2 tot β}

= ∑_{n,r′,s′} u^{n}(t_{1}^{2r′} + t_{1}^{2r′+1})(t_{2}^{2s′} + t_{2}^{2s′+1})

× ∑_{{w∈B_{n} \atop b,β,b_{1}≤r′, β_{1}≤s′}} t_{1}^{fdes w}t_{2}^{ifdes w}q_{1}^{fmaj w+2 tot b}q_{2}^{ifmaj w+2 tot β}Z^{neg w}

= ∑_{n,r′,s′}u^{n}t_{1}^{r′}t_{2}^{s′} ∑_{{w∈B_{n} \atop b,β,2b_{1}≤r′, 2β_{1}≤s′}} t_{1}^{fdes w}t_{2}^{ifdes w}q_{1}^{fmaj w+2 tot b}q_{2}^{ifmaj w+2 tot β}Z^{neg w}

= ∑_{n,r,s} u^{n}t_{1}^{r}t_{2}^{s} ∑_{w∈B_{n},b,β 2b_{1}+fdes w≤r, 2β_{1}+ifdes w≤s} q_{1}^{fmaj w+2 tot b}q_{2}^{ifmaj w+2 tot β}Z^{neg w}.

We can continue the calculation by using (3.3), (3.4) and (3.5), the inner summation being over matrices D^{e}, D^{o} of dimensions (r + 1) × (s + 1) with ∑_{i,j} d_{ij}^{e} + ∑_{i,j} d_{ij}^{o} = n, that is,

= ∑_{n,r,s} u^{n}t_{1}^{r}t_{2}^{s} ∑_{D^{e},D^{o}} q_{1}^{2Σ id_{ij}^{e}+2Σ id_{ij}^{o}+Σ d_{ij}^{o}}q_{2}^{2Σ jd_{ij}^{e}+2Σ jd_{ij}^{o}+Σ d_{ij}^{o}}Z^{Σ d_{ij}^{o}}

=∑_{r,s} t_{1}^{r}t_{2}^{s} ∑_{D^{e}} u^{Σ d_{ij}^{e}}q_{1}^{Σ (2i)d_{ij}^{e}}q_{2}^{Σ (2j)d_{ij}^{e}} ∑_{D^{o}} u^{Σ d_{ij}^{o}}q_{1}^{Σ (2i+1)d_{ij}^{o}}q_{2}^{Σ (2j+1)d_{ij}^{o}}Z^{Σ d_{ij}^{o}}

= ∑_{r,s} t_{1}^{r}t_{2}^{s} ∑_{D^{e}} ∏_{i,j}(uq_{1}^{2i}q_{2}^{2j})^{d_{ij}^{e}} ∑_{D^{o}} ∏_{i,j}(uZq_{1}^{2i+1}q_{2}^{2j+1})^{d_{ij}^{o}} (0≤i≤r, 0≤j ≤s)

= ∑_{r,s} t_{1}^{r}t_{2}^{s} \frac{1}{∏_{i,j}(1 − uq_{1}^{2i}q_{2}^{2j})} \frac{1}{∏_{i,j}(1 − uZq_{1}^{2i+1}q_{2}^{2j+1})} (0≤i≤r, 0≤j ≤s)

= ∑_{r≥0,s≥0} t_{1}^{r}t_{2}^{s} \frac{1}{∏_{0≤i≤r,0≤j≤s} (1 − uZ_{ij}q_{1}^{i}q_{2}^{j})}.

4. Specializations and Flag-inversion number

Define

(u; q_{1}, q_{2})_{r+1,s+1} = ∏_{{0≤i≤r \atop 0≤j≤s}}(1 − uq_{1}^{i}q_{2}^{j}); (u; q_{1}, q_{2})_{∞,∞} =∏_{i,j≥0}(1 − uq_{1}^{i}q_{2}^{j}).

When Z := 0 and t_{1}, t_{2}, q_{1}, q_{2} are replaced by their square roots, identity (1.8) becomes

(4.1) ∑_{n≥0} \frac{u^{n}}{(t_{1}; q_{1})_{n+1}(t_{2}; q_{2})_{n+1}} A_{n}(t_{1}, t_{2}, q_{1}, q_{2})= ∑_{r≥0,s≥0} \frac{t_{1}^{r}t_{2}^{s}}{(u; q_{1}, q_{2})_{r+1,s+1}} ,

where A_{n}(t_{1}, t_{2}, q_{1}, q_{2}) is the generating polynomial for the symmetric group 𝔖_{n} by the quadruple (des, ides, maj, imaj), an identity first derived by Garsia and Gessel [GaGe78]. Other approaches can be found in [Ra79], [DeFo85].

Remember that when a variable is missing in B_{n}(t_{1}, t_{2}, q_{1}, q_{2}, Z) it means that the variable has been given the value 1. Multiply both sides of (1.8) by (1 − t_{2}) and let t_{2} = 1. We get:

(4.2) ∑_{n≥0} \frac{u^{n}}{(t_{1}^{2}; q_{1}^{2})_{n+1}(q_{2}^{2}; q_{2}^{2})_{n}} (1 + t_{1})B_{n}(t_{1}, q_{1}, q_{2}, Z)

= ∑_{r≥0} t_{1}^{r}\frac{1}{∏_{0≤i≤r,j≥0} (1 − uZ_{ij}q_{1}^{i}q_{2}^{j})}.

Again multiply both sides by (1 − t_{1}) and let t_{1} = 1:

(4.3)  ∑_{n≥0} \frac{u^{n}}{(q_{1}^{2}; q_{1}^{2})_{n}(q_{2}^{2}; q_{2}^{2})_{n}} B_{n}(q_{1}, q_{2}, Z) =\frac{1}{∏_{i≥0,j≥0} (1 − uZ_{ij}q_{1}^{i}q_{2}^{j})}.

Also the (classical) generating function for the polynomials A_{n}(q_{1}, q_{2}) can be derived from identity (4.3) and reads:

∑_{n≥0} \frac{u^{n}}{(q_{1}; q_{1})_{n}(q_{2}; q_{2})_{n}} A_{n}(q_{1}, q_{2}) = \frac{1}{(u; q_{1}, q_{2})_{∞,∞}} .

With q_{1} = 1 the denominator of the fraction on the right side of identity (4.2) becomes

\{ \begin{matrix}(u; q_{2}^{2})_{∞}^{(r/2)+1}(uq_{2}Z; q_{2}^{2})_{∞}^{r/2}, & if r is even; \\ (u; q_{2}^{2})_{∞}^{(r+1)/2}(uq_{2}Z; q_{2}^{2})_{∞}^{(r+1)/2}, & if r is odd. \end{matrix}

Hence,

∑_{n≥0} \frac{u^{n}}{(1 − t_{1}^{2})^{n+1}(q_{2}^{2}; q_{2}^{2})_{n}} (1 + t_{1})B_{n}(t_{1}, q_{2}, Z)

= ∑_{s≥0} \frac{t_{1}^{2s+1}}{((u; q_{2}^{2})_{∞}(uq_{2}Z; q_{2}^{2})_{∞})^{s+1}} + ∑_{s≥0} \frac{t_{1}^{2s}}{((u; q_{2}^{2})_{∞}(uq_{2}Z; q_{2}^{2})_{∞})^{s}} \frac{1}{(u; q_{2}^{2})_{∞}} .

= \frac{1}{−t_{1}^{2} + (u; q_{2}^{2})_{∞}(uq_{2}Z; q_{2}^{2})_{∞}} (t_{1} + (uq_{2}Z; q_{2}^{2})_{∞}).

Now replace u by v(1 − t_{1}^{2}). This implies the following result stated as a theorem.

Theorem 4.1. Let B_{n}(t_{1}, q_{2}, Z) be the generating polynomial for the group B_{n} by the triple (fdes, ifmaj, neg). Then,

(4.4) ∑_{n≥0} \frac{v^{n}}{(q_{2}^{2}; q_{2}^{2})_{n}} B_{n}(t_{1}, q_{2}, Z)

= \frac{1 − t_{1}}{−t_{1}^{2} + (v(1 − t_{1}^{2}); q_{2}^{2})_{∞} (v(1 − t_{1}^{2})q_{2}Z; q_{2}^{2})_{∞}} (t_{1} + (v(1 − t_{1}^{2})q_{2}Z; q_{2}^{2})_{∞}).

Several consequences are drawn from Theorem 4.1. First, when Z = 0 and when t_{1}, q_{2} are replaced by their square roots, we get

(4.5)  ∑_{n≥0} \frac{v^{n}}{(q_{2}; q_{2})_{n}} A_{n}(t_{1}, q_{2}) = \frac{1 − t_{1}}{−t_{1} + (v(1 − t_{1}); q_{2})_{∞}} ,

where A_{n}(t_{1}, q_{2}) is the generating polynomial for the group 𝔖_{n} by the pair (des, imaj), but also by the pair (des, inv) (see [St76], [FoHa97]).

Let i w := w^{−1} denote the inverse of the signed permutation w. At this stage we have to remember that the bijection Ψ of B_{n} onto itself that we have constructed in our first paper [FoHa05a] preserves the inverse ligne of route [FoHa05a, Theorem 1.2], so that the chain

w  \underrightarrow{i}  w_{1}  \underrightarrow{Ψ}  w_{2}  \underrightarrow{i}  w_{3}
\binom{fdes}{ifmaj}  \binom{ifdes}{fmaj}  \binom{ifdes}{finv}  \binom{fdes}{finv}

shows that the four pairs (fdes, ifmaj), (ifdes, fmaj), (ifdes, finv) and (fdes, finv) are all equidistributed over B_{n}. Therefore,

∑_{w} t^{fdes w}q^{ifmaj w} =∑_{w} t^{ifdes w}q^{fmaj w} =∑_{w} t^{ifdes w}q^{finv w} =∑_{w} t^{fdes w}q^{finv w},

where w runs over B_{n}. The rightmost generating polynomial was designated by ^{finv}B_{n}(t, q) in (1.11). Therefore we can derive a formula for ^{finv}B_{n}(t, q) by using its (fdes, ifmaj) interpretation. We have then finvB_{n}(t, q) = B_{n}(t_{1}, q_{2}, Z) with t_{1} = t, q_{2} = q and Z = 1. Let Z := 1 in (4.4); as (v(1 − t_{1}^{2}); q_{2}^{2})_{∞} (v(1 − t_{1}^{2})q_{2}; q_{2}^{2})_{∞} = (v(1 − t_{1}^{2}); q_{2})_{∞}, identity (4.4) implies identity (1.12).

To recover Reiner’s identity (1.13) we make use of (1.12) by sorting the signed permutations according to the parity of their flag descent numbers: B_{n}(t, q) =: B′_{n}(t^{2}, q) + t B′′_{n}(t^{2}, q), so that ^{dess}B_{n}(t^{2}, q) = B′_{n}(t^{2}, q) + t^{2} B′′_{n}(t^{2}, q). Hence

∑_{n≥0} \frac{v^{n}}{(q^{2}; q^{2})_{n}}^{dess}B_{n}(t^{2}, q)= \frac{(v(1 − t^{2})q; q^{2})_{∞} − t^{2}}{−t^{2} + (v(1 − t^{2}); q)_{∞}} + t^{2} \frac{1 − (v(1 − t^{2})q; q^{2})_{∞}}{−t^{2} + (v(1 − t^{2}); q)_{∞}}

= \frac{1 − t^{2}}{−t^{2} + (v(1 − t^{2}); q)_{∞}} (v(1 − t^{2})q; q^{2})_{∞}.

As 1/(v(1−t^{2}); q)_{∞} can also be expressed as the q-exponential e_{q}(v(1−t^{2})), we then get identity (1.13).

5. The MacMahon Verfahren for signed words

Let w = x_{1}x_{2} … x_{m} be a signed word belonging to the class B_{m}, where m = (m_{1}, m_{2}, …, m_{r}) is a sequence of nonnegative integers such that m_{1} + m_{2} + ⋯ + m_{r} = m. Remember that this means that w is a rearrangement of 1^{m_{1}}2^{m_{2}} … r^{m_{r}}, with the convention that some letters i (1 ≤ i ≤ r) may be replaced by their opposite values \overline{i}. Again, let ϵ := ϵ(w) := ϵ_{1}ϵ_{2} … ϵ_{m} be the binary word defined by ϵ_{i} = 0 or 1, depending on whether x_{i} is positive or negative. As before, let b ∈ NIW(m).

The MacMahon Verfahren bijection for signed words is constructed as follows. First, compute the word z = z_{1}z_{2} … z_{m}, where z_{k} is equal to the number of descents in the right factor x_{k}x_{k+1} … x_{m}, as well as the word ϵ = ϵ_{1}ϵ_{2} … ϵ_{m} mentioned above, so that, as in the case of signed permutations,

(5.1)  fmaj w = 2 tot z + tot ϵ.

Next, define a_{k} := b_{k} + z_{k}, c′_{k} := 2a_{k} + ϵ_{k} (1 ≤ k ≤ m), then a := a_{1}a_{2} … a_{m} and c′ := c′_{1}c′_{2} … c′_{m}. Finally, form the two-row matrix

( \begin{matrix}c′ \\ abs w \end{matrix} ) = ( \begin{matrix}c′_{1} & c′_{2} & … & c′_{m} \\ |x_{1}| & |x_{2}| & … & |x_{m}| \end{matrix} ). Its bottom row is a rearrangement of

the word 1^{m_{1}}2^{m_{2}} … r^{m_{r}}.

Make the convention that two biletters \binom{c′_{k}}{|x_{k}|} and \binom{c′_{l}}{|x_{l}|} commute if and only if |x_{k}| and |x_{l}| are different and rearrange the biletters of that biword in such a way that the bottom row is precisely 1^{m_{1}}2^{m_{2}} … r^{m_{r}}. The top row in the resulting two-row matrix is then the juxtaposition product of r nonincreasing words b^{(1)} = b_{1}^{(1)} … b_{m_{1}}^{(1)}, b^{(2)} = b_{1}^{(2)} … b_{m_{2}}^{(2)}, …, b^{(r)} = b_{1}^{(r)} … b_{m_{r}}^{(r)}, of lengths m_{1}, m_{2}, …, m_{r}, respectively. Moreover,

tot b^{(1)} + tot b^{(2)} + ⋯ + tot b^{(r)} = tot c′ = 2 tot a + tot ϵ

= 2 tot b + 2 tot z + tot ϵ

= 2 tot b + fmaj w. (5.2)

On the other hand,

2b_{1} + fdes w = 2b_{1} + 2z_{1} + ϵ_{1} = c′_{1}

= max_{i} b_{1}^{(i)} (1 ≤ i ≤ r). (5.3)

As in the case of signed permutations, we can easily see that for each nonnegative integer s the map (b, w) ↦ (b^{(1)}, b^{(2)}, …, b^{(r)}) is a bijection of the set of pairs (b, w) ∈ NIW(m) × R_{m} such that 2b_{1}+ fdes w =s onto the set of juxtaposition products b^{(1)}b^{(2)} … b^{(r)} such that max_{i} b_{1}^{(i)} = s. The reverse bijection is constructed in the same way as in the case of signed permutations.

Example. Start with the pair (b, w), where w belongs to B_{m} with m = (2, 2, 2, 2, 2, 2), r = 6, m = 12, the negative elements being overlined.

\begin{aligned}Id & = & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 & 10 & 11 & 12 \\ b & = & 4 & 4 & 4 & 4 & 4 & 4 & 4 & 2 & 2 & 1 & 1 & 1 \\ w & = & 1 & \overline{5} & \overline{2} & 2 & \overline{3} & \overline{3} & \overline{1} & 4 & \overline{6} & \overline{5} & 4 & 6 \\ z & = & 3 & 2 & 2 & 2 & 1 & 1 & 1 & 1 & 0 & 0 & 0 & 0 \\ ϵ & = & 0 & 1 & 1 & 0 & 1 & 1 & 1 & 0 & 1 & 1 & 0 & 0 \\ a & = & 7 & 6 & 6 & 6 & 5 & 5 & 5 & 3 & 2 & 1 & 1 & 1 \\ c′ & = & 14 & 13 & 13 & 12 & 11 & 11 & 11 & 6 & 5 & 3 & 2 & 2 \\ abs w & = & 1 & 5 & 2 & 2 & 3 & 3 & 1 & 4 & 6 & 5 & 4 & 6 \\ b^{(1)} … b^{(r)} & = & 14 & 11 & 13 & 12 & 11 & 11 & 6 & 2 & 13 & 3 & 5 & 2 \\ 1^{m_{1}} … r^{m_{r}} & = & 1 & 1 & 2 & 2 & 3 & 3 & 4 & 4 & 5 & 5 & 6 & 6 \end{aligned}

We verify that 2 tot b+fmaj w = 2 tot b+2 tot z+tot ϵ = 2×35+2×13+7 = 103 = tot b^{(1)} + ⋯ + tot b^{(6)} and 2b_{1} + fdes w = 2b_{1} + 2z_{1} + ϵ_{1} = 2 × 4 + 2 × 3 + 0 = 14 = c′_{1} = max_{i} b_{1}^{(i)}.

The combinatorial theorem for signed words that corresponds to Theorem 2.1 is now stated.

Theorem 5.1. For each nonnegative integer s the above mapping is a bijection of the set of pairs (b, w) = (b_{1}b_{2} … b_{m}, x_{1}x_{2} … x_{m}) ∈ NIW(m)× B_{m} such that 2b_{1} + fdes w = s onto the set of juxtaposition products b^{(1)} … b^{(r)} ∈ NIW(m_{1})×⋯×NIW(m_{r}) such that max_{i} b_{1}^{(i)} = s. Moreover, (5.2) and (5.3) hold, together with

(5.4)  neg w = odd(b^{(1)} … b^{(r)})

Relation (5.4) is obvious, as the negative letters of w are in bijection with the odd letters of the juxtaposition product. Now consider the generating polynomial B_{m}(t, q, Z), as defined in (1.9). Making use of (2.2) and of the usual q-identities

\frac{1}{(u; q)_{N}} = ∑_{n≥0} \left[{N + n − 1 \atop n}\right]_{q} u^{n};

\left[{N + n \atop n}\right]_{q} = ∑_{b∈NIW(N), b_{1}≤n} q^{tot b};

we have

\frac{1 + t}{(t^{2}; q^{2})_{m+1}} B_{m}(t, q, Z) = ∑_{s′≥0}(t^{2s′} + t^{2s′+1})\left[{m + s′ \atop s′}\right]_{q^{2}} B_{m}(t, q, Z)

= ∑_{s′≥0} t^{s′} \left[{m + ⌊s′/2⌋ \atop ⌊s′/2⌋}\right]_{q^{2}} B_{m}(t, q, Z)

= ∑_{s′≥0} t^{s′} ∑_{{b∈NIW(m), \atop 2b_{1}≤s′}} q^{2 tot b} ∑_{w∈B_{m}} t^{fdes w}q^{fmaj w}Z^{neg w}

= ∑_{s≥0} t^{s} ∑_{b∈NIW(m), w∈B_{m} 2b_{1}+fdes w≤s} q^{2 tot b+fmaj w}Z^{neg w}.

But using (5.2), (5.3), (5.4) we can write

\frac{1 + t}{(t^{2}; q^{2})_{m+1}} B_{m}(t, q, Z) = ∑_{s≥0} t^{s} ∑_{{b^{(1)},...,b^{(r)}, \atop max_{i} b_{1}^{(i)}≤s}} q^{tot b^{(1)}+···+tot b^{(r)}}Z^{odd b^{(1)}+···+odd b^{(r)}}

and

∑_{m}(1+t)B_{m}(t, q, Z)\frac{u_{1}^{m_{1}} ⋯ u_{r}^{m_{r}}}{(t^{2}; q^{2})_{1+|m|}} = ∑_{s≥0} t^{s} ∏_{1≤i≤r} ∑_{m_{i}≥0} ∑_{b^{(i)}} u_{i}^{m_{i}}q^{tot b^{(i)}}Z^{odd b^{(i)}},

using the notation: |m| := m_{1} + ⋯ + m_{r}.

There remains to evaluate ∑_{m} ∑_{b} u^{m}q^{tot b}Z^{odd b}, where the second sum is over all nonincreasing words b = b_{1} … b_{m} of length m such that b_{1} ≤ s. Let 1 ≤ i_{1} < ⋯ < i_{k} ≤ m (resp. 1 ≤ j_{1} < ⋯ < j_{l} ≤ m) be the sequence of all integers i (resp. j) such that b_{i} is even (resp. b_{j} is odd). Then, b is completely characterized by the pair (b^{e}, b^{o}), where b^{e} := (b_{i_{1}}/2) … (b_{i_{k}}/2) and b^{o} := ((b_{j_{1}} − 1)/2) … ((b_{j_{l}} − 1)/2). Moreover, tot b = 2 tot b^{e} + 2 tot b^{o} + |b^{o}|. Hence,

∑_{m≥0} ∑_{b,|b|=m,b_{1}≤s} u^{m}q^{tot b}Z^{odd b} =∑_{b,b_{1}≤s} u^{|b|}q^{tot b}Z^{odd b}

= ∑_{b^{e}, 2b_{1}^{e}≤s} u^{|b^{e}|}q^{2 tot b^{e}} ∑_{b^{o}, 2b_{1}^{o}≤s−1} (uqZ)^{|b^{o}|}q^{2 tot b^{o}}

= \frac{1}{(u; q^{2})_{⌊s/2⌋+1}} \frac{1}{(uqZ; q^{2})_{⌊(s+1)/2⌋}} .

This completes the proof of Theorem 1.2.

6. Specializations

As has been seen in this paper a t-graded form such as (1.10) has an ungraded (infinite) version, obtained by multiplying the formula by (1−t) and letting t := 1. This gives

(6.1) ∑_{m} B_{m}(q, Z)\frac{u_{1}^{m_{1}} ⋯ u_{r}^{m_{r}}}{(q^{2}; q^{2})_{|m|}} = ∏_{1≤i≤r} \frac{1}{(u_{i}; q^{2})_{∞}} \frac{1}{(u_{i}qZ; q^{2})_{∞}}

= ∏_{1≤i≤r} e_{q^{2}}(u_{i}) e_{q^{2}}(u_{i}qZ),

where e_{q^{2}}(u) denotes the usual q-exponential with basis q^{2} ([GaRa90], p. 9). Notice that B_{m}(q, Z) is the generating polynomial for the class B_{m} by the pair (fmaj, neg), namely

(6.2)  B_{m}(q, Z) = ∑_{w} q^{fmaj w}Z^{neg w} (w ∈ B_{m}).

On the other hand, Let

(6.3)  ^{finv}B_{m}(q, Z) := ∑_{w∈B_{m}} q^{finv w}Z^{neg w}

be the generating polynomial for the class B_{m} by the pair (finv, neg). Using a different approach (the derivation is not reproduced in the paper; it is not quite straightforward), we can prove the identity

(6.4)  ^{finv}B_{m}(q, Z) = (−Zq; q)_{m_{1}+···+m_{r}} \frac{(q; q)_{m_{1}+···+m_{r}}}{(q; q)_{m_{1}} ⋯ (q; q)_{m_{r}}}

= (−Zq; q)_{m_{1}+···+m_{r}} \left[{m_{1} + ⋯ + m_{r} \atop m_{1}, …, m_{r}}\right]_{q},

using the traditional notation for the q-multinomial coefficient. In general, B_{m}(q, Z) ≠ ^{finv}B_{m}(q, Z). This can be shown by means of a combinatorial argument.

Let Z := 1 in (6.1) and make use of the q-binomial theorem (see [An76], p. 17, or [GaRa90], chap. 1), on the one hand, and let Z := 1 in (6.4), on the other hand. We get the evaluations

(6.5)  B_{m}(q) = (−q; q)_{m_{1}+···+m_{r}} \left[{m_{1} + ⋯ + m_{r} \atop m_{1}, …, m_{r}}\right]_{q} = ^{finv}B_{m}(q).

This shows that “fmaj” and “finv” are equidistributed over each class B_{m}, a property proved “bijectively” in our first paper [FoHa05a].

Next, let q := 1 in (6.4). We obtain

(6.6) ^{finv}B_{m}(Z) = (1 + Z)^{m_{1}+···+m_{r}} \binom{m_{1} + ⋯ + m_{r}}{m_{1}, …, m_{r}} (= B_{m}(Z)),

an identity which is equivalent to

(6.7)  ∑_{m} B_{m}(Z)\frac{u_{1}^{m_{1}} ⋯ u_{r}^{m_{r}}}{|m|!} = ∏_{1≤i≤r} exp(u_{i}) exp(u_{i}Z).

Thus, the q-analog of (6.6) yields (6.4) with a combinatorial interpretation in terms of the flag-inversion number “finv,” while (6.1) may be interpreted as q-analog of (6.7) with an interpretation in terms of the flag-major index number “fmaj.”

Finally, for Z = 0, formula (1.10) yields the identity

∑_{m} A_{m}(t, q)\frac{u_{1}^{m_{1}} ⋯ u_{r}^{m_{r}}}{(t; q)_{1+|m|}} = ∑_{s≥0} t^{s} ∏_{1≤i≤r} \frac{1}{(u_{i}; q)_{s+1}} ,

where A_{m}(t, q) is the generating polynomial for the class of the rearrangements of the word 1^{m_{1}}2^{m_{2}} … r^{m_{r}} by (des, maj). As done by Rawlings [Ra79], [Ra80], the polynomials A_{m}(t, q) can also be defined by a recurrence relation involving either the polynomials themselves, or their coefficients.

7. The Signed-Word-Euler-Mahonian polynomials

We end the paper by showing that the polynomials B_{m}(t, q) = B_{m}(t, q, Z) |_{Z=1} can be calculated not only by their factorial generating function given by (1.10) for Z := 1, but also by a recurrence formula.

Definition. A sequence (B_{m}(t, q) = ∑_{k≥0}t^{k}B_{m,k}(q)) (m = (m_{1}, …, m_{r});

m_{1} ≥ 0, …, m_{r} ≥ 0)) of polynomials in two variables t, q, is said to be signed-word-Euler-Mahonian, if one of the following four equivalent conditions holds:

(1) The (t^{2}, q^{2})-factorial generating function for the polynomials

(7.1)  C_{m}(t, q) := (1 + t)B_{m}(t, q)

is given by identity (1.10) when Z = 1, that is,

(7.2)  ∑_{m} C_{m}(t, q)\frac{u_{1}^{m_{1}} ⋯ u_{r}^{m_{r}}}{(t^{2}; q^{2})_{1+|m|}} = ∑_{s≥0} t^{s} ∏_{1≤i≤r} \frac{1}{(u_{i}; q)_{s+1}} .

(2) For each multiplicity m we have:

(7.3)  \frac{C_{m}(t, q)}{(t^{2}; q^{2})_{1+|m|}} = ∑_{s≥0} t^{s}\left[{m_{1} + s \atop s}\right]_{q} ⋯ \left[{m_{r} + s \atop s}\right]_{q}.

Let m + 1_{r} := (m_{1}, …, m_{r−1}, m_{r} + 1).

(3) The following recurrence relation

(7.4) (1 − q^{m_{r}+1})B_{m+1_{r}}(t, q)

= (1 − t^{2}q^{2+2|m|})B_{m}(t, q) − q^{m_{r}+1}(1 − t)(1 + tq)B_{m}(tq, q),

holds with B_{(0,...,0)}(t, q) = 1.

(4) The following recurrence relation for the coefficients B_{m,k}(q)

(7.5) (1 + q + ⋯ + q^{m_{r}})B_{m+1_{r},k}(q) = (1 + q + ⋯ + q^{m_{r}+k})B_{m,k}(q)

+ q^{m_{r}+k}B_{m,k−1}(q) + (q^{m_{r}+k} + q^{m_{r}+k+1} + ⋯ + q^{2|m|+1})B_{m,k−2}(q),

holds with B_{(0,...,0),0}(q) = 1 and B_{(0,...,0),k}(q) = 0 for every k ≠ 0.

Theorem 7.1. The conditions (1), (2), (3) and (4) in the previous definition are equivalent.

Proof. The proofs of the equivalences [(1) ⇔ (2)] and [(3) ⇔ (4)] are easy and therefore omitted. For proving the equivalence [(1) ⇔ (3)] proceed as follows. Let C(t, q; u_{1}, …, u_{r}) denote the right side of (7.2) and form the q-difference C(t, q; u_{1}, …, u_{r}) − C(t, q; u_{1}, …, u_{r−1}, u_{r}q) applied to the sole variable u_{r}. We get

(7.6) C(t, q; u_{1}, …, u_{r}) − C(t, q; u_{1}, …, u_{r−1}, u_{r}q)

= ∑_{s≥0} \frac{t^{s}}{(u_{1}; q)_{s+1} … (u_{r}; q)_{s+1}} − ∑_{s≥0} \frac{t^{s}}{(u_{1}; q)_{s+1} … (u_{r}q; q)_{s+1}}

= ∑_{s≥0} \frac{t^{s}}{(u_{1}; q)_{s+1} … (u_{r}; q)_{s+1}} [1 − \frac{1 − u_{r}}{1 − u_{r}q^{s+1}} ]

= u_{r} ∑_{s≥0} \frac{t^{s}}{(u_{1}; q)_{s+1} … (u_{r}; q)_{s+1}} [1 − q^{s+1} \frac{1 − u_{r}}{1 − u_{r}q^{s+1}} ]

= u_{r}(C(t, q; u_{1}, …, u_{r}) − qC(tq, q; u_{1}, …, u_{r−1}, u_{r}q)).

Now, let C(t, q; u_{1}, …, u_{r}) := ∑_{m} C_{m}(t, q)u_{1}^{m_{1}} ⋯ u_{r}^{m_{r}}/(t^{2}; q^{2})_{1+|m|} and express each term C(…) occurring in identity (7.6) as a factorial series in the u_{i}’s. We obtain

∑_{m}(1 − q^{m_{r}+1})C_{m+1_{r}}(t, q)\frac{u_{1}^{m_{1}} ⋯ u_{r}^{m_{r}+1}}{(t^{2}; q^{2})_{2+|m|}}

= ∑_{m}(1 − t^{2}q^{2+2|m|})C_{m}(t, q)\frac{u_{1}^{m_{1}} ⋯ u_{r}^{m_{r}+1}}{(t^{2}; q^{2})_{2+|m|}}

− ∑_{m} q^{m_{r}+1}(1 − t^{2})C_{m}(tq, q)\frac{u_{1}^{m_{1}} ⋯ u_{r}^{m_{r}+1}}{(t^{2}; q^{2})_{2+|m|}} .

Taking the coefficients of u_{1}^{m_{1}} … u_{r−1}^{m_{r−1}}u_{r}^{m_{r}+1} yields

(1−q^{m_{r}+1})C_{m+1_{r}}(t, q) = (1−t^{2}q^{2+2|m|})C_{m}(t, q)−q^{m_{r}+1}(1−t^{2})C_{m}(tq, q),

which in turn is equivalent to (7.4) in view of (7.1). All the steps of the argument are reversible.

Remark 1. The fact that B_{m}(t, q) is the generating polynomial for the class B_{m} by the pair (fdes, fmaj) can also be proved by the insertion technique using (7.5). The argument has been already developed in [ClFo95a, § 6] for ordinary words. Again let m := |m| = m_{1} + ⋯ + m_{r}. With each word from B_{m+1^{r}} associate (m_{r} + 1) new words obtained by marking one and only one letter equal to r or \overline{r}. Let B_{m+1^{r}}^{∗} denote the class of all those marked signed words. If w^{∗} = x_{1} … x_{i}^{∗} … x_{m+1} is such a word, where the i-th letter is marked (accordingly, equal to either r or \overline{r}), let mark_{i} be the number of letters equal to r or \overline{r} in the right factor x_{i+1}x_{i+2} … x_{m+1} and define:

fmaj^{∗} w^{∗} := fmaj w + mark_{i} w^{∗}.

On the other hand, let

B_{m,k}(q) := ∑_{w∈B_{m}, fdes w=k} q^{fmaj w}.

Clearly,

∑_{w^{∗}∈B_{m+1^{r}}^{∗} , fdes w=k} q^{fmaj^{∗} w^{∗}} = (1 + q + ⋯ + q^{m_{r}})B_{m+1_{r},k}(q).

Now each word w from the class B_{m} gives rise to 2(m+1) distinct marked signed words of length (m + 1), when the marked letter r or \overline{r} is inserted between letters of w, as well as in the beginning of and at the end of the word. As in the case of the signed permutations, we can verify that for each j = 0, 1, …, 2m+1 there is one and only one marked signed word w^{∗} of length (m + 1) derived by insertion such that fmaj^{∗} w^{∗} = fmaj w + j.

On the other hand, “fdes” is not modified if r is inserted to the right of w, or if r or \overline{r} is inserted into a descent x_{i} > x_{i+1}. Furthermore, “fdes” increases by one, if x_{1} > 0 (resp. x_{1} < 0) and \overline{r} (resp. r) is inserted to the left of w. For all the other insertions “fdes” increases by 2.

Hence, all the marked signed words w^{∗} from B_{m+1^{r}}^{∗}, such that fdes w^{∗} = k are derived by insertion from three sources:

(i) the set {w ∈ B_{m} : fdes w = k} and the contribution is: (1 + q + ⋯ + q^{m_{r}+k})B_{m,k}(q);

(ii) the set {w ∈ B_{m} : fdes w = k − 1} and the contribution is: q^{m_{r}+k}B_{m,k−1}(q);

(iii) the set {w ∈ B_{m} : fdes w = k − 2} and the contribution is: (q^{m_{r}+k} + ⋯ + q^{2|m|+1})B_{m,k−2}(q).

Remark 2. Let m := 1^{n} and B_{n}(t, q) = B_{m}(t, q), so that B_{n}(t, q) is now the generating polynomial for the set of signed permutations of order n. Then (7.3), (7.4) and (7.5) become

(7.7) \frac{(1 + t)B_{n}(t, q)}{(t^{2}; q^{2})_{n+1}} = ∑_{s≥0} t^{s}(1 + q + ⋯ + q^{s})^{n}

(7.8) (1 − q)B_{n}(t, q) = (1 − t^{2}q^{2n})B_{n−1}(t, q) − q(1 − t)(1 + tq)B_{n−1}(tq, q). (7.9) B_{n,k}(q) = (1 + q + ⋯ + q^{k})B_{n−1,k}(q)

+ q^{k}B_{n−1,k−1}(q) + (q^{k} + q^{k+1} + ⋯ + q^{2n−1})B_{n−1,k−2}(q).

The last three relations have been derived by Brenti et al. [ABR01], Chow and Gessel [ChGe04], Haglund et al. [HLR04].

Concluding remarks. The statistical study of the hyperoctahedral group B_{n} was initiated by Reiner ([Re93a], [Re93b], [Re93c], [Re95a], [Re95b]). It had been rejuvenated by Adin and Roichman [AR01] with their introduction of the flag-major index, which was shown [ABR01] to be equidistributed with the length function. See also their recent papers on the subject [ABR05], [ReRo05]. Another approach to Theorems 1.1 and 1.2 would be to make use of the Cauchy identity for the Schur functions, as was done in [ClFo95b].

Acknowledgements. We should like to thank Christian Krattenthaler and the anonymous referee for their careful readings and knowledgeable remarks.

References

[AR01] Ron M. Adin and Yuval Roichman, The flag major index and group actions on polynomial rings, Europ. J. Combin., vol. 22, 2001, p. 431–446.

[ABR01] Ron M. Adin, Francesco Brenti and Yuval Roichman, Descent Numbers and Major Indices for the Hyperoctahedral Group, Adv. in Appl. Math., vol. 27, 2001, p. 210–224.

[ABR05] Ron M. Adin, Francesco Brenti and Yuval Roichman, Equi-distribution over Descent Classes of the Hyperoctahedral Group, to appear in J. Comb. Theory, Ser. A., 2005.

[An76] George E. Andrews, The Theory of Partitions. Addison-Wesley, Reading MA, 1976 (Encyclopedia of Math.and its Appl., 2).

[Bo68] N. Bourbaki, Groupes et algèbres de Lie, chap. 4, 5, 6. Hermann, Paris, 1968.

[Ca56] L. Carlitz, The Expansion of certain Products, Proc. Amer. Math. Soc., vol. 7,

1956, p. 558–564.

[ChGe04] Chak-On Chow and Ira M. Gessel, On the Descent Numbers and Major Indices for the Hyperoctahedral Group, Manuscript, 18 p., 2004.

[ClFo95a] Ron J. Clarke and Dominique Foata, Eulerian Calculus, II: An Extension of Han’s Fundamental Transformation, Europ. J. Combinatorics, vol. 16, 1995, p. 221–252.

[ClFo95b] R. J. Clarke and D. Foata, Eulerian Calculus, III: The Ubiquitous Cauchy Formula, Europ. J. Combinatorics, vol. 16, 1995, p. 329–355.

[DeFo85] Jacques Désarménien and Dominique Foata, Fonctions symétriques et séries hypergéométriques basiques multivariées, Bull. Soc. Math. France, vol. 113, 1985, p. 3-22.

[FoHa97] Dominique Foata and Guo-Niu Han, Calcul basique des permutations signées, I : longueur et nombre d’inversions, Adv. in Appl. Math., vol. 18, 1997, p. 489–509.

[FoHa05a] Dominique Foata and Guo-Niu Han, Signed Words and Permutations, I; a Fundamental Transformation, to appear in Proc. Amer. Math. Soc., 2006.

[FoHa05b] Dominique Foata and Guo-Niu Han, Signed Words and Permutations, II; The Euler-Mahonian Polynomials, Electronic J. Combinatorics, vol. 11 (2) (The Stanley Festschrift), 2004-2005, R22.

[GaGe78] Adriano M. Garsia and Ira Gessel, Permutations Statistics and Partitions, Adv. in Math., vol. 31, 1979, p. 288–305.

[GaRa90] George Gasper and Mizan Rahman, Basic Hypergeometric Series. London, Cambridge Univ. Press, 1990 (Encyclopedia of Math. and Its Appl., 35).

[HLR04] J. Haglund, N. Loehr and J. B. Remmel, Statistics on Wreath Products, Perfect

Matchings and Signed Words, Europ. J. Combin., vol. 26, 2005, p. 835–868.

[Ra79] Don P. Rawlings, Permutation and Multipermutation Statistics, Ph. D. thesis, Univ. Calif. San Diego. Publ. I.R.M.A. Strasbourg, 49/P-23, 1979.

[Ra80] Don P. Rawlings, Generalized Worpitzky identities with applications to permutation enumeration, Europ. J. Comb., vol. 2, 1981, p. 67-78.

[Re93a] V. Reiner, Signed permutation statistics, Europ. J. Combinatorics, vol. 14, 1993, p. 553–567.

[Re93b] V. Reiner, Signed permutation statistics and cycle type, Europ. J. Combinatorics, vol. 14, 1993, p. 569–579.

[Re93c] V. Reiner, Upper binomial posets and signed permutation statistics, Europ. J. Combinatorics, vol. 14, 1993, p. 581–588.

[Re95a] V. Reiner, Descents and one-dimensional characters for classical Weyl groups, Discrete Math., vol. 140, 1995, p. 129–140.

[Re95b] V. Reiner, The distribution of descents and length in a Coxeter group, Electronic J. Combinatorics, vol. 2, 1995, # R25.

[ReRo05] Amitai Regev, Yuval Roichman, Statistics on Wreath Products and Generalized

Binomial-Stirling Numbers, to appear in Israel J. Math., 2005.

[St76] Richard P. Stanley, Binomial posets, Möbius inversion, and permutation enumeration, J. Combinatorial Theory Ser. A, vol. 20, 1976, p. 336–356.

Dominique Foata Institut Lothaire 1, rue Murner F-67000 Strasbourg, France

foata@math.u-strasbg.fr

Guo-Niu Han

I.R.M.A. UMR 7501

Université Louis Pasteur et CNRS 7, rue René-Descartes F-67084 Strasbourg, France

                       guoniu@math.u-strasbg.fr