MULTIBASIC EULERIAN POLYNOMIALS

BY

Dominique FOATA (^{∗}) AND Doron ZEILBERGER (^{∗∗})

ABSTRACT. — Eulerian polynomials with several bases are defined. Their combinatorial interpretations are given as well as congruence properties modulo some ideals generated by cyclotomic polynomials.

1. Introduction

It is well-known (see, e.g., [Ri, chap. 7]) that the identity

(1.1)  ∑_{n} \frac{u^{n}}{n!} A_{n}(t) = \frac{1 − t}{1 − t exp((1 − t)u)}  (n ≥ 0)

defines a sequence of polynomials (A_{n}(t)), called Eulerian polynomials, whose classical combinatorial interpretation is the following : for each permutation σ = σ(1) … σ(n) let des σ be the number of descents of σ, that is, the number of i such that 1 ≤ i ≤ n − 1 and σ(i) > σ(i + 1). Then A_{n}(t) = ∑_{σ} t^{1+des σ} (σ ∈ S_{n}). This shows, in particular, that each polynomial A_{n}(t) has positive integral coefficients whose sum is n!

As usual, let

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

denote the q-ascending factorial and also let

(u; q)_{∞} = ∏_{n=0}^{∞}(1 − uq^{n}).

(^{∗}) Department of Mathematics, Drexel University, Philadelphia, PA 19104, USA.

Supported in part by NSF grant DMS 8901610. On leave (1989) from Département de mathématique, Université Louis-Pasteur, 7, Rue René-Descartes, F-67084 Strasbourg, France.

(^{∗∗}) Department of Mathematics, Drexel University, Philadelphia, PA 19104, USA.

Supported in part by NSF grant DMS 8800663.

D. FOATA AND D. ZEILBERGER

Further, let

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

denote the Gaussian polynomial for 0 ≤ i ≤ n. Finally, let the two qexponentials be given by (see [An, chap. 2])

(1.2)  e(u; q) = ∑_{n≥0} \frac{u^{n}}{(q; q)_{n}} = (u; q)_{∞}^{−1} ;

(1.3)  E(u; q) = ∑_{n≥0} q^{n(n−1)/2} \frac{u^{n}}{(q; q)_{n}} = (−u; q)_{∞}.

Our purpose is to investigate the properties of a class of polynomials (A_{n}(s; q_{1}, …, q_{l})) (n = (n_{1}, …, n_{l}) ∈ N^{l}, l ≥ 1) in (l + 1) variables [in short, A_{n}(s; q)] defined by the identity

(1.4)  ∑_{n} \frac{∏_{j} u_{j}^{n_{j}}}{∏_{j}(q_{j}; q_{j})_{n_{j}}} A_{n}(s; q) = \frac{1 − s}{1 − s ∏_{j} e((1 − s)u_{j}; q_{j})},

where j goes from 1 to l. To convince ourselves that each A_{n}(s; q) is a polynomial with integral coefficients we may rewrite (1.4) as L = (1−R)^{−1}. The identity L(1 − R) = 1 yields the recurrence relation

(1.5)  A_{n}(s; q) = ∑_{i} ∏_{j} \left[{n_{j} \atop i_{j}}\right]_{q_{j}}A_{i}(s; q)s(1 − s)^{n_{1}−i_{1}+···+n_{l}−i_{l}−1},

where j goes from 1 to l and where i = (i_{1}, …, i_{l}) runs over all sequences of nonnegative integers satisfying i ≠ (n_{1}, …, n_{l}) and 0 ≤ i_{1} ≤ n_{1}, …, 0 ≤ i_{l} ≤ n_{l}. As A_{0}(s; q) = 1, relation (1.5) shows by induction that each A_{n}(s; q) is a polynomial with integral coefficients. To show that the coefficients are indeed positive and of sum (n_{1} + ⋯ + n_{l})! requires more analysis and will be a consequence of theorem 1 or theorem 2 below.

The second class of polynomials under study will be denoted by (B_{n}(s; q)) (n ∈ N^{k+1}, k ≥ 0, q = (q_{1}, …, q_{k})). They are defined by

(1.6) ∑_{n} \frac{∏_{j=1}^{k+1} u_{j}^{n_{j}}}{∏_{j=1}^{k}(q_{j}; q_{j})_{n_{j}}n_{k+1}!}B_{n}(s; q)

= \frac{1 − s}{1 − s ∏_{j=1}^{k} e((1 − s)u_{j}; q_{j}) exp((1 − s)u_{k+1})}.

Assume 0 ≤ k, k + 1 = l and let q_{l} = 1 in (1.5). Then A_{n}(s; q) is transformed into a polynomial in (k + 1) variables s, q_{1}, …, q_{k}. Furthermore, the Gaussian polynomial \left[{n_{l} \atop i_{l}}\right]_{q_{l}} becomes the ordinary binomial coefficient

\binom{n_{l}}{i_{l}}. Hence (1.4) itself is transformed into identity (1.6). Thus (1.7)

B_{n_{1},...,n_{k+1}}(s; q_{1}, …, q_{k}) = A_{n_{1},...,n_{k+1}}(s; q_{1}, …, q_{k}, q_{k+1})|q_{k+1} = 1.

Conversely, put u_{k+1} = 0 in (1.6) and let k = l. Then (1.6) yields (1.4), so that

(1.8)  A_{n_{1},...,n_{k}}(s; q_{1}, …, q_{k}) = B_{n_{1},...,n_{k},0}(s; q_{1}, …, q_{k}).

We emphasize the fact that A_{n}(s; q) has l indices and (l + 1) variables, whereas B_{n}(s; q) has (k + 1) indices and (k + 1) variables.

When k = 0, then B_{n}(s, q_{1}, …, q_{k}) reduces to the usual Eulerian polynomial A_{n}(s) defined in (1.1). When l = 1, then A_{n}(s, q_{1}, …, q_{l}) is the q-Eulerian polynomial A_{n}(s, q) that is known to be [St] the generating polynomial for the permutation group by the bivariate statistic (1 + number of descents, inversion number). Identity (1.6) for k = 1 was considered by Désarménien [De] for his definition of the q-Eulerian polynomials with two indices.

The theory of basic hypergeometric series is now well understood, witness the forthcoming book by Gasper and Rahman [GaRa2]. They have also paved the way for the almost untouched forest of multi-basic hypergeometric series ([Ga], [GaRa1]). Our intention here is to derive the properties of the multibase-analog of the classical Eulerian polynomials using mainly symmetric function techniques and combinatorial manipulations on the inversion numbers.

We first give a combinatorial interpretation to A_{n}(s; q) and B_{n}(s; q). Because of (1.7) it suffices to do it for the A_{n}(s; q)’s. Two combinatorial interpretations will be given, the first one in terms of lignes of route of permutations, the second one in terms of inversion numbers. The ligne of route Ligne σ of σ = σ(1) … σ(n) is defined to be the set of all r such that 1 ≤ r ≤ n − 1 and σ(r) > σ(r + 1). Hence |Ligne σ| is the number of descents, des σ, defined above. Furthermore, the sum of all r in Ligne σ is the classical major index, maj σ, of σ.

Let n = (n_{1}, …, n_{l}) satisfy n_{1}+⋯+n_{l} = n. Also let n_{0} = 0 and denote by n_{j} the partial sum n_{j} = n_{1} + ⋯ + n_{j} (0 ≤ j ≤ l). For j = 1, …, l define the j-th n-inverse ligne of route of σ as being

Iligne_{j} σ = {r : n_{j−1} + 1 ≤ r ≤ n_{j} − 1, σ^{−1}(r) > σ^{−1}(r + 1)},

and the j-th n-inversion number of σ as

inv_{j} σ = #{(r, r′) : n_{j−1} + 1 ≤ r < r′ ≤ n_{j}, σ^{−1}(r) > σ^{−1}(r′)}.

Also let

imaj_{j} σ = ∑{r − n_{j−1} : r ∈ Iligne_{j} σ} (j = 1, …, l).

When l = 1, the statistics imaj_{1} σ and inv_{1} σ are the familiar inverse major index and inversion number of the permutation σ, respectively.

The first two results of the paper can be stated as follows.

Theorem 1. — For each n = (n_{1}, …, n_{l}) the generating polynomial for the permutation group S_{n} by the (l+1)-vector (1+ des, imaj_{1}, …, imaj_{l}) is equal to A_{n}(s; q). In other words, if A_{n}(s; q) is defined by identity (1.4), then

(1.9)  A_{n}(s; q) = ∑_{σ} s^{1+des σ}q_{1}^{imaj_{1} σ} … q_{l}^{imaj_{l} σ}  (σ ∈ S_{n}).

Theorem 2. — For each n = (n_{1}, …, n_{l}) the generating polynomial for the permutation group S_{n} by the (l + 1)-vector (1+ des, inv_{1}, …, inv_{l}) is equal to A_{n}(s; q), i.e.,

(1.10)  A_{n}(s; q) = ∑_{σ} s^{1+des σ}q_{1}^{inv_{1} σ} … q_{l}^{inv_{l} σ}  (σ ∈ S_{n}).

The proof of theorem 1, derived in section 2, makes use of symmetric function techniques, especially the Schur function algebra. To prove theorem 2 it is more conventient to show that A_{n}(s; q), as defined in (1.10) satisfies the recurrence relation (1.5). This is done in section 3, by using an appropriate factorization of permutations.

The combination of (1.9) and (1.10) suggests that there must be a bijection of S_{n} onto itself that sends the vector (1+ des, imaj_{1}, …, imaj_{l}) onto (1+ des, inv_{1}, …, inv_{l}). Such a bijection can indeed be derived (section 4). Call it σ ↦ σ′. It has even the following stronger property.

Theorem 3. — The bijection σ ↦ σ′ satisfies :

Ligne σ = Ligne σ′; imaj_{j} σ_{j} = inv_{j} σ′ (j = 1, …, l).

In particular, des σ = des σ′ and maj σ = maj σ′.

In its turn theorem 3 suggests that the polynomial

1A_{n}(s, p; q) = ∑_{σ} s^{des σ}p^{maj σ}q_{1}^{imaj_{1} σ} … q_{l}^{imaj_{l} σ} (σ ∈ S_{n})

should also be investigated. Using the techniques developed in [DeFo2] its generating function can be calculated in the form

∑_{n} \frac{∏_{j} u_{j}^{n_{j}}}{(s; p)_{n_{1}+···+n_{l}} ∏_{j}(q_{j}; q_{j})_{n_{j}}} ^{1}A_{n}(s, p; q) = ∑_{r} \frac{s^{r}}{∏_{j}(u_{j}; p, q_{j})_{r+1,∞}} ,

where

(u_{j}; p, q_{j})_{r+1,∞} = ∏_{1≤i≤r+1}(u_{j}p^{i−1}; q_{j})_{∞} (j = 1, …, l).

However the series on the right-hand side cannot be put into a form explicit enough to deserve further study. Note that the previous generating function for the ^{1}A_{n}(s, p; q)’s specializes for l = 1 to an identity worked out by Gessel [Ge1]. For p = 1 the right-hand side can be summed, as will be shown in the proof of theorem 1 (section 2). The idea of having the ligne of route of a permutation split into compartments is due originally to Remmel [Re]. Further work along these lines can be found in [DeFo2].

The second goal of the paper is to work out congruence properties for the polynomials B_{n}(s; q) (n ∈ N^{k+1}). Let (d_{1}, …, d_{k}) be a given sequence of positive integers and for each n = (n_{1}, …, n_{k}, n_{k+1}) let

(1.11)  n_{j} = d_{j}a_{j} + b_{j}, 0 ≤ b_{j} ≤ d_{j} − 1  (1 ≤ j ≤ k)

be the Euclidean division of n_{j} by d_{j}. Then define div n to be

div n = (b_{1}, …, b_{k}, n_{k+1} + a_{1} + ⋯ + a_{k}).

Further let Φ_{d}(q) denote the d-th cyclotomic polynomial (Φ_{1}(q) = 1 − q, Φ_{2}(q) = 1 + q, …). We also prove the following theorem.

Theorem 4. — We have the congruences :

B_{n}(s; q) ≡ (1 − s)^{(d_{1}−1)a_{1}+···+(d_{k}−1)a_{k}}B_{div n}(s; q) (mod (Φ_{d_{1}}(q_{1}), …, Φ_{d_{k}}(q_{k})))

The case k = 1 is due originally to Désarménien [De] (see also [DeFo2]).

Corollary. — If all the remainders b_{j} in (1.11) are equal to 0 or 1, then

(1.12) B_{n}(s; q) ≡ (1 − s)^{(d_{1}−1)a_{1}+···+(d_{k}−1)a_{k}}A_{a_{1}+b_{1}+···+a_{k}+b_{k}+n_{k+1}}(s)

(mod (Φ_{d_{1}}(q_{1}), …, Φ_{d_{k}}(q_{k}))) ;

(1.13) A_{n}(s; q) ≡ (1 − s)^{(d_{1}−1)a_{1}+···+(d_{l}−1)a_{l}}A_{a_{1}+b_{1}+···+a_{l}+b_{l}}(s) (mod (Φ_{d_{1}}(q_{1}), …, Φ_{d_{k}}(q_{k}))) ;

where the polynomial A_{a_{1}+···}(s) on both right-hand sides is the Eulerian polynomial defined in (1.1).

In particular, if n = (2a_{1} + b_{1}, …, 2a_{l} + b_{l}) with b_{1} = 0, 1, …, b_{l} = 0, 1 and q_{1} = ⋯ = q_{l} = q, then

(1.14) A_{n}(s; q) ≡ (1 − s)^{a_{1}+···+a_{l}}A_{a_{1}+b_{1}+···+a_{l}+b_{l}}(s) (mod (1 + q)).

Both theorem 4 and its corollary are proved in section 5. The case l = 1 of (1.14) was in fact conjectured by Loday [Lod] for a side calculation of the cyclic homology of commutative algebras. It has since received several specific proofs in [DeFo2] and [Wa]. Michelle Wachs [Wa] derived a very ingenious involution for proving (1.14) in the case l = 1. In section 6 we give a Wachs-style combinatorial proof of theorem 4.

2. Proof of theorem 1

In fact (1.4) with the interpretation given in (1.7) can be viewed as a specialization of a result on the (k, l)-colored permutations derived in [DeFo2]. To make the paper self-contained we have preferred to prove theorem 1 from scratch using a working example. Take up again the notations preceding theorem 1 with σ designating a permutation of order n. For each j = 1, …, l let τ_{j} be the restriction of σ to the set σ^{−1}([n_{j−1} + 1, n_{j}]), so that:

(2.1)  τ_{j} : σ^{−1}([n_{j−1} + 1, n_{j}]) → [n_{j−1} + 1, n_{j}].

Using the Robinson-Schensted correspondence ([Kn, p. 48–72]) each bijection τ_{j} is mapped onto a pair (P_{j}, Q_{j}) of Young tableaux of the same shape that we shall denote by λ_{j}. It follows from the properties of that correspondence that the entries of P_{j} are the elements of the interval [n_{j−1} +1, n_{j}] and the entries of Q_{j} are those of the set σ^{−1}([n_{j−1} +1, n_{j}]). For j = 1, …, l let T_{j} be the Young tableau obtained from P_{j} by replacing each entry r by r − n_{j−1} and let U be the product

U = Q_{1} ⊗ ⋯ ⊗ Q_{l}.

In the French way of displaying tableaux this means that U is the skew tableau obtained by placing each Q_{j} to the right of Q_{j−1} and just under it for j = 2, …, l. Thus each T_{j} is a Young tableau of shape λ_{j} whose entries are 1, 2, …, n_{j} (j = 1, …, l); the entries of U are 1, 2, …, n and the shape of U is the skew shape λ_{1} ⊗ ⋯ ⊗ λ_{l}. We summarize all this by writing :

(2.2) shape T_{j} = λ_{j} ; |λ_{j}| = n_{j} ; (j = 1, …, l) ; shape U = λ_{1} ⊗ ⋯ ⊗ λ_{l}; |λ_{1}| + ⋯ + |λ_{l}| = n.

For instance, let l = 2, n = (5, 4) and

σ = ( \begin{matrix}1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 \\ 8 & 6 & 4 & 5 & 2 & 1 & 9 & 7 & 3 \end{matrix} ); σ^{−1} = ( \begin{matrix}1 & 2 & 3 & 4 & 5 \\ 6 & 5 & 9 & 3 & 4 \end{matrix} | \begin{matrix}6 & 7 & 8 & 9 \\ 2 & 8 & 1 & 7 \end{matrix} ) .

Then

τ_{1} = ( \begin{matrix}3 & 4 & 5 & 6 & 9 \\ 4 & 5 & 2 & 1 & 3 \end{matrix} ); τ_{2} = ( \begin{matrix}1 & 2 & 7 & 8 \\ 2 & 6 & 9 & 7 \end{matrix} ) .

Under the Robinson-Schensted correspondence

τ_{1} ↦ (P_{1}, Q_{1}) = (\begin{matrix}4 \\ 2 & 5 \\ 1 & 3 \end{matrix} , \begin{matrix}6 \\ 5 & 9 \\ 3 & 4 \end{matrix} ); λ_{1} = (2, 2, 1) ;

τ_{2} ↦ (P_{2}, Q_{2}) = (\begin{matrix}8 & 9 \\ 6 & 7 \end{matrix} , \begin{matrix}2 & 8 \\ 1 & 7 \end{matrix} ); λ_{2} = (2, 2) ;

and

T_{1} = P_{1} = 4 2 5 1 3 ; T_{2} = P_{2} − n_{1} = 3 4 1 2 ; U = 6 5 9 3 4 2 8 1 7 .

The inverse ligne of route Iligne U of U is defined as being the set of all entries r such that (r + 1) lies in a higher row than r in U (in the French way of displaying tableaux). Furthermore, define

imaj U = ∑{r : r ∈ Iligne U} ides U = |Iligne U| .

With the working example, Iligne U = {1, 2, 4, 5, 7, 8}, imaj U = 27 and ides U = 6.

Lemma 2.1. — The mapping (σ, n) ↦ (λ_{1}, …, λ_{l}; T_{1}, …, T_{l}; U) is a bijection having properties (2.2) and satisfying

(2.3)

Iligne_{j} σ_{j} − n_{j−1} = Iligne T_{j} (j = 1, …, l) ;
Ligne σ = Iligne U.

We do not prove lemma 2.1, as it was already derived in [DeFo2] in the context of the (k, l)-colored permutations. With our working example Iligne_{1} σ = {1, 3} = Iligne T_{1} ; Iligne_{2} σ = {2} = Iligne T_{2} ; Ligne σ = {1, 2, 4, 5, 7, 8} = Iligne U.

It follows from (2.3) that

(2.4)  imaj_{j} σ = imaj T_{j} (j = 1, …, l) ;  des σ = ides U.

Let s^{1}A_{n}(s; q) denote the right-hand side of (1.9). Then by (2.3) and (2.4)

(2.5)  ^{1}A_{n}(s; q) = ∑_{(λ_{j})} ∑_{(T_{j}),U} s^{ides U}q_{1}^{imaj T_{1}} … q_{l}^{imaj T_{l}},

where the first sum is over the sequences (λ_{1}, …, λ_{l}) of partitions satisfying |λ_{1}| = n_{1}, …, |λ_{l}| = n_{l}, and the second over all sequences of tableaux (T_{1}, …, T_{l}, U) satisfying (2.2).

The next step is to express the right-hand side of (2.5) in terms of skew Schur functions. Let S_{θ}(x_{1}, x_{2}, …) designate the skew Schur function associated with the skew diagram θ ([Mac, p. 39]). The following lemma was proved in [DeFo1].

Lemma 2.2. — If θ is a skew diagram of n elements, then

\frac{1}{(s; q)_{n+1}} ∑_{T} s^{ides T} q^{imaj T} = ∑_{r} s^{r}S_{θ}(1, q, q^{2}, …, q^{r}),

where the first sum is over all standard tableaux T of shape θ.

We are using here two specializations of this lemma obtained by letting q = 1 and s = 1, respectively :

(2.6)  \frac{1}{(1 − s)^{n+1}} ∑_{T} s^{ides T} = ∑_{r} t^{r}S_{θ}(1^{r+1}),

(2.7)  \frac{1}{(q; q)_{n}} ∑_{T} q^{imaj T} = S_{θ}(1, q, q^{2}, …),

where S_{θ}(1^{r+1}) is the skew Schur function obtained by taking an alphabet of (r + 1) letters all equal to 1.

By (2.5), (2.6) and (2.7) we have :

\frac{^{1}A_{n}(s, q)}{(1 − s)^{n} ∏_{j}(q_{j}; q_{j})_{n_{j}}} = \frac{1}{(1 − s)^{n} ∏_{j}(q_{j}; q_{j})_{n_{j}}} ∑_{(λ_{j}),(T_{j}),U} s^{ides U} ∏_{j} q_{j}^{imaj T_{j}}

= ∑_{(λ_{j})} ∑_{r} s^{r}S_{λ_{1}⊗···⊗λ_{l}}(1^{r+1}) ∏_{j} S_{λ_{j}}(1, q_{j}, q_{j}^{2}, …)

= ∑_{(λ_{j})} ∑_{r} s^{r} ∏_{j} S_{λ_{j}}(1^{r+1})S_{λ_{j}}(1, q_{j}, q_{j}^{2}, …),

as U is of shape λ_{1}⊗⋯⊗λ_{l}. In the last step we have used the fondamental multiplicative property of the Schur functions : S_{λ⊗μ}(x) = S_{λ}(x)S_{μ}(x). Now the Cauchy identity for Schur functions

∑_{λ} u^{|λ|}S_{λ}(x)S_{λ}(y) = ∏_{i,j} \frac{1}{(1 − ux_{i}y_{j})}

yields

MULTIBASIC EULERIAN POLYNOMIALS

\begin{aligned}∑_{λ_{j}} u_{j}^{|λ_{j}|}S_{λ_{j}}(1^{r+1})S_{λ_{j}}(1, q_{j}, q_{j}^{2}, …) & = ∏_{d≥1} \frac{1}{(1 − u_{j}q_{j}^{d−1})^{r+1}} \\ & = \frac{1}{(u_{j}; q_{j})_{∞}^{r+1}} . \end{aligned}

As |λ_{j}| = n_{j} (j = 1, …, l), we may write

∑_{n} \frac{∏_{j} u_{j}^{n_{j}}}{(1 − s)^{n} ∏_{j}(q_{j}; q_{j})_{n_{j}}} ^{1}A_{n}(s, q)

= ∑_{n} ∏_{j} u_{j}^{n_{j}} ∑_{(λ_{j})} ∑_{r} s^{r} ∏_{j} S_{λ_{j}}(1^{r+1})S_{λ_{j}}(1, q_{j}, q_{j}^{2}, …)

= ∑_{r} s^{r} ∑_{(λ_{j})} ∏_{j} u_{j}^{|λ_{j}|}S_{λ_{j}}(1^{r+1})S_{λ_{j}}(1, q_{j}, q_{j}^{2}, …)

= ∑_{r} s^{r} ∏_{j} ∑_{λ_{j}} u_{j}^{|λ_{j}|}S_{λ_{j}}(1^{r+1})S_{λ_{j}}(1, q_{j}, q_{j}^{2}, …)

= ∑_{r} ∏_{j} \frac{s^{r}}{(u_{j}; q_{j})_{∞}^{r+1}} = \frac{1}{−s + ∏_{j}(u_{j}; q_{j})_{∞}} .

Next replace each u_{j} by u_{j}/(1 − s). This yields

\begin{aligned}∑_{n} \frac{∏_{j} u_{j}^{n_{j}}}{∏_{j}(q_{j}; q_{j})_{n_{j}}} ^{1}A_{n}(s, q) & = \frac{1 − s}{−s + ∏_{j}((1 − s)u_{j}; q_{j})_{∞}} \\ & = \frac{1 − s}{−s + ∏_{j} E((s − 1)u_{j}; q_{j})}, \end{aligned}

using the notation of the second q-exponential introduced in (1.3).

The generating function for the polynomials A_{n}(s, q) involves the first q-exponential, as shown in the next calculation

\begin{aligned}1 + ∑_{n≠0} \frac{∏_{j} u_{j}^{n_{j}}}{∏_{j}(q_{j}; q_{j})_{n_{j}}} A_{n}(s, q) & = s\frac{1 − s}{−s + ∏_{j} E((s − 1)u_{j}; q_{j})} − s + 1 \\ & = \frac{1 − s}{1 − s ∏_{j} e((1 − s)u_{j}; q_{j})}, \end{aligned}

since E(u; q)e(−u; q) = 1. This proves theorem 1.

3. Proof of theorem 2

Call A_{n}^{inv}(s; q) the right-hand side of (1.10), namely the generating function for S_{n} by the vector (1 + des, inv_{1}, …, inv_{l}). We will prove that A_{n}^{inv}(s; q) satisfies recurrence (1.5), i.e., the equation obtained from (1.5) by replacing A_{n} and A_{i} by A_{n}^{inv} and A_{i}^{inv}, respectively. Since A_{0} = A_{0}^{inv} = 1 by convention, the result will follow by induction.

Consider the set T_{n} of all “commaed” permutations that consist of a permutation in S_{n} together with a comma inserted in such a way that the sequence after the comma is increasing. For example, 4 7 1 3, 2 5 6; 4 7 1 3 2, 5 6; 4 7 1 3 2 5, 6; are all members of T_{n}, but 4 7, 1 3 2 5 6 is not.

To each member (σ_{1}, σ_{2}) (i.e., σ_{2} is increasing and non-empty and σ := σ_{1}σ_{2} is a regular permutation of S_{n}) of T_{n} associate the weight

weight(σ_{1}, σ_{2}) = s^{1+des σ_{1}}s(1 − s)^{length σ_{2}−1} ∏_{j} q_{j}^{inv_{j} σ}.

Next to each σ in S_{n} associate the set C(σ) of all commaed permutations obtained from σ by inserting a comma right before one of the entries that belong to the maximal terminal increasing right factor of σ.

For example, σ = 4 7 1 3 2 5 6 gives rise to the following set

C(σ) = {4 7 1 3, 2 5 6 ; 4 7 1 3 2, 5 6 ; 4 7 1 3 2 5, 6 }.

We claim that this mapping C is weight preserving, i.e.,

s^{1+des σ} ∏_{j} q_{j}^{inv_{j} σ} = ∑_{τ∈C(σ)} weight τ.

Indeed the ∏_{j} q_{j}^{inv_{j} σ} factor is the same at both sides. The s-contribution is as follows, letting r be the length of the maximal increasing right factor of σ :

weight(σ(1) … σ(n − r))[s(1 − s)^{r−1} + s^{2}(1 − s)^{r−2} + ⋯ + s^{2}(1 − s)^{0}] = weight(σ(1) … σ(n − r))s = weight(σ(1) … σ(n)) = weight(σ).

Thus the sum of the weights of all the elements of S_{n} (i.e., A_{n}^{inv}(s; q)) is the same as the sum of all the weights of the elements of T_{n}. Let’s compute the latter, noting that inv_{j} σ is also equal to :

inv_{j} σ = #{(r, r′) : 1 ≤ r < r′ ≤ n, n_{j} ≥ σ(r) > σ(r′) ≥ n_{j−1} + 1 }.

Consider the subset of T_{n} consisting of all elements such that the comma comes right after i_{1} members of the first class, …, i_{l} members of the lth class. Let h_{1} = n_{1} − i_{1}, …, h_{l} = n_{l} − i_{l} and assume that after the comma we have the fixed increasing factor a_{1}^{(1)} … a_{h_{1}}^{(1)} … a_{1}^{(l)} … a_{h_{l}}^{(l)}, with n_{j−1} + 1 ≤ a_{1}^{(j)} < ⋯ < a_{h_{j}}^{(j)} ≤ n_{l} for j = 1, …, l. The total weight of the above factor is easily seen to be

A_{i}^{inv}(s; q) s(1 − s)^{n_{1}−i_{1}+n_{2}−i_{2}+···+n_{l}−i_{l}−1}

× ∏_{j} q_{j}^{(n_{j}−a_{h_{j}}^{(j)})+(n_{j}−a_{h_{j} −1}^{(j)}−1)+···+(n_{j}−a_{j}^{(j)}−(h_{j}−1))}.

Now for a fixed i = (i_{1}, i_{2}, …, i_{l}) we have that the sum runs independently with respect to each of the exponents of the q_{j}’s. It is easy to see that inside the exponent of q_{j} (j = 1, …, l) we have a typical partition of n with largest part at most equal to n_{j} − h_{j} (= i_{j}) and number of parts at most equal to h_{j}. The generating function of which is well known to be the qbinomial \left[{n_{j} \atop i_{j}}\right]_{q_{j}} to base q_{j}. Since the sums over each q_{j} run independently,

the total weight of members of T_{n} such that right before the comma come i_{1} members of the first class, …, i_{l} members of the l-th class (regardless of what comes after) is

∏_{j} \left[{n_{j} \atop i_{j}}\right]_{q_{j}}A_{i}^{inv}(s; q)s(1 − s)^{n_{1}−i_{1}+···+n_{l}−i_{l}−1}.

Summing over all conceivable i ≠ n establishes (1.5).

The technique used here was inspired by some methods developed in [Ge2] and [Ze].

4. Inversion numbers

The proof of theorem 3 relies upon the properties of the so-called second fundamental transformation ([Lot, chap. 10]), we shall designate by ϕ. Let w = x_{1} … x_{m} be a word whose letters belong to N and let x be an integer. If the last letter of w is greater (resp. smaller than or equal to) x, the word w admits a unique factorization (w_{1}y_{1}, …, w_{p}y_{p}), called its x-factorization having the following properties :

(i) each y_{i} (i = 1, …, p) satisfies y_{i} > x (resp. y_{i} ≤ x);

(ii) each word w_{i} (i = 1, …, p) is either empty, or has all its letters smaller than or equal to (resp. greater than) x.

Define γ_{x}(w) = y_{1}w_{1} … y_{p}w_{p}. (Note that w = w_{1}y_{1} … w_{p}y_{p}.) The transformation ϕ is defined by induction as follows : ϕ(w) = w, if w is of length one; if w has a length at least equal to 2, write w = vx with x being the last letter of w, and define :

ϕ(vx) = γ_{x}(ϕ(v))x.

Let W be the rearrangement class of some word w_{0}. It was proved in [Fo] that ϕ is a bijection of W onto itself having the property that

(4.1)  maj w = inv ϕ(w),

for every w ∈ W.

A further property of ϕ was stated and proved in [FoSch] for the rearrangement classes W containing only words without repetitions, say, subwords of permutations. If w is such a word, its inverse ligne of route Iligne w may be defined as being the set of all k such that k and (k + 1) are letters of w and (k + 1) is to the left of k in w. In particular, if w is a permutation of 1, 2, …, n, then Iligne w is simply the ligne of route of the inverse permutation w^{−1}. Thus when the rearrangement class W contains only subwords of permutations, it was shown in [FoSch] that

(4.2)  Iligne w = Iligne ϕ(w).

Recently, Björner and Wachs [BjWa] have extended the properties of the second fundamental transformation to a larger set of combinatorial objects, and found several characterizations for sets that satisfied (4.2). Our purpose presently is to include ϕ in the construction of a bijection that will serve to prove theorem 3.

If σ = σ(1) … σ(n) is a permutation and if n = (n_{1}, …, n_{l}) is a sequence of integers of sum n, let

σ_{j} = σ(n_{j−1} + 1) σ(n_{j−1} + 2) … σ(n_{j} + 1)

for j = 1, …, l. If Θ is any transformation on S_{n}, we will write :

(Θσ)_{j} = Θσ(n_{j−1} + 1) Θσ(n_{j−1} + 2) … Θσ(n_{j} + 1).

In particular, if we apply the second fundamental transformation ϕ to each σ_{j} and form the juxtaposition product

(4.3)  ψ(σ) = ϕ(σ_{1}) … ϕ(σ_{l}),

we define a new transformation on S_{n}. Furthermore, ϕ(σ_{j}) = (ψσ)_{j} using the previous notations.

Proposition 4.1. — The sequence n being given, the mapping ψ is a bijection of S_{n} onto itself satisfying :

(4.4)  maj σ_{j} = inv(ψσ)_{j}  (j = 1, …, l) ;

(4.5) Iligne σ = Iligne ψ(σ).

Proof. — Relation (4.4) is just (4.1) rewritten for the factors σ_{j}. Now by (4.2) we have Iligne σ_{j} = Iligne ϕ(σ_{j}). This takes care of all the pairs (k, k + 1) contained in a single factor σ_{j}, and therefore in a factor ϕ(σ_{j}). Next, if 1 ≤ i < j ≤ l and (k + 1) is a letter of σ_{i}, while k is a letter of σ_{j}, then (k + 1) will be to the left of k both in σ and ψ(σ).

Let i σ = σ^{−1} and form the sequence :

σ ↦ i σ ↦ ψ i σ ↦ i ψ i σ,

By (4.5) (4.6) Ligne σ = Iligne i σ = Iligne ψ i σ = Ligne i ψ i σ. Furthermore, by (4.4)

(4.7)  maj(i σ)_{j} = inv(ψ i σ)_{j}  (j = 1, …, l).

Define

σ′ := i ψ i σ.

Then σ ↦ σ′ is a bijection satisfying Ligne σ = Ligne σ′ by (4.6). Furthermore,

imaj_{j} σ_{j} = maj(i σ)_{j} = inv(ψ i σ)_{j} = inv(σ′^{−1})_{j} = inv_{j} σ′.

This completes the proof of theorem 3.

5. The Désarménien Verfahren

Let x = (x_{1}, x_{2}, …) be an infinite sequence of variables and for each r = 1, 2, … denote by h_{r}(x) the homogeneous symmetric function in the x_{j}’s and by p_{r}(x) the power sum ∑_{j} x_{j}^{r}. By convention, h_{0}(x) = 1. The generating function H(u; x) = ∑_{r≥0} u^{r}h_{r}(x) can be evaluated in different forms :

(5.1)  H(u; x) = ∏_{j≥1}(1 − ux_{j})^{−1} = exp ∑_{r≥1} u^{r} \frac{p_{r}(x)}{r}.

(See, e.g., [Mac, p. 14 and 17].)

Recall that a partition of an integer n can be expressed as a nonincreasing sequence λ = (λ_{1}, λ_{2}, …) (λ_{1} ≥ λ_{2} ≥ ⋯), or as a word λ = 1^{m_{1}}2^{m_{2}} … (the multiplicative notation) with the meaning that λ has m_{1} parts λ_{i} equal to 1, m_{2} parts λ_{i} equal to 2, etc… As usual, to each partition λ we attach the constant

z_{λ} = 1^{m_{1}}2^{m_{2}} … m_{1}! m_{2}! …

and the power symmetric function

p_{λ}(x) = p_{λ_{1}}(x)p_{λ_{2})}(x) …

Also |λ| = n means that λ is a partition of n and the notation l(λ) stands for the number of parts of λ.

Désarménien [De] introduced the polynomials

(5.2)  T_{λ}(q) = \frac{(q; q)_{n}}{∏_{j}(1 − q^{j})^{m_{j}}} ,

where λ = 1^{m_{1}}2^{m_{2}} … is a partition of n. He noticed that T_{λ}(q) is a polynomial of degree n(n − 1)/2 and can also be expressed as :

(5.3)  T_{λ}(q) = (q; q)_{n} p_{λ}(1, q, q^{2}, …).

Furthermore, he proved the following congruence property.

Lemma 5.1. — Let n = da + b, 0 ≤ b ≤ d − 1 and λ = 1^{m_{1}}2^{m_{2}} … be a partition of n. Then the following congruences hold :

(i) if m_{d} ≠ a, then T_{λ}(q) ≡ 0 (mod Φ_{d}(q)).

(ii) if m_{d} = a, let μ = λ\d^{a} be the partition obtained from λ by deleting the m_{d} parts equal to d. Then

T_{λ} ≡ d^{a}a! T_{μ}(q) (mod Φ_{d}(q)).

Now let (c_{i}) (i = 0, 1, …) be a sequence of elements belonging to some given ring. The relation

(5.4)  ∑_{i≥0} C_{i} \frac{u^{i}}{i!} = ∑_{i≥0} c_{i}(e^{u} − 1)^{i}

defines a sequence (C_{i}) in a unique manner.

Désarménien considered the expansion

∑_{m≥0, n≥0} C_{n,m}(x)u^{n} \frac{v^{m}}{m!} = ∑_{i≥0} c_{i}(H(u; x)e^{v} − 1)^{i}

and showed that C_{n,m}(x) can be expressed in terms of the symmetric finctions (p_{λ}(x)) as

C_{n,m}(x) = ∑_{λ} C_{m+l(λ)} \frac{p_{λ}(x)}{z_{λ}} (|λ| = n).

Then he defined the polynomials

K_{m,n}(q) = (q; q)_{n} C_{m,n}(1, q, q^{2}, …),

and using lemma 5.1 proved the congruence

K_{m,da+b}(q) ≡ K_{m+a,b}(q) (mod Φ_{d}(q)).

Finally, he applied the latter congruence to his q-Eulerian polynomials with two indices to obtain theorem 4 for k = 1.

The program for an arbitray k and consequently for the multibasic Eulerian polynomials will closely follow the foregoing pattern. This time we have to introduce l sequences of variables x^{j} = (x_{1}^{j}, x_{2}^{j}, …) (1 ≤ j ≤ l), and relation (5.4) being given we expand the expression ∑_{i≥0} c_{i}(∏_{j} H(u_{j}; x^{j}) − 1)^{i}, as a power series in the u_{j}’s. This is done as follows.

Proposition 5.2. — If

(5.5)  ∑_{n} ∏_{j=1}^{l} u_{j}^{n_{j}}C_{n} = ∑_{i≥0} c_{i}(∏_{j=1}^{l} H(u_{j}; x^{j}) − 1)^{i},

then

(5.6) C_{n} = ∑_{λ^{1},...,λ^{l}} C_{l(λ^{1})+···+l(λ^{l})} ∏_{j=1}^{l} \frac{p_{λ^{j}}(x^{j})}{z_{λ^{j}}},

the sum being over all partitions satisfying |λ^{1}| = n_{1}, …, |λ^{l}| = n_{l}.

The proof has been made in [DeFo2] in the case l = 2 and H(u_{2}; x^{2}) = e^{u_{2}}. The proof for an arbitrary l is quite similar and will therefore be left out.

Let 0 ≤ k and k + 1 = l and suppose that H(u_{l}; x^{l}) is equal to e^{u_{l}}. From (5.1) it follows that p_{1}(x^{l}) = 1 and p_{r}(x^{l}) = 0 for r ≥ 2. Hence, if |λ^{l}| = n_{l}, we have

(5.7)  \frac{p_{λ^{l}}(x^{l})}{z_{λ^{l}}} = \{ \begin{matrix}0, & if λ^{l} ≠ (1^{n_{l}}); \\ 1/n_{l}!, & if λ^{l} = (1^{n_{l}}). \end{matrix}

Hence (5.6) takes the form

(5.8)  C_{n} = ∑_{λ^{1},...,λ^{k}} C_{l(λ^{1})+···+l(λ^{k})+n_{k+1}} ∏_{j=1}^{k} \frac{p_{λ^{j}}(x^{j})}{z_{λ^{j}}} \frac{1}{n_{k+1}!},

where |λ^{1}| = n_{1}, …, |λ^{k}| = n_{k}, and (5.5) the form

(5.9)  ∑_{n} ∏_{j=1}^{k+1} u_{j}^{n_{j}}C_{n} = ∑_{i≥0} c_{i}(∏_{j=1}^{k} H(u_{j}; x^{j})e^{u_{k+1}} − 1)^{i}.

For j = 1, …, k and r = 1, 2, … replace each x_{r}^{j} by q_{j}^{r−1} in (5.8) and (5.9). This substitution being made, define

K_{n}(q_{1}, …, q_{k}) = ∏_{j=1}^{k}(q_{j}; q_{j})_{n_{j}} n_{k+1}! C_{n}|x_{r}^{j} ← q_{j}^{r−1}.

By (5.3) and (5.8) we obtain

(5.10) K_{n}(q_{1}, …, q_{k}) =  ∑_{|λ^{1}|=n_{1},...,|λ^{k}|=n_{k}}C_{l(λ^{1})+···+l(λ^{k})+n_{k+1}} ∏_{j=1}^{k} \frac{T_{λ^{j}}(q_{j})}{z_{λ^{j}}}.

On the other hand, by (1.2) and (5.1)

H(u_{j}; x^{j})|x_{r}^{j} ← q_{j}^{r−1} = ∏_{r≥1}(1 − u_{j}q_{j}^{r−1})^{−1} = e(u_{j}; q_{j}).

Hence (5.9) becomes (5.11)

∑_{n} \frac{∏_{j=1}^{l+1} u_{j}^{n_{j}}}{∏_{j=1}^{k}(q_{j}; q_{j})_{n_{j}}n_{k+1}!}K_{n}(q_{1}, …, q_{k}) = ∑_{i≥0}(∏_{j=1}^{k} e(u_{j}; q_{j})e^{u_{k+1}} − 1)^{i}.

Remark. — In the notations of lemma 5.1, case (ii) (m_{d} = a) we have l(λ) = l(μ) + a and z_{λ} = z_{μ}d^{a}a! Hence

(5.12)  \frac{T_{λ}(q)}{z_{λ}} ≡ \frac{T_{μ}(q)}{z_{μ}} (mod Φ_{d}(q)).

Now let (d_{1}, …, d_{k}) be given and let n_{j} = d_{j}a_{j}+b_{j} (0 ≤ b_{j} ≤ d_{j}−1; 1 ≤ j ≤ k). When K_{n} is taken mod (Φ_{d_{1}}(q_{1}), …, Φ_{d_{k}}(q_{k})), formula (5.10) becomes in view of lemma 5.1 and (5.12) :

K_{n}(q) = ∑_{|μ^{1}|=b_{1},...,|μ^{k}|=b_{k}}C_{l(μ^{1})+a_{1}+···+l(μ^{k})+a_{k}+n_{k+1}} ∏_{j=1}^{k} \frac{T_{μ^{j}}(q_{j})}{z_{μ^{j}}}.

But by (5.10) the right-hand side of the previous congruence is also equal to K_{div n}(q) with

div n = (b_{1}, …, b_{k}, n_{k+1} + a_{1} + ⋯ + a_{k}).

Hence

(5.13)  K_{n}(q) ≡ K_{div n}(q) (mod (Φ_{d_{1}}(q_{1}), …, Φ_{d_{k}}(q_{k}))).

To apply the foregoing congruence results to the multibasic Eulerian polynomials we note that (1.6) can be rewritten as

∑_{n} \frac{∏_{j=1}^{k+1} u_{j}^{n_{j}}}{∏_{j=1}^{k}(q_{j}; q_{j})_{n_{j}} n_{k+1}!} \frac{B_{n}(s; q)}{(1 − s)^{n_{1}+···+n_{k+1}}}

= ∑_{i≥0}(\frac{s}{1 − s})^{i}(∏_{j=1}^{k} e(u_{j}; q_{j})e^{u_{k+1}} − 1)^{i}.

Comparing the latter identity with (5.11) we see that we can apply (5.13) to K_{n}(q) = B_{n}(s; q)/(1 − s)^{n_{1}+···+n_{k+1}}, which are polynomials in the q_{j}’s with coefficients in the field Q(s). This gives immediately theorem 4.

Consider a polynomial B_{n}(s; q) (n ∈ N^{k+1}) and suppose that the first k components of n are equal to 0 or 1. It then follows from (1.7) and theorem 1 that there is no variable q_{j} occurring in the expression of B_{n}(s; q). Therefore, this polynomial reduces to the ordinary Eulerian polynomial A_{n_{1}+···+n_{k+1}}(s) defined in (1.1). The corollary is then a consequence of this observation and theorem 4.

6. A Wachs-style proof of Theorem 4

We will give a Wachs-style proof of theorem 2 of [DeFo2]., i.e. the one-colored case of theorem 4. The same argument then goes to prove theorem 4 itself. We use the combinatorial interpretation of theorem 2.

We have to prove that if ω = primitive d-th root of unity, then

(6.1)  B_{da+b,m}(s; ω) = (1 − s)^{(d−1)a}B_{b,m+a}(s; ω).

Let us first prove the case a = 1, b = 0, m = 0, i.e., that B_{d,0}(s; ω) = (1 − s)^{d−1}B_{0,1}(s; ω) = (1 − s)^{d−1}A_{1}(s) = (1 − s)^{d−1}s. This follows from recurrence (1.5) with one color, and the fact that

\left[{d \atop i}\right]_{q} = \frac{(1 − q^{d})(1 − q^{d−1}) … (1 − q^{d−i+1})}{(1 − q^{i}) … (1 − q)}

vanishes when q = ω and 1 ≤ i < d. Thus by plugging in q = ω in (1.5) there is only one surviving term, i = 0. We summarize this result as :

(6.2)  ∑_{S_{d+0}} weight σ = (1 − s)^{d−1}s.

Now let us prove (6.1) in general. We may write

(6.3)  B_{da+b,m}(s; q) = ∑_{S_{(da+b)+m}} weight π = ∑_{π} s^{1+des π}q^{inv_{1} π},

with π running over S_{(da+b)+m}, so that only the elements 1, 2, …, da + b are taken into account for the calculation of the exponent of q. Group those (da + b) colored elements into families of consecutive d elements :

V_{1} := {1, …, d}; V_{2} := {d + 1, …, 2d}; … V_{a} := {(a − 1)d + 1, …, ad}; plus a set of “bachelors”

W := {ad + 1, …, ad + b}.

It is possible to view a permutation as a “seating” in a one-row auditorium. From now on “seating” and “permutation” will be used interchangeably. A happy seating is one in which no family had to split, i.e., every family sits in d consecutive chairs. An unhappy seating is one in which at least one of the d families had to split. We claim

(i) The sum of all the weights of the happy seatings is

(1 − s)^{(d−1)a}B_{b,m+a}(s; ω).

(ii) The sum of the weights of all the unhappy seatings is zero.

Proof of (i). — Each happy seating can be characterized by a sequence π = (σ, π_{1}, …, π_{a}), where σ belongs to S_{(b)+(m+a)} and indicates how the b bachelors, the m uncolored elements and the a family-blocks are displayed on the one-row seating and where π_{1}, …, π_{a} are permutations that arrange the seatings within each family. We have

des π = des σ + des π_{1} + ⋯ + des π_{a},

since the total number of descents is the sum of the inter-family and intra-family descents. We also have that the number of inversions of π (that count, i.e., the inversions between the da + b elements themselves, disregarding relationships with the m elements that “don’t count”) equals d^{2} times the number of inversions in σ between the a family blocks, plus d times the number of inversions that result between the b bachelors and the a family blocks. To these we have to add, of course, the “intra-family” inversions, i.e., inv π_{1}+⋯+inv π_{a}, and finally we have to add the inversions between the b bachelors. Moding out by d the contributions from the first two kinds of inversions vanish and we have (recall q = ω, ω a primitive d-th root of unity)

weight π = s^{1+des σ}q^{inv_{1} σ}s^{des π_{1}}q^{inv π_{1}} … s^{des π_{a}}q^{inv π_{a}},

so that

s^{a} weight π = weight σ weight π_{1} … weight π_{a}.

Thus

∑_{π happy}weight π = s^{−a} ∑_{S_{b+(m+a)}}weight σ ∑_{S_{d}} weight π_{1} … ∑_{S_{d}} weight π_{a}

= B_{b,m+a}(s; ω)(1 − s)^{(d−1)a},

by (6.2) and (6.3).

Proof of (ii). — For any set X = {x_{1} < x_{2} < ⋯ < x_{L}} and any permutation ρ = x_{i_{1}}x_{i_{2}} … x_{i_{L}} of X we denote by red ρ the permutation of 1, 2, …, L, called the reduction of ρ, defined by red ρ = i_{1}i_{2} … i_{L}.

Michelle Wachs (d = 2) killed bad guys in pairs. We would have to exterminate them in bunches. Let r (1 ≤ r ≤ a) be the smallest unhappy family (i.e., r is the smallest integer for which V_{r} is an unhappy family). Let the connected components of the seats occupied by the V_{r}-family members have lengths α_{1}, …, α_{c}. Obviously c ≥ 2 and α_{1} + α_{2} + ⋯ + α_{c} = d.

Consider all permutations that give rise to the same unhappy r, same component sizes α_{1}, …, α_{c}, whose last connected component reduces to the same permutation p ∈ S_{α_{c}} and in which all the non-V_{r} objects stay the same. In other words, once the show has begun, only the V_{r}-family members can move seats between themselves, but they must observe the same “pattern” in the last component. We will now show that the sum of all the weights of the seatings that are related in such a way is zero.

The descents and inversions with “the outside world” remains fixed, as do the descents and inversions within “the outside world”. All the changes are the descents and inversions due to the placements of the V_{r}-family members themselves. Furthermore, even the descents and inversions due to the inhabitants of the last component among themselves remain fixed, since only the relative sizes matter. In addition the sum of the contributions to the weights from the relative placements of the members of the V_{r}-family within the first c−1 components remain the same, regardless the occupants of the last component. (Only relative size matters.) The only things that do change are the inversions caused by the interaction between the V_{r}-members that occupy the last component and the rest of their family. If the set of occupants of the last component is (let α_{c} = L) (x_{1}, …, x_{L})

(x_{1} < x_{2} < ⋯ < x_{L}), then the number of inversions contributed by these interactions is (d − \overline{x}_{L}) + (d − 1 − \overline{x}_{L−1}) + ⋯ + (d − (L − 1) − \overline{x}_{1}), where \overline{x}_{i} are the reduced labels in the V_{r}-family : \overline{x}_{i} := x_{i} − rd. What we get is a typical partition with ≤ L parts and largest part ≤ d−L, whose generating function (see [An, chap. 3]) is (1 − q^{d}) … (1 − q^{d−L+1})/(1 − q) … (1 − q^{L}), and therefore vanishes when q = ω. Since all the unhappy seatings can be partitioned into these sets, they all die.

Note. — The same argument exactly goes over to prove theorem 4 of the present paper. We partition each color into the appropriate number of families and “bachelors”, and in order to kill the unhappy seatings, we choose the lowest color that has an unhappy family, and within this color, the lowest unhappy family.

Tables of A_{n_{1},n_{2},n_{3}}(s; q_{1}, q_{2}, q_{3})

for 6 ≥ n_{1} ≥ n2 ≥ n_{3} ≥ 0

A table of the polynomials A_{n_{1},n_{2},n_{3}}(s; q_{1}, q_{2}, q_{3}) such that n_{2} = 0, 1 and n_{3} = 0, 1 and n_{1} ≤ 6 has already been published by Désarménien [De]. Write A_{m,n}^{d} for the notations adopted in [De] and keep A_{n_{1},n_{2},n_{3}} for ours. We have the correspondence A_{n_{1},n_{2},n_{3}} = A_{n_{2}+n_{3},n_{1}}^{d}, whenever 0 ≤ n_{2}, n_{3} ≤ 1. We then just list A_{2,2,0}, A_{3,2,0}, A_{2,2,1}, A_{4,2,0}, A_{3,3,0}, A_{3,2,1}, A_{2,2,2} that have not appeared before. Only the last one actually involves the four variables s, q_{1}, q_{2}, q_{3}.

For example, the (2, 2, 0)-table is to be read : A_{2,2,2}(s; q_{1}, q_{2}, q_{3}) = s + s^{2}(3 + 3q_{1} + 3q_{2} + q_{1}q_{2}) + s^{3}(1 + 3q_{1} + 3q_{2} + 4q_{1}q_{2}) + s^{4}.

\begin{aligned}& (2, 2, 0) \\ 1 & q_{1} & q_{2} & q_{1}q_{2} \\ s & 1 \\ s^{2} & 4 & 3 & 3 & 1 \\ s^{3} & 1 & 3 & 3 & 4 \\ s^{4} & 1 \end{aligned}  \begin{aligned}& & & & (3, 2, 0) \\ 1 & q_{1} & q_{2} & q_{1}^{2} & q_{1}q_{2} & q_{1}^{3} & q_{1}^{2}q_{2} & q_{1}^{3}q_{2} \\ s & 1 \\ s^{2} & 6 & 6 & 4 & 6 & 2 & 2 \\ s^{3} & 3 & 12 & 6 & 12 & 12 & 6 & 12 & 3 \\ s^{4} & 2 & 2 & 6 & 4 & 6 & 6 \\ s^{5} & & & & & & 1 \end{aligned}  \begin{aligned}& (2, 2, 1) \\ 1 & q_{1} & q_{2} & q_{1}q_{2} \\ s & 1 \\ s^{2} & 12 & 6 & 6 & 2 \\ s^{3} & 15 & 18 & 18 & 15 \\ s^{4} & 2 & 6 & 6 & 12 \\ s^{5} & & 1 \end{aligned}

(4, 2, 0)

(3, 3, 0)

1 q_{1} q_{2} q_{1}^{2} q_{1}q_{2} q_{1}^{3} q_{1}^{2}q_{2} q_{1}^{4} q_{1}^{3}q_{2} q_{1}^{5} q_{1}^{4}q_{2} q_{1}^{6} q_{1}^{5}q_{2} q_{1}^{6}q_{2} s 1 s^{2} 8 9 5 12 3 9 4 3 3  1 s^{3} 6 27 10 42 24 45 35 33 33 18 20  9 s^{4} 9  20 18 33 33 35 45 24 42 10 27 6 s^{5} 1 3 3 4 9 3 12 5 9 8 s^{6}  1 1 q_{1} q_{2} q_{1}^{2} q_{1}q_{2} q_{2}^{2} q_{1}^{3} q_{1}^{2}q_{2} q_{1}q_{2}^{2} q_{2}^{3} q_{1}^{3}q_{2} q_{1}^{2}q_{2}^{2} q_{1}q_{2}^{3} q_{1}^{3}q_{2}^{2} q_{1}^{2}q_{2}^{3} q_{1}^{3}q_{2}^{3} s 1 s^{2} 9 8 8 8 4 8 4 4 4 s^{3} 9 24 24 24 36 24 10 36 36 10 8 36 8 8 8 1 s^{4} 1 8 8 8 36 8 10 36 36 10 24 36 24 24 24 9 s^{5} 4 4 4 8 4 8 8 8 9 s^{6}  1

\begin{aligned}& & & & (3, 2, 1) \\ 1 & q_{1} & q_{2} & q_{1}^{2} & q_{1}q_{2} & q_{1}^{3} & q_{1}^{2}q_{2} & q_{1}^{3}q_{2} \\ s & 1 \\ s^{2} & 17 & 12 & 8 & 12 & 4 & 4 \\ s^{3} & 33 & 60 & 34 & 60 & 44 & 18 & 44 & 9 \\ s^{4} & 9 & 44 & 18 & 44 & 60 & 34 & 60 & 33 \\ s^{5} & 4 & 4 & 12 & 8 & 12 & 17 \\ s^{6} & & & & & & & 1 \end{aligned}  \begin{aligned}& & & & & (2, 2, 2) \\ 1 & q_{1} & q_{2} & q_{3} & q_{1}q_{2} & q_{1}q_{3} & q_{2}q_{3} & q_{1}q_{2}q_{3} \\ s & 1 \\ s^{2} & 20 & 9 & 9 & 9 & 4 & 3 & 3 & 1 \\ s^{3} & 48 & 45 & 45 & 45 & 33 & 33 & 33 & 20 \\ s^{4} & 20 & 33 & 33 & 33 & 45 & 45 & 45 & 48 \\ s^{5} & 1 & 3 & 3 & 3 & 9 & 9 & 9 & 20 \\ s^{6} & & & & & & & 1 \end{aligned}

REFERENCES

[An] ANDREWS (George E.). — The Theory of Partitions. — Reading, Mass., Addison-

Wesley, 1976 (Enclycopedia of Math. and Its. Appl., 2).

[BjWa] BJ^{}ÖRNER (Anders) and WACHS (Michelle L.). — Permutation Statistics and

Linear Extensions of Posets, 1988.

[De] D^{}ÉSARM^{}ÉNIEN (Jacques). — Fonctions symétriques associées à des suites clas-

siques de nombres, Ann. scient. Éc. Norm. Sup., v. 16, 1983, p. 271–304.

[DeFo1] D^{}ÉSARM^{}ÉNIEN (Jacques) et FOATA (Dominique). — Fonctions symétriques et séries hypergéométriques basiques multivariées, Bull. Soc. Math. France, v. 113, 1985, p. 3–22.

[DeFo2] D^{}ÉSARM^{}ÉNIEN (Jacques) et FOATA (Dominique). — Statistiques d’ordre sur les permutations colorées, to appear in Discrete Math.

[DeFo3] D^{}ÉSARM^{}ÉNIEN (Jacques) and FOATA (Dominique). — The signed Eulerian

Numbers, submitted.

[Fo] FOATA (Dominique). — On the Netto inversion number of a sequence, Proc.

Amer. Math. Soc., v. 19, 1968, p. 236–240.

[Fo-Sch] FOATA (Dominique) and SCH^{}ÜTZENBERGER (Marcel-Paul). — Major Index and

Inversion of Permutations, Math. Nachr., v. 83, 1978, p. 143–159.

[Ga] GASPER (George). — Summation, transformation, and expansion formulas for

bibasic series, Trans. Amer. Math. Soc., v. 312, 1989, p. 257–277.

[GaRa1] GASPER (George) and RAHMAN (Mizan). — An indefinite bibasic summation formula and some quadratic, cubic, and quartic summation and transformation formulas, preprint.

[GaRa2] GASPER (George) and RAHMAN (Mizan). — Basic Hypergeometric Series.

Cambridge Univ. Press, to appear.

[Ge1] GESSEL (Ira). — Generating functions and enumeration of sequences, Ph. D. thesis, Dept. Math., M.I.T., Cambridge, Mass., 111 p., 1977.

[Ge2] GESSEL (Ira). — A q-analogue of the exponential formula, Discrete Math., v. 40, 1982, p. 69–80.

[Kn] Knuth (Donald E.). — The Art of Computer Programming, vol. 3, Sorting and Searching. — Addison-Wesley, Reading, 1973.

[Lod] LODAY (Jean-Louis). — Opérations sur l’homologie cyclique des algèbres commutatives, Inv. Math., v. 96, 1989, p. 205–230.

[Lot] LOTHAIRE (M.). — Combinatorics on words. — Addison-Wesley, Reading, 1983 (Enclyclopedia of Math. and its Appl., 17).

[Mac] MACDONALD (I.G.). — Symmetric Functions and Hall polynomials. — Oxford, Clarendon Press, 1979.

[Re] REMMEL (J.B.). — Permutation Statistics and (k, l)-hook Schur functions, Discrete Math., v. 67, 1987, p. 271–298.

[Ri] RIORDAN (John). — An Introduction to Combinatorial Analysis. — New York, J. Wiley, 1958.

[St] STANLEY (Richard P.). — Binomial posets, Möbius inversion, and permutation enumeration, J. Combinatorial Theory Ser. A, v. 20, 1976, p. 336–356.

[Wa] WACHS (Michelle L.). — An involution for signed Eulerian numbers, submitted.

[Ze] ZEILBERGER (Doron). — A lattice walk approach to the counting of multiset permutations, J. Math. Anal. Appl., v. 74, 1980, p. 192–199.