Eulerian Calculus, III : The Ubiquitous Cauchy Formula

Robert J. CLARKE AND Dominique FOATA †

The purpose of this paper is to calculate the distributions of several joint statistics on the symmetric group and related structures that have been studied in the previous two Eulerian Calculus papers. It is shown how the Cauchy formula on symmetric functions, an old MacMahon bijection and a combinatorial lemma on skew-tableaux provide the necessary ingredients for calculating those distributions.

L’objet de cet article est de calculer les distributions de plusieurs statistiques à plusieurs variables définies sur le groupe symétrique et des structures parentes, qui ont été introduites dans les deux articles précédents sur le calcul eulérien. On montre que la formule de Cauchy sur les fonctions symétriques, une bijection ancienne de MacMahon et un lemme sur les tableaux gauches fournissent les ingrédients nécessaires pour le calcul de ces distributions.

1. Introduction

As was explained in our first paper [3], the motivation of this Eulerian Calculus series of three papers was to study the behaviour of several classical statistics on words, such as the number of descents, the number of excedances, the major index, when the strict inequalities required in their definitions were relaxed to include some equalities. Although this study takes all its cogency when those new statistics are defined on classes of words with repetitions, there is also a special analysis to be made for permutations, since statistical distributions can be calculated jointly for permutations and their inverses.

In the present paper we shall be mainly interested in the calculations of those distributions. Let (u_{1}, …, u_{j}), (v_{1}, …, v_{k}) be two sequences of commuting variables and c = (c_{1}, …, c_{j}) and d = (d_{1}, …, d_{k}) be two vectors with non-negative integer components. It will be convenient to write u^{c} for u_{1}^{c_{1}} … u_{j}^{c_{j}} and v^{d} for v_{1}^{d_{1}} … v_{k}^{d_{k}}. If (a; q)_{n} denotes the qascending factorial

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

† Supported in part by a grant of the Australian Research Council, 1993, while the author was on leave at the University of Adelaide, then at the University of New South Wales and by the E.E.C. network programme on Algebraic Combinatorics, while the author revised the paper in Strasbourg.

Robert J. Clarke and Dominique Foata

then (u; q)_{s+1} and (−qv; q)_{s} will stand for the two products

(u_{1}; q)_{s+1} … (u_{j}; q)_{s+1}  and  (−qv_{1}; q)_{s} … (−qv_{k}; q)_{s},

respectively.

From the analytic point of view the present paper is the study of the series

(1.1)  G(u, v; t : q) = ∑_{s≥0} t^{s} \frac{(−qv; q)_{s}}{(u; q)_{s+1}} ,

that will be shown to have an expansion in the algebra of q-series normalized by denominators of the form (t; q)_{n}. More precisely, we shall derive the identity

(1.2)  G(u, v; t : q) = ∑_{c,d} \frac{u^{c}v^{d}}{(t; q)_{1+c+d}} A_{c,d}(t, q),

where the series is over all vectors (c, d) = (c_{1}, …, c_{j}, d_{1}, …, d_{k}), where c = c_{1} + ⋯ + c_{j}, d = d_{1} + ⋯ + d_{k} and where each coefficient A_{c,d}(t, q) is a polynomial with integer coefficients.

As indicated by Andrews [2] in a private communication, the function G(u, v; t : q) introduced in (1.1) can be viewed as a multivariable extension of the basic hypergeometric series

(1.3)  F (a, b; t : q) = ∑_{s≥0} t^{s} \frac{(aq; q)_{s}}{(bq; q)_{s}} ,

thoroughly studied by Fine in the first chapter of his memoir [7]. (See, in particular, the scholarly comment made by Andrews in Fine’s book itself [7, p. 32–36].)

From the combinatorial point of view the purpose of this paper is to show that the polynomial A_{c,d}(t, q) occurring in (1.2) is the generating function for a finite class of words by a bivariable statistic. To define the relevant statistic we use the same notations as in our previous two papers, but for convenience sake we recall them here. First, X is a fixed non-empty set, referred to as an alphabet, that, in most cases, will be taken as the subset [ r] = {1, 2, …, r} (r ≥ 1) of the positive integers with its standard ordering. Unless explicitly stated, j and k will be two fixed non-negative integers of sum r. The letters 1, …, j will be called small and the letters j + 1, …, r large. It is also convenient to adjoin to the set X one element ⋆ that is small but greater than any other small letter.

The free monoid generated by X will be denoted by X^{∗}. The elements of X^{∗} are finite words w = x_{1}x_{2} … x_{m} with letters x_{i} taken from X. A word w′ is said to be a rearrangement of the word w if it can be obtained from w by permuting the letters x_{1}, x_{2}, …, x_{m} in some order.

Eulerian Calculus, III

Let c = (c_{1}, …, c_{j}) and d = (d_{1}, …, d_{k}) be two vectors with nonnegative integer components. The class of all m!/(c_{1}! … c_{j}! d_{1}! … d_{k}!) rearrangements of the non-decreasing word v = y_{1}y_{2} … y_{m} = 1^{c_{1}} … j^{c_{j}}(j + 1)^{d_{1}} … r^{d_{k}} will be denoted by R(c, d).

Let w = x_{1}x_{2} … x_{m} and let \overline{w} = v = y_{1}y_{2} … y_{m} be its non-decreasing rearrangement. As in the previous two papers, we say that the word w has a k-excedance at i (1 ≤ i ≤ m), if either x_{i} > y_{i}, or x_{i} = y_{i} and x_{i} large. We also say that w has a k-descent at i (1 ≤ i ≤ m), if either x > x_{i+1}, or x_{i} = x_{i+1} and x_{i} large. (By convention, x_{m+1} = ⋆.) The numbers of k-excedances and k-descents of a word w are denoted by exc_{k} w and des_{k} w.

The k-major index of a word w is also defined to be the sum, maj_{k} w, of all i such that i is a k-descent in w. In our second paper [4] we have also introduced another statistic, “den_{k},” to be paired with “exc_{k}” and constructed a bijection ρ of R(c, d) onto itself such that (des_{k}, maj_{k})(w) = (exc_{k}, den_{k})(ρ(w)) holds. The first result of the paper is the following theorem.

Theorem 1.1. The generating polynomial for the rearrangement class R(c, d) by the bivariable statistic (des_{k}, maj_{k}) is the polynomial A_{c,d}(t, q) occuring in (1.2).

That is, let

(1.4)  A_{c,d}(t, q) = ∑_{w} t^{des_{k} w}q^{maj_{k} w}  (w ∈ R(c, d)).

Then the following identity holds :

(1.5)  ∑_{c,d} \frac{u^{c}v^{d}}{(t; q)_{1+c+d}} A_{c,d}(t, q) = ∑_{s≥0} t^{s} \frac{(−qv; q)_{s}}{(u; q)_{s+1}} .

Rawlings [17] studied the series

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

(same subscripts (s + 1) and same variables u_{1}, …, u_{r} on both numerator and denominator) a series that can also pretend to be a multivariable extension of Fine’s series, and showed that it was equal to

∑_{c_{1}≥0,...,c_{r}≥0} \frac{u_{1}^{c_{1}} … u_{r}^{c_{r}}}{(t; q)_{c_{1}+···+c_{r}+1}} A_{c_{1},...,c_{r}}(t, q, a, b),

where A_{c_{1},...,c_{r}}(t, q, a, b) is the generating polynomial over the class of bicoloured rearrangements. A bicoloured rearrangement is a pair (w, f), where w = x_{1}x_{2}, … x_{m} is a rearrangement of 1^{c_{1}} … r^{c_{r}} (c_{1} +⋯+c_{r} = m) and f is a sequence of m letters equal to, say, “small” or “large.” His way of colouring the “places” of the letters in each word, instead of the letters themselves in the alphabet X = {1, …, r} lead him to derive different formulas. His technique is based upon an algebra of bicoloured matrices.

In our second paper [4] identity (1.5) was derived by first obtaining a recurrence relation for the polynomials A_{c,d}(t, q) defined by (1.4), then by solving a system of q-partial difference equations. In the present paper we use an entirely different approach : identity (1.5) is derived directly, using classical techniques on symmetric functions and especially the Cauchy identity that expresses the infinite product ∏_{i,j}(1 − x_{i}y_{j})^{−1} either as a

series of products of monomial and homogeneous symmetric functions, or as a series of products of Schur polynomials. We shall use the two forms together with their dual identities. Our main tools will also be, first, an old MacMahon bijection that is here updated to take more parameters into account (see § 3), secondly, a combinatorial lemma on skew-tableaux (see § 5).

The advantage of the present approach is to provide both a common set-up and a combinatorial interpretation to A_{c,d}(t, q) and also to several other generating polynomials for order statistics on words, such as the polynomials A_{c,d}^{I}(t, q), A_{c,d}^{II}(t, q), A_{c,d}^{III}(t, q) defined by

(1.6)  ∑_{c,d} \frac{u^{c}v^{d}}{(t; q)_{1+c+d}} A_{c,d}^{I}(t, q) = ∑_{s≥0} t^{s} \frac{1}{(u; q)_{s+1}(qv; q)_{s}} ,

(1.7)  ∑_{c,d} \frac{u^{c}v^{d}}{(t; q)_{1+c+d}} A_{c,d}^{II}(t, q) = ∑_{s≥0} t^{s}(−u; q)_{s+1}(−qv; q)_{s},

(1.8)  ∑_{c,d} \frac{u^{c}v^{d}}{(t; q)_{1+c+d}} A_{c,d}^{III}(t, q) = ∑_{s≥0} t^{s} \frac{(−u; q)_{s+1}}{(qv; q)_{s}} .

In particular, the following identity

(1.9) \frac{1}{(t; q)_{1+c+d}} A_{c,d}(t, q)

= ∑_{s≥0} t^{s}\left[{c_{1} + s \atop c_{1}}\right] … \left[{c_{j} + s \atop c_{j}}\right]q^{\binom{d_{1}+1}{2}}\left[{s \atop d_{1}}\right] … q^{\binom{d_{k}+1}{2}}\left[{s \atop d_{k}}\right],

where \left[{n \atop l}\right] stands for the q-binomial coefficient

\left[{n \atop l}\right] = \frac{(q; q)_{n}}{(q; q)_{n−l}(q; q)_{l}} ,

can be derived combinatorially as well as three other identities dealing with the polynomials A_{c,d}^{I}(t, q), A_{c,d}^{II}(t, q), A_{c,d}^{III}(t, q) by using the same MacMahon pattern (see section 4, where (1.9) is shown to be equivalent to (1.5) by means of the Cauchy identity).

Before deriving the above identities in sections 3 and 4 we find it convenient to recall the classical notations on q-series, together with the various forms of the Cauchy identity. This is the object of section 2.

Section 5 contains our second main tool, i.e., a combinatorial lemma on skew-tableaux. Let λ and μ be two fixed partitions ; the problem is to express the infinite series ∑_{s} t^{s}S_{λ}(q, …, q^{s})S_{μ}(1, q, …, q^{s}), where S_{λ} and S_{μ} are the Schur functions associated with λ and μ, as a generating function for skew-tableaux (see Lemma 5.3). Notice that the alphabets involved in the two Schur functions are not the same.

That lemma is used in Section 6 to derive another combinatorial interpretation of the polynomials A_{c,d}(t, q), first, in terms of pairs of skewtableaux, second in terms of words by a new pair of statistics (des_{k}^{∗}, maj_{k}^{∗}) (see Proposition 6.2). In the present paper two sorts of descents will be considered, the k-descents already introduced, and the k^{∗}-descents that lead to the pair (des_{k}^{∗}, maj_{k}^{∗}). The object of section 7 is to construct a bijection ψ of R(c, d) onto itself with the property that (des_{k}^{∗}, maj_{k}^{∗})(w) = (des_{k}, maj_{k})(ψ(w)) holds identically.

Now let

(a; q_{1}, q_{2})_{s_{1},s_{2}} = \{ \begin{matrix}1, & if s_{1} or s_{2} is zero ; \\ ∏_{1≤i_{1}≤s_{1}} ∏_{1≤i_{2}≤s_{2}}(1 − uq_{1}^{i_{1}−1}q_{2}^{i_{2}−1}), & if both s_{1}, s_{2} ≥ 1 ; \end{matrix}

be the bivariate extension of the q-ascending factorial. Section 8 is devoted to the combinatorial study of the following identities :

(1.10) ∑_{s_{1}≥0,s_{2}≥0} t_{1}^{s_{1}}t_{2}^{s_{2}} \frac{(−uxq_{1}q_{2}; q_{1}, q_{2})_{s_{1},s_{2}}}{(uy; q_{1}, q_{2})_{s_{1}+1,s_{2}+1}}

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

(1.11) ∑_{s_{1}≥0,s_{2}≥0} t_{1}^{s_{1}}t_{2}^{s_{2}} \frac{1}{(uxq_{1}q_{2}; q_{1}, q_{2})_{s_{1},s_{2}}(uy; q_{1}, q_{2})_{s_{1}+1,s_{2}+1}}

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

(1.12) ∑_{s_{1}≥0,s_{2}≥0} t_{1}^{s_{1}}t_{2}^{s_{2}}(−uxq_{1}q_{2}; q_{1}, q_{2})_{s_{1},s_{2}}(−uy; q_{1}, q_{2})_{s_{1}+1,s_{2}+1}

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

(1.13) ∑_{s_{1}≥0,s_{2}≥0} t_{1}^{s_{1}}t_{2}^{s_{2}} \frac{(−uy; q_{1}, q_{2})_{s_{1}+1,s_{2}+1}}{(uxq_{1}q_{2}; q_{1}, q_{2})_{s_{1},s_{2}}}

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

By means of the combinatorial Lemma 5.3 it is proved that A_{n}, A_{n}^{I}, A_{n}^{II} and A_{n}^{III} are polynomials in t_{1}, t_{2}, q_{1}, q_{2} with integral coefficients, and in fact, generating polynomials for pairs of skew-tableaux by a bivariate statistic.

The next problem is to show that those polynomials are also generating polynomials for linear structures. This is achieved by considering the coloured permutations, another way of introducing the classical signed permutations underlying the group B_{n}. The coloured permutations are counted acccording various k^{∗}-descents.

Identity (1.11) has been obtained by Reiner [18] (see also [19], [20]) in the B_{n}-signed permutation version, using a different approach.

2. Notations, q-series and symmetric functions

Besides the finite q- and (q_{1}, q_{2})-factorials introduced in the previous section we shall need the infinite extensions :

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

(a; q_{1}, q_{2})_{∞,∞} = lim_{s_{1},s_{2}}(q; q_{1}, q_{2})_{s_{1},s_{2}} = ∏_{i_{1}≥1} ∏_{i_{2}≥1}(1 − uq_{1}^{i_{1}−1}q_{2}^{i_{2}−1});

and also the q-multimonial coefficient :

\left[{c_{1} + ⋯ + c_{j} + d_{1} + ⋯ + d_{k} \atop c_{1}, …, c_{j}, d_{1}, …, d_{k}}\right] = \frac{(q; q)_{c_{1}+···+c_{j}+d_{1}+···+d_{k}}}{(q; q)_{c_{1}} … (q; q)_{c_{j}}(q; q)_{d_{1}} … (q; q)_{d_{k}}} .

Recall the q-binomial theorem (see [1, p. 15] or [9, § 1.3]) that states :

(2.1)  ∑_{n≥0} \frac{(a; q)_{n}}{(q; q)_{n}} u^{n} = \frac{(au; q)_{∞}}{(u; q)_{∞}} ,

together with the two q-exponential identities

(2.2)  exp_{q}(u) = ∑_{n≥0} \frac{u^{n}}{(q; q)_{n}} = \frac{1}{(u; q)_{∞}};

(2.3)  Exp_{q}(u) = ∑_{n≥0} \frac{q^{\binom{n}{2}}u^{n}}{(q; q)_{n}} = (−u; q)_{∞}.

The q-binomial theorem provides the two expansions (see [1, p. 15])

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

(2.5)  ∑_{n≥0} \left[{s \atop n}\right]q^{\binom{n+1}{2}}u^{n} = (−qu; q)_{s}.

Next a few notations about symmetric functions. First, h_{n}(x) and e_{n}(x) will designate the homogeneous symmetric functions and the elementary symmetric functions in the set of variables x = (x_{1}, x_{2}, …). Recall that h_{n}(x) is the sum of all the monomials of degree n in the variables taken from x. If λ = (λ_{1}, λ_{2}, …) is a partition of a positive integer, m_{λ} = m_{λ}(x) will designate the monomial symmetric function, i.e., the sum of the distinct rearrangements of the monomial x_{1}^{λ_{1}}x_{2}^{λ_{2}} … We will also adopt the usual notations : h_{λ} = h_{λ_{1}}h_{λ_{2}} … and e_{λ} = e_{λ_{1}}e_{λ_{2}} … The Schur function associated with the partition λ will be denoted by S_{λ} = S_{λ}(x) and λ′ will designate the conjugate partition to λ.

The first two identities following are straightforward ; the next four are classical (see, e.g., [13]) :

(2.6)  ∑_{n≥0} h_{n}u^{n} = ∏_{i≥1}(1 − x_{i}u)^{−1};
(2.7)  ∑_{n≥0} e_{n}u^{n} = ∏_{i≥1}(1 + x_{i}u);
(2.8)  ∑_{λ} m_{λ}(x)h_{λ}(y) = ∏_{i,j}(1 − x_{i}y_{j})^{−1};
(2.9)  ∑_{λ} m_{λ}(x)e_{λ}(y) = ∏_{i,j}(1 + x_{i}y_{j});
(2.10)  ∑_{λ} S_{λ}(x)S_{λ}(y) = ∏_{i,j}(1 − x_{i}y_{j})^{−1};
(2.11)  ∑_{λ} S_{λ}(x)S_{λ′}(y) = ∏_{i,j}(1 + x_{i}y_{j}).

Formulas (2.8) and (2.10) are the Cauchy identities ; (2.9) and (2.11) are their duals. The material on Schur functions needed in this paper will be presented in section 5.

When we specialize the variables in x or in y to be powers of a single variable q, the previous six identities are expressed in terms of q-series. For example, let x consist of (s + 1) variables x_{1}, x_{2}, …, x_{s+1} and make the substitutions x_{i} ← q^{i−1} (i = 1, 2, …, s + 1). Then (2.6) is transformed into

(2.12)  ∑_{n≥0} h_{n}(1, q, …, q^{s})u^{n} = \frac{1}{(u; q)_{s+1}} .

Now take x = (x_{1}, x_{2}, …, x_{s}) and make the substitutions x_{i} ← q^{i} (i = 1, 2, …, s). Then (2.7) is transformed into

(2.13)  ∑_{n≥0} e_{n}(q, …, q^{s})u^{n} = (−qu; q)_{s}.

By comparing (2.4) and (2.12), and then (2.5) and (2.13) we conclude that

(2.14)  h_{n}(1, q, …, q^{s}) = \left[{s + n \atop n}\right];
(2.15)  e_{n}(q, …, q^{s}) = q^{\binom{n+1}{2}}\left[{s \atop n}\right].

Now take x = (u_{1}, …, u_{j}) and y = (1, q, …, q^{s}). Then (2.8)–(2.11) yield the following identities

(2.16) ∑_{λ} m_{λ}(u_{1}, …, u_{j})h_{λ}(1, q, …, q^{s}) = \frac{1}{(u_{1}; q)_{s+1} … (u_{j}; q)_{s+1}} ;

(2.17) ∑_{μ} m_{μ}(v_{1}, …, v_{k})e_{μ}(q, …, q^{s}) = (−qv_{1}; q)_{s} … (−qv_{k}; q)_{s};

(2.18) ∑_{μ} S_{μ}(u_{1}, …, u_{j})S_{μ}(1, q, …, q^{s}) = \frac{1}{(u_{1}; q)_{s+1} … (u_{j}; q)_{s+1}} ;

(2.19) ∑_{λ} S_{λ′}(v_{1}, …, v_{k})S_{λ}(q, …, q^{s}) = (−qv_{1}; q)_{s} … (−qv_{k}; q)_{s};

In the latter four identities λ (resp. μ) ranges over partitions whose number of parts l(λ) (resp. l(μ)) is at most j (resp. k). If we multiply (2.16) by (2.17) and (2.18) by (2.19) we get :

(2.20) ∑_{λ,μ} h_{λ}(1, q, …, q^{s})e_{μ}(q, …, q^{s})m_{λ}(u_{1}, …, u_{j})m_{μ}(v_{1}, …, v_{k})

= \frac{(−qv_{1}; q)_{s} … (−qv_{k}; q)_{s}}{(u_{1}; q)_{s+1} … (u_{j}; q)_{s+1}} .

(2.21) ∑_{λ,μ} S_{λ}(q, …, q^{s})S_{μ}(1, q, …, q^{s})S_{μ}(u_{1}, …, u_{j})S_{λ′}(v_{1}, …, v_{k})

= \frac{(−qv_{1}; q)_{s} … (−qv_{k}; q)_{s}}{(u_{1}; q)_{s+1} … (u_{j}; q)_{s+1}} .

Now consider the sets of variables x = (1, q_{1}, …, q_{1}^{s_{1}}) and y = (1, q_{2}, …, q_{2}^{s_{2}}). Identities (2.10) and (2.11) become by replacing λ by μ and introducing two variables of homogeneity u, y :

(2.22) ∑_{n≥0}(uy)^{n} ∑_{|μ|=n} S_{μ}(1, q_{1}, …, q_{1}^{s_{1}})S_{μ}(1, q_{2}, …, q_{2}^{s_{2}})

= \frac{1}{(uy; q_{1}, q_{2})_{s_{1}+1,s_{2}+1}} ;

(2.23) ∑_{n≥0}(uy)^{n} ∑_{|μ|=n} S_{μ}(1, q_{1}, …, q_{1}^{s_{1}})S_{μ′}(1, q_{2}, …, q_{2}^{s_{2}})

= (−uy; q_{1}, q_{2})_{s_{1}+1,s_{2}+1}.

Let us also record identities (2.10) and (2.11) when the sets of variables are x = (q_{1}, …, q_{1}^{s_{1}}) and y = (q_{2}, …, q_{2}^{s_{2}}). This time we take x, u as variables of homogeneity and keep λ in the summation.

(2.24) ∑_{n≥0}(ux)^{n} ∑_{|λ|=n} S_{λ}(q_{1}, …, q_{1}^{s_{1}})S_{λ}(q_{2}, …, q_{2}^{s_{2}})

= \frac{1}{(uxq_{1}q_{2}; q_{1}, q_{2})_{s_{1},s_{2}}} ;

(2.25) ∑_{n≥0}(ux)^{n} ∑_{|λ|=n} S_{λ}(q_{1}, …, q_{1}^{s_{1}})S_{λ′}(q_{2}, …, q_{2}^{s_{2}})

= (−uxq_{1}q_{2}; q_{1}, q_{2})_{s_{1},s_{2}}.

3. Updating a MacMahon bijection

In this section we shall update a construction used by MacMahon [14] (see also [16]) to derive (1.9). Keep the same notations as in the introduction and consider the polynomial A_{c,d}(t, q) in its (des_{k}, maj_{k}) interpretation, i.e., A_{c,d}(t, q) = ∑_{w} t^{des_{k} w}q^{maj_{k} w} (w ∈ R(c, d)). Next let s′

be a non-negative integer, let w = x_{1}x_{2} … x_{m} be a word in R(c, d) and let b = (b_{1}, b_{2}, …, b_{m}) be a non-increasing sequence of non-negative integers satisfying s′ ≥ b_{1}.

The number des_{k} w of k-descents and the k-major index, maj_{k} w, of w can be evaluated as follows : for each i = 1, 2, …, m denote by z_{i} the number of k-descents in the right factor x_{i}x_{i+1} … x_{m} of w. Then z_{1} = des_{k} w and maj_{k} w = z_{1} + ⋯ + z_{m}.

Now consider the non-increasing word v = y_{1}y_{2} … y_{m} defined by y_{i} = b_{i} + z_{i} (1 ≤ i ≤ m) and form the biword

( \begin{matrix}v \\ w \end{matrix} ) = ( \begin{matrix}y_{1} y_{2} … y_{m} \\ x_{1} x_{2} … x_{m} \end{matrix} ) .

If we rearrange the columns of the previous matrix in such a way that the mutual orders of the columns with the same bottom entries are preserved, and the entire bottow row itself becomes non-decreasing, we get a matrix of the form :

(3.1)  ( \begin{matrix}a_{1,1} … a_{1,c_{1}} … a_{r,1} … a_{r,d_{k}} \\ 1 … 1 … r … r \end{matrix} ) .

We can also record the entries of this matrix by splitting the top row into r rows to form the following tableau

(3.2)  T = \begin{matrix}a_{1,1} & a_{1,2} & … & a_{1,c_{1}} \\ … & … & … & … \\ a_{j,1} & a_{j,2} & … & a_{2,c_{j}} \\ a_{j+1,1} & a_{j+1,2} & … & a_{j+1,d_{1}} \\ … & … & … & … \\ a_{r,1} & a_{r,2} & … & a_{r,d_{k}} \end{matrix}

Because of the method of rearranging the columns in (3.1), each row in T is a subword of the non-increasing word v = y_{1}y_{2} … y_{m} and, as such, is also non-increasing. Suppose x_{i} = x_{i′} ≥ j + 1, where i < i′. Then there is necessarily a descent within x_{i}x_{i+1} … x_{i′−1}x_{i′}. Hence z_{i} > z_{i′} and so y_{i} > y_{i′}. Consequently, each of the last k rows in T is strictly decreasing. Finally, if x_{m} is large, there is a k-descent at the end of w, so z_{m} = 1 and y_{m} = b_{m} + z_{m} ≥ 1. Therefore, the rows of T have the following form :

(3.3)  \begin{matrix}. & . & . & . & . & . & . & . & . & . & . & . & . & . & . & . & . & . & . & . & . & . & . & . & . & . & . & . & . & . & . & . & . & . & . \\ a_{i,1} ≥ a_{i,2} ≥ ⋯ ≥ a_{i,c_{i}} ≥ 0 \\ . & . & . & . & . & . & . & . & . & . & . & . & . & . & . & . & . & . & . & . & . & . & . & . & . & . & . & . & . & . & . & . & . & . & . \\ a_{j+i′,1} > a_{j+i′,2} > ⋯ > a_{j+i′,d_{i′}} ≥ 1 \\ . & . & . & . & . & . & . & . & . & . & . & . & . & . & . & . & . & . & . & . & . & . & . & . & . & . & . & . & . & . & . & . & . & . & . \end{matrix}

with i = 1, …, j and i′ = 1, …, k. Now define : s = s′ + des_{k} w, so that each entry a_{i,l} is at most equal to y_{1} = b_{1} + z_{1} = b_{1} + des_{k} w ≤ s′ +des_{k} w = s. The mapping (s′, b, w) ↦ (s, T) is clearly a bijection. The reverse bijection is easy to set up. Moreover, if we let Σ(T) = ∑_{i,l} a_{i,l} and Σ(b) = b_{1} + b_{2} + ⋯ + b_{m}, then

(3.4)  Σ(T) = Σ(b) + maj_{k} w  and  s = s′ + des_{k} w.

Now by using identity (2.4)

\frac{1}{(t; q)_{1+m}} A_{c,d}(t, q)=∑_{s′,w} \left[{m + s′ \atop m}\right]t^{s′+des_{k} w}q^{maj_{k} w} (s′ ≥ 0, w ∈ R(c, d)).

Next use the fact that \left[{m+s′ \atop m}\right] is the generating polynomial for all nonincreasing sequences b = (b_{1}, b_{2}, …, b_{m}) satisfying s′ ≥ b_{1} ≥ b_{2} ≥ ⋯ ≥ b_{n} ≥ 0 (see, e.g., [1, p. 33]), i.e.,

\left[{m + s′ \atop m}\right] = ∑_{b} q^{Σ(b)}.

Then

\frac{1}{(t; q)_{1+m}} A_{c,d}(t, q) = ∑_{(s′,b,w)} t^{s′+des_{k} w}q^{Σ(b)+maj_{k} w} = ∑_{(s,T)} t^{s}q^{Σ(T)},

summed over the pairs (s, T) using the above bijection.

Again use the fact that \left[{c_{i}+s \atop c_{i}}\right] is the generating polynomial for all nonincreasing sequences (a_{i,1}, …, a_{i,c_{i}}) satisfying s ≥ a_{i,1} ≥ ⋯ ≥ a_{i,c_{i}} ≥ 0, which is the case for each of the first j rows of T. Each of the last k rows (s ≥ a_{j+i′,1} > ⋯ > a_{j+i′,d_{i′}} ≥ 1) in T can be mapped onto a non-increasing row

(s−d_{i′} ≥ a_{j+i′,1} −d_{i′} ≥ ⋯ ≥ a_{j+i′,l} −(d_{i′} −l+1) ≥ ⋯ ≥ a_{j+i′,d_{i′}} −1 ≥ 0) in a bijective manner. Furthermore, the sum of the entries in the (j +i′)-th row can be written as

∑_{l=0}^{d_{i′}}(a_{j+i′,l} − (d_{i′} − l + 1)) + \frac{d_{i′}(d_{i′} + 1)}{2}.

Thus, the (j + i′)-th row has the generating function q^{\binom{d_{i′} +1}{2}}\left[{d_{i′} +(s−d_{i′}) \atop d_{i′}}\right]. We then get formula (1.9) with m = c + d.

Formula (1.9) is the “k-extension” of the formula found by MacMahon [15, vol. 2, p. 211] for the case k = 0 (see also [10, p. 98] and [8]).

When instead of the bijection (s′, b, w) ↦ (s, T), we only consider the bijection (b, w) ↦ T, and we follow the original pattern of MacMahon (see also [1, p. 42–45]), we get

(3.5) \frac{A_{c,d}(1, q)}{(q; q)_{m}} = ∑_{T} q^{Σ(T)} = \frac{1}{(q; q)_{c_{1}} … (q; q)_{c_{j}}} \frac{q^{\binom{d_{1}+1}{2}} … q^{\binom{d_{k}+1}{2}}}{(q; q)_{d_{1}} … (q; q)_{d_{k}}} ,

that can also be put into the form

(3.6) A_{c,d}(1, q) = \left[{c_{1} + ⋯ + c_{j} + d_{1} + ⋯ + d_{k} \atop c_{1}, …, c_{j}, d_{1}, …, d_{k}}\right]q^{\binom{d_{1}+1}{2}+···+\binom{d_{k}+1}{2}}.

We can as well multiply (3.5) by u^{c} and v^{d} and sum it using (2.2) and (2.3) to obtain

(3.7) ∑_{c,d} \frac{A_{c,d}(1, q)}{(q; q)_{c+d}}u^{c}v^{d} = \frac{(−qv_{1}; q)_{∞} … (−qv_{k}; q)_{∞}}{(u_{1}; q)_{∞} … (u_{j}; q)_{∞}}

= exp_{q}(u_{1}) … exp_{q}(u_{j}) Exp_{q}(qv_{1}) … Exp_{q}(qv_{k}).

4. The generating functions

By using (2.14) and (2.15), formula (1.9) may be rewritten

(4.1) \frac{1}{(t; q)_{1+m}} A_{c,d}(t, q)

= ∑_{s≥0} t^{s}h_{c_{1}}(1, q, …, q^{s}) … h_{c_{j}}(1, q, …, q^{s})e_{d_{1}}(q, …, q^{s}) … e_{d_{k}}(q, …, q^{s}).

But the polynomial A_{c,d}(t, q) remains the same, if any permutation is performed on the components of c or on the components of d. This is also a consequence of the invariance principle for the k-major index discussed

in our second paper [4]. Therefore, the summation ∑_{c,d} \frac{u^{c}v^{d}}{(t; q)_{1+m}} A_{c,d}(t, q) can be written as

(4.2)  ∑_{λ,μ} \frac{1}{(t; q)_{1+|λ|+|μ|}} A_{λ,μ}(t, q)m_{λ}(u_{1}, …, u_{j})m_{μ}(v_{1}, …, v_{k}),

where l(λ) ≤ j, l(μ) ≤ k and where |λ| and |μ| stand for the sums of the parts in λ and μ, respectively. But with (c, d) = (λ, μ) and the notations for h_{λ} and e_{μ} recalled just before (2.6), identity (4.1) becomes

(4.3)  \frac{1}{(t; q)_{1+|λ|+|μ|}} A_{λ,μ}(t, q) = ∑_{s≥0} t^{s}h_{λ}(1, q, …, q^{s})e_{μ}(q, …, q^{s}).

Combining (4.2) and (4.3) leads to

(4.4) ∑_{c,d} \frac{u^{c}v^{d}}{(t; q)_{1+c+d}} A_{c,d}(t, q)

= ∑_{λ,μ} ∑_{s≥0} t^{s}h_{λ}(1, q, …, q^{s})e_{μ}(q, …, q^{s})m_{λ}(u_{1}, …, u_{j})m_{μ}(v_{1}, …, v_{k})

= ∑_{s≥0} t^{s}∑_{λ} h_{λ}(1, q, …, q^{s})m_{λ}(u_{1}, …, u_{j})∑_{μ} e_{μ}(q, …, q^{s})m_{μ}(v_{1}, …, v_{k})

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

by using (2.20). This provides a new proof of identity (1.5).

Our next task is to show that (1.6), (1.7) and (1.8) define generating polynomials for rearrangement classes R(c, d) by pairs of statistics that are already implicitly defined in the construction of section 3. In that section a bijection was constructed that maps each triple (s′, b, w) with s′ an integer, b a non-increasing sequence of non-negative integers and w a word of length m, onto the pair (s, T) with s an integer and T a tableau of numbers (see (3.2)). The tableau T consisted of non-increasing rows, as shown in (3.3). Suppose instead of (3.3) one of the following conditions (I), (II), (III) holds :

(I)  \begin{matrix}. & . & . & . & . & . & . & . & . & . & . & . & . & . & . & . & . & . & . & . & . & . & . & . & . & . & . & . & . & . & . & . & . & . & . & . & . & . & . \\ s ≥ a_{i,1} ≥ a_{i,2} ≥ ⋯ ≥ a_{i,c_{i}} ≥ 0 \\ . & . & . & . & . & . & . & . & . & . & . & . & . & . & . & . & . & . & . & . & . & . & . & . & . & . & . & . & . & . & . & . & . & . & . & . & . & . & . \\ s ≥ a_{j+i′,1} ≥ a_{j+i′,2} ≥ ⋯ ≥ a_{j+i′,d_{i′}} ≥ 1 \\ . & . & . & . & . & . & . & . & . & . & . & . & . & . & . & . & . & . & . & . & . & . & . & . & . & . & . & . & . & . & . & . & . & . & . & . & . & . & . \end{matrix}

(II)  \begin{matrix}. & . & . & . & . & . & . & . & . & . & . & . & . & . & . & . & . & . & . & . & . & . & . & . & . & . & . & . & . & . & . & . & . & . & . & . & . & . & . \\ s ≥ a_{i,1} > a_{i,2} > ⋯ > a_{i,c_{i}} ≥ 0 \\ . & . & . & . & . & . & . & . & . & . & . & . & . & . & . & . & . & . & . & . & . & . & . & . & . & . & . & . & . & . & . & . & . & . & . & . & . & . & . \\ s ≥ a_{j+i′,1} > a_{j+i′,2} > ⋯ > a_{j+i′,d_{i′}} ≥ 1 \\ . & . & . & . & . & . & . & . & . & . & . & . & . & . & . & . & . & . & . & . & . & . & . & . & . & . & . & . & . & . & . & . & . & . & . & . & . & . & . \end{matrix}

(III)  \begin{matrix}. & . & . & . & . & . & . & . & . & . & . & . & . & . & . & . & . & . & . & . & . & . & . & . & . & . & . & . & . & . & . & . & . & . & . & . & . & . & . \\ s ≥ a_{i,1} > a_{i,2} > ⋯ > a_{i,c_{i}} ≥ 0 \\ . & . & . & . & . & . & . & . & . & . & . & . & . & . & . & . & . & . & . & . & . & . & . & . & . & . & . & . & . & . & . & . & . & . & . & . & . & . & . \\ s ≥ a_{j+i′,1} ≥ a_{j+i′,2} ≥ ⋯ ≥ a_{j+i′,d_{i′}} ≥ 1 \\ . & . & . & . & . & . & . & . & . & . & . & . & . & . & . & . & . & . & . & . & . & . & . & . & . & . & . & . & . & . & . & . & . & . & . & . & . & . & . \end{matrix}

As was shown in section 3, there are strict inequalities in row (j + i′) in (3.3), if and only if equalities of the form x_{l} = x_{l+1} are counted as k-descents in the word w = x_{1}x_{2} … x_{m}, whenever 1 ≤ l ≤ m − 1 and x_{l} large. Also condition a_{j+i′,d_{i′}} ≥ 1 holds, if and only if a k-descent is counted at the end of w, whenever the last letter x_{m} is large.

Accordingly, the bijection (s′, b, w) ↦ (s, T) of section 3 satisfies condition (I) (resp. (II), resp. (III)) above, if and only if (3.4) holds with des_{k} and maj_{k} replaced by des_{k}^{I} and maj_{k}^{I} (resp. des_{k}^{II} and maj_{k}^{II}, resp. des_{k}^{III} and maj_{k}^{III}), those latter statistics being defined as follows :

(4.5)_{I} the word w = x_{1}x_{2} … x_{m} has a k-descent of type I at i (1 ≤ i ≤ m), if either 1 ≤ i ≤ m − 1 and x_{i} > x_{i+1}, or i = m and x_{m} is large. Thus in case (I) only strict descents are counted within the word together with a descent at the end if the last letter is large. The number of k-descents of type I in w and the sum of all i such that i is a k-descent of type I are respectively denoted by des_{k}^{I} w and maj_{k}^{I} w.

(4.5)_{II} the word w = x_{1}x_{2} … x_{m} has a k-descent of type II at i (1 ≤ i ≤ m), if either 1 ≤ i ≤ m − 1 and x_{i} ≥ x_{i+1}, or i = m and x_{m} is large. Thus in case (II) only usual descents and equalities x_{i} = x_{i+1} are counted within the word and one descent at the end if the last letter is large. In the same manner, we define des_{k}^{II} w and maj_{k}^{II}.

(4.5)_{III} the word w = x_{1}x_{2} … x_{m} has a k-descent of type III at i (1 ≤ i ≤ m), if one of the two conditions (1), (2) holds : (1) 1 ≤ i ≤ m−1, x_{i} > x_{i+1} and x_{i} large, or x_{i} ≥ x_{i+1} and x_{i} small ; (2) i = m and x_{m} is large. Thus in case (III) strict descents are taken into account together with equalities x_{i} = x_{i+1} when x_{i} is small, with a descent at the end if the last letter is large. In the same manner, we define des_{k}^{III} and maj_{k}^{III}.

Now let

A_{c,d}^{I}(t, q) = ∑_{w} t^{des_{k}^{I} w}q^{maj_{k}^{I} w} (w ∈ R(c, d)),

with analogous definitions for A_{c,d}^{II}(t, q) and A_{c,d}^{III}(t, q). The generating functions for the rows in tableaux (I), (II) and (III) can be calculated using the method of section 3 and lead to the following formulas analogous to (1.9) :

(4.6)_{I} \frac{1}{(t; q)_{1+m}} A_{c,d}^{I}(t, q)

= ∑_{s≥0} t^{s}\left[{c_{1} + s \atop c_{1}}\right] … \left[{c_{j} + s \atop c_{j}}\right]q^{d_{1}} \left[{d_{1} + s − 1 \atop d_{1}}\right] … q^{d_{k}} \left[{d_{k} + s − 1 \atop d_{k}}\right];

(4.6)_{II} \frac{1}{(t; q)_{1+m}} A_{c,d}^{II}(t, q)

= ∑_{s≥0} t^{s}q^{\binom{c_{1}}{2}}\left[{s + 1 \atop c_{1}}\right] … q^{\binom{c_{j}}{2}}\left[{s + 1 \atop c_{j}}\right]q^{\binom{d_{1}+1}{2}}\left[{s \atop d_{1}}\right] … q^{\binom{d_{k}+1}{2}}\left[{s \atop d_{k}}\right];

(4.6)_{III} \frac{1}{(t; q)_{1+m}} A_{c,d}^{III}(t, q)

= ∑_{s≥0} t^{s}q^{\binom{c_{1}}{2}}\left[{s + 1 \atop c_{1}}\right] … q^{\binom{c_{j}}{2}}\left[{s + 1 \atop c_{j}}\right]q^{d_{1}} \left[{d_{1} + s − 1 \atop d_{1}}\right] … q^{d_{k}} \left[{d_{k} + s − 1 \atop d_{k}}\right].

Now, using the methods of the beginning of this section, it is easy to prove that identities (1.6), (1.7) and (1.8) hold with the above interpretations for the polynomials A_{c,d}^{I}(t, q), A_{c,d}^{II}(t, q), A_{c,d}^{III}(t, q), respectively.

Remark 1. As was shown in (3.7) for A_{c,d}(1, q), we can also verify that the polynomials A_{c,d}^{I}(1, q), A_{c,d}^{II}(1, q), A_{c,d}^{III}(1, q), in the single variable q,

are products of the q-multinomial number \left[{m \atop c_{1}, …, c_{j}, d_{1}, …, d_{k}}\right] by a certain power of q.

Remark 2. When q = 1, identities (1.6), (1.7) and (1.8) reduce to identities that can also be derived from the MacMahon Master Theorem by using the equidistribution property for “des” and “exc” (see our fourth paper [5]). For an arbitrary q the MacMahon Master Theorem was no longer available, and there was a need for another combinatorial set-up, that was provided by the very construction developed in this section.

Remark 3. Notice that when the word w is a permutation (i.e., a word without repetitions of letters), there are equivalences between the four definitions of k-descent : only the strict descents are counted within the permutation, plus a descent at the end, if the last letter is large. Accordingly the four polynomials A_{c,d}(t, q), A_{c,d}^{I}(t, q), A_{c,d}^{II}(t, q), A_{c,d}^{III}(t, q) must be equal when (c, d) = (1^{j}, 1^{k}). It is true indeed and the four formulas (1.9), (4.6)_{I}, (4.6)_{II} and (4.6)_{III} all reduce to

(4.7)  \frac{1}{(t; q)_{1+j+k}} A_{1^{j},1^{k}}(t, q) = ∑_{s≥0} t^{s}[s + 1]_{q}^{j}q^{k}[s]_{q}^{k},

where [s]_{q} stands for the polynomial 1 + q + ⋯ + q^{s−1}. Identity (4.7) has also been derived in our second paper [5, § 8] by another method.

5. A combinatorial lemma on skew tableaux

The purpose of this section is to prove that if λ and μ are two partitions, the sum ∑_{s≥0} t^{s}S_{λ}(q, …, q^{s})S_{μ}(1, q, …, q^{s}) can be expressed as a rational

fraction (1/(t; q)_{|λ|+|μ|+1})P (λ, μ), where P (λ, μ) is a polynomial in t, q that is also the generating function for some specific tableaux. Before stating this result in its full extent, a few basic notions on partitions and tableaux are to be recalled.

First, the Ferrers diagram associated with a partition λ = (λ_{1}, …, λ_{p}) (λ_{p} ≥ 1) of an integer n is the set of all pairs (i, j) in the Euclidean plane satisfying 1 ≤ i ≤ λ_{j}, 1 ≤ j ≤ p. It is convenient to identify each partition with its Ferrers diagram.

Let ν and θ be two Ferrers diagrams. If ν ⊃ θ, the set-difference ν \ θ, commonly denoted by ν/θ, is called a skew-diagram. We will be mainly concerned with skew-diagrams of the following form : let λ = (λ_{1}, …, λ_{p}) and μ = (μ_{1}, …, μ_{r}) be any two Ferrers diagrams ; then λ ⊗ μ will denote the skew diagram made of all pairs (λ_{1} + i, j) (1 ≤ i ≤ μ_{j}; 1 ≤ j ≤ r) and (i, r + j) (1 ≤ i ≤ λ_{j}; 1 ≤ j ≤ p). In other words, λ ⊗ μ is obtained by placing the Ferrers diagram λ above and to the left of the Ferrers diagram μ. For instance, with λ = (3, 2) and μ = (3, 1), the skew-diagram λ ⊗ μ has the following shape :

\begin{aligned}× & × \\ × & × & × \\ & & & × \\ & & & × & × & × \end{aligned}

Let the skew-diagram ν/θ have n points. Then a standard tableau T of shape ν/θ is defined to be a display of the n integers 1, 2, …, n on the n points of ν/θ, in such a way that the entries are increasing in each row from left to right and in each column from bottom to top.

For instance,

(5.1)  T = 6 8 4 5 9 3 1 2 7

is a standard tableau of shape λ ⊗ μ = (3, 2) ⊗ (3, 1).

The inverse ligne of route, iligne T, of a standard tableau T is defined as the the set of all integers i such that 1 ≤ i ≤ n − 1 and (i + 1) is located higher than i on T. Next, let

ides T = # iligne T; imaj T = ∑_{i} i (i ∈ iligne T).

With the previous example, we get iligne T = {2, 3, 5, 7}, so that ides T = 4 and imaj T = 2 + 3 + 5 + 7 = 17.

Next recall the notion of semi-standard tableau (or column-strict tableau). Start with a skew-diagram ν/θ with n points and place n positive integers, not necessarily distinct, on those n points, in such a way that the entries are non-increasing in each row (from left to right), but strictly decreasing in each column (from bottom to top). In the usual definition (see, e.g., [13, p. 42-43]) “non-increasing” and “strictly decreasing” are replaced by “non-decreasing” and “strictly increasing.” The ordering convention introduced here will be used only in this section. The display thereby obtained is called a semi-standard tableau of shape ν/θ.

For instance,

(5.2)  τ = 2 1 3 3 1 5 8 6 2

is such a tableau of shape λ ⊗ μ = (3, 2) ⊗ (3, 1).

With each semi-standard tableau τ of shape ν/θ is associated a total order on the points of the diagram ν/θ, if we make the convention that the point (i, j) occurs before (i′, j′), if the integer τ(i, j) written on the point (i, j) is greater than τ(i′, j′), or when τ(i, j) = τ(i′, j′), if (i, j) is to the left of (i′, j′), i.e., if i < i′. Now write k on the point (i, j) in ν/θ, if (i, j) is the k-th greatest element with respect to this total order. What we obtain is a standard tableau T, of shape ν/θ. Reading the entries of the semi-standard tableau τ in increasing order (according to that order) yields a non-increasing sequence

(5.3)  c(τ) = (c_{1}(τ), c_{2}(τ), …, c_{n}(τ)).

On the other hand, we have the property :

(5.4)  k ∈ iligne T ⟹ c_{k}(τ) > c_{k+1}(τ).

Next define d(τ) = (d_{1}(τ), d_{2}(τ), …, d_{n}(τ)) by

(5.5) d_{k}(τ) = \{ \begin{matrix}c_{k}(τ) − c_{k+1}(τ), & if k ∉ iligne T and k ≤ n − 1 ; \\ c_{k}(τ) − c_{k+1}(τ) − 1, & if k ∈ iligne T ; \\ c_{n}(τ) − 1, & if k = n; \end{matrix}

and let (5.6) φ(τ) = T.

Working again with the previous example (5.2) we see that the standard tableau φ(τ) associated with τ is the tableau T displayed in (5.1). Furthermore, c(τ) = (8, 6, 5, 3, 3, 2, 2, 1, 1) and d(τ) = (2, 0, 1, 0, 0, 0, 0, 0, 0).

The following result is proved in [13, p. 49]. Actually, it was stated for Ferrers diagrams only, but it holds for skew-diagrams as well.

Proposition 5.1. Let ν/θ be a skew-diagram with n points. Then the mapping

τ ↦ (φ(τ), d(τ))

is a bijection of the the set of all semi-standard tableaux of shape ν/θ onto the set of all pairs (T, d), where T is a standard tableau of shape ν/θ and d is a sequence of n non-negative integers.

It also follows from (5.5) that

(5.7)  ∑_{k=1}^{n} d_{k}(τ) = c_{1}(τ) − 1 − ides φ(τ);

(5.8)  ∑_{k=1}^{n} kd_{k}(τ) = ∑_{k=1}^{n} c_{k}(τ) − n − imaj φ(τ).

Finally, recall the combinatorial interpretation of skew Schur functions. Let τ be a semi-standard tableau of shape ν/θ and let c(τ) = (c_{1}(τ), …, c_{n}(τ)) be the non-increasing sequence of its entries, as defined in (5.3). Then put

(5.9)  x(τ) = ∏_{1≤k≤n} x_{c_{k}(τ)}.

For instance, with the semi-standard tableau shown in (2.2) we get x(τ) = x_{8}x_{6}x_{5}x_{3}^{2}x_{2}^{2}x_{1}^{2}.

Then we have (see [13, p. 42])

(5.10)  S_{ν/θ}(x_{1}, x_{2}, …) = ∑_{τ} x(τ),

where the summation is over all semi-standard tableaux τ of shape ν/θ [in abridged form : |τ| = ν/θ.]

It will also be convenient to have a notation for the substitution x_{i} ← q^{i−1} (i = 1, 2, …). If a = a(x_{1}, x_{2}, …) is a polynomial in the variables x_{1}, x_{2}, …, then let

(5.11)  a |x_{i} ← q^{i−1}

be the polynomial in q, where each variable x_{i} has been replaced by q^{i−1} (i = 1, 2, …). The next corollary already appeared in [6, theorem 4.1], (see also [21]). Here we give a detailed proof, as a further property on the maximum entry in each skew-tableau is needed in the sequel.

Corollary 5.2. Let ν/θ be a skew-diagram with n points and let T be a standard tableau of shape ν/θ. Then the following identity holds :

(5.12)  ∑_{s≥0} t^{s} ∑_{τ} x(τ) |x_{i} ← q^{i−1}= t^{ides T} q^{imaj T} \frac{1}{(t; q)_{n+1}} ,

where the second summation is over all semi-standard tableaux τ such that φ(τ) = T (according to (5.6)), and the maximum entry c_{1}(τ) in τ is at most (s + 1).

Proof. First

x(τ) |x_{i} ← q^{i−1} = q^{(c_{1}(τ)+···+c_{n}(τ))−n}  [by (5.9)];
= q^{imaj φ(τ)+(1.d_{1}(τ)+···+nd_{n}(τ))} [by (5.8)].

By (5.7) the restriction c_{1}(τ) ≤ s + 1 can be rewritten as d_{1}(τ) + ⋯ + d_{n}(τ) ≤ s − ides T. Hence, by using the bijection of Proposition 5.1, we have

∑_{s≥0} t^{s} ∑_{τ} x(τ) |x_{i} ← q^{i−1}= q^{imaj T} ∑_{s} t^{s} ∑_{d} q^{1.d_{1}+···+nd_{n}},

where the last summation is over all sequences d = (d_{1}, …, d_{n}) of nonnegative integers such that d_{1} + ⋯ + d_{n} ≤ s − ides T. Thus

∑_{s≥0} t^{s} ∑_{τ} x(τ) |x_{i} ← q^{i−1} = q^{imaj T} t^{ides T} ∑_{s≥ides T} t^{s−ides T} ∑_{d} q^{1.d_{1}+···+nd_{n}}

= q^{imaj T} t^{ides T} ∑_{j≥0} t^{j} ∑_{{d=(d_{1},...,d_{n}) \atop d_{1}+···+d_{n}≤j}} q^{1.d_{1}+···+nd_{n}}

= q^{imaj T} t^{ides T} ∑_{j≥0} t^{j} ∑_{{(d_{0},d_{1},...,d_{n}) \atop d_{0}+d_{1}+···+d_{n}=j}} q^{0.d_{0}+1.d_{1}+···+nd_{n}}

= q^{imaj T} t^{ides T} ∑_{(d_{0},...,d_{n})} t^{d_{0}+···+d_{n}}q^{0.d_{0}+1.d_{1}+···+nd_{n}}

= q^{imaj T} t^{ides T} \frac{1}{(t; q)_{n+1}} .

In the sequel, a standard tableau of shape λ ⊗ μ will be denoted by T ⊗ U, where T and U are the subtableaux of shape λ and μ, respectively. In general, T and U are not standard, but contain distinct entries. If |λ|+|μ| = n, the set of all the entries in T and U are the integers 1, 2, …, n. In particular, the entry 1 occurs either in tableau T, or in U. Write 1 ∈ T or 1 ∈ U to express this occurrence. With each standard tableau T ⊗ U of shape λ ⊗ μ is associated a monomial F (T ⊗ U) defined by :

(5.13)  F (T ⊗ U) = \{ \begin{matrix}q^{|λ|} t^{1+ides T ⊗U}q^{imaj T ⊗U}, & if 1 ∈ T ; \\ q^{|λ|} t^{ides T ⊗U}q^{imaj T ⊗U}, & if 1 ∈ U. \end{matrix}

We are now ready to state our combinatorial lemma.

Lemma 5.3. The following identity holds

(5.14) ∑_{s} t^{s}S_{λ}(q, …, q^{s})S_{μ}(1, q, …, q^{s})

= \frac{1}{(t; q)_{|λ|+|μ|+1}} ∑_{|T ⊗U|=λ⊗μ} F (T ⊗ U),

where the last summation is over all standard tableaux T ⊗ U of shape λ ⊗ μ.

Proof. It follows from (5.9), (5.10) and (5.11) that

\begin{aligned}S_{λ}(q, …, q^{s})S_{μ}(1, q, …, q^{s}) & = q^{|λ|}S_{λ}(1, q, …, q^{s−1})S_{μ}(1, q, …, q^{s}) \\ & = q^{|λ|} ∑_{τ,υ} x(τ)x(υ) |x_{i} ← q^{i−1}, \end{aligned}

where |τ| = λ, c_{1}(τ) ≤ s, |υ| = μ and c_{1}(υ) ≤ s + 1, because the Schur functions S_{λ} and S_{μ} involve s and (s + 1) variables, respectively.

Now examine the pairs of tableaux (τ, υ) occurring in the last summation. Place τ above and to the left of υ to obtain a skew tableau τ ⊗ υ of shape λ ⊗ μ. The last summation is then made over all tableaux τ ⊗ υ of shape λ ⊗ μ, having their entries at most equal to (s + 1), with the further restriction that the maximum entry in τ is at most s, i.e.,

S_{λ}(q, …, q^{s})S_{μ}(1, q, …, q^{s}) = q^{|λ|} ∑_{τ⊗υ} x(τ ⊗ υ) |x_{i} ← q^{i−1},

with |τ ⊗ υ| = λ ⊗ μ, c_{1}(τ ⊗ υ) ≤ s + 1, c_{1}(τ) ≤ s. Now examine the effect of the last two restrictions on the bijection derived in Proposition 5.1, a bijection that will be rewritten as

τ ⊗ υ ↦ (φ(τ ⊗ υ), d(τ ⊗ υ)).

The standard tableau T ⊗ U = φ(τ ⊗ υ) has one of the following two forms :

1 λ  Tμ  U (case I)  1 λ  Tμ  U (case II)

Fig. 1

Remember that to obtain the standard tableau T ⊗ U = φ(τ ⊗ υ), we have to label the greatest elements of τ ⊗ υ first and, if there are several of those, the highest point gets the least label. Therefore, in case I the restriction c_{1}(τ ⊗ υ) ≤ s + 1 implies the restriction c_{1}(τ) ≤ s. In case II we must impose c_{1}(τ ⊗ υ) ≤ s. Therefore

∑_{s} t^{s}S_{λ}(q, …, q^{s})S_{μ}(1, q, …, q^{s})

= q^{|λ|} ∑_{s} t^{s} ∑_{(case I)}x(τ ⊗υ) |x_{i} ← q^{i−1} +q^{|λ|} ∑_{s} t^{s} ∑_{(case II)}x(τ ⊗υ) |x_{i} ← q^{i−1}.

Now ∑_{s} t^{s} ∑_{(case I)} = ∑_{T ⊗U} ∑_{s} t^{s} ∑ x(τ ⊗ υ) |x_{i} ← q^{i−1}, where the first

summation on the right-hand side is over all standard tableaux T ⊗ U of shape λ ⊗ μ such that 1 ∈ U, and the third one over all semi-standard tableaux τ ⊗ υ such that φ(τ ⊗ υ) = T ⊗ U and c_{1}(τ ⊗ υ) ≤ s + 1. By (5.12) we then have

(5.15)  ∑_{s} t^{s} ∑_{(case I)} = ∑_{{|T ⊗U|=λ⊗μ \atop 1∈U}} t^{ides T ⊗U}q^{imaj T ⊗U} \frac{1}{(t; q)_{n+1}} .

Next ∑_{s} t^{s} ∑_{(case II)} = ∑_{|T ⊗U|=λ⊗μ, 1∈T} ∑_{s} t^{s} ∑ x(τ ⊗υ) |x_{i} ← q^{i−1}, where the

last summation is over semi-standard tableaux τ ⊗ υ satisfying φ(τ ⊗ υ) = T ⊗ U and c_{1}(τ ⊗ υ) ≤ s. Therefore,

∑_{s} t^{s} ∑_{(case II)} = t ∑_{T ⊗U} ∑_{s} t^{s−1} ∑_{c_{1}(τ⊗υ)≤(s−1)+1} x(τ ⊗ υ) |x_{i} ← q^{i−1}

(5.16) = t ∑_{{|T ⊗U|=λ⊗μ \atop 1∈T}} t^{ides T ⊗U}q^{imaj T ⊗U} \frac{1}{(t; q)_{n+1}} ,

by Corollary 5.2. The sum of (5.15) and (5.16) yields identity (5.14).

6. Tableaux and lignes of route

In this section we use Lemma 5.3 and the algebra of tableaux to derive another combinatorial interpretation of the polynomials A_{c,d}(t, q). Start with the series

A := ∑_{s} t^{s} \frac{(−qv_{1}; q)_{s} … (−qv_{k}; q)_{s}}{(u_{1}; q)_{s+1} … (u_{j}; q)_{s+1}} ,

which was shown in (4.4) to be the generating function for those polynomials and express it in terms of Schur functions. This can be done by multiplying (2.21) by t^{s} and summing over s, as we get :

A = ∑_{λ,μ} S_{μ}(u_{1}, …, u_{j})S_{λ′}(v_{1}, …, v_{k}) ∑_{s} t^{s}S_{λ}(q, …, q^{s})S_{μ}(1, q, …, q^{s}).

Hence, by Lemma 5.3

A = ∑_{λ,μ} \frac{1}{(t; q)_{|λ|+|μ|+1}} S_{μ}(u_{1}, …, u_{j})S_{λ′}(v_{1}, …, v_{k}) ∑_{|T ⊗U|=λ⊗μ} F (T ⊗ U).

Now use the combinatorial definition of Schur functions (see (5.10)) :

S_{μ}(u_{1}, …, u_{j}) = ∑_{{(c_{1},...,c_{j}) \atop c_{1}+···+c_{j}=|μ|}} u_{1}^{c_{1}} … u_{j}^{c_{j}} ∑_{{|V |=μ \atop Cont V =1^{c_{1}} ...j^{c_{j}}}} 1,

where the last summation is over all semi-standard tableaux V of shape μ, whose content, Cont V, consists of c_{1} 1’s, …, c_{j} j’s. (This time, it is convenient to use the traditional convention for the ordering of the entries in the semi-standard tableaux.) Actually, the last summation is the Kostka number K_{μ,c}, which is symmetric in c. In the same manner,

S_{λ′}(v_{1}, …, v_{k}) = ∑_{{(d_{1},...,d_{k}) \atop d_{1}+···+d_{k}=|λ′|}} v_{1}^{d_{1}} … v_{k}^{d_{k}} ∑_{{|W |=λ′ \atop Cont W =(j+1)^{d_{1}} ...r^{d_{k}}}} 1.

Altogether

A = ∑_{c,d} \frac{1}{(t; q)_{c+d+1}} ∑_{{λ,μ \atop |λ|=c,|μ|=d}} ∑_{{(c_{1},...,c_{j}) \atop c_{1}+···+c_{j}=c}}u_{1}^{c_{1}} … u_{j}^{c_{j}} ∑_{{(d_{1},...,d_{k}) \atop d_{1}+···+d_{k}=d}}v_{1}^{d_{1}} … v_{k}^{d_{k}}

× ∑_{(V,W,T ⊗U)} F (T ⊗ U),

where (V, W, T ⊗U) ranges over all triplets having the following property :

(6.1) V (resp. W) is a semi-standard tableau of shape μ (resp. λ′) with content Cont V = 1^{c_{1}} … j^{c_{j}} (resp. Cont W = (j + 1)^{d_{1}} … r^{d_{k}}) and where T ⊗ U is a standard tableau of shape λ ⊗ μ. (See Fig. 2.)

V μ  λ′  W  λ  T  μ  U

Fig. 2

Thus

A = ∑_{c,d} \frac{1}{(t; q)_{c+d+1}} ∑_{{c,d \atop |c|=c, |d|=d}} u^{c}v^{d} ∑_{{λ,μ \atop |λ|=|c|, |μ|=|d|}} ∑_{(V,W,T ⊗U)} F (T ⊗ U)

= ∑_{c,d} \frac{1}{(t; q)_{|c|+|d|+1}} u^{c}v^{d} ∑_{{λ,μ \atop |λ|=|c|, |μ|=|d|}} ∑_{(V,W,T ⊗U)} F (T ⊗ U).

If we compare the latter expression with the left-hand side of (4.4) we obtain the following interpretation for the polynomials A_{c,d}(t, q).

Proposition 6.1. For each pair (c, d) the following identity holds

(6.2)  A_{c,d}(t, q) = ∑_{{λ,μ \atop |λ|=|c|, |μ|=|d|}} ∑_{{(V,W,T ⊗U) \atop (6.1)}} F (T ⊗ U).

The next step is to carry the information contained in (6.2) from tableaux to words and express A_{c,d}(t, q) as a generating polynomial for the rearrangement class R(c, d). Again use the notations c = |c| = c_{1}+⋯+c_{j}, d = |d| = d_{1} + ⋯ + d_{k} and c + d = m. Let w = x_{1}x_{2} … x_{m} be a word in that class written as a biword

w = ( \begin{matrix}1 & 2 & … & j & j + 1 & … & m \\ x_{1} & x_{2} & … & x_{j} & x_{j+1} & … & x_{m} \end{matrix} ) .

Let (i_{1}, …, i_{c}) (resp. (j_{1}, …, j_{d})) be the increasing sequence of all i such that x_{i} is small (resp. large). Next form the following two subwords of w :

a = ( \begin{matrix}i_{1} & … & i_{c} \\ x_{i_{1}} & … & x_{i_{j}} \end{matrix} ) b = ( \begin{matrix}l_{1} & … & l_{d} \\ x_{l_{1}} & … & x_{l_{k}} \end{matrix} )

and rearrange the columns of a in such a way that the bottom row is nondecreasing and if two consecutive letters in the bottom row are equal, their corresponding top letters are in increasing order. Then a is transformed into a biword denoted by a′.

Next permute the columns of b in such a way that the bottom row is non-increasing, and if two consecutive letters in the bottom row are equal, their corresponding top letters are in decreasing order. Call b′ the resulting biword.

Finally, form the juxtaposition product of the top row of b′ followed by the top row of a′, to get a word denoted by z(w) = z_{1}z_{2} … z_{m} (which is a certain permutation of 1, 2, …, m). The word z(w) has a certain inverse ligne of route, iligne z(w), defined as the set of all i such that 1 ≤ i ≤ m−1 and (i + 1) is to the left of i in z_{1}z_{2} … z_{m}.

As for tableaux, define

ides z(w) = # iligne z(w); imaj z(w) = ∑_{i} i (i ∈ iligne z(w)).

For each word w = x_{1}x_{2} … x_{m} ∈ R(c, d) define

(6.3)  f(w) = \{ \begin{matrix}q^{d} t^{1+ides z(w)}q^{imaj z(w)}, & if x_{1} is large ; \\ q^{d} t^{ides z(w)}q^{imaj z(w)}, & if x_{1} is small. \end{matrix}

Proposition 6.2. For each pair (c, d) the following identity holds

(6.4)  A_{c,d}(t, q) = ∑_{w} f(w)  (w ∈ R(c, d)).

The proof of Proposition 6.2 consists of constructing a bijection

(6.5)  w ↦ (λ, μ, V, W, T ⊗ U)

of R(c, d) onto the set of all quintuplets (λ, μ, V, W, T ⊗ U), where λ and μ are two partitions satisfying |λ| = c, |μ| = d and where the triplet (V, W, T ⊗ U) satisfies (6.1) such that f(w) = F (T ⊗ U) holds.

Such a bijection is constructed by means of the Robinson-Schensted correspondence for words with repetitions (see [11] for an exposé on the subject, see also [8] for an analogous construction). We proceed as follows : under the Robinson-Schensted correspondence, the two biwords a and b are mapped onto two pairs of tableaux (V, U), (W, T′), respectively, where

(i) T′ and U are two tableaux with content Cont T′ = {l_{1}, …, l_{d}} and Cont U = {i_{1}, …, i_{c}}, respectively ; let λ′ and μ denote their shapes ;

(ii) V (resp. W) is a semi-standard tableau of shape μ (resp. λ′) with content Cont V = 1^{c_{1}} … j^{c_{j}} (resp. Cont W = (j + 1)^{d_{1}} … r^{d_{k}}).

Let top a′ and top b′ denote the top rows of the biwords a′ and b′. It also follows from the classical properties of that correspondence (see, e.g., [6]) that iligne top b′ = iligne T and iligne top a′ = iligne U. Let T be the transpose of T′ (then of shape λ).

If we form the skew-tableau T ⊗ U, the set of all i such that i occurs in U and (i + 1) occurs in T is identical with the set of the i occurring in top a′ while (i + 1) is a letter of top b′. In other words,

(6.6)  iligne T ⊗ U = iligne(top(b′) top(a′)) = iligne z(w).

Also, 1 ∈ T (i.e., 1 ∈ Cont T) iff l_{1} = 1 and so x_{1} is large. Hence, the two values F (T ⊗ U) (given in (5.13)) and f(w) (given in (6.3)) coincide. Finally, the quintuple associated with w is (λ, μ, V, W, T ⊗ U). This bijection has the desired properties.

The statistic “f” can also be given a definition in terms of so-called k^{∗}- descents introduced as follows. Let w = x_{1}x_{2} … x_{m} be a word in R(c, d) ; an integer i is said to be a k^{∗}-descent of w, if 1 ≤ i ≤ m − 1 and if one of the following conditions holds :

(i) x_{i}, x_{i+1} small and x_{i} > x_{i+1} ; (ii) x_{i}, x_{i+1} large and x_{i} ≤ x_{i+1} ; (iii) x_{i} small and x_{i+1} large. Let des_{k}^{∗} w be the number of k^{∗}-descents of w, if x_{1} is small, and one

plus that number, if x_{1} is large. Also let maj_{k}^{∗} w be the sum of all i’s such that i is a k^{∗}-descent, plus d (the number of large letters in w). Then

(6.7)  f(w) = t^{des_{k}^{∗} w}q^{maj_{k}^{∗} w}.

The proof of (6.7) is immediate.

Example. Consider the biword

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

and suppose that 1, 2, 3 are small, while 4, 5 and 6 are large, so that d = 7. The k^{∗}-descents of w are printed in bold-face. Accordingly, des_{k}^{∗} w = 7 and maj_{k}^{∗} w = 1 + 2 + 3 + 6 + 7 + 9 + 11 + d = 46. The biwords a, b, a′, b′ read

a = ( \begin{matrix}1 2 5 6 7 11 \\ 3 1 2 2 1 3 \end{matrix} ); b = ( \begin{matrix}3 4 8 9 10 12 13 \\ 5 5 5 4 6 6 4 \end{matrix} );

a′ = ( \begin{matrix}2 7 5 6 1 11 \\ 1 1 2 2 3 3 \end{matrix} ); b′ = ( \begin{matrix}12 10 8 4 3 13 9 \\ 6 6 5 5 5 4 4 \end{matrix} );

and the word z(w)

z(w) = 12, 10, 8, 4, 3, 13, 9; 2, 7, 5, 6, 1, 11.

The letters belonging to iligne z(w) are printed in bold-face and correspond to the k^{∗}-descents of w.

Under the Robinson-Schensted correspondence

a ↦ (V, U) = 3 2 1 1 2 3 , 7 2 1 5 6 11 ; b ↦ (W, T′) = 5 5 4 4 5 6 6 , 9 13 3 4 8 10 12 ; and the skew-tableau T ⊗ U is

T ⊗ U = 12 10 8 4 13 3 9 7 2 1 5 6 11

Both z(w) and T ⊗ U have the same inverse ligne of route. Moreover, 1 ∈ U and “3” the first letter of w is small. Therefore, F (T ⊗ U) and f(w) coincide, equal to q^{7}t^{7}q^{1+2+3+6+7+9+11} = t^{7}q^{46}.

7. The two bivariate statistics

Proposition 6.2 with the definition of “f” given in (6.7) says that the pairs (des_{k}^{∗}, maj_{k}^{∗}) and (des_{k}, maj_{k}) are equidistributed on each rearrangement class R(c, d). The next problem arises : can we prove the result directly, i.e., construct a bijection ψ of R(c, d) onto itself with the property that

(7.1)  (des_{k}^{∗}, maj_{k}^{∗}) w = (des_{k}, maj_{k}) ψ(w)

holds identically. The purpose of this section to derive such a bijection. Each word w ∈ R(c, d) factorizes into a product

(7.2)  w = u_{1}v_{1}u_{2}v_{2} … u_{h}v_{h}u_{h+1}

(u_{1} and u_{h+1} possibly empty), where each u_{l} (resp. v_{l}) has small (resp. large) letters only. In each factor v_{l} replace each (large) letter x_{i} by its complement within the interval [j + 1, r], i.e., x_{i} ← r + j + 1 − x_{i}. Then each word v_{l} is transformed into a word denoted by v_{l}^{c} still having large letters. Next define :

(7.3)  w^{∗} = u_{1}v_{1}^{c}u_{2}v_{2}^{c} … u_{h}v_{h}^{c}u_{h+1}.

Also denote by d̃ the mirror-image d̃ = (d_{k}, …, d_{1}) of d.

Proposition 7.1. The mapping w ↦ w^{∗} is a bijection of R(c, d) onto R(c, d̃) satisfying

(7.4)  (des_{k}^{∗}, maj_{k}^{∗}) w = (des_{k}, maj_{k}) w^{∗}.

Proof. The transformation w ↦ w^{∗} is clearly bijective. Now examine how the three cases (i), (ii), (iii) considered just before (6.7) are modified by the transformation :

(i) is untouched ; (ii) j+1 ≤ x_{i} ≤ x_{i+1} is transformed into the k-descent (r+j+1)−x_{i} ≥

(r + j + 1) − x_{i+1} in w^{∗};

(iii) the integers i in this case are the lengths of the factors u_{1}, u_{1}v_{1}u_{2}, u_{1}v_{1}u_{2}v_{2}u_{3}, …, u_{1}v_{2}u_{2}v_{2} … u_{h}. There are then h of those integers, except if u_{1} is empty. In the latter case however the first letter x_{1} of w is large and according to (6.7) an extra descent is counted in des_{k}^{∗} w.

On the other hand, the k-descents in w^{∗} that have not been taken into account in (i) and (ii) are the lengths of the factors u_{1}v_{1}^{c}, u_{1}v_{1}^{c}u_{2}v_{2}^{c}, …, u_{1}v_{1}^{c}u_{2} … v_{h}^{c}. Note that the fact that u_{h+1} may be empty is irrelevant for the counting of the k-descents. There are then exactly h of those k-descents in w^{∗}.

This proves the result about descents. Now

maj_{k}^{∗} w = ∑_{cases (i),(ii)} i + |u_{1}| + |u_{1}v_{1}u_{2}| + ⋯ + |u_{1}v_{2}u_{2}v_{2} … u_{h}| + d

and

maj_{k} w^{∗} = ∑_{cases (i),(ii)} i + |u_{1}v_{1}^{c}| + |u_{1}v_{1}^{c}u_{2}v_{2}^{c}| + ⋯ + |u_{1}v_{1}^{c}u_{2} … v_{h}^{c}| .

The difference maj_{k}^{∗} w − maj_{k} w^{∗} is equal to d − (|v_{1}^{c}| + |v_{2}^{c}| + ⋯ + |v_{h}^{c}|), which is zero.

Now from the invariance principle discussed in our second paper on (des_{k}, maj_{k}) there is a bijection μ of R(c, d̃) onto R(c, d) such that (des_{k}, maj_{k})(w) = (des_{k}, maj_{k})(μ(w)). Hence, the bijection w ↦ μ(w^{∗}) is a bijection of R(c, d) onto itself that satisfies (7.1).

Example. As in section 6 let w = 3, 1, 5, 5, 2, 2, 1, 5, 4, 6, 3, 6, 4 with 1, 2, 3 small and 4, 5, 6 large, so that d = (2, 3, 2) and d̃ = (2, 3, 2). In the following display the k^{∗}-descents of w are shown on the first row and the k-descents of w^{∗} on the fourth row.

k^{∗}-descents :

w =
w^{∗} =

k-descents :

\begin{matrix}1 & 2 \\ 3 & 1 \\ 3 & 1 \\ 1 & . \end{matrix} | \begin{matrix}3 & . \\ 5 & 5 \\ 5 & 5 \\ 3 & 4 \end{matrix} | \begin{matrix}. & 6 & 7 \\ 2 & 2 & 1 \\ 2 & 2 & 1 \\ . & 6 & . \end{matrix} | \begin{matrix}. & 9 & . \\ 5 & 4 & 6 \\ 5 & 6 & 4 \\ . & 9 & 10 \end{matrix} | \begin{matrix}11 \\ 3 \\ 3 \\ . \end{matrix} |

\begin{matrix}. & . \\ 6 & 4 \\ 4 & 6 \\ . & 13 \end{matrix}

∈ R(c, d) ∈ R(c, d̃)

Thus

des_{k}^{∗} w = des_{k} w^{∗} = 7 ; maj_{k}^{∗} w = 1 + 2 + 3 + 6 + 7 + 9 + 11 + 7 = 46 ;
maj_{k} w^{∗} = 1 + 3 + 4 + 6 + 9 + 10 + 13 = 46.

Remark. We can also define k^{∗}-descents of type I, II and III corresponding to the k-descents introduced in (4.5)_{I}, (4.5)_{II} and (4.5)_{III} and construct three bijections satisfying properties analogous to (7.4). We do not reproduce those constructions.

8. Six-variable statistics

The combinatorial lemma 5.3 has been used in section 6 to derive a result on the distribution on words. We can as well use the same combinatorial lemma to obtain an analogous result for permutations. This time a joint study of order statistics on the permutation and its inverse is possible.

First, let us verify that the coefficients A_{n}, A_{n}^{I}, A_{n}^{II} and A_{n}^{III} occurring in identities (1.10)–(1.13) are polynomials in t_{1}, t_{2}, q_{1}, q_{2} with integral coefficients. We only give the proof for (1.10), the other proofs being completely analogous. By multiplying (2.22) by (2.25) we get :

∑_{n≥0} u^{n} ∑_{{λ,μ \atop |λ|+|μ|=n}} x^{|λ|}y^{|μ|}S_{λ}(q_{1}, …, q_{1}^{s_{1}})S_{μ}(1, q_{1}, …, q_{1}^{s_{1}})

× S_{λ′}(q_{2}, …, q_{2}^{s_{2}})S_{μ}(1, q_{2}, …, q_{2}^{s_{2}})

= \frac{(−uxq_{1}q_{2}; q_{1}, q_{2})_{s_{1},s_{2}}}{(uy; q_{1}, q_{2})_{s_{1}+1,s_{2}+1}} .

Next multiply the above identity by t_{1}^{s_{1}}t_{2}^{s_{2}} and sum over s_{1} ≥ 0 and s_{2} ≥ 0, writing the right-hand side first :

∑_{s_{1}≥0,s_{2}≥0} t_{1}^{s_{1}}t_{2}^{s_{2}} \frac{(−uxq_{1}q_{2}; q_{1}, q_{2})_{s_{1},s_{2}}}{(uy; q_{1}, q_{2})_{s_{1}+1,s_{2}+1}}

= ∑_{n≥0} u^{n} ∑_{{λ,μ \atop |λ|+|μ|=n}} x^{|λ|}y^{|μ|} ∑_{s_{1}} t_{1}^{s_{1}}S_{λ}(q_{1}, …, q_{1}^{s_{1}})S_{μ}(1, q_{1}, …, q_{1}^{s_{1}})

× ∑_{s_{2}} t_{2}^{s_{2}}S_{λ′}(q_{2}, …, q_{2}^{s_{2}})S_{μ}(1, q_{2}, …, q_{2}^{s_{2}})

Next, make use of Lemma 5.3 : with the exception of λ and μ replace each letter occurring in identity (5.14) by the same letter with the subscript i (i = 1, 2). We obtain

∑_{s_{1}≥0,s_{2}≥0} t_{1}^{s_{1}}t_{2}^{s_{2}} \frac{(−uxq_{1}q_{2}; q_{1}, q_{2})_{s_{1},s_{2}}}{(uy; q_{1}, q_{2})_{s_{1}+1,s_{2}+1}}

= ∑_{n≥0} \frac{u^{n}}{(t_{1}; q_{1})_{n+1}(t_{2}; q_{2})_{n+1}} ∑_{{λ,μ \atop |λ|+|μ|=n}} x^{|λ|}y^{|μ|} ∑ F_{1}(T_{1} ⊗ U_{1})F_{2}(T′_{2} ⊗ U_{2}).

Then

A_{n} = ∑ x^{|λ|}y^{|μ|}F_{1}(T_{1} ⊗ U_{1})F_{2}(T′_{2} ⊗ U_{2}),

where the sum is over all sequences (λ, μ, T_{1} ⊗ U_{1}, T_{2} ⊗ U_{2}), where λ and μ are two partitions such that |λ| + |μ| = n and T_{1} ⊗ U_{1} and T_{2} ⊗ U_{2} are two standard tableaux of shape λ⊗μ and T′_{2} is the transpose of T_{2}. Thus A_{n} is a generating polynomial in six variables and (1.10) provides an expression for the generating function of those polynomials in the algebra of basic hypergeometric series with two bases q_{1}, q_{2}.

In the same manner, A_{n}^{I}, A_{n}^{II} and A_{n}^{III} are generating polynomials over the same sequences (λ, μ, T_{1} ⊗ U_{1}, T_{2} ⊗ U_{2}), but the argument in the F_{i}’s varies, some tableaux being replaced by their transposes, namely

(8.2)  A_{n}^{I} = ∑ x^{|λ|}y^{|μ|}F_{1}(T_{1} ⊗ U_{1})F_{2}(T_{2} ⊗ U_{2});
(8.3)  A_{n}^{II} = ∑ x^{|λ|}y^{|μ|}F_{1}(T_{1} ⊗ U_{1})F_{2}(T′_{2} ⊗ U′_{2});
(8.4)  A_{n}^{III} = ∑ x^{|λ|}y^{|μ|}F_{1}(T_{1} ⊗ U_{1})F_{2}(T_{2} ⊗ U′_{2}).

The next step is to interpret the different polynomials A_{n} as generating polynomials for linear structures and no longer tableaux. As was shown in [6], pairs of standard skew-tableaux of the same shape are in a one-to-one correspondence with coloured permutations. What is meant by coloured permutation is an ordinary permutation w of order n together with a subset K ⊂ [ n]. There are then 2^{n}n! coloured permutations of order n.

Let (w, K) be a coloured permutation of order n. Put K^{c} = [ n] \ K. The restriction of w to K (resp. to K^{c}) is a bijection σ of K into w(K) (resp. σ′ of K^{c} onto w(K^{c})). If i_{1} < i_{2} < ⋯ < i_{|K|} (resp. j_{1} < j_{2} < ⋯ < j_{|K^{c}|} ) is the increasing sequence of the elements of K (resp. K^{c}), we also denote by σ (resp. σ′) the word σ = w(i_{1})w(i_{2}) … w(i_{|K|}) (resp. σ′ = w(j_{1})w(j_{2}) … w(j_{|K^{c}|})). In the same manner, σ^{−1} and σ^{′−1} will denote the words σ^{−1} = w^{−1}(k_{1})w^{−1}(k_{2}) … w^{−1}(k_{|K|}) (resp. σ^{′−1} = w^{−1}(l_{1})w^{−1}(l_{2}) … w^{−1}(l_{|K^{c}|})), where k_{1} < k_{2} < ⋯ < k_{|K|} and l_{1} < l_{2} < ⋯ < l_{|K^{c}|} are the increasing sequences of the elements of w(K) and w(K^{c}), respectively.

To avoid cumbersome notations denote by r w the mirror-image of a word w (previously denoted by w̃). With each coloured permutation (w, K) associate four pairs of associate words defined as follows. The first associates are the juxtaposition products

a_{1} = a_{1}^{I} = a_{1}^{II} = a_{1}^{III} = σσ′,

while their second associates are the juxtaposition products a_{2} = rσ^{−1}σ^{′−1} ; a_{2}^{I} = σ^{−1}σ^{′−1} ; a_{2}^{II} = rσ^{−1}rσ^{′−1} ; a_{2}^{III} = σ^{−1}rσ^{′−1}.

Recall that the inverse ligne of route, iligne w, of a permutation w written as a word w = w(1)w(2) … w(n) is the set of all i such that 1 ≤ i ≤ n − 1 and (i + 1) is to the left of the letter i in the word w. Also as in section 6 define

ides w = # iligne w  and  imaj w = ∑ i (i ∈ iligne w).

Note that all the previous associates are permutations of order n. We can then speak of their inverse lignes of route. The following theorem was proved in [6, théorème 3.1], although stated in a slightly different way.

Theorem 8.1. To each coloured permutation (w, K) of order n there corresponds, in a one-to-one manner, a skew-diagram λ ⊗ μ and a pair of standard tableaux (T_{1} ⊗ U_{1}, T_{2} ⊗ U_{2}) both of shape λ ⊗ μ such that

|K| = |λ| , |K^{c}| = |μ| ,

Cont T_{1} = w(K), Cont T_{2} = K, Cont U_{1} = w(K^{c}), Cont U_{2} = K^{c},

iligne a_{1} = iligne a_{1}^{I} = iligne a_{1}^{II} = iligne a_{1}^{III} = iligne T_{1} ⊗ U_{1},

iligne a_{2} = iligne T′_{2} ⊗ U_{2}, iligne a_{2}^{I} = iligne T_{2} ⊗ U_{2},
iligne a_{2}^{II} = iligne T′_{2} ⊗ U′_{2}, iligne a_{2}^{III} = iligne T_{2} ⊗ U′_{2}.

The bijection (w, K) ↦ (λ ⊗ μ, T_{1} ⊗ U_{1}, T_{2} ⊗ U_{2}) in the previous theorem is derived, as the bijection constructed in section 6, by means of the Robinson-Schensted correspondence. We will illustrate the bijection involved in the preceding theorem with an example.

Let

w = ( \begin{matrix}1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 \\ 6 & 2 & 3 & 4 & 1 & 7 & 9 & 8 & 5 \end{matrix} )  and  K = \{1, 2, 6, 9\}.

Then

K^{c} = {3, 4, 5, 7, 8}, w(K) = {2, 5, 6, 7}, w(K^{c}) = {1, 3, 4, 8, 9},

σ = ( \begin{matrix}1 & 2 & 6 & 9 \\ 6 & 2 & 7 & 5 \end{matrix} ) , σ′ = ( \begin{matrix}3 & 4 & 5 & 7 & 8 \\ 3 & 4 & 1 & 9 & 8 \end{matrix} ) ,

w^{−1} = ( \begin{matrix}1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 \\ 5 & 2 & 3 & 4 & 9 & 1 & 6 & 8 & 7 \end{matrix} ), σ^{−1} = ( \begin{matrix}2 & 5 & 6 & 7 \\ 2 & 9 & 1 & 6 \end{matrix} ), σ^{′−1} = ( \begin{matrix}1 & 3 & 4 & 8 & 9 \\ 5 & 3 & 4 & 8 & 7 \end{matrix} ),

so that the associates are :

a_{1} = a_{1}^{I} = a_{1}^{II} = a_{1}^{III} = σσ′ = 6, 2, 7, 5; 3, 4, 1, 9, 8;

a_{2} = rσ^{−1} σ^{′−1} = 6, 1, 9, 2; 5, 3, 4, 8, 7;
a_{2}^{I} = σ^{−1} σ^{′−1} = 2, 9, 1, 6; 5, 3, 4, 8, 7;
a_{2}^{II} = rσ^{−1} rσ^{′−1} = 6, 1, 9, 2; 7, 8, 4, 3, 5;
a_{2}^{III} = σ^{−1} rσ^{′−1} = 2, 9, 1, 6; 7, 8, 4, 3, 5.

The Robinson-Schensted correspondence (see, e.g., [12, p. 48–72]) maps the bijections σ and σ′ onto the pairs of tableaux :

(T_{1}, T_{2}) = ( \begin{matrix}6 & 7 \\ 2 & 5 & , \end{matrix} \begin{matrix}2 & 9 \\ 1 & 6 \end{matrix} ) , (U_{1}, U_{2}) = ( \begin{matrix}3 & 9 \\ 1 & 4 & 8 & , \end{matrix} \begin{matrix}5 & 8 \\ 3 & 4 & 7 \end{matrix} ) ,

respectively. We then form the skew-tableaux

T_{1} ⊗ U_{1} = 6 7 2 5 3 9 1 4 8 , T_{2} ⊗ U_{2} = 2 9 1 6 5 8 3 4 7 .

Observe that iligne a_{1} = iligne a_{1}^{I} = iligne a_{1}^{II} = iligne a_{1}^{III} = iligne T_{1} ⊗ U_{1} = {1, 4, 5, 8}; also iligne a_{2} = iligne T′_{2} ⊗ U_{2} = {4, 5, 7, 8}; iligne a_{2}^{I} = iligne T_{2} ⊗ U_{2} = {1, 4, 5, 7, 8}; iligne a_{2}^{II} = iligne T′_{2} ⊗ U′_{2} = {3, 5, 8}; iligne a_{2}^{III} = iligne T_{2} ⊗ U′_{2} = {1, 3, 5, 8}.

Now rewrite the definition of F_{i} (i = 1, 2), as it was stated in (5.13),

F_{i}(T_{i} ⊗ U_{i}) = \{ \begin{matrix}q_{i}^{|λ|} t_{i}^{1+ides T_{i}⊗U_{i}}q_{i}^{imaj T_{i}⊗U_{i}}, & if 1 ∈ T_{i}; \\ q_{i}^{|λ|} t_{i}^{ides T_{i}⊗U_{i}}q_{i}^{imaj T_{i}⊗U_{i}}, & if 1 ∈ U_{i}. \end{matrix}

It follows from Theorem 8.1 that 1 ∈ T_{1} iff 1 ∈ w(K) and 1 ∈ T_{2} iff 1 ∈ K.

Definition. For each coloured permutation (w, K) let f_{1}^{I}(w, K) = f_{1}^{II}(w, K) = f_{1}^{III}(w, K) = f_{1}(w, K) and define

f_{1}(w, K) = \{ \begin{matrix}q_{1}^{|K|} t_{1}^{1+ides a_{1}}q_{1}^{imaj a_{1}}, & if 1 ∈ w(K) ; \\ q_{1}^{|K|} t_{1}^{ides a_{1}}q_{1}^{imaj a_{1}}, & if 1 ∉ w(K) ; \end{matrix}

f_{2}(w, K) = \{ \begin{matrix}q_{2}^{|K|} t_{2}^{1+ides a_{2}}q_{2}^{imaj a_{2}}, & if 1 ∈ K; \\ q_{2}^{|K|} t_{2}^{ides a_{2}}q_{2}^{imaj a_{2}}, & if 1 ∉ K; \end{matrix}

also let f_{2}^{I}(w, K), f_{2}^{II}(w, K), f_{2}^{III}(w, K) have the same definitions as f_{2}(w, K), the corresponding superscript I, II, III being added to a_{2}, respectively.

If (w, K) is mapped onto (λ ⊗ μ, T_{1} ⊗ U_{1}, T_{2} ⊗ U_{2}) by the bijection of Theorem 8.1, then

\begin{aligned}f_{1}(w, K)f_{2}(w, K) & = F_{1}(T_{1} ⊗ U_{1})F_{2}(T′_{2} ⊗ U_{2}); \\ f_{1}^{I}(w, K)f_{2}^{I}(w, K) & = F_{1}(T_{1} ⊗ U_{1})F_{2}(T_{2} ⊗ U_{2}); \\ f_{1}^{II}(w, K)f_{2}^{II}(w, K) & = F_{1}(T_{1} ⊗ U_{1})F_{2}(T′_{2} ⊗ U′_{2}); \\ f_{1}^{III}(w, K)f_{2}^{III}(w, K) & = F_{1}(T_{1} ⊗ U_{1})F_{2}(T_{2} ⊗ U′_{2}). \end{aligned}

It follows from Theorem 8.1 that the polynomials expressed in (8.1)–(8.4) have also the combinatorial interpretations stated in the next theorem.

Theorem 8.2. The polynomials occurring in the expansions (1.10)– (1.13) are also the generating polynomials

\begin{aligned}A_{n} & = ∑ x^{|K|}y^{n−|K|}f_{1}(w, K)f_{2}(w, K); \\ A_{n}^{I} & = ∑ x^{|K|}y^{n−|K|}f_{1}^{I}(w, K)f_{2}^{I}(w, K); \\ A_{n}^{II} & = ∑ x^{|K|}y^{n−|K|}f_{1}^{II}(w, K)f_{2}^{II}(w, K); \\ A_{n}^{III} & = ∑ x^{|K|}y^{n−|K|}f_{1}^{III}(w, K)f_{2}^{III}(w, K); \end{aligned}

where all the summations are over the coloured permutations (w, K) of order n.

The previous theorem can rephrased in terms of k^{∗}-descents. First, define the inverse of the coloured permutation (w, K) to be (w, K)^{−1} = (w^{−1}, w(K)). Then, consider the following conditions :

(i) i, (i + 1) ∈ K^{c} and w(i) > w(i + 1) ; (i′) i, (i + 1) ∈ K^{c} and w(i) < w(i + 1) ; (ii) i, (i + 1) ∈ K and w(i) < w(i + 1) ; (ii′) i, (i + 1) ∈ K and w(i) > w(i + 1) ; (iii) i ∈ K^{c} and (i + 1) ∈ K.

Now say that an integer i is a k^{∗}-descent (resp. k^{∗}-descent of type I, resp. k^{∗}-descent of type II, resp. k^{∗}-descent of type III) in a coloured permutation (w, K) of order n, if |K| = k, 1 ≤ i ≤ n − 1 and if one of the conditions (i), (ii), (iii) holds (resp. (i), (ii′), (iii) holds, resp. (i′), (ii), (iii) holds, resp. (i′), (ii′), (iii) holds). Also let des_{k}^{∗}(w, K) (resp. des_{k}^{∗I}(w, K), resp. des_{k}^{∗II}(w, K), resp. des_{k}^{∗III}(w, K)) be the number of k^{∗}-descents (resp. k^{∗}-descents of type I, resp. k^{∗}-descents of type II, resp. k^{∗}-descents of type III) in (w, K), if 1 ∈ K^{c}, and one plus that number, if 1 ∈ K. Finally, let maj_{k}^{∗}(w, K) (resp. maj_{k}^{∗I}(w, K), resp. maj_{k}^{∗II}(w, K), resp. maj_{k}^{∗III}(w, K)) be the sum of all i’s such that i is a k^{∗}-descent (resp. a k^{∗}-descent of type I, resp. a k^{∗}-descent of type II, resp. a k^{∗}-descent of type III) plus k.

With this terminology it is readily seen that

f_{1}(w, K) = ⋯ = f_{1}^{III}(w, K) = t_{1}^{des_{k}^{∗I}(w,K)^{−1}}q_{1}^{maj_{k}^{∗I}(w,K)^{−1}};
f_{2}(w, K) = t_{2}^{des_{k}^{∗}(w,K)}q_{2}^{maj_{k}^{∗}(w,K)};
f_{2}^{I}(w, K) = t_{2}^{des_{k}^{∗I}(w,K)}q_{2}^{maj_{k}^{∗I}(w,K)};
f_{2}^{II}(w, K) = t_{2}^{des_{k}^{∗II}(w,K)}q_{2}^{maj_{k}^{∗II}(w,K)};
f_{2}^{III}(w, K) = t_{2}^{des_{k}^{∗III}(w,K)}q_{2}^{maj_{k}^{∗III}(w,K)};

so that Theorem 8.2 can be restated as follows.

Theorem 8.2′. We also have :

A_{n} = ∑ x^{|K|}y^{n−|K|}t_{1}^{des_{k}^{∗I}(w,K)^{−1}}q_{1}^{maj_{k}^{∗I}(w,K)^{−1}}t_{2}^{des_{k}^{∗}(w,K)}q_{2}^{maj_{k}^{∗}(w,K)};
A_{n}^{I} = ∑ x^{|K|}y^{n−|K|}t_{1}^{des_{k}^{∗I}(w,K)^{−1}}q_{1}^{maj_{k}^{∗I}(w,K)^{−1}}t_{2}^{des_{k}^{∗I}(w,K)}q_{2}^{maj_{k}^{∗I}(w,K)};
A_{n}^{II} = ∑ x^{|K|}y^{n−|K|}t_{1}^{des_{k}^{∗I}(w,K)^{−1}}q_{1}^{maj_{k}^{∗I}(w,K)^{−1}}t_{2}^{des_{k}^{∗II}(w,K)}q_{2}^{maj_{k}^{∗II}(w,K)};
A_{n}^{III} = ∑ x^{|K|}y^{n−|K|}t_{1}^{des_{k}^{∗I}(w,K)^{−1}}q_{1}^{maj_{k}^{∗I}(w,K)^{−1}}t_{2}^{des_{k}^{∗III}(w,K)}q_{2}^{maj_{k}^{∗III}(w,K)};

where all the summations are over the coloured permutations (w, K) of order n.

REFERENCES

1. George E. Andrews. The Theory of Partitions. London, Addison-Wesley, 1976 (Encyclopedia of Math. and Its Appl., 2).

2. George E. Andrews. Private communication, 1994.

3. Robert J. Clarke and Dominique Foata. Eulerian Calculus, I : univariable statistics, Europ. J. Combinatorics, v. 15, 1994, p. 345–362.

4. Robert J. Clarke and Dominique Foata. Eulerian Calculus, II : an extension of Han’s fundamental transformation, to appear in Europ. J. Combinatorics 1994.

5. Robert J. Clarke and Dominique Foata. Eulerian Calculus, IV : specializations, in preparation, 1994.

6. Jacques Désarménien and Dominique Foata. Fonctions symétriques et séries hypergéométriques basiques multivariées, Bull. Soc. Math. France, v. 113, 1985, p. 3–22.

7. Nathan J. Fine. Basic Hypergeometric Series and Applications. Providence, Amer. Math. Soc., 1988.

8. Dominique Foata. Les distributions Euler-Mahoniennes sur les mots, preprint, to appear in the Proceedings of the Formal Series and Algebraic Combinatorics, Montréal, 1992, Discrete Math.

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

10. Ira Gessel. Generating functions and enumeration of sequences, Ph. D. thesis, Dept. Math., M.I.T., Cambridge, Mass., 111 p., 1977.

11. Donald E. Knuth. Permutations, matrices, and generalized Young tableaux, Pacific J. Math., v. 34, 1970, p. 709–727.

12. Donald E. Knuth. The Art of Computer Programming, vol. 3, Sorting and Searching. Addison-Wesley, Reading, 1973.

13. Ian G. Macdonald. Symmetric Functions and Hall Polynomials. Oxford, Clarendon Press, 1979.

14. (Major) P. A. MacMahon. The indices of permutations and the derivation therefrom of functions of a single variable associated with the permutations of any assemblage of objects, Amer. J. Math., v. 35, 1913, p. 314–321.

15. (Major) P.A. MacMahon. Combinatory Analysis, vol. 1. Cambridge, Cambridge Univ. Press, 1915 (Reprinted by Chelsea, New York, 1955).

16. (Major) P.A. MacMahon. Collected Papers, vol. 1 [G.E. Andrews, ed.]. Cambridge, Mass., The M.I.T. Press, 1978.

17. Don Rawlings. Multicolored Simon Newcomb Problems, J. Combinatorial Theory, Ser. A, v. 53, 1990, p. 53–67.

18. Victor Reiner. Signed permutation statistics, Europ. J. Combinatorics, v. 14, 1993, p. 553–567.

19. Victor Reiner. Signed Permutations statistics and Cycle Type, Europ. J. Combinatorics, v. 14, 1993, p. 569–579.

20. Victor Reiner. Upper Binomial Posets and Signed Permutations statistics, Europ. J. Combinatorics, v. 14, 1993, p. 581–588.

21. Richard P. Stanley. Ordered Structures and Partitions. Providence, R.I., Amer. Math. Soc., 1972 (Memoirs Amer. Math. Soc., 119).

Robert J. Clarke, Pure Mathematics Department, University of Adelaide, Adelaide, South Australia 5005, Australia email : rclarke@maths.adelaide.edu.au Dominique Foata, Département de mathématique, Université Louis-Pasteur, 7, rue René-Descartes, F-67084 Strasbourg, France. email : foata@math.u-strasbg.fr