SIGNED WORDS AND PERMUTATIONS, II; THE EULER-MAHONIAN POLYNOMIALS

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

Submitted: May 6, 2005; Accepted: Oct. 28, 2005; Published: Nov. 08, 2005 Mathematics Subject Classifications: 05A15, 05A30, 05E15

Dans la théorie de Morse, quand on veut étudier un espace, on introduit une fonction numérique; puis on aplatit cet espace sur l’axe de la valeur de cette fonction. Dans cette opération d’aplatissement, on crée des singularités de la fonction et celles-ci sont en quelque sorte les vestiges de la topologie qu’on a tuée. René Thom, Logos et Théorie des catastrophes, 1982. Dedicated to Richard Stanley, on the occasion of his sixtieth birthday.

Abstract

As for the symmetric group of ordinary permutations there is also a statistical study of the group of signed permutations, that consists of calculating multivariable generating functions for this group by statistics involving record values and the length function. Two approaches are here systematically explored, using the flag-major index on the one hand, and the flag-inversion number on the other hand. The MacMahon Verfahren appears as a powerful tool throughout.

1. Introduction

The elements of the hyperoctahedral group B_{n} (n ≥ 0), usually called signed permutations, may be viewed as words w = x_{1}x_{2} … x_{n}, where the letters x_{i} are positive or negative integers and where |x_{1}| |x_{2}| … |x_{n}| is a permutation of 1 2 … n (see [Bo68] p. 252–253). For typographical reasons we shall use the notation \overline{i} := −i in the sequel. 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 the signed permutation 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 verify that the length function (see [Bo68, p. 7], [Hu90, p. 12]), that will be denoted by “finv” (flag-inversion number) in the whole paper, can be defined, using the notation

neg w := ∑_{1≤j≤n}χ(x_{j} < 0), by

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

Another equivalent definition will be given in (7.1). The flag-major index “fmaj” and the flag descent number “fdes” were introduced by Adin and Roichman [AR01] and 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}).

Another class of statistics needed here is the class of lower records. A letter x_{i} (1 ≤ i ≤ n) is said to be a lower record of the signed permutation w = x_{1}x_{2} … x_{n}, if |x_{i}| < |x_{j}| for all j such that i + 1 ≤ j ≤ n. When reading the lower records of w from left to right we get a signed subword, called the lower record subword, denoted by Lower w. Denote the number of positive (resp. negative) letters in Lower w by lowerp w (resp. lowern w).

In our previous paper [FoHa05] we gave the construction of a transformation Ψ on (arbitrary) signed words, that is, words, whose letters are positive or negative with repetitions allowed. When applied to the group B_{n}, the transformation Ψ has the following properties:

(a) fmaj w = finv Ψ(w) for every signed permutation w;

(b) Ψ is a bijection of B_{n} onto itself, so that “fmaj” and “finv” are equidistributed over the hyperoctahedral group B_{n};

(c) Lower w = Lower Ψ(w), so that lowerp w = lowerp Ψ(w) and lowern w = lowern Ψ(w).

Actually, the transformation Ψ has stronger properties than those stated above, but these restrictive properties will suffice for the following derivation. Having properties (a)–(c) in mind, we see that the two three-variable statistics (fmaj, lowerp, lowern) and (finv, lowerp, lowern) are equidistributed over B_{n}. Hence, the two generating polynomials

fmajB_{n}(q, X, Y) := ∑_{w∈B_{n}} q^{fmaj}X^{lowerp w}Y^{lowern w}
finvB_{n}(q, X, Y) := ∑_{w∈B_{n}} q^{finv}X^{lowerp w}Y^{lowern w}

are identical. To derive the analytical expression for the common polynomial we have two approaches, using the “fmaj” interpretation, on the one hand, and the “finv” geometry, on the other. In each case we will go beyond the three-variable case, as we consider the generating polynomial for the group B_{n} by the five-variable statistic (fdes, fmaj, lowerp, lowern, neg)

(1.1)  ^{fmaj}B_{n}(t, q, X, Y, Z) := ∑_{w∈B_{n}} t^{fdes w}q^{fmaj w}X^{lowerp w}Y^{lowern w}Z^{neg w}

and the generating polynomial for the group B_{n} by the four-variable statistic (finv, lowerp, lowern, neg)

(1.2)  ^{finv}B_{n}(q, X, Y, Z) := ∑_{w∈B_{n}} q^{finv w}X^{lowerp w}Y^{lowern w}Z^{neg w}.

Using the usual notations for the q-ascending factorial

(1.3)  (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.4)  (a; q)_{∞} := lim_{n}(a; q)_{n} = ∏_{n≥0}(1 − aq^{n});

in its infinite form, we consider the products

(1.5) H_{∞}(u) := \frac{(uq(\frac{Z + q}{1 − q^{2}} − ZY ); q^{2})_{∞}}{(u(\frac{q(Z + q)}{1 − q^{2}} + X); q^{2})_{∞}} ,

in its infinite version, and

(1.6) H_{2s}(u):= \frac{1 − q^{2}}{1 − q^{2} + uq^{2s+1}(Z + q)} \frac{(uq \frac{Z + q − ZY (1 − q^{2})}{1 − q^{2} + uq^{2s+1}(Z + q)}; q^{2})_{s}}{(u\frac{q(Z + q) + X(1 − q^{2})}{1 − q^{2} + uq^{2s+1}(Z + q)}; q^{2})_{s+1}} ,

as well as

(1.7) H_{2s+1}(u) := \frac{(uq \frac{Z + q − ZY (1 − q^{2})}{1 − q^{2} + uq^{2s+2}(Zq + 1)}; q^{2})_{s+1}}{(u\frac{q(Z + q) + X(1 − q^{2})}{1 − q^{2} + uq^{2s+2}(Zq + 1)}; q^{2})_{s+1}} ,

in its graded version under the form ∑_{s≥0} t^{s}H_{s}(u).

The purpose of this paper is to prove the following two theorems and derive several applications regarding statistical distributions over B_{n}.

Theorem 1.1 (the “fmaj” approach). Let ^{fmaj}B_{n}(t, q, X, Y, Z) be the generating polynomial for the group B_{n} by the five-variable statistic (fdes, fmaj, lowerp, lowern, neg) as defined in (1.1). Then

(1.8)  ∑_{n≥0}(1 + t)^{fmaj}B_{n}(t, q, X, Y, Z)\frac{u^{n}}{(t^{2}; q^{2})_{n+1}} = ∑_{s≥0} t^{s}H_{s}(u),

where H_{s}(u) is the finite product introduced in (1.6) and (1.7).

Theorem 1.2 (the “finv” approach). Let ^{finv}B_{n}(q, X, Y, Z) be the generating polynomial for the group B_{n} by the four-variable statistic (finv, lowerp, lowern, neg), as defined in (1.2). Then

(1.9) ^{finv}B_{n}(q, X, Y, Z) = (X + q + ⋯ + q^{n−1} + q^{n}Z + ⋯ + q^{2n−2}Z + q^{2n−1}Y Z) ⋯ × (X + q + q^{2} + q^{3}Z + q^{4}Z + q^{5}Y Z)(X + q + q^{2}Z + q^{3}Y Z)(X + qY Z).

The proofs of those two theorems are very different in nature. For proving Theorem 1.1 we re-adapt the MacMahon Verfahren to make it work for signed permutations. René Thom’s quotation that appears as an epigraph to this paper illustrates the essence of the MacMahon Verfahren. The topology of the signed permutations measured by the various statistics, “fdes”, “fmaj”, … must be reconstructed when the group of the signed permutations is mapped onto a set of plain words for which the calculation of the associated statistic is easy. There is then a combinatorial bijection between signed permutations and plain words that describes the “flattening” (“aplatissement”) process. This is the content of Theorem 4.1.

Another approach might have been to make use of the P -partition technique introduced by Stanley [St72] and successfully employed by Reiner [Re93a, Re93b, Re93c, Re95a, Re95b] in his statistical study of the hyperoctahedral group.

Theorem 1.2 is based upon another definition of the length function for B_{n} (see formula (7.1)). Notice that in the two theorems we have included a variable Z, which takes the number “neg” of negative letters into account. This allows us to re-obtain the classical results on the symmetric group by letting Z = 0.

In the next section we show that the infinite product H_{s}(u) first appears as the generating function for a class of plain words by a four-variable statistic (see Theorem 2.2). This theorem will be an essential tool in section 4 in the MacMahon Verfahren for signed permutations to handle the five-variable polynomial ^{fmaj}B_{n}(t, q, X, Y, Z). Section 3 contains an axiomatic definition of the Record-Signed-Euler-Mahonian Polynomials B_{n}(t, q, X, Y, Z). They are defined, not only by (1.8) (with B_{n} replacing ^{fmaj}B_{n}), but also by a recurrence relation. The proof of Theorem 1.1 using the MacMahon Verfahren is found in Section 4. In Section 5 we show how to prove that the polynomials fmajB_{n}(t, q, X, Y, Z) satisfy the same recurrence as the polynomials B_{n}(t, q, X, Y, Z), using an insertion technique. The specializations of Theorem 1.1 are numerous and described in section 6. We end the paper with the proof of Theorem 1.2 and its specializations.

2. Lower Records on Words

As mentioned in the introduction, Theorem 2.2 below, dealing with ordinary words, appears to be a preparation lemma for Theorem 1.1, that takes the geometry of signed permutations into account. Consider an ordinary word c = c_{1}c_{2} … c_{n}, whose letters belong to the alphabet {0, 1, …, s}, that is, a word from the free monoid {0, 1, …, s}^{∗}. A letter c_{i} (1 ≤ i ≤ n) is said to be an even lower record (resp. odd lower record) of c, if c_{i} is even (resp. odd) and if c_{j} ≥ c_{i} (resp. c_{j} > c_{i}) for all j such that 1 ≤ j ≤ i−1. Notice the discrepancy between even and odd letters. Also, to define those even and odd lower records for words the reading is made from left to right, while for signed permutations, the lower records are read from right to left (see Sections 1 and 4). We could have considered a totally ordered alphabet with two kinds of letters, but playing with the parity of the nonnegative integers is more convenient for our applications. For instance, the even (resp. odd) lower records of the word c = 5 4 4 1 5 2 1 0 4 0 3 are reproduced in boldface (resp. in italic).

For each word c let evenlower c (resp. oddlower c) be the number of even (resp. odd) lower records of c. Also let tot c (“tot” stands for “total”) be the sum c_{1} +c_{2} +⋯+c_{n} of the letters of c and odd c be the number of its odd letters. Also denote its length by |c| and let |c|_{k} be the number of letters in c equal to k. Our purpose is to calculate the generating function for {0, 1, …, s}^{∗} by the four-variable statistic (tot, evenlower, oddlower, odd).

Say that c = c_{1}c_{2} … c_{n} is of minimal index k (0 ≤ k ≤ s/2), if min c := min{c_{1}, …, c_{n}} is equal to 2k or 2k + 1. Let c_{j} be the leftmost letter of c equal to 2k or 2k + 1. Then, c admits a unique factorization

(2.1) c = c′c_{j}c′′, having the following properties:

c′ ∈ {2k + 2, 2k + 3, …, s}^{∗}, c_{j} = 2k or 2k + 1, c′′ ∈ {2k, 2k + 1, …, s}^{∗}.

With the forementioned example we have the factorization c′ = 5 4 4, c_{j} = 1, c′′ = 5 2 1 0 4 0 3. In this example notice that c_{j} = 1 ≠ min c = 0.

Lemma 2.1. The numbers of even and odd lower records of a word c can be calculated by induction as follows: evenlower c = oddlower c := 0 if c is empty; otherwise, let c = c′c_{j}c′′ be its minimal index factorization (defined in (2.1)). Then

(2.2)  evenlower c = evenlower c′ + χ(c_{j} = 2k) + |c′′|_{2k};
(2.3)  oddlower c = oddlower c′ + χ(c_{j} = 2k + 1).

Proof. Keep the same notations as in (2.1). If c_{j} = 2k, then c_{j} is an even lower record, as well as all the letters equal to 2k to the right of c_{j}. On the other hand, there is no even lower record equal to 2k to the left of c_{j}, so that (2.2) holds. If c_{j} = 2k + 1, then c_{j} is an odd lower record and there is no odd lower record equal to 2k + 1 to the right of c_{j}. Moreover, there is no odd lower record to the left of c_{j} equal to c_{j}. Again (2.3) holds.

It is straightforward to verify that the fraction H_{s}(u) displayed in (1.6) and (1.7) can also be expressed as

(2.4) H_{2s}(u) = ∏_{0≤k≤s}\frac{1 − u([q^{2k+1}(1 − Y)Z + q^{2k+2} + ⋯ + q^{2s−2} + q^{2s−1}Z + q^{2s}])}{1 − u(q^{2k}X + [q^{2k+1}Z + q^{2k+2} + ⋯ + q^{2s−2} + q^{2s−1}Z + q^{2s}])}

(2.5) H_{2s+1}(u) = ∏_{0≤k≤s}\frac{1 − u(q^{2k+1}(1 − Y)Z + [q^{2k+2} + ⋯ + q^{2s} + q^{2s+1}Z])}{1 − u(q^{2k}X + q^{2k+1}Z + [q^{2k+2} + ⋯ + q^{2s} + q^{2s+1}Z])},

where the expression between brackets vanishes whenever k = s, and that the H_{s}(u)’s satisfy the recurrence formula

(2.6) H_{0}(u) = \frac{1}{1 − uX}; H_{1}(u) = \frac{1 − uqZ(1 − Y)}{1 − u(X + qZ)}; and for s ≥ 1

H_{2s}(u) = \frac{1 − u(q(1 − Y)Z + q^{2} + q^{3}Z + ⋯ + q^{2s−1}Z + q^{2s})}{1 − u(X + qZ + q^{2} + q^{3}Z + ⋯ + q^{2s−1}Z + q^{2s})}H_{2s−2}(uq^{2});

H_{2s+1}(u)= \frac{1 − u(q(1 − Y)Z + q^{2} + q^{3}Z+⋯+q^{2s} + q^{2s+1}Z)}{1 − u(X + qZ + q^{2} + q^{3}Z + ⋯ + q^{2s} + q^{2s+1}Z)}H_{2s−1}(uq^{2}).

Theorem 2.2. The generating function for the free monoid {0, 1, …, s}^{∗} by the fourvariable statistic (tot, evenlower, oddlower, odd) is equal to H_{s}(u), that is to say,

(2.7)  ∑_{c∈{0,1,...,s}^{∗}} u^{|c|}q^{tot c}X^{evenlower c}Y^{oddlower c}Z^{odd c} = H_{s}(u).

Proof. Let H_{s}^{∗}(u) denote the left-hand side of (2.7). Then,

H_{0}^{∗}(u) = ∑_{c∈\{0\}^{∗}} u^{|c|}q^{0}X^{|c|}Y^{0}Z^{0} = \frac{1}{1 − uX} .

When s = 1 the minimal index factorization of each nonempty word c reads c = c_{j}c′′, so that

H_{1}^{∗}(u) = 1 + u(X + qY Z) ∑_{c′′∈{0,1}^{∗}} u^{|c′′|}q^{|c′′|_{1}}X^{|c′′|_{0}}Y^{0}Z^{|c′′|_{1}}

= 1 + u(X + qY Z)\frac{1}{1 − u(X + qZ)} = \frac{1 − uqZ(1 − Y)}{1 − u(X + qZ)}.

Consequently, H_{s}^{∗}(u) = H_{s}(u) for s = 0, 1. For s ≥ 2 we write

H_{s}^{∗}(u) = ∑_{0≤k≤s/2} H_{s,k}^{∗}(u)

with

H_{s,k}^{∗}(u) := ∑_{{c∈\{0,1,...,s\}^{∗} \atop min_{i} c_{i}=2k or 2k+1}} u^{|c|}q^{tot c}X^{evenlower c}Y^{oddlower c}Z^{odd c}.

the electronic journal of combinatorics 12 (2005), #R00 6

From Lemma 2.1 it follows that

H_{s,0}^{∗}(u) = ∑_{c′∈{2,...,s}^{∗}} u^{|c′|}q^{tot c′}X^{evenlower c′}Y^{oddlower c′}Z^{odd c′} × u(X + qY Z)

× ∑_{c′′∈{0,...,s}^{∗}} u^{|c′′|}q^{tot c′′}X^{|c′′|_{0}}Z^{odd c′′}

= ∑_{c′∈{0,...,s−2}^{∗}} (uq^{2})^{|c′|}q^{tot c′}X^{evenlower c′}Y^{oddlower c′}Z^{odd c′}× u(X + qY Z)

× ∑_{c′′∈{0,...,s}^{∗}} (uX)^{|c′′|_{0}}(uqZ)^{|c′′|_{1}}(uq^{2})^{|c′′|_{2}}(uq^{3}Z)^{|c′′|_{3}}(uq^{4})^{|c′′|_{4}} ⋯

= H_{s−2}^{∗}(uq^{2})u(X + qY Z)\frac{1}{1 − u(X + qZ + q^{2} + q^{3}Z + q^{4} + ⋯)},

the polynomial in the denominator ending with ⋯ + q^{s−1}Z + q^{s} or ⋯ + q^{s−1} + q^{s}Z depending on whether s is even or odd.

On the other hand,

∑_{1≤k≤s/2} H_{s,k}^{∗}(u) = ∑_{c∈{2,3,...,s}^{∗}} u^{|c|}q^{tot c}X^{evenlower c}Y^{oddlower c}Z^{odd c}

= ∑_{c∈{0,1,...,s−2}^{∗}} (uq^{2})^{|c|}q^{tot c}X^{evenlower c}Y^{oddlower c}Z^{odd c}

= H_{s−2}^{∗}(uq^{2}). Hence,

H_{s}^{∗}(u) = (1 + \frac{u(X + qY Z)}{1 − u(X + qZ + q^{2} + q^{3}Z + q^{4} + ⋯)})H_{s−2}^{∗}(uq^{2})

= \frac{1 − u(qZ(1 − Y) + q^{2} + q^{3}Z + q^{4} + ⋯)}{1 − u(X + qZ + q^{2} + q^{3}Z + q^{4} + ⋯)}H_{s−2}^{∗}(uq^{2}).

As the fractions H_{s}^{∗}(u) satisfy the same induction relation as the H_{s}(u)’s, we conclude that H_{s}^{∗}(u) = H_{s}(u) for all s.

When s tends to infinity, then H_{s}(u) tends to H_{∞}(u), whose expression is shown in (1.5). In particular, we have the identity:

(2.8)  ∑_{c∈{0,1,2,... }^{∗}} u^{|c|}q^{tot c}X^{evenlower c}Y^{oddlower c}Z^{odd c} = H_{∞}(u).

3. The Record-Signed-Euler-Mahonian Polynomials

Our next step is to form the series ∑_{s≥0} t^{s}H_{s}(u) and show that the series can be expanded as a series in the variable u in the form

(3.1)  ∑_{n≥0} C_{n}(t, q, X, Y, Z)\frac{u^{n}}{(t^{2}; q^{2})_{n+1}} = ∑_{s≥0} t^{s}H_{s}(u),

where B_{n}(t, q, X, Y, Z) := C_{n}(t, q, X, Y, Z)/(1 + t) is a polynomial with nonnegative integral coefficients such that B_{n}(1, 1, 1, 1, 1) = 2^{n}n! .

Definition. A sequence (B_{n}(t, q, X, Y, Z) = ∑_{k≥0} t^{k}B_{n,k}(q, X, Y, Z)) (n ≥ 0) of

polynomials in five variables t, q, X, Y and Z is said to be record-signed-Euler-Mahonian, if one of the following equivalent three conditions holds:

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

(3.2)  C_{n}(t, q, X, Y, Z) := (1 + t)B_{n}(t, q, X, Y, Z)

is given by identity (3.1).

(2) For n ≥ 2 the recurrence relation holds:

(3.3) (1 − q^{2})B_{n}(t, q, X, Y, Z)

=(X(1 − q^{2}) + (Zq + q^{2})(1 − t^{2}q^{2n−2}) + t^{2}q^{2n−1}(1 − q^{2})ZY )B_{n−1}(t, q, X, Y, Z)

− \frac{1}{2}(1 − t)q(1 + q)(1 + tq)(1 + Z)B_{n−1}(tq, q, X, Y, Z)

+ \frac{1}{2}(1 − t)q(1 − q)(1 − tq)(1 − Z)B_{n−1}(−tq, q, X, Y, Z),

while B_{0}(t, q, X, Y, Z) = 1, B_{1}(t, q, X, Y, Z) = X + tqY Z.

(3) The recurrence relation holds for the coefficients B_{n,k}(q, X, Y, Z):

(3.4) B_{0,0}(q, X, Y, Z) = 1, B_{0,k}(q, X, Y, Z) = 0 for all k ≠ 0;

B_{1,0}(q, X, Y, Z) = X, B_{1,1}(q, X, Y, Z) = qY Z,

B_{1,k}(q, X, Y, Z) = 0 for all k ≠ 0, 1;

B_{n,2k}(q, X, Y, Z) = (X + qZ + q^{2} + q^{3}Z + ⋯ + q^{2k})B_{n−1,2k}(q, X, Y, Z)

+ q^{2k}B_{n−1,2k−1}(q, X, Y, Z)

+ (q^{2k} + q^{2k+1}Z + ⋯ + q^{2n−1}Y Z)B_{n−1,2k−2}(q, X, Y, Z),

B_{n,2k+1}(q, X, Y, Z)=(X + qZ + q^{2} + ⋯ + q^{2k} + q^{2k+1}Z)B_{n−1,2k+1}(q, X, Y, Z) + q^{2k+1}ZB_{n−1,2k}(q, X, Y, Z) + (q^{2k+1}Z + q^{2k+2} + ⋯ + q^{2n−2} + q^{2n−1}Y Z)B_{n−1,2k−1}(q, X, Y, Z),

for n ≥ 2 and 0 ≤ 2k + 1 ≤ 2n − 1. Theorem 3.1. The conditions (1), (2) and (3) in the previous definition are equivalent.

Proof. The equivalence (2) ⇔ (3) requires a lengthy but elementary algebraic argument and will be omitted. The other equivalence (1) ⇔ (2) involves a more elaborate q-series technique, which is now developed. Let G_{s}(u) := H_{s}(u^{2}); then

G_{0}(u) = \frac{1}{1 − u^{2}X}; G_{1}(u) = \frac{1 − u^{2}qZ(1 − Y)}{1 − u^{2}(X + qZ)};

the electronic journal of combinatorics 12 (2005), #R00 8

and by (2.6)

G_{2s}(u) = \frac{1 − u^{2}(qZ(1 − Y) + q^{2} + q^{3}Z + ⋯ + q^{2s−1}Z + q^{2s})}{1 − u^{2}(X + qZ + q^{2} + q^{3}Z + ⋯ + q^{2s−1}Z + q^{2s})}G_{2s−2}(uq),
G_{2s+1}(u) = \frac{1 − u^{2}(qZ(1 − Y)+q^{2}+q^{3}Z+⋯+q^{2s}+q^{2s+1}Z)}{1 − u^{2}(X + qZ + q^{2} + q^{3}Z + ⋯ + q^{2s} + q^{2s+1}Z)}G_{2s−1}(uq),

for s ≥ 1. Working with the series ∑_{s≥0} t^{s}G_{s}(u) we obtain

∑_{s≥0} t^{2s}G_{2s}(u)(1 − u^{2}(X + \frac{Zq + q^{2}}{1 − q^{2}} − \frac{q^{2s}}{1 − q^{2}} (Zq + q^{2})))

+ ∑_{s≥0} t^{2s+1}G_{2s+1}(u)(1 − u^{2}(X + \frac{Zq + q^{2}}{1 − q^{2}} − \frac{q^{2s+2}}{1 − q^{2}} (Zq + 1)))

= 1 + t(1 − u^{2}qZ(1 − Y))

+ ∑_{s≥1} t^{2s}G_{2s−2}(qu)(1 − u^{2}(−qZY + \frac{Zq + q^{2}}{1 − q^{2}} − \frac{q^{2s}}{1 − q^{2}} (Zq + q^{2})))

+ ∑_{s≥1} t^{2s+1}G_{2s−1}(qu)(1 − u^{2}(−qZY + \frac{Zq + q^{2}}{1 − q^{2}} − \frac{q^{2s+2}}{1 − q^{2}} (Zq + 1))),

which may be rewritten as

∑_{s≥0} t^{s}G_{s}(u)(1 − u^{2}(X + \frac{Zq + q^{2}}{1 − q^{2}} )) = 1 + t(1 − u^{2}qZ(1 − Y))

+ ∑_{s≥0} t^{s+2}G_{s}(qu)(1 − u^{2}(−qZY + \frac{Zq + q^{2}}{1 − q^{2}} ))

− ∑_{s≥0}(tq)^{2s}(G_{2s}(u) − t^{2}q^{2}G_{2s}(qu))u^{2} \frac{Zq + q^{2}}{1 − q^{2}}

− ∑_{s≥0}(tq)^{2s+1}(G_{2s+1}(u) − t^{2}q^{2}G_{2s+1}(qu))u^{2}q \frac{Zq + 1}{1 − q^{2}}.

Now let _{∑n≥0}b_{n}(t)u^{2n} := _{∑s≥0}t^{s}G_{s}(u). This gives:

∑_{n≥0} b_{n}(t)u^{2n}(1 − u^{2}(X + \frac{Zq + q^{2}}{1 − q^{2}} )) = 1 + t(1 − u^{2}qZ(1 − Y))

+ ∑_{n≥0} b_{n}(t)t^{2}q^{2n}u^{2n}(1 − u^{2}(−qZY + \frac{Zq + q^{2}}{1 − q^{2}} ))

− ∑_{n≥0} \frac{b_{n}(tq) + b_{n}(−tq)}{2}(1 − t^{2}q^{2n+2})u^{2n+2} \frac{Zq + q^{2}}{1 − q^{2}}

− ∑_{n≥0} \frac{b_{n}(tq) − b_{n}(−tq)}{2}(1 − t^{2}q^{2n+2})u^{2n+2}q \frac{Zq + 1}{1 − q^{2}}.

the electronic journal of combinatorics 12 (2005), #R00 9

We then have b_{0}(t) = \frac{1}{1 − t}, b_{1}(t) = \frac{X + tqY Z}{(1 − t)(1 − t^{2}q^{2})} and for n ≥ 2

b_{n}(t)(1 − t^{2}q^{2n}) = (X + \frac{Zq + q^{2}}{1 − q^{2}} + t^{2}q^{2n−1}ZY − t^{2}q^{2n−2} \frac{Zq + q^{2}}{1 − q^{2}} )b_{n−1}(t)

− \frac{b_{n−1}(tq)}{2(1 − q^{2})}(1 − t^{2}q^{2n})q(1 + q)(1 + Z) + \frac{b_{n−1}(−tq)}{2(1 − q^{2})}(1 − t^{2}q^{2n})q(1 − q)(1 − Z).

Because of the presence of the factors of the form (1 − t^{2}q^{2n}) we are led to introduce the coefficients C_{n}(t, q, X, Y, Z) := b_{n}(t)(t^{2}; q^{2})_{n+1} (n ≥ 0). By multiplying the latter equation by (t^{2}; q^{2})_{n} we get for n ≥ 2

(3.5) (1 − q^{2})C_{n}(t, q, X, Y, Z)

=(X(1 − q^{2}) + (Zq + q^{2})(1 − t^{2}q^{2n−2}) + t^{2}q^{2n−1}(1 − q^{2})ZY )C_{n−1}(t, q, X, Y, Z)

− \frac{1}{2}(1 − t^{2})q(1 + q)(1 + Z)C_{n−1}(tq, q, X, Y, Z)

+ \frac{1}{2}(1 − t^{2})q(1 − q)(1 − Z)C_{n−1}(−tq, q, X, Y, Z),

while C_{0}(t, q, X, Y, Z) = 1 + t, C_{1}(t, q, X, Y, Z) = (1 + t)(X + tqY Z).

Finally, with C_{n}(t, q, X, Y, Z) := (1 + t)B_{n}(t, q, X, Y, Z) (n ≥ 0) we get the recurrence formula (3.3), knowing that the factorial generating function for the polynomials C_{n}(t, q, X, Y, Z) = (1+t)B_{n}(t, q, X, Y, Z) is given by (3.1). As all the steps are perfectly reversible, the equivalence holds.

4. The MacMahon Verfahren

Now having three equivalent definitions for the record-signed-Euler-Mahonian polynomial B_{n}(t, q, X, Y, Z), our next task is to prove the identity

(4.1)  ^{fmaj}B_{n}(t, q, X, Y, Z) = B_{n}(t, q, X, Y, Z).

Let ℕ^{n} (resp. NIW(n)) be the set of all the words (resp. all the nonincreasing words) of length n, whose letters are nonnegative integers. As we have seen in section 2 (Theorem 2.2), we know how to calculate the generating function for words by a certain four-variable statistic. The next step is to map each pair (b, w) ∈ NIW(n) × B_{n} onto c ∈ ℕ^{n} in such a way that the geometry on w can be derived from the latter statistic on c.

For the construction we proceed 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 = z_{1}z_{2} … z_{n} and ϵ = ϵ_{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 := a_{1}a_{2} … a_{n} and c′ := c′_{1}c′_{2} … c′_{n}. Finally, form the

two-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 = 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 & = & 1 & 1 & 1 & 0 & 0 & 0 & 0 \\ w & = & 6 & \overline{5} & \overline{4} & 1 & 7 & \overline{3} & \overline{2} \\ z & = & 2 & 1 & 1 & 1 & 1 & 0 & 0 \\ ϵ & = & 0 & 1 & 1 & 0 & 0 & 1 & 1 \\ a & = & 3 & 2 & 2 & 1 & 1 & 0 & 0 \\ c′ & = & 6 & 5 & 5 & 2 & 2 & 1 & 1 \\ c & = & 2 & 1 & 1 & 5 & 5 & 6 & 2 \end{aligned}

Theorem 4.1. For each nonnegative integer r the above mapping is a bijection of the set of all the 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 = r onto the set of the words c = c_{1}c_{2} … c_{n} ∈ ℕ^{n} such that max c = r. Moreover,

(4.2) 2b_{1} + fdes w = max c; 2 tot b + fmaj w = tot c; (4.3) lowerp w = evenlower c; lowern w = oddlower c; neg w = odd c.

Before giving the proof of Theorem 4.1 we derive its analytic consequences. First, it is q-routine to prove the three identities, where b_{1} is the first letter of b,

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

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

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

We then consider

\frac{1 + t}{(t^{2}; q^{2})_{n+1}}^{fmaj}B_{n}(t, q, X, Y, Z),

where

fmajB_{n}(t, q, X, Y, Z) := ∑_{w∈B_{n}} t^{fdes w}q^{fmaj w}X^{lowerp w}Y^{lowern w}Z^{neg w},

which we rewrite as

∑_{r′≥0}(t^{2r′} + t^{2r′+1})\left[{n + r′ \atop r′}\right]_{q^{2}}^{fmaj}B_{n}(t, q, X, Y, Z)  [by (4.4)]

= ∑_{r≥0} t^{r}\left[{n + ⌊r/2⌋ \atop ⌊r/2⌋}\right]_{q^{2}}^{fmaj}B_{n}(t, q, X, Y, Z)  [and by (4.5)]

= ∑_{r≥0} t^{r} ∑_{b∈NIW(n), 2b_{1}≤r} q^{2 tot b} ∑_{w∈B_{n}} t^{fdes w}q^{fmaj w}X^{lowerp w}Y^{lowern w}Z^{neg w}

= ∑_{s≥0} t^{s} ∑_{{b∈NIW(n), w∈B_{n} \atop 2b_{1}+fdes w≤s}} q^{2 tot b+fmaj w}X^{lowerp w}Y^{lowern w}Z^{neg w}.

By Theorem 4.1 the set {(b, w) : b ∈ NIW(n), w ∈ B_{n}, 2b_{1} + fdes w ≤ s} is in bijection with the set {0, 1, …, s}^{n} and (4.2) and (4.3) hold. Hence,

\frac{1 + t}{(t^{2}; q^{2})_{n+1}} ^{fmaj}B_{n}(t, q, X, Y, Z) = ∑_{s≥0} t^{s} ∑_{c∈\{0,...,s\}^{n}} q^{tot c}X^{evenlower c}Y^{oddlower c}Z^{odd c}.

Now use Theorem 2.2:

∑_{s≥0} t^{s}H_{s}(u) = ∑_{s≥0} t^{s} ∑_{c∈{0,1,...,s}^{∗}} u^{|c|}q^{tot c}X^{evenlower c}Y^{oddlower c}Z^{odd c}

= ∑_{n≥0} u^{n} ∑_{s≥0} t^{s} ∑_{c∈{0,1,...,s}^{n}} q^{tot c}X^{evenlower c}Y^{oddlower c}Z^{odd c}

= ∑_{n≥0}(1 + t)^{fmaj}B_{n}(t, q, X, Y, Z)\frac{u^{n}}{(t^{2}; q^{2})_{n+1}} .

Thus, identity (4.1) is proved, as well as Theorem 1.1.

Let us now complete the proof of Theorem 4.1. First, max c = c′_{1} = 2a_{1} + ϵ_{1} = 2b_{1} +2z_{1} +ϵ_{1} = 2b_{1} +fdes w; also tot c = tot c′ = 2 tot a+tot ϵ = 2 tot b+2 tot z +tot ϵ = 2 tot b + fmaj w. Hence (4.2) holds.

Next, prove that (b, w) ↦ c is bijective. As both sequences b and z are nonincreasing, a = b + z is also nonincreasing. If x_{k} > x_{k+1}, then z_{k} = z_{k+1} + 1 and a_{k} ≥ a_{k+1} + 1, then c′_{k} = 2a_{k} + ϵ_{k} ≥ 2a_{k+1} + 2 + ϵ_{k} ≥ 2a_{k+1} + 2 > 2a_{k+1} + ϵ_{k+1} = c′_{k+1}. Thus,

(4.7)  x_{k} > x_{k+1} ⇒ c′_{k} > c′_{k+1}.

To construct the reverse bijection we proceed as follows. Start with a sequence c = c_{1}c_{2} … c_{n}; form the word δ = δ_{1}δ_{2} … δ_{n}, where δ_{i} := χ(c_{i} even) − χ(c_{i} odd) (1 ≤ i ≤ n) and the two-row matrix

( \begin{matrix}c_{1} & c_{2} & … & c_{n} \\ 1δ_{1} & 2δ_{2} & … & nδ_{n} \end{matrix} ) .

Rearrange the columns in such a way that \binom{c_{i}}{i} occurs to the left of \binom{c_{j}}{j}, if either c_{i} > c_{j}, or c_{i} = c_{j}, i < j. The bottom of the new matrix is a signed permutation w. After those two transformations the new matrix reads

\binom{c′}{w} = ( \begin{matrix}c′_{1} & c′_{2} & … & c′_{n} \\ x_{1} & x_{2} & … & x_{n} \end{matrix} ) .

The sequences ϵ and z are defined as above, as well as the sequence a := (c′ − ϵ)/2. As the sequence c′ is nonincreasing, the inequality c′_{k} − ϵ_{k} ≥ c′_{k+1} − ϵ_{k+1} holds if ϵ_{k} = 0 or if ϵ_{k} = ϵ_{k+1} = 1. It also holds when ϵ_{k} = 1 and ϵ_{k+1} = 0, because in such a case c′_{k} is odd and c′_{k+1} even and then c′_{k} ≥ 1 + c′_{k+1}. Hence, a is also nonincreasing.

Finally, define b := a − z. Because of (4.7) we have z_{k} = z_{k+1} + 1 ⇒ c′_{k} > c′_{k+1}. If c′_{k} and c′_{k+1} are of the same parity, then c′_{k} > c′_{k+1} ⇒ a_{k} > a_{k+1}. If c′_{k} > c′_{k+1} holds and the two terms are of different parity, then c′_{k} is even and c′_{k+1} odd. Hence, a_{k} = c′_{k}/2 > (c′_{k+1} − ϵ_{k+1})/2 = a_{k+1}. Thus z_{k} = z_{k+1} + 1 ⇒ a_{k} > a_{k+1}. As z_{n} = 0, we conclude by a decreasing induction that b_{k} = a_{k} − z_{k} ≥ a_{k+1} − z_{k+1} = b_{k+1}, so that b is a nonincreasing sequence of nonnegative integers.

There remains to prove (4.3). First, the letter c_{j} of c is odd, if and only if j occurs with the minus sign in w, so that neg w = odd c. Next, suppose that x_{j} is a positive lower record of w = x_{1}x_{2} … x_{n}. For j < i we have x_{j} < |x_{i}|. Hence, the following implications hold: |x_{i}| < x_{j} ⇒ i < j ⇒ c′_{i} ≥ c′_{j} ⇒ c_{|x_{j}|} ≤ c_{|x_{i}|} and c_{x_{i}} is an even lower record of c. If x_{j} is a negative lower record of w, then j < i ⇒ −x_{j} < |x_{i}|, so that |x_{i}| < −x_{j} ⇒ i < j ⇒ c′_{i} > c′_{j} ⇒ c_{|x_{j}|} < c_{|x_{i}|} and c_{|x_{i}|} is an odd lower record of c.

5. The Insertion Method

Another method for proving identity (4.1) is to make use of the insertion method. Each signed permutation w′ = x′_{1} … x′_{n−1} of order (n − 1) gives rise to 2n signed permutations of order n when n or −n is inserted to the left or to the right w′, or between two letters of w′. Assuming that w′ has a flag descent number equal to fdes w′ = k, our duty is then to watch how the statistics “fmaj”, “lowerp”, “lowern”, “neg” are modified after the insertion of n or −n into the possible n slots. Such a method has already been used by Adin et al. [ABR01], Chow and Gessel [ChGe04], Haglund et al. [HLR04], for “fmaj” only. They all have observed that for each j = 0, 1, …, 2n − 1 there is one and only one signed permutation of order n derived by the insertion of n or −n whose flag-major index is increased by j.

In our case we observe that the number of positive (resp. negative) lower records remains alike, except when n (resp. −n) is inserted to the right of w′, where it increases by 1. The number of negative letters increases only when −n is inserted. For controlling “fdes” we make a distinction between the signed permutations having an even flag descent number and those having an odd one. For the former ones the first letter is positive. When n (resp. −n) is inserted to the left of w′, the flag descent number increases by 2 (resp. by 1). For the latter ones the first letter is negative. When n (resp. −n) is inserted to the left of w′, the flag descent number increases by 1 (resp. remains invariant).

For n ≥ 2, 0 ≤ k ≤ 2n − 1 let
fmajB_{n,k} := ∑_{w∈B_{n}, fdes w=k} q^{fmaj w}X^{lowerp w}Y^{lowern w}Z^{neg w},

and ^{fmaj}B_{0,0} := 1, ^{fmaj}B_{0,k} := 0 when k ≠ 0; ^{fmaj}B_{1,0} = X, ^{fmaj}B_{1,1} = qY Z. Making use of the observations above we easily see that the polynomials ^{fmaj}B_{n,k} satisfy the same recurrence relation, displayed in (3.4), as the B_{n,k}(q, Y, Y, Z).

Remark. How to compare the MacMahon Verfahren and the insertion method? Recurrence relations may be difficult to be truly verified. The first procedure has the advantage of giving both a new identity on ordinary words (Theorem 2.1) and a closed expression for the factorial generating function for the polynomials ^{fmaj}B_{n}(t, q, X, Y, Z) (formula (1.8)).

6. Specializations

When a variable has been deleted in the following specializations of the polynomials B_{n}(t, q, X, Y, Z), this means that the variable has been given the value 1. For instance, B_{n}(q, X, Y, Z) := B_{n}(1, q, X, Y, Z).

When s tends to infinity, then H_{s}(u) tends to H_{∞}(u) given in (1.1). Hence, when identity (3.1) is multiplied by (1 − t) and t is replaced by 1, identity (3.1) specializes into

(6.1)  ∑_{n≥0} B_{n}(q, X, Y, Z)\frac{u^{n}}{(q^{2}; q^{2})_{n}} =H_{∞}(u)= \frac{(uq(\frac{Z + q}{1 − q^{2}} − ZY ); q^{2})_{∞}}{(u(\frac{q(Z + q)}{1 − q^{2}} + X); q^{2})_{∞}} .

Now expand H_{∞}(u) by means of the q-binomial theorem [GaRa90, chap.1]. We get:

H_{∞}(u) = ∑_{n≥0}(\frac{q(\frac{Z + q}{1 − q^{2}} − Y Z)}{\frac{q(Z + q)}{1 − q^{2}} + X}; q^{2})_{n}(u(\frac{q(Z + q)}{1 − q^{2}} + X))^{n}/(q^{2}; q^{2})_{n}.

By identification

B_{n}(q, X, Y, Z) = (\frac{q(\frac{Z + q}{1 − q^{2}} − Y Z)}{\frac{q(Z + q)}{1 − q^{2}} + X}; q^{2})_{n}(\frac{q(Z + q)}{1 − q^{2}} + X)^{n},

which can also be written as (6.2) B_{n}(q, X, Y, Z) = (X + qZ + q^{2} + q^{3}Z + ⋯ + q^{2n−2} + Y Zq^{2n−1})

⋯ × (X + qZ + q^{2} + q^{3}Z + q^{4} + q^{5}Y Z)(X + qZ + q^{2} + q^{3}Y Z)(X + qY Z),

or, by induction, (6.3) B_{n}(q, X, Y, Z) = (X + qZ + q^{2} + q^{3}Z + ⋯ + q^{2n−2} + Y Zq^{2n−1})B_{n−1}(q, X, Y, Z) for n ≥ 2 and B_{1}(q, X, Y, Z) = X + qY Z.

In particular, the polynomial ^{fmaj}B_{n}(q, X, Y) defined in the introduction is equal to

(6.4) B_{n}(q, X, Y) = (X + q + q^{2} + q^{3} + ⋯ + q^{2n−2} + Y q^{2n−1})

⋯ × (X + q + q^{2} + q^{3} + q^{4} + q^{5}Y)(X + q + q^{2} + q^{3}Y)(X + qY).

Finally, when X = Y = Z := 1, identity (6.4) reads

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

an identity derived by several authors (Adin et al. [ABR01], Chow & Gessel [ChGe04], Haglund et al. [HLR04]) with ad hoc methods. Also notice that for X = Y = Z := 1 formula (6.2) yields B_{n}(q) = (q^{2}; q^{2})_{n}/(1 − q)^{n}.

For Z = 0 we get

fmajB_{n}(t, q, X, Y, 0) = ∑_{w∈𝔖_{n}} t^{fdes w}q^{fmaj w}X^{lowerp w},

since the monomials corresponding to signed permutations having negative letters vanish. The summation is then over the ordinary permutations. Also notice that fmajB_{n}(t, q, X, Y, 0) = ^{fmaj}B_{n}(t, q, X, 0, 0). Moreover, for each ordinary permutation w we have: fdes w = 2 des w and fmaj w = 2 maj w. When Y = Z = 0 we also have

H_{2+1}(u) = H_{2s}(u) = \frac{(\frac{uq^{2}}{1 − q^{2} + uq^{2(s+1)}} ; q^{2})_{s+1}}{(u\frac{X(1 − q^{2}) + q^{2}}{1 − q^{2} + uq^{2(s+1)}} ; q^{2})_{s+1}}

and

∑_{n≥0}(1 + t) ^{fmaj}B_{n}(t, q, X, 0, 0)\frac{u^{n}}{(t^{2}; q^{2})_{n+1}} = ∑_{s≥0}(t^{2s} + t^{2s+1})H_{2s}(u).

With A_{n}(t, q, X) := ^{fmaj}B_{n}(t^{1/2}, q^{1/2}, X, 0, 0) = ∑_{w∈𝔖_{n}}t^{des w}q^{maj w}X^{lowerp w} we obtain the identity

(6.7)  ∑_{n≥0} A_{n}(t, q, X)\frac{u^{n}}{(t; q)_{n+1}} = ∑_{s≥0} t^{s} \frac{(\frac{uq}{1 − q + uq^{s+1}} ; q)_{s+1}}{(u\frac{X(1 − q) + q}{1 − q + uq^{s+1}} ; q)_{s+1}} ,

apparently a new identity for the generating function for the symmetric groups 𝔖_{n} by the three-variable statistic (des, maj, lowerp), as well as the following one obtained by multiplying the identity by (1 − t) and letting t go to infinity:

(6.8)  ∑_{n≥0} A_{n}(q, X)\frac{u^{n}}{(q; q)_{n}} = \frac{(\frac{uq}{1 − q}; q)_{∞}}{(uX + \frac{uq}{1 − q}; q)_{∞}} .

the electronic journal of combinatorics 12 (2005), #R00 15

7. Lower Records and Flag-inversion Number

The purpose of this section is prove Theorem 1.2. We proceed as follows. For each (ordinary) permutation σ = σ_{1}σ_{2} … σ_{n} of order n and for each i = 1, 2, …, n let b_{i}(σ) denote the number of letters σ_{j} to the left of σ_{i} such that σ_{j} < σ_{i}. On the other hand, for each signed permutation w = x_{1}x_{2} … x_{n} of order n let abs w denote the (ordinary) permutation |x_{1}| |x_{2}| … |x_{n}|. It is straightforward to see that another expression for the flag-inversion number (or the length function), finv w, of w is the following

(7.1)  finv w = inv abs w + ∑_{1≤i≤n}(2b_{i}(abs w) + 1)χ(x_{i} < 0).

The generating polynomial ^{finv}B_{n}(q, X, Y) can be derived as follows. Let Lower σ denote the set of the (necessarily positive) records of the ordinary permutation σ. By (7.1) we have

finvB_{n}(q, X, Y, Z) =∑_{w∈B_{n}} q^{finv w}X^{lowerp w}Y^{lowern w}Z^{neg w}

=∑_{σ∈𝔖_{n}} ∑_{abs w=σ} q^{finv w}X^{lowerp w}Y^{lowern w}Z^{neg w}

=∑_{σ∈𝔖_{n}} q^{inv σ} ∏_{σ_{i}∈Lower σ} (X + Y Zq^{2b_{i}(σ)+1}) ∏_{σ_{i}∉Lower σ} (1 + Zq^{2b_{i}(σ)+1})

:=∑_{σ∈𝔖_{n}} f(σ),

showing that^{finv}B_{n}(q, X, Y, Z) is simply a generating polynomial for the group 𝔖_{n} itself.

But 𝔖_{n} can be generated from 𝔖_{n−1} by inserting the letter n into the possible n slots of each permutation of order n − 1. Let σ′ = σ′_{1}σ′_{2} … σ′_{n−1} be such a permutation. Then

f(σ′_{1}σ′_{2} … σ′_{n−2}σ′_{n−1}n) = f(σ′)(X + Y Zq^{2n−1});
f(σ′_{1}σ′_{2} … σ′_{n−2}nσ′_{n−1}) = f(σ′)q(1 + Zq^{2n−3});
⋯  ⋯
f(σ′_{1}nσ′_{2} … σ′_{n−2}σ′_{n−1}) = f(σ′)q^{n−2}(1 + Zq^{3});
f(nσ′_{1}σ′_{2} … σ′_{n−2}σ′_{n−1}) = f(σ′)q^{n−1}(1 + Zq).

Hence, ^{finv}B_{n}(q, X, Y, Z) = ^{finv}B_{n−1}(q, X, Y, Z)(X +q +⋯+q^{n−1} +q^{n}Z +⋯+q^{2n−2}Z + q^{2n−1}Y Z) (n ≥ 2). As ^{finv}B_{1}(q, X, Y, Z) = X + qY Z, we get the expression displayed in (1.9).

Comparing (6.2) with (1.9) we see that the two polynomials ^{finv}B_{n}(q, Z) and B_{n}(q, Z) are different as soon as n ≥ 2, while ^{finv}B_{n}(q, X, Y) = B_{n}(q, X, Y) for all n. This means that any bijection Ψ of the group B_{n} onto itself having the property that

fmaj w = finv Ψ(w)

does not leave the number of negative letters “neg” invariant. It was, in particular, the case for the bijection constructed in our previous paper [FoHa05].

Remark 1. Instead of considering lower records from right to left we can introduce lower records from left to right. Let lowerp′ w and lowern′ w denote the numbers of such records, positive and negative, respectively and introduce

finvB_{n}(q, X, Y, X′, Y′):= ∑_{w∈B_{n}}q^{finv w}X^{lowerp w}Y^{lowern w}X^{′ lowerp′ w}Y^{′ lowern′ w}.

Using the method developed in the proof of the previous theorem we can calculate this polynomial in the form

finvB_{n}(q, X, Y, X′, Y′)

= (X + q + ⋯ + q^{n−2} + q^{n−1}X′ + q^{n}Y′ + q^{n+1} + ⋯ + q^{2n−2} + q^{2n−1}Y) ⋯ × (X + q + q^{2}X′ + q^{3}Y′ + q^{4} + q^{5}Y)(X + qX′ + q^{2}Y′ + q^{3}Y)(XX′ + qY Y′).

Remark 2. The same method may be used for ordinary permutations. For each permutation σ let upper σ denote the number of its upper records from right to left and define:

invA_{n}(q, X, V) := ∑_{σ∈𝔖_{n}} q^{inv σ}X^{lowerp σ}V^{upper σ}.

Then

invA_{n}(q, X, V) = XV (X + qV)(X + q + q^{2}V) ⋯ (X + q + q^{2} + ⋯ + q^{n−1}V),

an identity which can be put into the form

(7.2) ∑_{n≥0}^{inv}A_{n}(q, X, V)\frac{u^{n}}{(q; q)_{n}} = 1 − \frac{XV}{X + V − 1} + \frac{XV}{X + V − 1} \frac{(\frac{u}{1 − q} − ux; q)_{∞}}{(uX + \frac{uq}{1 − q}; q)_{∞}} ,

which specializes into

(7.3)  ∑_{n≥0}^{inv}A_{n}(q, X)\frac{u^{n}}{(q; q)_{n}} = \frac{(\frac{uq}{1 − q}; q)_{∞}}{(uX + \frac{uq}{1 − q}; q)_{∞}};

(7.4)  ∑_{n≥0}^{inv}A_{n}(q, V)\frac{u^{n}}{(q; q)_{n}} = \frac{(\frac{u}{1 − q} − uV; q)_{∞}}{(\frac{u}{1 − q}; q)_{∞}} .

Comparing (7.3) with (6.8) we then see that A_{n}(q, X) = ^{inv}A_{n}(q, X). In other words, the generating polynomial for 𝔖_{n} by (maj, lowerp) is the same as the generating polynomial by (inv, lowerp). A combinatorial proof of this result is due to Björner and Wachs [BjW88], who have made use of the transformation constructed in [Fo68]. Finally, the expression of ^{inv}A_{n}(q, X, V) for q = 1 was derived by David and Barton ([DaBa62], chap. 10).

Acknowledgements. The authors should like to thank the referee for his careful reading and his 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.

[BjW88] Anders Björner and Michelle L. Wachs, Permutation Statistics and Linear Extensions of Posets,

J. Combin. Theory, Ser. A, vol. 58, 1991, p. 85–114.

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

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

[DaBa62] F. N. David and D. E. Barton, Combinatorial Chance. London, Charles Griffin, 1962.

[Fo68] Dominique Foata, On the Netto inversion of a sequence, Proc. Amer. Math. Soc., vol. 19, 1968,

p. 236–240.

[FoHa05] Dominique Foata and Guo-Niu Han, Signed Words and Permutations, I; a Fundamental Transformation, 2005.

[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, Manuscript, 49 p., 2004.

[Hu90] James E. Humphreys, Reflection Groups and Coxeter Groups. Cambridge Univ. Press, Cambridge (Cambridge Studies in Adv. Math., 29), 1990.

[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. Combina-

torics, vol. 2, 1995, # R25.

[St72] Richard P. Stanley, Ordered structures and partitions. Mem. Amer. Math. Soc. no. 119, Amer. Math. Soc., Providence, 1972.