2006/08/10

SIGNED WORDS AND PERMUTATIONS, IV; FIXED AND PIXED POINTS

Dominique Foata and Guo-Niu Han

Von Jacobs hat er die Statur, Des Rechnens ernstes Führen, Von Lottärchen die Frohnatur und Lust zu diskretieren. To Volker Strehl, a dedication à la Goethe, on the occasion of his sixtieth birthday.

Abstract

The flag-major index “fmaj” and the classical length function “ℓ” are used to construct two q-analogs of the generating polynomial for the hyperoctahedral group B_{n} by number of positive and negative fixed points (resp. pixed points). Specializations of those q-analogs are also derived dealing with signed derangements and desarrangements, as well as several classical results that were previously proved for the symmetric group.

1. Introduction

The statistical study of the hyperoctahedral group B_{n}, initiated by Reiner ([Re93a], [Re93b], [Re93c], [Re95a], [Re95b]), has 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]. It then appeared natural to extend the numerous results obtained for the symmetric group 𝔖_{n} to the groug B_{n}. Furthermore, flag-major index and length function become the true q-analog makers needed for calculating various multivariable distributions on B_{n}.

In the present paper we start with a generating polynomial for B_{n} by a three-variable statistic involving the number of fixed points (see formula (1.3)) and show that there are two ways of q-analogizing it, by using the flag-major index on the one hand, and the length function on the other hand. As will be indicated, the introduction of an extra variable Z makes it possible to specialize all our results to the symmetric group. Let us first give the necessary notations.

DOMINIQUE FOATA AND GUO-NIU HAN

Let B_{n} be the hyperoctahedral group of all signed permutations of order n. The elements of B_{n} may be viewed as words w = x_{1}x_{2} ⋯ x_{n}, where each x_{i} belongs to {−n, …, −1, 1, …, n} and |x_{1}||x_{2}| ⋯ |x_{n}| is a permutation of 12 … n. The set (resp. the number) of negative letters among the x_{i}’s is denoted by Neg w (resp. neg w). A positive fixed point of the signed permutation w = x_{1}x_{2} ⋯ x_{n} is a (positive) integer i such that x_{i} = i. It is convenient to write \overline{i} := −i for each integer i. Also, when A is a set of integers, let \overline{A} := \{\overline{i} : i ∈ A\}. If x_{i} = \overline{i} with i positive, we say that \overline{i} is a negative fixed point of w. The set of all positive (resp. negative) fixed points of w is denoted by Fix^{+} w (resp. Fix^{−} w). Notice that Fix^{−} w ⊂ Neg w. Also let

2000 Mathematics Subject Classification. Primary 05A15, 05A30, 05E15.

Key words and phrases. Hyperoctahedral group, length function, flag-major index, signed permutations, fixed points, pixed points, derangements, desarrangements, pixed factorization.

(1.1)  fix^{+} w := # Fix^{+} w; fix^{−} w := # Fix^{−} w.

There are 2^{n}n! signed permutations of order n. The symmetric group 𝔖_{n} may be considered as the subset of all w from B_{n} such that Neg w = ∅.

The purpose of this paper is to provide two q-analogs for the polynomials B_{n}(Y_{0}, Y_{1}, Z) defined by the identity

(1.2) ∑_{n≥0} \frac{u^{n}}{n!} B_{n}(Y_{0}, Y_{1}, Z) = (1 − u(1 + Z))^{−1} × \frac{exp(u(Y_{0} + Y_{1}Z))}{exp(u(1 + Z))}.

When Z = 0, the right-hand side becomes (1 − u)^{−1} exp(uY_{0})/ exp(u), which is the exponential generating function for the generating polynomials for the groups 𝔖_{n} by number of fixed points (see [Ri58], chap. 4). Also, by identification, B_{n}(1, 1, 1) = 2^{n}n! and it is easy to show (see Theorem 1.1) that B_{n}(Y_{0}, Y_{1}, Z) is in fact the generating polynomial for the group B_{n} by the three-variable statistic (fix^{+}, fix^{−}, neg), that is,

(1.3)  B_{n}(Y_{0}, Y_{1}, Z) = ∑_{w∈B_{n}} Y_{0}^{fix^{+}w} Y_{1}^{fix^{−}w} Z^{neg w}.

Recall the traditional notations for the q-ascending factorials

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

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

for the q-multinomial coefficients

(1.5) \left[{n \atop m_{1}, …, m_{k}}\right]_{q} := \frac{(q; q)_{n}}{(q; q)_{m_{1}} ⋯ (q; q)_{m_{k}}} (m_{1} + ⋯ + m_{k} = n);

and for the two q-exponentials (see [GaRa90, chap. 1])

(1.6) e_{q}(u) = ∑_{n≥0} \frac{u^{n}}{(q; q)_{n}} = \frac{1}{(u; q)_{∞}}; E_{q}(u) = ∑_{n≥0} \frac{q^{\binom{n}{2}}u^{n}}{(q; q)_{n}} = (−u; q)_{∞}.

FIXED AND PIXED POINTS

Our two q-analogs, denoted by ^{ℓ}B_{n}(q, Y_{0}, Y_{1}, Z) and B_{n}(q, Y_{0}, Y_{1}, Z), are respectively defined by the identities:

(1.7) ∑_{n≥0} \frac{u^{n}}{(−Zq; q)_{n} (q; q)_{n}} ^{ℓ}B_{n}(q, Y_{0}, Y_{1}, Z)

= (1 − \frac{u}{1 − q} )^{−1} × (u; q)_{∞} (∑_{n≥0} \frac{(−qY_{0}^{−1}Y_{1}Z; q)_{n} (uY_{0})^{n}}{(−Zq; q)_{n} (q; q)_{n}} );

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

= (1 − u\frac{1 + qZ}{1 − q^{2}} )^{−1}× \frac{(u; q^{2})_{∞}}{(uY_{0}; q^{2})_{∞}} \frac{(−uqY_{1}Z; q^{2})_{∞}}{(−uqZ; q^{2})_{∞}} .

Those two identities can be shown to yield (1.2) when q = 1.

There is also a graded form of (1.8) in the sense that an extra variable t can be added to form a new polynomial B_{n}(t, q, Y_{0}, Y_{1}, Z) with nonnegative integral coefficients that specializes into B_{n}(q, Y_{0}, Y_{1}, Z) for t = 1. Those polynomials are defined by the identity

(1.9) ∑_{n≥0}(1 + t)B_{n}(t, q, Y_{0}, Y_{1}, Z)\frac{u^{n}}{(t^{2}; q^{2})_{n+1}}

= ∑_{s≥0} t^{s}(1 − u ∑_{i=0}^{s} q^{i}Z^{χ(i odd)})^{−1}×\frac{(u; q^{2})_{⌊s/2⌋+1}}{(uY_{0}; q^{2})_{⌊s/2⌋+1}} \frac{(−uqY_{1}Z; q^{2})_{⌊(s+1)/2⌋}}{(−uqZ; q^{2})_{⌊(s+1)/2⌋}} ,

where for each statement A we let χ(A) = 1 or 0 depending on whether A is true or not. The importance of identity (1.9) lies in its numerous specializations, as can be seen in Fig. 1.

The two q-extensions ^{ℓ}B_{n}(q, Y_{0}, Y_{1}, Z) and B_{n}(t, q, Y_{0}, Y_{1}, Z) being now defined, the program is to derive appropriate combinatorial interpretations for them. Before doing so we need have a second combinatorial interpretation for the polynomial B_{n}(Y_{0}, Y_{1}, Z) besides the one mentioned in (1.3). Let w = x_{1}x_{2} ⋯ x_{n} be a word, all letters of which are integers without any repetitions. Say that w is a desarrangement if x_{1} > x_{2} > ⋯ > x_{2k} and x_{2k} < x_{2k+1} for some k ≥ 1. By convention, x_{n+1} = ∞. We could also say that the leftmost trough of w occurs at an even position. This notion was introduced by Désarménien [De84] and elegantly used in a subsequent paper [DeWa88]. Notice that there is no one-letter desarrangement. By convention, the empty word e is also a desarrangement.

Now let w = x_{1}x_{2} ⋯ x_{n} be a signed permutation. Unless w is increasing, there is always a nonempty right factor of w which is a desarrangement. It then makes sense to define w^{d} as the longest such a right factor. Hence, w admits a unique factorization w = w^{−}w^{+}w^{d}, called its pixed^{(1)} factorization, where w^{−} and w^{+} are both increasing, the letters of w^{−} being negative, those of w^{+} positive and where w^{d} is the longest right factor of w which is a desarrangement.

(1) “Pix,” of course, must not be taken here for the abbreviated form of “pictures.”

For example, the pixed factorizations of the following signed permutations are materialized by vertical bars: w = \overline{5} \overline{2} | e | \overline{3} \overline{4} 1; w = \overline{5} | e | \overline{2} \overline{3} 1 \overline{4}; w = \overline{5} \overline{3} \overline{2} | 1 4 | e; w = \overline{5} \overline{3} | 1 | 4 2; w = \overline{5} \overline{3} | e | 4 1 2.

Let w = w^{−}w^{+}w^{d} be the pixed factorization of w = x_{1}x_{2} ⋯ x_{n}. If w^{−} = x_{1} ⋯ x_{k}, w^{+} = x_{k+1} ⋯ x_{k+l}, define Pix^{−} w := {x_{1}, …, x_{k}}, Pix^{+} w := {x_{k+1}, …, x_{k+l}}, pix^{−} w := # Pix^{−} w, pix^{+} w := # Pix^{+} w.

Theorem 1.1. The polynomial B_{n}(Y_{0}, Y_{1}, Z) defined by (1.2) admits the following two combinatorial interpretations:

B_{n}(Y_{0}, Y_{1}, Z) = ∑_{w∈B_{n}} Y_{0}^{fix^{+} w} Y_{1}^{fix^{−} w} Z^{neg w} = ∑_{w∈B_{n}} Y_{0}^{pix^{+} w} Y_{1}^{pix^{−} w} Z^{neg w}.

Theorem 1.1 is proved in section 2. A bijection ϕ of B_{n} onto itself will be constructed that satisfies (Fix^{−}, Fix^{+}, Neg) w = (Pix^{−}, Pix^{+}, Neg) ϕ(w).

Let “ℓ” be the length function of B_{n} (see [Bo68, p. 7], [Hu90, p. 12] or the working definition given in (3.1)). As seen in Theorem 1.2, “ℓ” is to be added to the three-variable statistic (pix^{+}, pix^{−}, neg) (and not to (fix^{+}, fix^{−}, neg)) for deriving the combinatorial interpretation of ℓB_{n}(q, Y_{0}, Y_{1}, Z). This theorem is proved in section 3.

Theorem 1.2. For each n ≥ 0 let ^{ℓ}B_{n}(q, Y_{0}, Y_{1}, Z) be the polynomial defined in (1.7). Then

(1.10)  ^{ℓ}B_{n}(q, Y_{0}, Y_{1}, Z) = ∑_{w∈B_{n}} q^{ℓ(w)} Y_{0}^{pix^{+} w} Y_{1}^{pix^{−} w} Z^{neg w}.

The variables t and q which are added to interpret our second extension B_{n}(t, q, Y_{0}, Y_{1}, Z) will carry the flag-descent number “fdes” and the flagmajor index “fmaj.” For each signed permutation w = x_{1}x_{2} ⋯ x_{n} the usual number of descents “des” is defined by des w := ∑_{i=1}^{n−1} χ(x_{i} > x_{i+1}), the major index “maj” by maj w := ∑_{i=1}^{n−1} i χ(x_{i} > x_{i+1}), the flag descent number “fdes” and the flag-major index “fmaj” by

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

Theorem 1.3. For each n ≥ 0 let B_{n}(t, q, Y_{0}, Y_{1}, Z) be the polynomial defined in (1.9). Then

(1.12) B_{n}(t, q, Y_{0}, Y_{1}, Z) = ∑_{w∈B_{n}} t^{fdes w} q^{fmaj w} Y_{0}^{fix^{+} w} Y_{1}^{fix^{−} w} Z^{neg w}.

Theorem 1.3 is proved in Section 5 after discussing the combinatorics of the so-called weighted signed permutations in Section 4. Section 6 deals with numerous specializations of Theorem 1.2 and 1.3 obtained by taking numerical values, essentially 0 or 1, for certain variables. Those specializations are illustrated by the following diagram (Fig. 1). When Z = 0, the statistic “neg” plays no role and the signed permutations become plain permutations; the second column of the diagram is then mapped on the third one that only involves generating polynomials for 𝔖_{n} or subsets of that group.

[figure: (fmaj,fix^{−},neg); D_{n}^{B}; D_{n}^{B}(q, Y_{1}, Z); fdes; D_{n}(q); des; neg; maj; D_{n}; D_{n}^{B}(t, q, Y_{1}, Z); ^{fix^{+}}; neg; D_{n}(t, q); ^{fix^{+}}; B_{n}(t, q, Y_{0}, Y_{1}, Z); neg; fdes; B_{n}(q, Y_{0}, Y_{1}, Z); A_{n}(q, Y_{0}); des; A_{n}(t, q, Y_{0}); (fix^{+},fix^{−},neg); (pix^{+},pix^{−},neg); B_{n}; B_{n}(Y_{0}, Y_{1}, Z); fmaj; A_{n}(Y_{0}); maj; ^{fix^{+}}; ^{pix^{+}}; 𝔖_{n}; inv; ^{ℓ}B_{n}(q, Y_{0}, Y_{1}, Z); ^{inv}A_{n}(q, Y_{0}); ℓ; ^{fix^{+}}; ^{pix^{+}}; ^{ℓ}K_{n}^{B}(q, Y_{1}, Z); ^{pix^{+}}; ^{inv}K_{n}(q); (ℓ,pix^{−},neg); K_{n}^{B}; inv; imaj; K_{n}; neg; neg; neg; neg]

Fig. 1

The first (resp. fourth) column refers to specific subsets of B_{n} (resp. of 𝔖_{n}):

(1.13)

D_{n} := {w ∈ B_{n} : Fix^{+} w = Neg w = ∅};
K_{n} := {w ∈ B_{n} : Pix^{+} w = Neg w = ∅};
D_{n}^{B} := {w ∈ B_{n} : Fix^{+} w = ∅};
K_{n}^{B} := {w ∈ B_{n} : Pix^{+} w = ∅}.

The elements of D_{n} are the classical derangements and provide the most natural combinatorial interpretations of the derangement numbers d_{n} = #D_{n} (see [Co70], p. 9–12). By analogy, the elements of D_{n}^{B} are called signed derangements. They have been studied by Chow [Ch06] in a recent note. The elements of K_{n} (resp. of K_{n}^{B}) are called desarrangements (resp. signed desarrangements) of order n. When Y_{0} = 0, the statistic fix^{+} (resp. pix^{+}) plays no role. We can then calculate generating functions for signed and for plain derangements (resp. desarrangements), as shown in the first two rows (resp. last row). The initial polynomial, together with its two q-analogs are reproduced in boldface.

2. Proof of Theorem 1.1

As can be found in ([Co70], p. 9–12)), the generating function for the derangement numbers d_{n} (n ≥ 0) is given by

(2.1)  ∑_{n≥0} d_{n} \frac{u^{n}}{n!} = (1 − u)^{−1}e^{−u}.

An easy calculation then shows that the polynomials B_{n}(Y_{0}, Y_{1}, Z), introduced in (1.2), can also be defined by the identity

(2.2) B_{n}(Y_{0}, Y_{1}, Z) = ∑_{i+j+k+l=n} \binom{n}{i, j, k, l}Y_{0}^{i} Y_{1}^{j} Z^{j+k} d_{k+l} (n ≥ 0).

For each signed permutation w = x_{1}x_{2} ⋯ x_{n} let A := Fix^{+} w, B := Fix^{−} w, C := Neg w \ Fix^{−} w, D := [n] \ (A ∪ \overline{B} ∪ \overline{C}). Then (A, \overline{B}, \overline{C}, D) is a sequence of disjoint subsets of integers, whose union is the interval [n] := \{1, 2, …, n\}. Also the mapping τ defined by τ(\overline{j}) = x_{j} if \overline{j} ∈ C and τ(j) = x_{j} if j ∈ D is a derangement of the set C + D. Hence, w is completely characterized by the sequence (A, B, C, D, τ). The generating polynomial for B_{n} by the statistic (fix^{+}, fix^{−}, neg) is then equal to the right-hand side of (2.2). This proves the first identity of Theorem 1.1.

Each signed permutation w = x_{1}x_{2} ⋯ x_{n} can be characterized, either by the four-term sequence (Fix^{+} w, Fix^{−} w, Neg w, τ), as just described, or by (Pix^{+} w, Pix^{−} w, Neg w, w^{d}), where w^{d} is the desarrangement occurring as the third factor in its pixed factorization. To construct a bijection ϕ of B_{n} onto B_{n} such that (fix^{−}, fix^{+}, neg) w = (pix^{−}, pix^{+}, neg) ϕ(w) and accordingly prove the second identity of Theorem 1.1, we only need a bijection τ ↦ f(τ), that maps each derangement τ onto a desarrangement f(τ) by rearranging the letters of τ. But such a bijection already exists. It is due to Désarménien (op. cit.). We describe it by means of an example.

Start with a derangement τ = (\begin{matrix}1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 \\ 9 & 7 & 4 & 3 & 8 & 2 & 6 & 5 & 1 \end{matrix}) and express it as a

product of its disjoint cycles: τ = (1 9)(2 7 6)(3 4)(5 8). In each cycle, write the minimum in the second position: τ = (9 1)(6 2 7)(4 3)(8 5). Then, reorder the cycles in such a way that the sequence of those minima, when reading from left to right, is decreasing: τ = (8 5)(4 3)(6 2 7)(9 1). The desarrangement f(τ) is derived from the latter expression by removing the parentheses: f(τ) = 8 5 4 3 6 2 7 9 1.

Let (Fix^{+} w, Fix^{−} w, Neg w, τ) be the sequence associated with the signed permutation w and let v^{−} (resp. v^{+}) be the increasing sequence of the elements of Fix^{−} w (resp. of Fix^{+} w). Then, v^{−} | v^{+} | f(τ) is the pixed factorization of v^{−}v^{+}f(τ) and we may define ϕ(w) by

(2.3)  ϕ(w) := v^{−}v^{+}f(τ).

This defines a bijection of B_{n} onto itself, which has the further property:

(2.4)  (Fix^{−}, Fix^{+}, Neg) w = (Pix^{−}, Pix^{+}, Neg) ϕ(w).

For instance, with w = (\begin{matrix}1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 \\ 3 & \overline{2} & 8 & 4 & 5 & \overline{1} & 9 & \overline{6} & 7 \end{matrix}) we have v^{+} = 4 5, v^{−} = \overline{2},

τ = (\begin{matrix}\overline{1} & 3 & \overline{6} & 7 & 8 & 9 \\ 3 & 8 & \overline{1} & 9 & \overline{6} & 7 \end{matrix}) = (9 7)(8 \overline{6} \overline{1} 3) and f(τ) = 9 7 8 \overline{6} \overline{1} 3. Hence, the pixed

factorization of ϕ(w) reads \overline{2} | 4 5 | 9 7 8 \overline{6} \overline{1} 3 and ϕ(w) = \overline{2} 4 5 9 7 8 \overline{6} \overline{1} 3.

3. Proof of Theorem 1.2

The length function “ℓ” for B_{n} is expressed in many ways. We shall use the following expression derived by Brenti [Br94]. Let w = x_{1}x_{2} ⋯ x_{n} be a signed permutation; its length ℓ(w) is defined by

(3.1)  ℓ(w) := inv w + ∑_{i} |x_{i}| χ( x_{i} < 0),

where “inv” designates the usual number of inversions for words:

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

The generating polynomial for K_{n} (as defined in (1.13)) by “inv” (resp. for D_{n} by “maj”) is denoted by K_{n}(q) := ^{inv}K_{n}(q) (resp. D_{n}(q)). As was proved in [DeWa93] we have:

(3.2)  K_{n}(q) = D_{n}(q).

Also

(3.3)  ∑_{n≥0} \frac{u^{n}}{(q; q)_{n}} D_{n}(q) = (1 − \frac{u}{1 − q} )^{−1} × (u; q)_{∞},

as shown by Wachs [Wa90] in an equivalent form. Another expression for D_{n}(q) will be derived in section 6, Proposition 6.2.

If A is a finite set of positive integers, let tot A denote the sum ∑ a (a ∈ A). For the proof of Theorem 1.2 we make use of the following classical result, namely that q^{N(N+1)/2}\left[{n \atop N}\right]_{q} is equal to the sum ∑ q^{tot A}, where the sum is over all subsets A of cardinality N of the set [n].

Remember that each signed permutation w = x_{1}x_{2} … x_{n} is characterized by a sequence (A, B, C, D, τ), where A = Pix^{+} w, B = Pix^{−} w, C = Neg w \ B, D = [n] \ (A ∪ \overline{B} ∪ \overline{C}) and τ is a desarrangement of the set C + D. Let inv(B, C) be the number of pairs of integers (i, j) such that i ∈ B, j ∈ C and i > j. As inv(B, C) = inv(\overline{C}, \overline{B}), we have inv w = inv(\overline{B}, \overline{C}) + inv(A, D) + #A × #C + inv τ. From (3.1) it follows that

ℓ(w) = inv w + ∑_{x_{i}<0} |x_{i}| = inv w + tot \overline{B} + tot \overline{C}
= tot \overline{B} + tot \overline{C} + inv(\overline{C}, \overline{B}) + inv(A, D) + #A × #C + inv τ.

Denote the right-hand side of (1.10) by G_{n} := G_{n}(q, Y_{0}, Y_{1}, Z). We will calculate G_{n}(q, Y_{0}, Y_{1}, Z) by first summing over all sequences (A, B, C, D, τ) such that #A = i, #B = j, #C = k, #D = l. Accordingly, τ is a desarrangement of a set of cardinality k + l. We may write:

G_{n} = ∑_{i+j+k+l=n} ∑_{(A,B,C,D)} q^{tot \overline{B}+tot \overline{C}+inv(\overline{C},\overline{B})+inv(A,D)+i·k}

× Y_{0}^{i}Y_{1}^{j}Z^{j+k} ∑_{τ∈K_{k+l}} q^{inv τ}

= ∑_{m+p=n} ∑_{{j+k=m, \atop i+l=p}} ∑_{{#E=m, \atop F =[n]\E}} ∑_{{\overline{C}+\overline{B}=E, \atop A+D=F}}q^{tot E+inv(\overline{C},\overline{B})+inv(A,D)+i·k}

× Y_{0}^{i}(Y_{1}Z)^{j}Z^{k}D_{k+l}(q)

= ∑_{m+p=n} ∑_{{j+k=m, \atop i+l=p}} Y_{0}^{i}(Y_{1}Z)^{j}(Zq^{i})^{k}D_{k+l}(q)

× ∑_{{#E=m, \atop F =[n]\E}}q^{tot E} ∑_{{\overline{C}+\overline{B}=E, \atop A+D=F}}q^{inv(\overline{C},\overline{B})+inv(A,D)}

= ∑_{m+p=n} ∑_{{j+k=m, \atop i+l=p}} Y_{0}^{i}(Y_{1}Z)^{j}(Zq^{i})^{k}D_{k+l}(q)

× q^{m(m+1)/2}\left[{n \atop m}\right]_{q} \left[{m \atop j, k}\right]_{q} \left[{p \atop i, l}\right]_{q}.

Thus

(3.4)  G_{n} = ∑_{i+j+k+l=n} \left[{n \atop i, j, k, l}\right]_{q}q^{\binom{j+k+1}{2}}Y_{0}^{i}(Y_{1}Z)^{j}(Zq^{i})^{k}D_{k+l}(q).

Now form the factorial generating function

G(q, Y_{0}, Y_{1}, Z; u) := ∑_{n≥0} \frac{u^{n}}{(−Zq; q)_{n} (q; q)_{n}} G_{n}(q, Y_{0}, Y_{1}, Z).

It follows from (3.4) that

G(q, Y_{0}, Y_{1}, Z; u) = ∑_{n≥0} \frac{1}{(−Zq; q)_{n}} ∑_{i+j+k+l=n} q^{\binom{j+k+1}{2}} \frac{(uY_{0})^{i}}{(q; q)_{i}} \frac{(uY_{1}Z)^{j}}{(q; q)_{j}}

× u^{n−i−j} \frac{D_{k+l}(q)(Zq^{i})^{k}}{(q; q)_{k}(q; q)_{l}} .

But \binom{j+k+1}{2} = \binom{j+1}{2} + (j + 1)k + \binom{k}{2}. Hence

G(q, Y_{0}, Y_{1}, Z; u) = ∑_{n≥0} \frac{1}{(−Zq; q)_{n}} ∑_{m=0}^{n} ∑_{i+j=m} q^{\binom{j+1}{2}} \frac{(uY_{0})^{i}}{(q; q)_{i}} \frac{(uY_{1}Z)^{j}}{(q; q)_{j}}

× \frac{u^{n−m}}{(q; q)_{n−m}} D_{n−m}(q) ∑_{k+l=n−m} \left[{n − m \atop k, l}\right]_{q}(Zq^{m+1})^{k}q^{\binom{k}{2}}.

Now

(−Zq^{m+1}; q)_{n−m} = ∑_{k+l=n−m} \left[{n − m \atop k, l}\right]_{q}(Zq^{m+1})^{k}q^{\binom{k}{2}};

and

(−Zq; q)_{n} = (−Zq; q)_{m} (−Zq^{m+1}; q)_{n−m}.

Hence

G(q, Y_{0}, Y_{1}, Z; u) = ∑_{n≥0} ∑_{m=0}^{n} \frac{1}{(−Zq; q)_{m}} ∑_{i+j=m} \frac{(uY_{0})^{i}}{(q; q)_{i}} q^{\binom{j+1}{2}} \frac{(uY_{1}Z)^{j}}{(q; q)_{j}}

× \frac{u^{n−m}}{(q; q)_{n−m}} D_{n−m}(q)

= (∑_{n≥0} \frac{a_{n} u^{n}}{(−Zq; q)_{n} (q; q)_{n}} )(∑_{n≥0} \frac{u^{n}}{(q; q)_{n}} D_{n}(q)),

with

a_{n} = ∑_{i+j=n} \left[{n \atop i, j}\right]_{q}Y_{0}^{i}q^{\binom{j}{2}}(qY_{1}Z)^{j}

= Y_{0}^{n} ∑_{i+j=n} \left[{n \atop i, j}\right]_{q}(qY_{0}^{−1}Y_{1}Z)^{j}q^{\binom{j}{2}}

= Y_{0}^{n}(−qY_{0}^{−1}Y_{1}Z; q)_{n}.

By taking (3.3) into account this shows that G(q, Y_{0}, Y_{1}, Z; u) is equal to the right-hand side of (1.7) and then G_{n}(q, Y_{0}, Y_{1}, Z) = ^{ℓ}B_{n}(q, Y_{0}, Y_{1}, Z) holds for every n ≥ 0. The proof of Theorem 1.2 is completed. By (3.4) we also conclude that the identity

(3.5) ^{ℓ}B_{n}(q, Y_{0}, Y_{1}, Z) = ∑_{i+j+k+l=n} \left[{n \atop i, j, k, l}\right]_{q}q^{\binom{j+k+1}{2}}Y_{0}^{i}(Y_{1}Z)^{j}(Zq^{i})^{k}D_{k+l}(q)

is equivalent to (1.7). As its right-hand side tends to the right-hand side of (2.2) when q → 1, we can then assert that (1.7) specializes into (1.2) for q = 1.

4. Weighted signed permutations

We use the following notations: if c = c_{1}c_{2} ⋯ c_{n} is a word, whose letters are nonnegative integers, let λ(c) := n be the length of c, tot c := c_{1} + c_{2} + ⋯ + c_{n} the sum of its letters and odd c the number of its odd letters. Furthermore, NIW_{n} (resp. NIW_{n}(s)) designates the set of all nonincreasing words of length n, whose letters are nonnegative integers (resp. nonnegative integers at most equal to s). Also let NIW_{n}^{e}(s) (resp. DW_{n}^{o}(s)) be the subset of NIW_{n}(s) of the nonincreasing (resp. strictly decreasing) words all letters of which are even (resp. odd).

Next, each pair \binom{c}{w} is called a weighted signed permutation of order n if the four properties (wsp1)–(wsp4) hold:

(wsp1) c is a word c_{1}c_{2} ⋯ c_{n} from NIW_{n};

(wsp2) w is a signed permutation x_{1}x_{2} ⋯ x_{n} from B_{n};

(wsp3) c_{k} = c_{k+1} ⇒ x_{k} < x_{k+1} for all k = 1, 2, …, n − 1;

(wsp4) x_{k} is positive (resp. negative) whenever c_{k} is even (resp. odd).

When w has no fixed points, either negative or positive, we say that \binom{c}{w} is a weighted signed derangement. The set of weighted signed permutations (resp. derangements) \binom{c}{w} = \binom{c_{1}c_{2}···c_{n}}{x_{1}x_{2}···x_{n}} of order n is denoted by WSP_{n} (resp. by WSD_{n}). The subset of all those weighted signed permutations (resp. derangements) such that c_{1} ≤ s is denoted by WSP_{n}(s) (resp. by WSD_{n}(s)).

For example, the following pair

\binom{c}{w} = ( \begin{matrix}1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 & 10 & 11 & 12 & 13 \\ 10 & 10 & 9 & 7 & 7 & 7 & 4 & 4 & 4 & 3 & 2 & 2 & 1 \\ 1 & 2 & \overline{7} & \overline{6} & \overline{5} & \overline{4} & 3 & 8 & 9 & \overline{10} & 12 & 13 & \overline{11} \end{matrix} )

is a weighted signed permutation of order 13. It has four positive fixed points (1, 2, 8, 9) and two negative fixed points (\overline{5}, \overline{10}).

Proposition 4.1. With each weighted signed permutation \binom{c}{w} from the set WSP_{n}(s) can be associated a unique sequence (i, j, k, \binom{c′}{w′}, v^{e}, v^{o}) such that

(1) i, j, k are nonnegative integers of sum n;

(2) \binom{c′}{w′} is a weighted signed derangement from the set WSD_{i}(s);

(3) v^{e} is a nonincreasing word with even letters from the set NIW_{j}^{e}(s);

(4) v^{o} is a decreasing word with odd letters from the set DW_{k}^{o}(s); having the following properties:

(4.1)

tot c = tot c′ + tot v^{e} + tot v^{o}; neg w = neg w′ + λ(v^{o});
fix^{+} w = λ(v^{e}); fix^{−} w = λ(v^{o}).

The bijection \binom{c}{w} ↦ (\binom{c′}{w′}, v^{e}, v^{o}) is quite natural to define. Only its reverse requires some attention. To get the latter three-term sequence from \binom{c}{w} proceed as follows:

(a) let l_{1}, …, l_{α} (resp. m_{1}, …, m_{β}) be the increasing sequence of the integers l_{i} (resp. m_{i}) such that x_{l_{i}} (resp. x_{m_{i}}) is a positive (resp. negative) fixed point of w;

(b) define: v^{e} := c_{l_{1}} ⋯ c_{l_{α}} and v^{o} := c_{m_{1}} ⋯ c_{m_{β}};

(c) remove all the columns \binom{c_{l_{1}}}{x_{l_{1}}}, …, \binom{c_{lα}}{x_{lα}}, \binom{c_{m_{1}}}{x_{m_{1}}}, …, \binom{c_{m_{β}}}{x_{m_{β}}} from \binom{c}{w} and let c′ be the nonincreasing word derived from c after the removal;

(d) once the letters x_{l_{1}}, …, x_{l_{α}}, x_{m_{1}}, …, x_{m_{β}} have been removed from the signed permutation w the remaining ones form a signed permutation of a subset A of [n], of cardinality n − α − β. Using the unique increasing bijection ϕ of A onto the interval [n − α − β] replace each remaining letter x_{i} by ϕ(x_{i}) if x_{i} > 0 or by −ϕ(−x_{i}) if x_{i} < 0. Let w′ be the signed derangement of order n − α − β thereby obtained.

For instance, with the above weighted signed permutation we have: v^{e} = 10, 10, 4, 4 and v^{o} = 7, 3. After removing the fixed point columns we obtain:

( \begin{matrix}3 & 4 & 6 & 7 & 11 & 12 & 13 \\ 9 & 7 & 7 & 4 & 2 & 2 & 1 \\ \overline{7} & \overline{6} & \overline{4} & 3 & 12 & 13 & \overline{11} \end{matrix} ) and then \binom{c′}{w′} = ( \begin{matrix}1 & 2 & 3 & 4 & 5 & 6 & 7 \\ 9 & 7 & 7 & 4 & 2 & 2 & 1 \\ \overline{4} & \overline{3} & \overline{2} & 1 & 6 & 7 & \overline{5} \end{matrix} ) .

There is no difficulty verifying that the properties listed in (4.1) hold. For reconstructing \binom{c}{w} from the sequence (\binom{c′}{w′}, v^{e}, v^{o}) consider the nonincreasing rearrangement of the juxtaposition product v^{e}v^{o} in the form b_{1}^{h_{1}} ⋯ b_{m}^{h_{m}}, where b_{1} > ⋯ > b_{m} and h_{i} ≥ 1 (resp. h_{i} = 1) if b_{i} is even (resp. odd). The pair \binom{c′}{w′} being decomposed into matrix blocks, as shown in the example, each letter b_{i} indicates where the h_{i} fixed point columns are to be inserted. We do not give more details and simply illustrate the construction with the running example.

With the previous example b_{1}^{h_{1}} ⋯ b_{m}^{h_{m}} = 10^{2} 7 4^{2} 3. First, implement 10^{2}:

( \begin{matrix}1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 \\ 10 & 10 & 9 & 7 & 7 & 4 & 2 & 2 & 1 \\ 1 & 2 & \overline{6} & \overline{5} & \overline{4} & 3 & 8 & 9 & \overline{7} \end{matrix} );

then 7:

( \begin{matrix}1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 & 10 \\ 10 & 10 & 9 & 7 & 7 & 7 & 4 & 2 & 2 & 1 \\ 1 & 2 & \overline{7} & \overline{6} & \overline{5} & \overline{4} & 3 & 9 & 10 & \overline{8} \end{matrix} );

notice that because of condition (wsp3) the letter 7 is to be inserted in second position in the third block; then insert 4^{2}:

( \begin{matrix}1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 & 10 & 11 & 12 \\ 10 & 10 & 9 & 7 & 7 & 7 & 4 & 4 & 4 & 2 & 2 & 1 \\ 1 & 2 & \overline{7} & \overline{6} & \overline{5} & \overline{4} & 3 & 8 & 9 & 11 & 12 & \overline{10} \end{matrix} ) .

The implementation of 3 gives back the original weighted signed permutation \binom{c}{w}.

5. Proof of Theorem 1.3

It is q-routine (see, e.g., [An76, chap. 3]) to prove the following identities, where v_{1} is the first letter of v:

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

\frac{1}{(u; q)_{N+1}} = ∑_{n≥0} u^{n} ∑_{v∈NIW_{n}(N)} q^{tot v} = \frac{1}{1 − u} ∑_{v∈NIW_{n}} q^{tot v}u^{v_{1}};

(5.1) \frac{1}{(u; q^{2})_{⌊s/2⌋+1}} = ∑_{n≥0} u^{n} ∑_{v^{e}∈NIW_{n}^{e}(s)} q^{tot v^{e}};

(5.2) (−uq; q^{2})_{⌊(s+1)/2⌋} = ∑_{n≥0} u^{n} ∑_{v^{o}∈DW_{n}^{o}(s)} q^{tot v^{o}}.

The last two formulas and Proposition 4.1 are now used to calculate the generating function for the weighted signed permutations. The symbols NIW^{e}(s), DW^{o}(s), WSP(s), WSD(s) designate the unions for n ≥ 0 of the corresponding symbols with an n-subscript.

Proposition 5.2. The following identity holds:

(5.3) ∑_{n≥0} u^{n} ∑_{\binom{c}{w}∈WSP_{n}(s)} q^{tot c}Y_{0}^{fix^{+} w}Y_{1}^{fix^{−} w}Z^{neg w}

= \frac{(u; q^{2})_{⌊s/2⌋+1}}{(uY_{0}; q^{2})_{⌊s/2⌋+1}} \frac{(−uqY_{1}Z; q^{2})_{⌊(s+1)/2⌋}}{(−uqZ; q^{2})_{⌊(s+1)/2⌋}} × ∑_{n≥0} u^{n} ∑_{\binom{c}{w}∈WSP_{n}(s)} q^{tot c}Z^{neg w} .

Proof. First, summing over (w^{e}, w^{o}, \binom{c}{w}) ∈ NIW^{e}(s) × DW^{o}(s) × WSP(s), we have

∑_{w^{e},w^{o},\binom{c}{w}} u^{λ(w^{e})}q^{tot w^{e}} × (uZ)^{λ(w^{o})}q^{tot w^{o}} × u^{λ(c)}q^{tot c}Y_{0}^{fix^{+} w}Y_{1}^{fix^{−} w}Z^{neg w}

(5.4) = \frac{(−uqZ; q^{2})_{⌊(s+1)/2⌋}}{(u; q^{2})_{⌊s/2⌋+1}} × \begin{matrix}∑ \\ ( & {c \atop w} & ) \end{matrix} u^{λ(c)}q^{tot c}Y_{0}^{fix^{+} w}Y_{1}^{fix^{−} w}Z^{neg w}

by (5.1) and (5.2). Now, Proposition 4.1 implies that the initial expression can also be summed over five-term sequences (\binom{c′}{w′}, v^{e}, v^{o}, w^{e}, w^{o}) from WSD(s) × NIW^{e}(s) × DW^{o}(s) × NIW^{e}(s) × DW^{o}(s) in the form

∑_{\binom{c′}{w′},v^{e},v^{o},w^{e},w^{o}} u^{λ(c′)}q^{tot c′}Z^{neg w′} × (uY_{0})^{λ(v^{e})}q^{tot v^{e}} × (uY_{1}Z)^{λ(v^{o})}q^{tot v^{o}}

× u^{λ(w^{e})}q^{tot w^{e}} × (uZ)^{λ(w^{o})}q^{tot w^{o}}

= ∑_{v^{e},v^{o}}(uY_{0})^{λ(v^{e})}q^{tot v^{e}} × (uY_{1}Z)^{λ(v^{o})}q^{tot v^{o}}

× ∑_{\binom{c′}{w′},w^{e},w^{o}} u^{λ(c′)}q^{tot c′}Z^{neg w′} × u^{λ(w^{e})}q^{tot w^{e}} × (uZ)^{λ(w^{o})}q^{tot w^{o}}.

The first summation can be evaluated by (5.1) and (5.2), while by Proposition 4.1 again the second sum can be expressed as a sum over weighted signed permutations \binom{c}{w} ∈ WSP(s). Therefore, the initial sum is also equal to

(5.5)  \frac{(−uqY_{1}Z; q^{2})_{⌊(s+1)/2⌋}}{(uY_{0}; q^{2})_{⌊s/2⌋+1}} × ∑_{\binom{c}{w}∈WSP(s)} u^{λ(c)}q^{tot c}Z^{neg w}.

Identity (5.3) follows by equating (5.4) with (5.5).

Proposition 5.3. The following identity holds:

(5.6)  ∑_{n≥0} u^{n} ∑_{\binom{c}{w}∈WSP_{n}(s)} q^{tot c}Z^{neg w} = (1 − u ∑_{i=0}^{s} q^{i}Z^{χ(i odd)})^{−1}.

Proof. For proving the equivalent identity

(5.7)  ∑_{\binom{c}{w}∈WSP_{n}(s)} q^{tot c}Z^{neg w} = (∑_{i=0}^{s} q^{i}Z^{χ(i odd)})^{n} (n ≥ 0)

it suffices to construct a bijection \binom{c}{w} ↦ d of WSP_{n}(s) onto \{0, 1, …, s\}^{n} such that tot c = tot d and neg w = odd d. This bijection is one of the main ingredients of the MacMahon Verfahren for signed permutations that has been fully described in [FoHa05, § 4]. We simply recall the construction of the bijection by means of an example.

Start with (\begin{matrix}c \\ w \end{matrix}) = (\begin{matrix}10 & 9 & 7 & 4 & 4 & 2 & 2 & 1 & 1 \\ 1 & \overline{4} & \overline{3} & 2 & 5 & 6 & 8 & \overline{9} & \overline{7} \end{matrix}). Then, form the two-matrix

(\begin{matrix}10 & 9 & 7 & 4 & 4 & 2 & 2 & 1 & 1 \\ 1 & 4 & 3 & 2 & 5 & 6 & 8 & 9 & 7 \end{matrix}), where the negative integers on the bottom row have been replaced by their opposite values. Next, rearrange its columns in such a way that the bottom row is precisely 1 2 … n. The word d is defined

to be the top row in the resulting matrix. Here \binom{d}{Id}=(\begin{matrix}10 & 4 & 7 & 9 & 4 & 2 & 1 & 2 & 1 \\ 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 \end{matrix}).

As d is a rearrangement of c, we have tot c = tot d and neg w = odd d. For reconstructing the pair \binom{c}{w} from d = d_{1}d_{2} ⋯ d_{n} simply make a full use of condition (wsp3).

Using the properties of this bijection we have:

∑_{\binom{c}{w}∈WSP_{n}(s)} q^{tot c}Z^{neg w} = ∑_{d∈\{0,1,...,s\}^{n}} q^{tot d}Z^{odd d} = ∑_{d∈\{0,1,...,s\}^{n}} ∏_{i=1}^{n} q^{d_{i}}Z^{χ(d_{i} odd)}

= ∏_{i=1}^{n} ∑_{d_{i}∈{0,1,...,s}} q^{d_{i}}Z^{χ(d_{i} odd)} = (∑_{i=0}^{s} q^{i}Z^{χ(i odd)})^{n}.

Proposition 5.4. Let G_{n}:= G_{n}(t, q, Y_{0}, Y_{1}, Z) denote the right-hand side of (1.12) in the statement of Theorem 1.3. Then

(5.8)  \frac{1 + t}{(t^{2}; q^{2})_{n+1}} G_{n} = ∑_{s≥0} t^{s} ∑_{\binom{c}{w}∈WSP_{n}(s)} q^{tot c}Y_{0}^{fix^{+} w}Y_{1}^{fix^{−} w}Z^{neg w}.

Proof. A very similar calculation has been made in the proof of Theorem 4.1 in [FoHa05]. We also make use of the identities on the qascending factorials that were recalled in the beginning of this section. First,

\frac{1 + t}{(t^{2}; q^{2})_{n+1}} = ∑_{r′≥0}(t^{2r′} + t^{2r′+1})\left[{n + r′ \atop r′}\right]_{q^{2}}

= ∑_{r≥0} t^{r}\left[{n + ⌊r/2⌋ \atop ⌊r/2⌋}\right]_{q^{2}} = ∑_{r≥0} t^{r} ∑_{b∈NIW_{n}(⌊r/2⌋)} q^{2 tot b}.

Then,

\frac{1 + t}{(t^{2}; q^{2})_{n+1}} G_{n} = ∑_{r≥0} t^{r} ∑_{{b∈NIW_{n}, \atop 2b_{1}≤r}} q^{2 tot b} ∑_{w∈B_{n}} t^{fdes w}q^{fmaj w}Y_{0}^{fix^{+} w}Y_{1}^{fix^{−} 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}Y_{0}^{fix^{+} w}Y_{1}^{fix^{−} w}Z^{neg w}.

As proved in [FoHa05, § 4] to each \binom{c}{w} = \binom{c_{1}···c_{n}}{x_{1}···x_{n}} ∈ WSP_{n}(s) there corresponds a unique b = b_{1} ⋯ b_{n} ∈ NIW_{n} such that 2b_{1} + fdes w = c_{1} and 2 tot b + fmaj w = tot c. Moreover, the mapping \binom{c}{w} ↦ (b, w) is a bijection of WSP_{n}(s) onto the set of all pairs (b, w) such that b = b_{1} ⋯ b_{n} ∈ NIW_{n} and w ∈ B_{n} with the property that 2b_{1} + fdes w ≤ s.

The word b is determined as follows: write the signed permutation w as a linear word w = x_{1}x_{2} … x_{n} and for each k = 1, 2, …, n let z_{k} be the number of descents (x_{i} > x_{i+1}) in the right factor x_{k}x_{k+1} ⋯ x_{n} and let ϵ_{k} be equal to 0 or 1 depending on whether x_{k} is positive or negative. Also for each k = 1, 2, …, n define a_{k} := (c_{k} − ϵ_{k})/2, b_{k} := (a_{k} − z_{k}) and form the word b = b_{1} ⋯ b_{n}.

For example,

\begin{aligned}Id & = & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 & 10 \\ c & = & 9 & 7 & 7 & 4 & 4 & 4 & 2 & 2 & 1 & 1 \\ w & = & \overline{4} & \overline{3} & \overline{2} & 1 & 5 & 6 & 8 & 9 & \overline{10} & \overline{7} \\ z & = & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 0 & 0 \\ ϵ & = & 1 & 1 & 1 & 0 & 0 & 0 & 0 & 0 & 1 & 1 \\ a & = & 4 & 3 & 3 & 2 & 2 & 2 & 1 & 1 & 0 & 0 \\ b & = & 3 & 2 & 2 & 1 & 1 & 1 & 0 & 0 & 0 & 0 \end{aligned}

Pursuing the above calculation we get (5.8).

We can complete the proof of Theorem 1.3:

∑_{n≥0}(1 + t)G_{n}(t, q, Y_{0}, Y_{1}, Z)\frac{u^{n}}{(t^{2}; q^{2})_{n+1}}

= ∑_{s≥0} t^{s} ∑_{n≥0} u^{n} ∑_{\binom{c}{w}∈WSP_{n}(s)} q^{tot c}Y_{0}^{fix^{+} w}Y_{1}^{fix^{−} w}Z^{neg w}  [by (5.8)]

= ∑_{s≥0} t^{s} \frac{(u; q^{2})_{⌊s/2⌋+1}}{(uY_{0}; q^{2})_{⌊s/2⌋+1}} \frac{(−uqY_{1}Z; q^{2})_{⌊(s+1)/2⌋}}{(−uqZ; q^{2})_{⌊(s+1)/2⌋}}

× ∑_{n≥0} u^{n} ∑_{\binom{c}{w}∈WSP_{n}(s)} q^{tot c}Z^{neg w} [by (5.3)]

= ∑_{s≥0} t^{s}(1 − u ∑_{i=0}^{s} q^{i}Z^{χ(i odd)})^{−1}

× \frac{(u; q^{2})_{⌊s/2⌋+1}}{(uY_{0}; q^{2})_{⌊s/2⌋+1}} \frac{(−uqY_{1}Z; q^{2})_{⌊(s+1)/2⌋}}{(−uqZ; q^{2})_{⌊(s+1)/2⌋}} [by (5.6)].

Hence, G_{n}(t, q, Y_{0}, Y_{1}, Z) = B_{n}(t, q, Y_{0}, Y_{1}, Z) for all n ≥ 0.

6. Specializations

For deriving the specializations of the polynomials ^{ℓ}B_{n}(q, Y_{0}, Y_{1}, Z) and B_{n}(t, q, Y_{0}, Y_{1}, Z) with their combinatorial interpretations we refer to the diagram displayed in Fig. 1. Those two polynomials are now regarded as generating polynomials for B_{n} by the multivariable statistics (ℓ, pix^{+}, pix^{−}, neg) and (fdes, fmaj, fix^{+}, fix^{−}, neg), their factorial generating functions being given by (1.7) and (1.9), respectively.

First, identity (1.8) is deduced from (1.9) by the traditional token that consists of multiplying (1.9) by (1 − t) and making t = 1. Accordingly, B_{n}(q, Y_{0}, Y_{1}, Z) occurring in (1.8) is the generating polynomial for the group B_{n} by the statistic (fmaj, fix^{+}, fix^{−}, neg).

Now, let

(6.1)  B(q, Y_{0}, Y_{1}, Z; u) := ∑_{n≥0} \frac{u^{n}}{(q^{2}; q^{2})_{n}} B_{n}(q, Y_{0}, Y_{1}, Z).

The involution of B_{n} defined by w = x_{1}x_{2} ⋯ x_{n} ↦ \overline{w} := \overline{x}_{1}\overline{x}_{2} ⋯ \overline{x}_{n} has the following properties:

(6.2)  fmaj w + fmaj \overline{w} = n^{2}; neg w + neg \overline{w} = n;
(6.3)  fix^{+} w = fix^{−} \overline{w}; fix^{−} w = fix^{+} \overline{w}.

Consequently, the duality between positive and negative fixed points must be reflected in the expression of B(q, Y_{0}, Y_{1}, Z; u) itself, as shown next.

Proposition 6.1. We have:

(6.4)  B(q, Y_{0}, Y_{1}, Z; u) = B(q^{−1}, Y_{1}, Y_{0}, Z^{−1}; −uq^{−1}Z).

Proof. The combinatorial proof consists of using the relations written in (6.2), (6.3) and easily derive the identity

(6.5)  B_{n}(q, Y_{0}, Y_{1}, Z) = q^{n^{2}}Z^{n} B_{n}(q^{−1}, Y_{1}, Y_{0}, Z^{−1}).

With this new expression for the generating polynomial identity (6.1) becomes

B(q, Y_{0}, Y_{1}, Z; u) = ∑_{n≥0} \frac{(−uq^{−1}Z)^{n}}{(q^{−2}; q^{−2})_{n}} B_{n}(q^{−1}, Y_{1}, Y_{0}, Z^{−1}),

which implies (6.4).

The analytical proof consists of showing that the right-hand side of identity (1.8) is invariant under the transformation

(q, Y_{0}, Y_{1}, Z, u) ↦ (q^{−1}, Y_{1}, Y_{0}, Z^{−1}, −uq^{−1}Z).

The factor 1 − u(1 + qZ)/(1 − q^{2}) is clearly invariant. As for the other two factors it suffices to expand them by means of the q-binomial theorem ([GaRa90], p. 7) and observe that they are simply permuted when the transformation is applied.

The polynomial D_{n}^{B}(t, q, Y_{1}, Z) := B_{n}(t, q, 0, Y_{1}, Z) (resp. D_{n}^{B}(q, Y_{1}, Z) := B_{n}(q, 0, Y_{1}, Z)) is the generating polynomial for the set D_{n}^{B} of the signed derangements by the statistic (fdes, fmaj, fix^{−}, neg) (resp. (fmaj, fix^{−}, neg)). Their factorial generating functions are obtained by letting Y_{0} = 0 in (1.9) and (1.8), respectively.

Let Y_{0} = 0, Y_{1} = 1 in (1.8). We then obtain the factorial generating function for the polynomials D_{n}^{B}(q, Z) := ∑ q^{fmaj w}Z^{neg w} (w ∈ D_{n}^{B}) in the form

(6.6)  ∑_{n≥0} \frac{u^{n}}{(q^{2}; q^{2})_{n}} D_{n}^{B}(q, Z) = (1 − u\frac{1 + qZ}{1 − q^{2}} )^{−1} × (u; q^{2})_{∞}.

It is worth writing the equivalent forms of that identity:

(6.7) \frac{(q^{2}; q^{2})_{n}}{(1 − q^{2})^{n}} (1 + qZ)^{n} = ∑_{k=0}^{n} \left[{n \atop k}\right]_{q^{2}}D_{k}^{B}(q, Z) (n ≥ 0);

(6.8) D_{n}^{B}(q, Z)=∑_{k=0}^{n} \left[{n \atop k}\right]_{q^{2}} (−1)^{k}q^{k(k−1)} \frac{(q^{2}; q^{2})_{n−k}}{(1 − q^{2})^{n−k}} (1 + qZ)^{n−k} (n ≥ 0);

(6.9) D_{0}^{B}(q, Z) = 1, and for n ≥ 0

D_{n+1}^{B}(q, Z) = (1 + qZ)\frac{1 − q^{2n+2}}{1 − q^{2}} D_{n}^{B}(q, Z) + (−1)^{n+1}q^{n(n+1)}.

(6.10) D_{0}^{B}(q, Z) = 1, D_{1}^{B}(q, Z) = Zq, and for n ≥ 1

D_{n+1}^{B}(q, Z) = (\frac{1 − q^{2n}}{1 − q^{2}} + qZ \frac{1 − q^{2n+2}}{1 − q^{2}} )D_{n}^{B}(q, Z)

+ (1 + qZ)q^{2n} \frac{1 − q^{2n}}{1 − q^{2}} D_{n−1}^{B}(q, Z).

Note that (6.8) is derived from (6.6) by taking the coefficients of u^{n} on both sides. Next, multiply both sides of (6.6) by the second q^{2}-exponential E_{q^{2}}(−u) and look for the coefficients of u^{n} on both sides. This yields (6.7). Now, write (6.6) in the form

(6.11)  E_{q^{2}}(−u) = (1 − u\frac{1 + qZ}{1 − q^{2}} ) ∑_{n≥0} \frac{u^{n}}{(q^{2}; q^{2})_{n}} D_{n}^{B}(q, Z)

and take the coefficients of u^{n} on both sides. This yields (6.9). Finally, (6.10) is a simple consequence of (6.9).

When Z = 1, formulas (6.6), (6.8), (6.9) have been proved by Chow [Ch06] with D_{n}^{B}(q) = ∑_{w} q^{fmaj w} (w ∈ D_{n}^{B}).

Now the polynomial K_{n}^{B}(q, Y_{1}, Z) := ^{ℓ}B_{n}(q, 0, Y_{1}, Z) is the generating polynomial for the set K_{n}^{B} of the signed desarrangements by the statistic (ℓ, pix^{−}, neg). From (1.7) we get

(6.12) ∑_{n≥0} \frac{u^{n}}{(−Zq; q)_{n} (q; q)_{n}} K_{n}^{B}(q, Y_{1}, Z)

= (1 − \frac{u}{1 − q} )^{−1} × (u; q)_{∞} (∑_{n≥0} \frac{q^{\binom{n+1}{2}}(Y_{1}Zu)^{n}}{(−Zq; q)_{n} (q; q)_{n}} ).

When the variable Z is given the zero value, the polynomials in the second column of Fig. 1 are mapped on generating polynomials for the symmetric group, listed in the third column. Also the variable Y_{1} vanishes. Let A_{n}(t, q, Y_{0}) := B_{n}(t^{1/2}, q^{1/2}, Y_{0}, 0, 0). Then

(6.13) A_{n}(t, q, Y_{0}) = ∑_{σ∈𝔖_{n}} t^{des σ}q^{maj σ}Y_{0}^{fix σ} (fix := fix^{+}).

Identity (1.9) specializes into

(6.14) ∑_{n≥0} A_{n}(t, q, Y_{0})\frac{u^{n}}{(t; q)_{n+1}} = ∑_{s≥0} t^{s}(1 − u ∑_{i=0}^{s} q^{i})^{−1} \frac{(u; q)_{s+1}}{(uY_{0}; q)_{s+1}} ,

an identity derived by Gessel and Reutenauer ([GeRe93], Theorem 8.4) by means of a quasi-symmetric function technique. Note that they wrote their formula for “1 + des” and not for “des.”

Multiply (6.14) by (1−t) and let t := 1, or let Z := 0 and q^{2} be replaced by q in (1.8). Also, let A_{n}(q, Y_{0}) := ∑_{σ} q^{maj σ}Y^{fix σ} (σ ∈ 𝔖_{n}); we get

(6.15)  ∑_{n≥0} \frac{u^{n}}{(q; q)_{n}} A_{n}(q, Y_{0}) = (1 − \frac{u}{1 − q} )^{−1} \frac{(u; q)_{∞}}{(uY_{0}; q)_{∞}} ,

an identity derived by Gessel and Reutenauer [GeRe93] and also by Clarke et al. [ClHaZe97] by means of a q-Seidel matrix approach.

We do not write the specialization of (6.14) when Y_{0} := 0 to obtain the generating function for the polynomials D_{n}(t, q) := ∑_{σ∈D_{n}} t^{des σ}q^{maj σ}.

As for the polynomial D_{n}(q) := ∑_{σ∈D_{n}} q^{maj σ}, it has several analytical

expressions, which can all be derived from (6.7)–(6.10) by letting Z := 0 and q^{2} being replaced by q. We only write the identity which corresponds to (6.7)

(6.16) D_{0}(q) = 1 and \frac{(q; q)_{n}}{(1 − q)^{n}} = ∑_{k=0}^{n} \left[{n \atop k}\right]_{q}D_{k}(q) for n ≥ 1,

which is then equivalent to the identity

(6.17) e_{q}(u) ∑_{n≥0} \frac{u^{n}}{(q; q)_{n}} D_{n}(q) = (1 − \frac{u}{1 − q} )^{−1}.

The specialization of (6.8) for Z := 0 and q^{2} replaced by q was originally proved by Wachs [Wa98] and again recently by Chen and Xu [ChXu06]. Those two authors make use of the now classical MacMahon Verfahren, that has been exploited in several papers and further extended to the case of signed permutation, as described in our previous paper [FoHa05].

In the next proposition we show that D_{n}(q) can be expressed as a polynomial in q with positive integral coefficients. In the same manner, the usual derangement number d_{n} is an explicit sum of positive integers. To the best of the authors’ knowledge those formulas have not appeared elsewhere. In (6.19) we make use of the traditional notation for the ascending factorial : (a)_{n} = 1 if n = 0 and (a)_{n} = a(a + 1) ⋯ (a + n − 1) if n ≥ 1.

Proposition 6.2. The following expressions hold:

(6.18) D_{n}(q) = ∑_{2≤2k≤n−1}\frac{1 − q^{2k}}{1 − q} \frac{(q^{2k+2}; q)_{n−2k−1}}{(1 − q)^{n−2k−1}} q^{\binom{2k}{2}} + q^{\binom{n}{2}}χ(n even),
(6.19)  d_{n} = ∑_{2≤2k≤n−1}(2k)(2k + 2)_{n−2k−1} + χ(n even).

Proof. When q = 1, then (6.18) is transformed into (6.19). As for (6.18), an easy q-calculation shows that its right-hand side satisfies (6.9) when Z = 0 and q replaced by q^{1/2}. As shown by Fu [Fu06], identity (6.18) can also be directly derived from (6.17) by a simple q-calculation.

Now, let ^{inv}A_{n}(q, Y_{0}) := ^{ℓ}B_{n}(q, Y_{0}, 0, 0). Then

(6.20)  ^{inv}A_{n}(q, Y_{0}) = ∑_{σ∈𝔖_{n}} q^{inv σ} Y_{0}^{pix σ} (pix := pix^{+}).

Formula (1.7) specializes into

(6.21) ∑_{n≥0} \frac{u^{n}}{(q; q)_{n}} ^{inv}A_{n}(q, Y_{0}) = (1 − \frac{u}{1 − q} )^{−1} \frac{(u; q)_{∞}}{(uY_{0}; q)_{∞}};

In view of (6.15) we conclude that

(6.22)  A_{n}(q, Y_{0}) = ^{inv}A_{n}(q, Y_{0}).

For each permutation σ = σ(1) ⋯ σ(n) let the ligne of route of σ be defined by Ligne σ := {i : σ(i) > σ(i + 1)} and the inverse ligne of route by Iligne σ := Ligne σ^{−1}. Notice that maj σ = ∑_{i} i χ(i ∈ Ligne σ); we also let imaj σ := ∑_{i} i χ(i ∈ Iligne σ). Furthermore, let i : σ ↦ σ^{−1}. If Φ designates the second fundamental transformation described in [Fo68], [FoSc78], it is known that the bijection Ψ := i Φ i of 𝔖_{n} onto itself has the following property: (Ligne, imaj) σ = (Ligne, inv) Ψ(σ). Hence

(6.23)  (pix, imaj) σ = (pix, inv) Ψ(σ)

and then A_{n}(q, Y_{0}) has the other interpretation:

(6.24)  A_{n}(q, Y_{0}) = ∑_{σ∈𝔖_{n}} q^{imaj σ}Y_{0}^{pix σ}.

Finally, let K_{n}(q) := ∑_{σ∈K_{n}} q^{inv σ}. Then, with Y_{0} := 0 in (6.22) we have:

(6.25)  K_{n}(q) = ^{inv}A_{n}(q, 0) = A_{n}(q, 0) = D_{n}(q).

However, it can be shown directly that K_{n}(q) is equal to the right-hand side of (6.18), because the sum occurring in (6.18) reflects the geometry of the desarrangements. The running term is nothing but the generating polynomial for the desarrangements of order n whose leftmost trough is at position 2k by the number of inversions “inv.”

The bijection Ψ also sends K_{n} onto itself, so that

(6.26)  ∑_{σ∈K_{n}} q^{inv σ} = ∑_{σ∈K_{n}} q^{imaj σ},

a result obtained in this way by Désarménien and Wachs [DeWa90, 93], who also proved that for every subset E ⊂ [n − 1] we have

(6.27)  #{σ ∈ D_{n} : Ligne σ = E} = #{σ ∈ K_{n} : Iligne σ = E}.

Acknowledgement. The authors should like to thank the referee for his careful reading and knowledgeable remarks.

References

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

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

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

[Br94] Francesco Brenti. q-Eulerian Polynomials Arising from Coxeter Groups, Europ.

J. Combin., vol. 15, 1994, p. 417–441.

[ClHaZe97] Robert J. Clarke, Guo-Niu Han, Jiang Zeng. A Combinatorial Interpretation of the Seidel Generation of q-derangement Numbers, Annals of Combin., vol. 1, 1997, p. 313–327.

[Ch06] Chak-On Chow. On derangement polynomials of type B, Sém. Lothar. Combin., B55b 2006, 6 p.

[ChXu06] William Y. C. Chen, Deheng Xu. Labeled Partitions and the q-Derangement

Numbers, arXiv:math.CO/0606481 v1 20 Jun 2006, 6 p.

[Co70] Louis Comtet. Analyse Combinatoire, vol. 2. Presses Universitaires de France, Paris, 1970.

[De84] Jacques Désarménien. Une autre interprétation du nombre des dérangements, Sém. Lothar. Combin., B08b, 1982, 6 pp. (Publ. I.R.M.A. Strasbourg, 1984, 229/S-08, p. 11-16).

[DeWa88] Jacques Désarménien, Michelle L. Wachs. Descentes des dérangements et mots circulaires, Sém. Lothar. Combin., B19a, 1988, 9 pp. (Publ. I.R.M.A. Strasbourg, 1988, 361/S-19, p. 13-21).

[DeWa93] Jacques Désarménien, Michelle L. Wachs. Descent Classes of Permutations with a Given Number of Fixed Points, J. Combin. Theory, Ser. A, vol. 64, 1993, p. 311–328.

[Fo68] Dominique Foata. On the Netto inversion number of a sequence, Proc. Amer.

Math. Soc., vol. 19, 1968, p. 236–240.

[FoHa05] Dominique Foata, Guo-Niu Han. Signed words and permutations, II; the Euler-Mahonian Polynomials, Electronic J. Combin., vol. 11(2), 2005, #R22, 18 p. (The Stanley Festschrift).

[FoSc78] Dominique Foata, Marcel-Paul Schützenberger. Major index and inversion num-

ber of permutations, Math. Nachr., vol. 83, 1978, p. 143–159.

[Fu06] Amy M. Fu. Private communication, 2006.

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

[GeRe93] Ira M. Gessel, Christophe Reutenauer. Counting Permutations with Given Cycle

Structure and Descent Set, J. Combin. Theory, Ser. A, vol. 64, 1993, p. 189–215.

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

[Ri58] John Riordan. An Introduction to Combinatorial Analysis. New York, John Wiley & Sons, 1958.

[Wa89] Michelle L. Wachs. On q-derangement numbers, Proc. Amer. Math. Soc., vol. 106, 1989, p. 273–278.

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