Séminaire Lotharingien de Combinatoire, B32b, 1994, 12 pp.

EULERIAN CALCULUS, IV : SPECIALIZATIONS

BY

Robert J. CLARKE AND Dominique FOATA (^{∗})

ABSTRACT. — Further excedance and descent statistics can be defined on each rearragement class and their generating functions explicitly calculated. Those generating functions coincide with the classical ones when the rearrangement class is a permutation group, but differ as soon as the class involves repeated elements.

1. Introduction. — In our previous three papers on Eulerian Calculus [ClFo94, ClFo95a, ClFo95b] we have investigated further constructions of transformations on the symmetric group and related structures, and derived explicit formulas for classical order statistics on those structures. Let (a; q)_{n} denote the q-ascending factorial

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

Also 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. Write c = c_{1} + ⋯ + c_{j}, d = d_{1} + ⋯ + d_{k}, then u^{c} for u_{1}^{c_{1}} … u_{j}^{c_{j}} and v^{d} for v_{1}^{d_{1}} … v_{k}^{d_{k}}, finally (u; q)_{s+1} and (−qv; q)_{s} for the two products

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

respectively. In our third paper [ClFo95b] we have considered the identities of the form

(1.1)  ∑_{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}} ,

(1.2)  ∑_{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.3)  ∑_{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.4)  ∑_{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}} ,

(^{∗}) Supported in part by the E.E.C Programme on Algebraic Combinatorics, 1994-95.

ROBERT J. CLARKE AND DOMINIQUE FOATA

and showed that the coefficients A_{c,d}(t, q), A_{c,d}^{I}(t, q), A_{c,d}^{II}(t, q) and A_{c,d}^{III}(t, q) were generating polynomials for words that are rearrangements of the word v = y_{1}y_{2} … y_{m} = 1^{c_{1}} … j^{c_{j}}(j + 1)^{d_{1}} … r^{d_{k}} by pairs of the following statistics.

Call R(c, d) the class of those words and let w = x_{1}x_{2} … x_{m} be a word in this class. 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 kdescent 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} = ⋆, where ⋆ is an extra letter which is bigger that the small letters 1, 2, …, j, but smaller than the large letters (j + 1), …, r.] 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.

The other three pairs of statistics are defined as follows :

(1.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.

(1.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}.

(1.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}.

One of the results of our third paper was to prove the following theorem.

Theorem 1.1. — The coefficients A_{c,d}(t, q) occurring in identity (1.1) are the following generating polynomials

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

with analogous results for A_{c,d}^{I}(t, q), A_{c,d}^{II}(t, q) and A_{c,d}^{III}(t, q) concerning identities (1.2), (1.3) and (1.4), respectively.

EULERIAN CALCULUS, 4

We proved Theorem 1.1 in three different ways : first, by finding recurrence relations for the generating polynomials A_{c,d}(t, q) that imply a system of q-difference equations for their factorial generating functions, a system that can be intregrated to yield (1.1) – (1.4) ; second, by using a standard rearrangement technique for biwords that goes back to MacMahon, the celebrated MacMahon Verfahren ; third, by using the symmetric function technique and especially the Cauchy identity for Schur functions.

Now if we let q = 1 in identities (1.1) – (1.4), we obtain

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

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

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

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

where A_{c,d}(t) stands for A_{c,d}(t, q) |_{q=1} with analogous expressions for the other polynomials and where (1+v)^{s} stands for (1+v_{1})^{s} … (1+v_{k})^{s} with an analagous expression for (1 − v)^{s+1}.

The purpose of this paper is to reprove identities (1.6) – (1.9) by using a fourth technique based on the MacMahon Master Theorem. As there is no q-analogue (so far ?) of this theorem, such a technique is not available for proving their q-versions (1.1) – (1.4).

We conclude the paper by showing the the polynomials A_{c,d}(t), A_{c,d}^{I}(t) and A_{c,d}^{II}(t) also have combinatorial interpretations in terms of excedances.

2. Determinantal expressions. — For each j and each k such that (0 ≤ j, k ≤ r) and j + k = r denote by B_{k} and B′_{j} the following two r × r matrices. The matrix B_{k} has only 1’s under the diagonal and only t’s above, but its diagonal, diag B_{k}, is made of j 1’s, followed by k t’s, i.e.,

(2.1)  diag B_{k} = (1, …, 1,t, …, t) j times k times

In the matrix B′_{j} the diagonal entries consists of j t’s followed by k 1’s, i.e.,

(2.2)  diag B′_{j} = (t, …, t,1, …, 1) j times k times

and the other entries consist of t’s above the diagonal and 1’s under it. Notice that B_{r} = B′_{r} and B_{0} = B′_{0}, a matrix that has t’s above the diagonal and 1’s on and under the diagonal.

Let the infinite series occurring in the right-hand sides of (1.6), (1.7), (1.8) and (1.9) be denoted by A(u, v, t), A^{I}(u, v, t), A^{II}(u, v, t) and A^{III}(u, v, t), respectively. Furthermore, let U be the diagonal matrix U = diag(u_{1}, …, u_{j}, v_{1}, …, v_{k}). We first prove the identities :

(2.3)  (1 − t) A(u(1 − t), v(1 − t), t) = \frac{1}{det(I_{r} − B_{k}U)};
(2.4) (1 − t) A^{I}(u(1 − t), v(1 − t), t) = \frac{(1 − v(1 − t))}{det(I_{r} − B_{0}U)};
(2.5) (1 − t) A^{II}(u(1 − t), v(1 − t), t) = \frac{(1 + u(1 − t))}{det(I_{r} − B_{r}U)};
(2.6) (1 − t) A^{III}(u(1 − t), v(1 − t), t) = \frac{(1 + u(1 − t))(1 − v(1 − t))}{det(I_{r} − B′_{j}U)}.

Identity (2.3) has been derived in [ClFo94]. The same technique applies for the other three identities. Let us simply prove (2.4). First, it is routine to derive

det(I_{r} − B_{0}U)

= 1 − e_{1}(u, v) + (1 − t)e_{2}(u, v) − ⋯ + (−1)^{r}(1 − t)^{r−1}e_{r}(u, v),

where the e_{i}(u, v)’s are the elementary symmetric function in the variables u_{1}, …, u_{j}, v_{1}, …, v_{k}. Hence

(1 − t) det(I_{r} − B_{0}U) = (1 − t) − e_{1}(u(1 − t), v(1 − t)) + e_{2}(u(1 − t), v(1 − t))

− ⋯ + (−1)^{r}e_{r}(u(1 − t), v(1 − t)).
= −t + (1 − u(1 − t))(1 − v(1 − t)),

and then

\frac{(1 − v(1 − t))}{det(I_{r} − B_{0}U)} = (1 − t) ∑_{s≥0} t^{s} \frac{1}{(1 − u(1 − t))^{s+1}(1 − v(1 − t))^{s}}

= (1 − t) A^{I}(u(1 − t), v(1 − t), t).

As we will make full use of the MacMahon Master Theorem [Mac15, p. 97] to exploit identities (2.3) - (2.6), it is appropriate to restate this theorem now :

Let B = (b(i, j)) (1 ≤ i, j ≤ r) be a square matrix with coefficients in a commutative ring and let X^{∗} be the free monoid generated by X = [ r]. If w = x_{1}x_{2} … x_{m} is a word in X^{∗} whose non-decreasing rearrangement is v = y_{1}y_{2} … y_{m} = 1^{c_{1}} … j^{c_{j}}(j + 1)^{d_{1}} … r^{d_{k}}, define

β(w) = b(y_{1}, x_{1})b(y_{2}, x_{2}) … b(y_{m}, x_{m}) and u(w) = u^{c}v^{d}.

Then the following identity holds

(2.7)  \frac{1}{det(I_{r} − BU)} = ∑_{w} β(w) u(w),

where I_{r} is the identity matrix and where the sum is over all words w ∈ X^{∗}.

Make the substitution B ← B_{k} in identity (2.7). Then the monomial β(w) is simply equal to t^{exc_{k} w}, so that the MacMahon Master Theorem yields the identity

(2.8)  \frac{1}{det(I_{r} − B_{k}U)} = ∑_{w} t^{exc_{k} w}u^{c}v^{d}.

With the substitution B ← B′_{j} we get the identity

(2.9)  \frac{1}{det(I_{r} − B′_{j}U)} = ∑_{w} t^{exc^{j} w}u^{c}v^{d},

where

(2.10) exc^{j} w is the number of i such that 1 ≤ i ≤ m and either x_{i} > y_{i}, or x_{i} = y_{i} and x_{i} ≤ j.

Thus the inverses of the denominators occurring on the right-hand sides of (2.3) - (2.6) are interpreted in terms of excedences. To get an interpretation in terms of descents we need to recall the construction of the transformation that maps excedences onto descents.

3. Descents. — In our first paper [ClFo94] we have constructed a bijection Φ_{k} of each rearrangement class R(c, d) onto itself such that

(3.1)  des_{k} w = exc_{k} Φ_{k}(w)

for each word w in R(c, d). Hence (2.8) and (3.1) imply

(3.2)  \frac{1}{det(I_{r} − B_{k}U)} = ∑_{w} t^{des_{k} w}u^{c}v^{d} = ∑_{c,d} u^{c}v^{d}A_{c,d}(t)

To do the counterpart for identity (2.9) and write

(3.3)  \frac{1}{det(I_{r} − B′_{j}U)} = ∑_{w} t^{des^{j} w}u^{c}v^{d},

we need an appropriate definition for “des^{j}” and a new transformation Ψ^{j} of R(c, d) onto itself having the property

(3.4)  des^{j} w = exc^{j} Ψ^{j}(w).

For “des^{j} we take the definition

(3.5) Let w = x_{1}x_{2} … x_{m} be a word ; then des^{j} w is the number of i such that 0 ≤ i ≤ m − 1 and either x_{i} > x_{i+1}, or x_{i} = x_{i+1} and x_{i} ≤ j. [By convention, x_{0} = x_{1}.]

As for Ψ^{j} we take the conjugate of Φ_{k} in a sense that will be made more precise. First, recall the construction of Φ_{k} using a running example (see [ClFo94, § 5]).

Suppose j = 2, k = 4, r = 6 and let ⋆ be an extra letter between 2 (the largest small letter) and 3 (the smallest large letter). Next consider the word

w = 2, 1, 1, 3, 1, 3, 3, 5, 5, 2, 3, 3, 2, 1, 4, 5, 4, 6, 6, 1, 3.

(a) Add ⋆ at the end of w :

w⋆ = 2, 1, 1, 3, 1, 3, 3, 5, 5, 2, 3, 3, 2, 1, 4, 5, 4, 6, 6, 1, 3, ⋆;

(b) cut w before each left to right upper record :

w⋆ = | 2, 1, 1 | 3, 1 | 3 | 3 | 5 | 5, 2, 3, 3, 2, 1, 4 | 5, 4 | 6 | 6, 1, 3, ⋆ |;

(c) change the mutual orders of all factors beginning with the same large letter (here 3, 5, 6) :

w′ = | 2, 1, 1 | 3 | 3 | 3, 1 | 5, 4 | 5, 2, 3, 3, 2, 1, 4 | 5 | 6, 1, 3, ⋆ | 6 |;

(d) form the following biword where the top word in each factor is simply equal to bottom factor shifted to the left, the first letter being moved to the end :

\binom{Δw′}{w′} = ( \begin{matrix}1 1 2 \\ 2 1 1 \end{matrix} | {3 \atop 3} | \begin{matrix}3 \\ 3 \end{matrix} | {1 3 \atop 3 1} | \begin{matrix}4 5 \\ 5 4 \end{matrix} | \begin{matrix}2 3 3 2 1 4 5 \\ 5 2 3 3 2 1 4 \end{matrix} | {5 \atop 5} | \begin{matrix}1 3 ⋆ 6 \\ 6 1 3 ⋆ \end{matrix} | \begin{matrix}6 \\ 6 \end{matrix} );

(e) remove the vertical bars and rearrange the columns of the latter biword in such a way that the top row is non-decreasing and the mutual order of all the biletters having the same top letter is preserved :

( \begin{matrix}… \\ Φ(w′) \end{matrix} ) = ( \begin{matrix}1 1 1 1 1 2 2 2 ⋆ 3 3 3 3 3 3 4 4 5 5 5 6 6 \\ 2 1 3 2 6 1 5 3 3 3 3 1 2 3 1 5 1 4 4 5 ⋆ 6 \end{matrix} );

(e′) cut the biword before each change of top letter :

( \begin{matrix}… \\ Φ(w′) \end{matrix} ) = ( \begin{matrix}1 1 1 1 1 \\ 2 1 3 2 6 \end{matrix} | \begin{matrix}2 2 2 \\ 1 5 3 \end{matrix} | \begin{matrix}⋆ \\ 3 \end{matrix} | \begin{matrix}3 3 3 3 3 3 \\ 3 3 1 2 3 1 \end{matrix} | \begin{matrix}4 4 \\ 5 1 \end{matrix} | {5 5 5 \atop 4 4 5} | \begin{matrix}6 6 \\ ⋆ 6 \end{matrix} );

(f) within each factor of the biword whose top word has only (equal) large letters reverse (i.e., take the mirror-image of) the bottom word :

( \begin{matrix}… \\ w′′ \end{matrix} ) = ( \begin{matrix}1 1 1 1 1 \\ 2 1 3 2 6 \end{matrix} | \begin{matrix}2 2 2 \\ 1 5 3 \end{matrix} | \begin{matrix}⋆ \\ 3 \end{matrix} | \begin{matrix}3 3 3 3 3 3 \\ 1 3 2 1 3 3 \end{matrix} | \begin{matrix}4 4 \\ 1 5 \end{matrix} | {5 5 5 \atop 5 4 4} | \begin{matrix}6 6 \\ 6 ⋆ \end{matrix} );

(g) remove the vertical bars, delete ⋆ that necessarily occurs at the end of the bottom word ; the remaining bottom word is, by definition, Φ_{k}(w), i.e., Φ_{k}(w)⋆ = w′′ :

( \begin{matrix}… \\ Φ_{k}(w) \end{matrix} ) = ( \begin{matrix}1 1 1 1 1 2 2 2 3 3 3 3 3 3 4 4 5 5 5 6 6 \\ 2 1 3 2 6 1 5 3 3 1 3 2 1 3 3 1 5 5 4 4 6 \end{matrix} ) .

In particular, des_{k} w = exc_{k} Φ_{k}(w) = 12.

Furthermore, let c = c_{1} + ⋯ + c_{j}, d = d_{1} + ⋯ + d_{k} and let x be the last letter of w, so that w = w_{1}x. Then, Φ_{k}(w_{1}x) admits the factorization (w_{2}, x, w_{3}), where w_{2} and w_{3} are words of length l(w_{2}) = c and l(w_{3}) = d − 1. (If d = 0, l(w_{2}) = c − 1.) Thus

(3.5) the last letter of w is equal to the (c + 1)-st letter of Φ_{k}(w).

In particular,

(3.6)  Φ_{0}(w_{2}x) = w_{3}x  and  Φ_{r}(w_{2}x) = xw_{4}.

The construction of Ψ^{j} will also be given by means of an example with j = 4, k = 2, r = 6.

(a) start with a word w_{5} = z_{1}z_{2} … z_{m} in R(c, d) (remember that all the letters are taken from the alphabet [ r]) and for each i = 1, 2, …, m define

x_{i} = r + 1 − z_{m+1−i}  and form the word  w_{6} = x_{1}x_{2} … x_{m}.

Clearly des^{k} w_{5} = des_{k} w_{6}. Under this transformation the image of

v = 4, 6, 1, 1, 3, 2, 3, 6, 5, 4, 4, 5, 2, 2, 4, 4, 6, 4, 6, 6, 5

is precisely the word w in the preceding example.

(b) apply Φ_{k} to w_{6} to get

( \begin{matrix}… \\ Φ_{k}(w) \end{matrix} ) = ( \begin{matrix}\overline{w} & 7 \\ w_{7} \end{matrix} ) = ( \begin{matrix}1 1 1 1 1 2 2 2 3 3 3 3 3 3 4 4 5 5 5 6 6 \\ 2 1 3 2 6 1 5 3 3 1 3 2 1 3 3 1 5 5 4 4 6 \end{matrix} );

(c) replace each entry z in the above biword by (r + 1 − z) to obtain

α = ( \begin{matrix}6 6 6 6 6 5 5 5 4 4 4 4 4 4 3 3 2 2 2 1 1 \\ 5 6 4 5 1 6 2 4 4 6 4 5 6 4 4 6 2 2 3 3 1 \end{matrix} )

(d) consider the above biword as a circuit in the terminology developed in [CaFo69]. Such a circuit can be expressed as a product of true cycles, and the factorization is unique except for the order of the factors (see [CaFo69, chap. 4, Proposition 4.1]). The true cycles are sorted out to the left one by one. With the running example we get :

[ \begin{matrix}6 5 \\ 5 6 \end{matrix} ][ \begin{matrix}6 \\ 6 \end{matrix} ][ \begin{matrix}4 \\ 4 \end{matrix} ][ \begin{matrix}6 4 \\ 4 6 \end{matrix} ][ \begin{matrix}2 \\ 2 \end{matrix} ][ \begin{matrix}2 \\ 2 \end{matrix} ][ \begin{matrix}4 \\ 4 \end{matrix} ][ \begin{matrix}5 2 3 4 \\ 2 3 4 5 \end{matrix} ][ \begin{matrix}6 5 4 \\ 5 4 6 \end{matrix} ][ \begin{matrix}4 \\ 4 \end{matrix} ][ \begin{matrix}6 1 3 \\ 1 3 6 \end{matrix} ][ \begin{matrix}1 \\ 1 \end{matrix} ];

(e) take the inverse of each true cycle, i.e., exchange top and bottom words within each true cycle :

[ \begin{matrix}5 6 \\ 6 5 \end{matrix} ][ \begin{matrix}6 \\ 6 \end{matrix} ][ \begin{matrix}4 \\ 4 \end{matrix} ][ \begin{matrix}4 6 \\ 6 4 \end{matrix} ][ \begin{matrix}2 \\ 2 \end{matrix} ][ \begin{matrix}2 \\ 2 \end{matrix} ][ \begin{matrix}4 \\ 4 \end{matrix} ][ \begin{matrix}2 3 4 5 \\ 5 2 3 4 \end{matrix} ][ \begin{matrix}5 4 6 \\ 6 5 4 \end{matrix} ][ \begin{matrix}4 \\ 4 \end{matrix} ][ \begin{matrix}1 3 6 \\ 6 1 3 \end{matrix} ][ \begin{matrix}1 \\ 1 \end{matrix} ];

(f) suppress the brackets in the above product and reorder the columns to get a circuit whose top row is non-decreasing, i.e.,

( \begin{matrix}\overline{w} & 8 \\ w_{8} \end{matrix} ) = ( \begin{matrix}1 1 2 2 2 3 3 4 4 4 4 4 4 5 5 5 6 6 6 6 6 \\ 6 1 2 2 5 2 1 4 6 4 3 5 4 6 4 6 5 6 4 4 3 \end{matrix} ) .

The bottom word is by definition Ψ^{k}(v).

It is readily verified that exc_{k} w_{7} = exc^{k} w_{6}, and so des^{k} v = des_{k} w_{6} = exc_{k} Ψ_{k}(w_{6}) (= exc_{k} w_{7}) = exc^{k} w_{8} = exc^{k} Ψ^{k}(v). In the running example all those quantities are equal to 12.

Thus (3.4) is verified and identity (3.3) holds.

4. The proofs of (1.6) - (1.9). — Identity (1.6) is a consequence of (2.3) and (3.2).

For the proof of (1.7) we proceed as follows. Let des = des_{0} and D = det(I_{r} − B_{0}U). Then (1/D)v_{k} = ∑_{w} t^{des w}u(w)v_{k} by (3.2) for k = 0. As r is the maximum letter of the alphabet, it does not create a descent, if it is placed at the end of a word : des wr = des w. But w ↦ wr is a bijection of the set X^{∗} of all words onto the set X^{∗}r of words ending with r. Therefore,

\frac{1}{D} − \frac{1}{D} v_{k} = ∑_{w} t^{des w}u(w) − ∑_{w} t^{des w}u(w)v_{k}

= ∑_{w} t^{des w}u(w) − ∑_{w} t^{des wr}u(wr) = ∑_{w∈X^{∗}\X^{∗}r} t^{des w}u(w),

where the last summation is over all words not ending with r.

In the same manner, (1/D)tv_{k} is the generating function for words ending with r by “1 + des.” Define

des′ w = \{ \begin{matrix}1 + des w, & if w ends with r; \\ des w, & otherwise. \end{matrix}

Then

(4.1)  \frac{1 − v_{k}(1 − t)}{D} = \frac{1}{D} − \frac{1}{D} v_{k} + \frac{1}{D} tv_{k} = ∑_{w} t^{des′ w}u(w).

Now continue with other factors :

\frac{(1 − v_{k−1}(1 − t))(1 − v_{k}(1 − t))}{D} = (∑_{w} t^{des′ w}u(w))(1 − v_{k−1} + tv_{k−1}).

In the same manner, w ↦ w(r − 1) maps X^{∗} onto the set X^{∗}(r − 1) of all words ending with (r − 1). Furthermore, des′ w = des′ w(r − 1), for, either w ends with r and its last letter is counted as a descent, or w ends with a letter ≤ (r − 1) and no other descent is created. Again,

∑_{w} t^{des′ w}u(w) − ∑_{w} t^{des′ w}u(w)v_{k−1} = ∑_{w∈X^{∗}\X^{∗}(r−1)} t^{des′ w}u(w)

and the factor (∑_{w} t^{des′ w}u(w))tv_{k−1} adds back all the words ending with (r − 1) and an extra descent is to be counted for all those words. Define

des′′ w = \{ \begin{matrix}1 + des′ w, & if w ends with (r − 1) ; \\ des′ w, & otherwise ; \end{matrix}

or, in an equivalent manner,

des′′ w = \{ \begin{matrix}1 + des w, & if w ends with (r − 1), r; \\ des w, & otherwise. \end{matrix}

Then

\frac{1 − v_{k−1}(1 − t)(1 − v_{k}(1 − t))}{D} = ∑_{w} t^{des′′ w}u(w).

More generally, let

(4.2) des^{I} w = \{ \begin{matrix}1 + des w, & if w ends with a large letter ; \\ des w, & if w ends with a small letter ; \end{matrix}

and let

(7.11)  A_{c,d}^{I}(t) = ∑_{w} t^{des^{I} w}  (w ∈ R(c, d)).

Then, by induction, we can prove the identity

(4.3) ∑_{c,d} u^{c}v^{d}A_{c,d}^{I}(t) = (1−t) A^{I}(u(1−t), v(1−t), t) = \frac{(1 − v(1 − t))}{det(I_{r} − B_{0}U)},

i.e., we have proved (1.7).

Next, 1/(det(I_{r}−B_{r}U)) is the generating function for X^{∗} by “des_{r}” and the statistic “des_{r}” always includes one descent at the end of each nonempty word w. In the same manner, the product (1 − tu_{1} + u_{1}) … (1 − tu_{j} + u_{j}) may be regarded as an operator that kills the ultimate descent in each non-empty word, if the last letter is small.

Hence if we let

A_{c,d}^{II}(t) = ∑_{w} t^{des^{II}} w (w ∈ R(c, d)),

the following identity holds

∑_{c,d} u^{c}v^{d}A_{c,d}^{II}(t) = (1 − t) A^{II}(u(1 − t), v(1 − t), t) = \frac{(1 + u(1 − t))}{det(I_{r} − B_{r}U)},

i.e., identity (1.8) is proved.

Now 1/ det(I_{r} −B′_{j}U) = ∑_{w} t^{des^{j} w}u(w). The numerator of the fraction on the right-hand side of (2.6) is an operator that kills a descent at the beginning of a non-empty word w, if its first letter is small, but adds a descent at the end if its last letter is large.

Let

A_{c,d}^{III}(t) = ∑_{w} t^{des^{III}} w (w ∈ R(c, d))

Then the following identity holds :

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

and this proves (1.9).

5. Excedance statistics. — The final problem is to associate excedance statistics to those descent statistics. We will only do it for des^{I} and des^{II}. Let Φ = Φ_{0}.

It follows from (3.1) and (1.5)_{I} that

des^{I} w′x = \{ \begin{matrix}1 + des w′x = 1 + exc Φ(w′x) = 1 + exc w_{1}x, & if x is large ; \\ des w′x = exc Φ(w′x) = exc w_{1}x, & if x is small. \end{matrix}

We are then led to define

(5.1)  exc^{I} w = \{ \begin{matrix}1 + exc w, & if the last letter of w is large ; \\ exc w, & if the last letter of w is small. \end{matrix}

We have then proved the following proposition

Proposition 5.1. — The transformation Φ also satisfies exc^{I} Φ(w) = des^{I} w, and consequently

A_{c,d}^{I}(t) = ∑_{w} t^{des^{I} w} = ∑_{w} t^{exc^{I} w} (w ∈ R(c, d)).

Now using (3.6), des^{II} w′x is equal to

\{ \begin{matrix}des_{r} w′x − 1 = exc_{r} Φ_{r}(w′x) − 1 = exc_{r} xw_{2} − 1, & if x is small ; \\ des_{r} w′x = exc_{r} Φ_{r}(w′x) = exc_{r} xw_{2}, & if x is large. \end{matrix}

Again, for each word w = x_{1}x_{2} … x_{m} whose non-decreasing rearrangement is \overline{w} = y_{1}y_{2} … y_{m}, we are led to define

(5.2) exc^{II} w to be the number of i such that 1 ≤ i ≤ m and x_{i} ≥ y_{i}, minus one if x_{1} is small.

We have then the following result.

Proposition 5.2. — The transformation Φ_{r} also satisfies

exc^{II} Φ_{r}(w) = des^{II} w,

and consequently

A_{c,d}^{II}(t) = ∑_{w} t^{des^{II} w} = ∑_{w} t^{exc^{II} w} (w ∈ R(c, d)).

Remark. — Keep the same notations, in particular, consider the letters 1, …, j as being small, and the other letters large. Furthermore, keep the natural ordering on [ r]. When restricted to permutations, the statistics “des^{I},” “des^{II}” “des^{III}” coincide with the definition of “des_{k}.” However “exc_{k},” “exc^{I},” and “exc^{II}” differ from one another. Consequently, Φ_{k}, Φ and Φ_{r} provide three different bijections that map the same “des_{k}” onto three different excedance statistics.

In the following table we have displayed the actions of those three transformations on the elements of S_{3} with one small letter (j = 1) and two large letters 2 and 3 (k = 2) The letters giving rise to excedances in the various cases have been printed in bold-face.

\begin{matrix}w & des_{2} w & Φ_{2} & Φ & Φ_{3} \\ 1, 2, 3 & 1 & 1, 3, 2 & 1, 2, 3 & 3, 1, 2 \\ 1, 3, 2 & 2 & 1, 2, 3 & 1, 3, 2 & 2, 1, 3 \\ 2, 1, 3 & 2 & 2, 3, 1 & 2, 1, 3 & 3, 2, 1 \\ 2, 3, 1 & 1 & 3, 1, 2 & 3, 2, 1 & 1, 3, 2 \\ 3, 1, 2 & 2 & 3, 2, 1 & 3, 1, 2 & 2, 3, 1 \\ 3, 2, 1 & 2 & 2, 1, 3 & 2, 3, 1 & 1, 2, 3 \end{matrix}

REFERENCES

[CaFo69] Pierre Cartier and Dominique Foata. — Problèmes combinatoires de commutation et réarrangements. — Berlin, Springer-Verlag, 1969 (Lecture Notes in Math., 85).

[ClFo94] Robert J. Clarke and Dominique Foata. — Eulerian Calculus, I : univariable statistics, Europ. J. Combinatorics, vol. 15, 1994, p. 345–362.

[ClFo95a] Robert J. Clarke and Dominique Foata. — Eulerian Calculus, II : an extension of Han’s fundamental transformation, Europ. J. Combinatorics, vol. 16, 1995, p. 221–252.

[ClFo95b] Robert J. Clarke and Dominique Foata. — Eulerian Calculus, III : The ubiquitous

Cauchy formula, to appear in Europ. J. Combinatorics, 1995.

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

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