Eulerian Calculus, I : Univariable Statistics†

BY

ROBERT J. CLARKE AND DOMINIQUE FOATA (∗)

Further transformations are derived on the symmetric group and related structures that extend previous works on the equidistributions of several classical univariable statistics. De nouvelles transformations sur le groupe symétrique et les structures parentes sont explicitées et servent à prolonger des travaux antérieurs sur l’équidistribution de plusieurs statistiques classiques à une variable.

1. INTRODUCTION

This paper is the first one of a series of three articles (see [ClFo93b] and [ClFo93c] for the other two), in which we investigate further extensions of the classical Eulerian Calculus that involves, first, the constructions of transformations on the symmetric group and related structures, then, explicit calculations of distributions of order statistics on those structures.

In his treatise on Combinatory Analysis, MacMahon [Mac15] made an extensive study of the distributions of several statistics on permutations, or more generally, on permutations with repeated elements (called permutations on multisets by several authors, but referred to as words in the present paper). He introduced the notions of descents, excedances, major index for finite sequences of numbers and calculated the first generating functions.

Those three notions can be defined as follows: let X^{∗} be the free monoid generated by a totally ordered alphabet X that for convenience we shall take as being the subset [ r] = {1, 2, …, r} (r ≥ 1) of the positive integers with its standard ordering. 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. The set of all the rearrangements of a word w will be denoted by C(w). Such a set necessarily contains a unique word v = y_{1}y_{2} … y_{m} whose letters are in non-decreasing order: y_{1} ≤ y_{2} ≤ ⋯ ≤ y_{m}. There is then a one-to-one correspondence between rearrangement classes and non-decreasing words. It will be convenient to denote by \overline{w} the unique non-decreasing word in the class C(w) [also equal to C(\overline{w})].

† The paper has been published in Europ. J. Combinatorics (1994) 15, 345–263.

(^{∗}) Supported in part by a grant of the Australian Research Council, 1993, while the author was on leave at the University of Adelaide.

Let w = x_{1}x_{2} … x_{m} and let \overline{w} = v = y_{1}y_{2} … y_{m} be its non-decreasing rearrangement. The number of excedances, exc w, and the number of descents, des w, of the word w are classically defined as (see [CaFo69])

exc w = #{i : 1 ≤ i ≤ m, x_{i} > y_{i}},
des w = #{i : 1 ≤ i ≤ m − 1, x_{i} > x_{i+1}},

while the major index, maj w, is the sum of the i’s such that 1 ≤ i ≤ m−1 and x_{i} > x_{i+1}.

MacMahon [Mac15, p. 186] proved that for each rearrangement class C(v) and each integer j there are as many words w ∈ C(v) such that exc w = j as there are words w′ ∈ C(v) such that des w′ = j. To establish the result, he made use of his so-called Master Theorem [Mac15, p. 97], that can be stated as follows (see [CaFo69, chap. V] for a non-commutative version):

Let B = (b(i, j)) (1 ≤ i, j ≤ r) be a square matrix with coefficients in a commutative ring, let X^{∗} be the free monoid generated by X = [ r] and let u_{1}, u_{2}, …, u_{r} be r commutative variables. 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}}2^{c_{2}} … r^{c_{r}}, define

β(w) = b(y_{1}, x_{1})b(y_{2}, x_{2}) … b(y_{m}, x_{m}) and u(w) = u_{1}^{c_{1}}u_{2}^{c_{2}} … u_{r}^{c_{r}}.

Let also U be the diagonal matrix U = diag(u_{1}, u_{2}, …, u_{r}). Then the following identity holds

(1.1)  \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^{∗}.

If v is the non-decreasing word 1^{c_{1}}2^{c_{2}} … r^{c_{r}}, we will also denote the rearrangement class C(v) by R(c) and put u^{c} = u_{1}^{c_{1}}u_{2}^{c_{2}} … u_{r}^{c_{r}}. The rearrangement classes will then be indexed by sequences of non-negative integers c = (c_{1}, c_{2}, …, c_{r}) of length r. (A more refined notation will be used in the sequel.)

When b(i, j) = t, if i < j, and 1 in the other cases, it is readily seen that the monomial β(w) is equal to t^{exc w}. Let then

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

be the generating polynomial for R(c) by the number of excedances “exc.” The generating function for those polynomials is then directly derived from the Master Theorem

(1.2)  \frac{1}{det(I_{r} − BU)} = ∑_{c} u^{c}A_{c}(t),

a result already obtained by MacMahon.

Now the determinant occurring in (1.2) can be further evaluated. An easy calculation shows that

\begin{aligned}det(I_{r} − BU) & = | \begin{matrix}1 − u_{1} & −tu_{2} & … & −tu_{r} \\ −u_{1} & 1 − u_{2} & … & −tu_{r} \\ ⋮ & ⋮ & ... & ⋮ \\ −u_{1} & −u_{2} & … & 1 − u_{r} \end{matrix} | \\ & = 1 − e_{1}(u) + (1 − t)e_{2}(u) − ⋯ + (−1)^{r}(1 − t)^{r−1}e_{r}(u), \end{aligned}

where the e_{i}(u)’s are the elementary symmetric functions in the u_{i}’s. Taking this calculation into account after replacing each u_{i}(1 − t) by u_{i} and substituting into (1.2) leads to the identity

(1.3)  ∑_{s≥0} \frac{t^{s}}{(1 − u_{1})^{s+1} … (1 − u_{r})^{s+1}} = ∑_{c} \frac{u^{c}}{(1 − t)^{c+1}} A_{c}(t),

where c = c_{1} + ⋯ + c_{r}. The expression (1.3) is more appropriate for proving that the left-hand side is actually the generating function for the polynomials A_{c}(t) in the “des”-interpretation. See section 2 in which a calculation is made in a more general case. Those techniques are standard (see, e.g. [Ga79]). In fact, MacMahon proved his result on the equidistribution of “exc” and “des” by obtaining (1.3) in two different ways, in the “exc” and “des” interpretations.

Several years later, a “bijective” proof (as some people say to-day) was devised to prove the MacMahon equidistribution property. The so-called first fundamental transformation Φ of X^{∗} onto itself was constructed (see [CaFo69] and also [Lo83, chap. 10]); it maps each rearrangement class C(v) onto itself, in a bijective manner, and has the property that

(1.4)  exc Φ(w) = des w

holds for every w ∈ C(v).

For each pair of letters (a, b) and each word w = x_{1}x_{2} … x_{m} denote by [a, b](w) the number of subscripts i such that 1 ≤ i ≤ m − 1 and x_{i} = a, x_{i+1} = b. If v = y_{1}y_{2} … y_{m} is the non-decreasing rearrangement of w, denote by \left[{b \atop a}\right](w) the number of subscripts i such that 1 ≤ i ≤ m

and y_{i} = b, x_{i} = a. As was proved in [CaFo69], the first fundamental transformation has the further property that for each pair (a, b) satisfying a > b, the identity

(1.5)  [a, b](w) = \left[{b \atop a}\right] (Φ(w))

holds. Of course property (1.4) is a consequence of (1.5).

A further analysis of the properties of Φ shows that the restriction a > b assumed in (1.5) can be relaxed under certain conditions to include equality a = b. The purpose of this paper is to investigate those conditions. Instead of taking the matrix B as above, having only 1’s on and under the diagonal and t above it, choose two non-negative integers j and k such that j + k = r. Then form the matrix B_{k} of order r still having only 1’s under the diagonal and only t’s above, but let its diagonal, diag B_{k}, be made of j 1’s, followed by k t’s, i.e.,

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

The monomial β(w) = b(y_{1}, x_{1}) … b(y_{m}, x_{m}) attached to the word w = x_{1} … x_{m} in the Master Theorem is then a power of t, say, t^{exc_{k} w}, where

(1.7) exc_{k} 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 + 1.

A refined definition will be given further in the paper. The following two questions arise: what statistic, say “des_{k},” must be defined on X^{∗} that has the same distribution as “exc_{k}” on each rearrangement class C(v) and that reduces to “des” when k = 0? Suppose that such a statistic can be defined in simple terms (it can!) and has such a property. The second question is how a transformation Φ_{k} on X^{∗} can be constructed that maps each rearrangement class onto itself and satisfies the identity

(1.8)  des_{k} w = exc_{k} Φ_{k}(w).

In section 2 we show that a calculation à la MacMahon first suggests the definition of the appropriate statistic “des_{k},” that can be stated as:

(1.9) des_{k} w is the number of i such that 1 ≤ i ≤ m and either x_{i} > x_{i+1}, or x_{i} = x_{i+1} and x_{i} ≥ j + 1. (By convention, x_{m+1} = j + \frac{1}{2}.)

Section 2 also provides an answer to the first question by proving that the generating polynomials for each rearrangement class C(v) by either “exc_{k},” or “des_{k},” are the same.

In fact, there are several statistics “des_{k,D}” and “exc_{k,D}” that can be defined and for which property (1.8) holds, depending on different total orders D we may impose on the interval [ r]. This leads to proving invariance principles that essentially say that the distributions of all those statistics “des_{k,D}” and “exc_{k,D}” are independent of the ordering D. All this is the object of section 3 (see Theorems 3.1 and 3.2).

In section 4 we recall the construction of the first fundamental transformation Φ. Section 5 contains the main result of the paper, i.e., the construction of a transformation Φ_{k} that satisfies identity (1.8). In fact, the construction can be made for each pair (des_{k,D}, exc_{k,D}), as long as the ordering D is compatible with k, a notion that will be further defined.

In section 6 we specialize our results to the case of permutations. When c_{1} = ⋯ = c_{r} = 1, the polynomial

∑_{w} t^{des w} = ∑_{w} t^{exc w} (w ∈ R(c))

is the usual Eulerian polynomial A_{r}(t) of order r (see, e.g., [Ri58, FoSc70]). When “des” or “exc” are replaced by “des_{k}” or “exc_{k},” the generating polynomial A_{r}^{k}(t) thereby obtained appears to be a natural interpolation between A_{r}(t) and t A_{r}(t). We have managed to give several explicit formulas for those polynomials. Steingrìmsson [Ste93] has also generalized the definitions of “des” and “exc” from permutations to so-called “indexed permutations”, i.e., elements of the wreath product Z_{k} ≀ S_{n}. As shown in section 6, his model coincides partly with ours in this permutation case.

In the two subsequent papers we consider joint statistics, and especially, will study the joint behaviours of “des_{k}” with a new major index “maj_{k},” and “exc_{k}” with another new mahonian statistic “den_{k}.” We will also calculate the distributions of those joint statistics using the algebra of symmetric functions.

The following notations will be used throughout. Let r be a positive integer, let X = [ r] and let k be a fixed integer, 0 ≤ k ≤ r. Put j = r − k. Let c = (c_{1}, …, c_{j}) and d = (d_{1}, …, d_{k}) be two vectors with positive integer components. Let c = c_{1} + ⋯ + c_{j}, d = d_{1} + ⋯ + d_{k} and c + d = m. We will work with the rearrangement class R(c, d) 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}}. We call the letters 1, …, j small and the letters j + 1, …, r large. It is convenient to adjoin to the set X one element ⋆ that is small but greater than any other small letter.

2. A CALCULATION A LA MACMAHON

In this section we take the natural ordering on X = [ r]. If w = x_{1}x_{2} … x_{m} is a word of the rearrangement class R(c, d), then “exc_{k}” refers to the definition stated in (1.7). It will be convenient to replace the variables u_{j+1}, …, u_{r} by v_{1}, …, v_{k} and write u^{c} for u_{1}^{c_{1}} … u_{j}^{c_{j}} and v^{d} for v_{1}^{d_{1}} … v_{k}^{d_{k}}. However we keep the notation U for the matrix U = diag(u_{1}, …, u_{j}, v_{1}, …, v_{k}). Now let

(2.1)  A_{c,d}(t) = ∑_{w} t^{exc_{k} w}  (w ∈ R(c, d)),

be the generating polynomial for the class R(c, d) by “exc_{k}.” We have seen in the introduction that the generating function for those polynomials was simply

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

where B_{k} is the matrix defined in (1.6).

LEMMA 2.1. The following identity holds

(2.3) det(I_{r} − B_{k}U) = 1 + ∑_{i=1}^{j}(−1)^{i}(1 − t)^{i−1}e_{i}(u_{1}, …, u_{j})

− ∑_{i=1}^{k} t(1 − t)^{i−1}e_{i}(v_{1}, …, v_{k}),

where the e_{i}’s stand for the elementary symmetric functions in the variables between parentheses.

Proof. First

det(I_{r} − B_{k}U) = 1 + ∑_{i=1}^{r}(−1)^{i} ∑_{1≤l_{1}<···<l_{i}≤r} u_{l_{1}} … u_{l_{i}} det(b(l, l′))_{(l,l′∈{l_{1},...,l_{i}})},

by letting u_{j+1} = v_{1}, …, u_{r} = v_{k}. Secondly notice that the determinant det(b(l, l′))_{(l,l′∈{l_{1},...,l_{i}})} is zero, if {l_{1}, …, l_{i}} has a non-empty intersection with both the intervals [1, j] and [j + 1, r], is equal to (1 − t)^{i−1}, if 1 ≤ l_{1} < ⋯ < l_{i} ≤ j, and to t(t − 1)^{i−1}, if j + 1 ≤ l_{1} < ⋯ < l_{i} ≤ r.

Now substitute the value (2.3) into identity (2.2), multiply numerator and denominator of the fraction by (1 − t) and make the substitution u_{i}(1 − t) ← u_{i} and v_{i}(1 − t) ← v_{i}. We get (remember that c = c_{1} + ⋯ + c_{j} and d = d_{1} + ⋯ + d_{k}, so that c + d = m)

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

= \frac{1}{(1 − t) + ∑_{i=1}^{j}(−1)^{i}e_{i}(u_{1}, …, u_{j}) − ∑_{i=1}^{k} te_{i}(v_{1}, …, v_{k})}

= \frac{1}{(1 − u_{1}) … (1 − u_{j}) − t(1 + v_{1}) … (1 + v_{k})},

and finally

(2.4)  ∑_{c,d} \frac{u^{c}v^{d}}{(1 − t)^{c+d+1}} A_{c,d}(t) = ∑_{s≥0} t^{s} \frac{(1 + v_{1})^{s} … (1 + v_{k})^{s}}{(1 − u_{1})^{s+1} … (1 − u_{j})^{s+1}} .

Now recurrence relations for the polynomials A_{c,d}(t) can be derived, following a classical pattern (see, e.g., [Ga79]). Let A be the common value of the previous series. Comparing the derivatives D_{v_{k}}A and D_{t}A calculated with the right-hand side of (2.4) leads to the relation

(2.5)  (1 + v_{k})D_{v_{k}}A = t D_{t}A.

Now with the help of the left-hand side of (2.4) the latter identity yields

(2.6) (d_{k} + 1)A_{c,d+1_{k}}(t)

= (t(c + d + 1 + d_{k}) − d_{k})A_{c,d}(t) + t(1 − t)A′_{c,d}(t),

where d + 1_{k} is the sequence (d_{1}, …, d_{k} + 1) and A′_{c,d}(t) is the derivative of A_{c,d}(t). Next let A_{c,d}(t) = ∑_{s} A_{c,d,s}t^{s}. Then (2.6) is equivalent to the recurrence relation

(2.7) (d_{k} + 1)A_{c,d+1_{k},s} = (c + d + d_{k} + 2 − s)A_{c,d,s−1} + (s − d_{k})A_{c,d,s}.

We could as well look for a relation between D_{u_{j}}A and D_{t}A and easily obtain

(2.8) (1 − u_{j})D_{u_{j}}A = t D_{t}A + A, from which we can derive the relations: (2.9) (c_{j} + 1)A_{c+1_{j},d}(t)

= (t(c + d − c_{j}) + c_{j} + 1)A_{c,d}(t) + t(1 − t)A′_{c,d}(t),

(2.10) (c_{j} +1)A_{c+1_{j},d,s} = (c+d+1−s−c_{j})A_{c,d,s−1}+(c_{j} +1+s)A_{c,d,s},

where c + 1_{j} = (c_{1}, …, c_{j−1}, c_{j} + 1).

The two pairs of recurrence relations (2.6), (2.9), on the one hand, and (2.7), (2.10), on the other hand, uniquely determine the polynomials A_{c,d}(t) using the initial condition A_{0,0}(t) = 1 (or A_{0,0,0} = 1 and A_{0,0,s} = 0 for s ≠ 0). Actually, using the two relations (2.5) and (2.8), we can reprove that the left-hand side of (2.4) is precisely equal to the right-hand side.

PROPOSITION 2.2. Let A_{c,d}^{des}(t) be the generating polynomial for R(c, d) by the number of k-descents “des_{k}.” Then

A_{c,d}^{des}(t) = A_{c,d}(t).

Proof. We already know that the coefficients of A_{c,d}(t) satisfy (2.7) and (2.10). We only have to verify that the same holds for the coefficients A_{c,d,s}^{des} of A_{c,d}^{des}(t). But (d_{k} + 1)A_{c,d+1_{k},s}^{des} is the number of words in R(c, d + 1_{k}) with s k-descents having d_{k} letters equal to r, plus one letter, say, equal to ṙ. To generate such a word, we can choose a word in R(c, d) having s k-descents and insert ṙ into any one of the (s − d_{k}) k-descents that do not begin with r. Exactly (s − d_{k})A_{c,d,s}^{des} words can be obtained by such an insertion.

The other possibility is to take a word in R(c, d) having (s − 1) kdescents and insert ṙ into each of the slots that is not a k-descent (there are exactly (c + d − (s − 1)) such slots) and also after each letter r and at the end of the word (there are exactly (d_{k} + 1) such slots). Altogether, (c + d + d_{k} + 2 − s)A_{c,d,s−1}^{des} words in R(c, d + 1_{k}) with a single dotted ṙ can be obtained in this way. This shows that the coefficients A_{c,d,s}^{des} also satisfy (2.8).

The same technique applies to identity (2.10).

REMARK. Let σ (resp. τ) be a permutation of {1, 2, …, j} (resp. of {1, …, k}). Denote by σc and by τd the sequences (c_{σ1}, …, c_{σj}) and (d_{τ1}, …, d_{τk}), respectively, and by R(σc, τd) the class of all the rearrangements of the word 1^{c_{σ1}} … j^{c_{σj}}(j + 1)^{d_{τ1}} … r^{d_{τk}}. As formula (2.4) is symmetric in the u_{i}’s and in the v_{i}’s, the two polynomials A_{c,d}(t) and A_{σc,τd}(t) are identical. (The result will be proved combinatorially in Theorem 3.1.) In the next table we have then only displayed the values of the polynomials A_{c,d}(t) when c and d are partitions, i.e., non-increasing sequences.

A short table for the polynomials A_{c,d}(t): A_{(0),(0)}(t) = 1, A_{(1),(0)}(t) = 1, A_{(0),(1)}(t) = t, A_{(2),(0)}(t) = 1, A_{(1,1),(0)}(t) = 1+t, A_{(1),(1)}(t) = 2t, A_{(0),(1,1)}(t) = t+t^{2}, A_{(0),(2)}(t) = t^{2}, A_{(3),(0)}(t) = 1, A_{(2,1),(0)}(t) = 1 + 2t, A_{(1,1,1),(0)}(t) = 1 + 4t + t^{2}, A_{(2),(1)}(t) = 3t, A_{(1,1),(1)} = 4t + 2t^{2}, A_{(1),(1,1)}(t) = 2t + 4t^{2}, A_{(1),(2)}(t) = 3t^{2}, A_{(0),(1,1,1)}(t) = t + 4t^{2} + t^{3}, A_{(0),(2,1)}(t) = 2t^{2} + t^{3}, A_{(0),(3)}(t) = t^{3}.

3. INVARIANCE PRINCIPLES

Let D be a total ordering on [ r]. We say that D is compatible with k if, for all x large and y small, we have x >_{D} y. Again let w = x_{1}x_{2} … x_{m} ∈ X^{∗} and \overline{w} = v = y_{1}y_{2} … y_{m} be its non-decreasing rearrangement. We say that w has a k-excedance at i (1 ≤ i ≤ m), if either x_{i} > y_{i}, or x_{i} = y_{i} and x_{i} is large. We also say that w has a k-descent at i (1 ≤ i ≤ m), if either x_{i} > x_{i+1}, or x_{i} = x_{i+1} and x_{i} is large. (By convention, x_{m+1} = ⋆.) Note that there is a descent at m if x_{m} is large.

The number of k-excedances and k-descents of a word w will be denoted by exc_{k} w and des_{k} w, respectively. We will sometimes use the notations exc_{k,D} and des_{k,D} if we need to draw attention to the ordering D.

For example, if X = [ 3 ], D is the standard ordering and w is the word w = 3, 2, 2, 1, 1, 2 then des_{0} w = 2 = des_{1} w, des_{2} w = 4, des_{3} w = 5. As \overline{w} = 1, 1, 2, 2, 2, 3, exc_{0} w = exc_{1} w = 2, exc_{2} w = exc_{3} w = 3.

THEOREM 3.1. Let D and E be total orderings of [ r] compatible with k. Then there is a bijection χ of R(c, d) onto itself such that for all w ∈ R(c, d),

des_{D} w = des_{E} χ(w).

THEOREM 3.2. Let D and E be total orderings of [ r], not necessarily compatible with k. Then there is a bijection θ of R(c, d) onto itself such that for all w ∈ R(c, d),

exc_{D} w = exc_{E} θ(w).

Note that Theorem 3.1 is not true without the assumption of compatibility. For example, let r = 2, k = 1 and consider R((1), (1)), the rearrangement class of v = 1, 2. Note that 1 is small and 2 is large. Let 2 >_{D} 1, 1 >_{E} 2. Then D is compatible with k, but E is not. Now

des_{D} 1, 2 = des_{D} 2, 1 = exc_{D} 1, 2 = exc_{D} 2, 1 = 1,

but

des_{E} 1, 2 = 2, des_{E} 2, 1 = 0, exc_{E} 1, 2 = exc_{E} 2, 1 = 1.

Proof of Theorem 3.1. Suppose first that a, b are letters in [ r] such that a >_{D} b and that there is no letter x in X such that a >_{D} x >_{D} b (i.e., a covers b.) We assume that E is obtained from D by reversing the order of a and b. (We may say that E is obtained from D by a transposition.) Since both D and E are compatible with k, either both a and b are large or both are small.

Given a word w ∈ R(c, d), write w = u_{1}v_{1} … u_{m}v_{m}, where each u_{i} contains only the letters a and b, and each v_{i} does not contain any a or b. Let u′_{i} be the word obtained from u_{i} by reversing the order of its letters. Accordingly, if u_{i} = z_{1}z_{2} … z_{s}, then u′_{i} = z_{s} … z_{2}z_{1}. Put w′ = u′_{1}v_{1} … u′_{r}v_{r}. Since [b, a](w′) = [a, b](w), [a, a](w′) = [a, a](w) and [b, b](w′) = [b, b](w), while for any letters x, y other than a and b, [a, x](w′) + [b, x](w′) = [a, x](w) + [b, x](w) and [x, a](w′) + [x, b](w′) = [x, a](w) + [x, b](w) and also [x, y](w′) = [x, y](w), we see that

des_{D} w = des_{E} w′.

Hence we may define χ(w) = w′. It is clear that χ is a bijection, as one may easily write down its inverse.

In the general case, if D and E are any orderings on X that are compatible with k, one can obtain E from D by a sequence of transpositions. This completes the proof of Theorem 3.1.

Before proving Theorem 3.2, we introduce some more notation. If w and v are words, the two-rowed matrix \binom{v}{w} is called a biword. It is a circuit if v is a rearrangement of w. When calculating excedances, it is often convenient to consider the circuit w̃ = \binom{v}{w}, where v is the non-

decreasing rearrangement of w. A cycle is a circuit \binom{δw}{w} such that δw is

the right to left cyclic shift of w, i.e., w = x_{1} … x_{n} and δw = x_{2} … x_{n}x_{1}.

We will write this cycle as [x_{1}, x_{2}, …, x_{n}]. A true cycle is a cycle \binom{δw}{w}

in which no letter of w is repeated.

Multiplication of biwords \binom{v}{w} is defined to be juxtaposition. We as-

sume that the biwords \binom{v}{w} and \binom{v′}{w′} commute if v and v′ have no letters

in common. With these definitions, it was shown in [CaFo69] that every circuit can be written as a product of true cycles, and that the factorization is unique except for the order of the factors. More precisely (see [CaFo69, chapter 4, proposition 4.1]), if a circuit factorizes into two different true cycle products, say α_{1}α_{2} … α_{s} and β_{1}β_{2} … β_{t}, then s = t and we can go from the first product to the second one by finitely many steps consisting of permuting in a product two consecutive true cycles having no letters in common. Furthermore, there is an algorithm that transforms each circuit into a product of true cycles. Note of course that there may be more than one way of writing the same cycle. For example, the cycles

[1, 2, 3] = ( \begin{matrix}2 3 1 \\ 1 2 3 \end{matrix} ) and [2, 3, 1] = ( \begin{matrix}3 1 2 \\ 2 3 1 \end{matrix} ) are the same.

As an example of factorization, let w = 3, 1, 1, 4, 3, 2, 3, 2, 5, 4, 2, 3, 2, 2.

Then

w̃ = \binom{\overline{w}}{w} = ( \begin{matrix}1 1 2 2 2 2 2 3 3 3 3 4 4 5 \\ 3 1 1 4 3 2 3 2 5 4 2 3 2 2 \end{matrix} )

= ( \begin{matrix}1 2 3 \\ 3 1 2 \end{matrix} | {1 \atop 1} | \begin{matrix}2 5 3 4 \\ 4 2 5 3 \end{matrix} | {3 2 4 \atop 4 3 2} | \begin{matrix}2 \\ 2 \end{matrix} | \begin{matrix}2 3 \\ 3 2 \end{matrix} )

= [3, 1, 2][1][4, 2, 5, 3][4, 3, 2][2][3, 2],

which is a product of true cycles. (The algorithm is explained in detail in [CaFo69].)

Proof of Theorem 3.2. As in the proof of Theorem 3.1, we may assume that a, b are letters in [ r] such that a >_{D} b and a covers b. We assume that E is obtained from D by reversing the order of a and b. Note that in this case neither D nor E are assumed to be compatible with k, so we do not assume that a and b are both large or both small.

Let w be a word in C(v). Factorize the circuit w̃ into true cycles:

w̃ = α_{1}α_{2} … α_{m}.

Consider the cycle α_{i}. If the letters a and b do not both occur in this cycle then put α′_{i} = α_{i}. If the letters a and b do both occur in α_{i} then let α′_{i} be the cycle obtained from α_{i} by interchanging a and b. Let w̃′ be the product of the cycles α′_{i}. Finally, reorder the columns of w̃′ (remembering

that columns \binom{x}{y} and \binom{x′}{y′} commute if x ≠ x′) to get the circuit \binom{v′}{w′},

where v′ is the non-decreasing rearrangement of w′ (in the ordering E). Then define θ(w) = w′.

The following relations hold :

\left[{b \atop a}\right] (w′) = \left[{a \atop b}\right] (w), \left[{a \atop a}\right] (w′) = \left[{a \atop a}\right] (w), \left[{b \atop b}\right] (w′) = \left[{b \atop b}\right] (w);

furthermore, for any letters x and y other than a and b, we have

\left[{a \atop x}\right] (w′) + \left[{b \atop x}\right] (w′) = \left[{a \atop x}\right] (w) + \left[{b \atop x}\right] (w),

\left[{x \atop a}\right] (w′) + \left[{x \atop b}\right] (w′) = \left[{x \atop a}\right] (w) + \left[{x \atop b}\right] (w)

and

\left[{x \atop y}\right] (w′) = \left[{x \atop y}\right] (w).

It follows that exc_{D} w = exc_{E} w′.

For example, let w = 3, 1, 2, 1, 3, 3, 3, 2, 2, 4, 5, 2, 2, 4. Then as before

w̃ = \binom{\overline{w}}{w} = [3, 1, 2][1][4, 2, 5, 3][4, 3, 2][2][3, 2].

Let a = 2, b = 3. Then

\begin{aligned}w̃′ = [2, 1, 3][1][4, 3, 5, 2][4, 2, 3][2][2, 3] & = ( \begin{matrix}1 3 2 1 3 5 2 4 2 3 4 2 3 2 \\ 2 1 3 1 4 3 5 2 4 2 3 2 2 3 \end{matrix} ) \\ & = ( \begin{matrix}1 1 3 3 3 3 2 2 2 2 2 4 4 5 \\ 2 1 1 4 2 2 3 5 4 2 3 2 3 3 \end{matrix} ) , \end{aligned}

so w′ = 2, 1, 1, 4, 2, 2, 3, 5, 4, 2, 3, 2, 3, 3.

4. THE FIRST FONDAMENTAL TRANSFORMATION

As in [Lo83, chap. 10] the construction of Φ may be described as follows.

(a) Start with a word w = x_{1}x_{2} … x_{m} ∈ C(v) and form its left to right dominated factorization w = w_{1}w_{2} … w_{p}. The factors w_{1}, w_{2}, …, w_{p} of that factorization are dominated, in the sense that each w_{i} starts with its maximum letter, say a_{i}, and no other letter is equal to a_{i} in the factor. Furthermore, when reading those first letters from left to right, they form a non-decreasing sequence: a_{1} ≤ a_{2} ≤ ⋯ ≤ a_{p}.

For instance, the left to right dominated factorization of the following word is indicated by vertical bars:

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

Notice that the first letters are increasing: 3 ≤ 5 ≤ 5 ≤ 5 ≤ 6 ≤ 6.

(b) The next step consists of forming a second word Δw = δw_{1} … δw_{p}, where each δw_{i} is the right to left cyclic shift of w_{i}, as defined in the previous section. By means of the words Δw and w we set up the biword

\binom{Δw}{w}. With our example

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

(c) In the following stage the two-row columns of \binom{Δw}{w} are rear-

ranged in such a way that the top row is non-decreasing. When making the rearrangement we adopt the previous commutation rules:

(4.1)  ( \begin{matrix}a \\ b \end{matrix} ) ( \begin{matrix}c \\ d \end{matrix} ) = ( \begin{matrix}c \\ d \end{matrix} ) ( \begin{matrix}a \\ b \end{matrix} ) ,  iff a ≠ c.

In particular, two two-row columns with identical top entries cannot commute. Again working with the same example leads to the biword:

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

(e) By definition the bottom word of this last two-row matrix is the transformed word Φ(w). Its excedances have been printed in bold-face and they correspond, in a one-to-one manner, with the descents of w that are: 31, 52, 32, 21, 61.

5. THE CONSTRUCTION OF Φk

First, assume that the total ordering on [ r] is the natural ordering. We then construct a bijection Φ_{k} of each rearrangement class R(c, d) onto itself such that for all w ∈ R(c, d),

(5.1)  des_{k} w = exc_{k} Φ_{k}(w).

When k = 0, it suffices to take Φ_{k} = Φ (the first fundamental transformation), since des_{k} = des and exc_{k} = exc in such a case. Suppose that 1 ≤ k ≤ r and consider a word w = x_{1}x_{2} … x_{m} ∈ C(v) = R(c, d). The construction of Φ_{k}(w) is made in several steps (the reader is advised to follow the successive steps with the help of the example given just after this present description) :

(a) Add ⋆ at the end of w.

(b) Consider the left to right dominated factorization of w⋆ and for a reason that will be evident hereafter denote it by

w⋆ = | a_{1}u_{1} | … | a_{p}u_{p} | b_{1}v_{1,1} | b_{1}v_{1,2} | … | b_{1}v_{1,m_{1}} | … | b_{q}v_{q,1} | b_{q}v_{q,2} | … | b_{q}v_{q,m_{q}} | ,

where the a’s and b’s are letters, the u’s and v’s words, such that 1 ≤ a_{1} ≤ ⋯ ≤ a_{p} ≤ j, j + 1 ≤ b_{1} < ⋯ < b_{q} = r and where all letters in u_{i} (resp. v_{i,l}) are less than a_{i} (resp. b_{i}).

(c) Next form the word

w′ = | a_{1}u_{1} | … | a_{p}u_{p} | b_{1}v_{1,m_{1}} | … | b_{1}v_{1,2} | b_{1}v_{1,1} | … | b_{q}v_{q,m_{q}} | … | b_{q}v_{q,2} | b_{q}v_{q,1} | .

Notice the difference between w and w′: we have only changed the orders of the factors beginning with the same large letter.

(d) Then form the biword

\binom{Δw′}{w′} = ( \begin{matrix}u_{1}a_{1} \\ a_{1}u_{1} \end{matrix} | \begin{matrix}… \\ … \end{matrix} | \begin{matrix}u_{p}a_{p} \\ a_{p}u_{p} \end{matrix} | \begin{matrix}v_{1,m_{1}}b_{1} \\ b_{1}v_{1,m_{1}} \end{matrix} | \begin{matrix}… \\ … \end{matrix} | \begin{matrix}v_{1,2}b_{1} \\ b_{1}v_{1,2} \end{matrix} | \begin{matrix}v_{1,1}b_{1} \\ b_{1}v_{1,1} \end{matrix} |

\begin{matrix}… \\ … \end{matrix} | \begin{matrix}v_{q,m_{q}}b_{q} \\ b_{q}v_{q,m_{q}} \end{matrix} | \begin{matrix}… \\ … \end{matrix} | \begin{matrix}v_{q,2}b_{q} \\ b_{q}v_{q,2} \end{matrix} | \begin{matrix}v_{q,1}b_{q} \\ b_{q}v_{q,1} \end{matrix} )

(e) Rearrange the columns of the latter biword in such a way that the top row is non-decreasing, still using the previous commutation rules (4.1). Thereby we obtain Φ(w′):

( \begin{matrix}… \\ Φ(w′) \end{matrix} ) = ( \begin{matrix}1^{c_{1}} & … & j^{c_{j}} & ⋆ & (j + 1)^{d_{1}} & … & r^{d_{k}} \\ w_{1} & … & w_{j} & w_{⋆} & z_{1} & … & z_{k} \end{matrix} ) ,

where w_{1}, …, w_{j}, w_{⋆}, z_{1}, …, z_{k} are words of lengths c_{1}, …, c_{j}, 1, d_{1}, …, d_{k}, respectively. Note that w_{⋆} is equal to the last letter of w.

(f) Now reverse (i.e., take the mirror-image of) each of the words z_{1}, …, z_{k} to obtain z̃_{1}, …, z̃_{k} within the biword

( \begin{matrix}… \\ w′′ \end{matrix} ) = ( \begin{matrix}1^{c_{1}} & … & j^{c_{j}} & ⋆ & (j + 1)^{d_{1}} & … & r^{d_{k}} \\ w_{1} & … & w_{j} & w_{⋆} & z̃_{1} & … & z̃_{k} \end{matrix} );

(g) By construction, ⋆ is the last letter of v_{q,m_{q}}, then becomes the first letter of z_{k}, and, finally, appears as the last letter of z̃_{k} and therefore of w′′. Write z̃_{k} = ỹ_{k}⋆. We can then drop the last letter of the bottom word w′′ of the previous biword and obtain a word of the class R(c, d), which is, by definition, the word Φ_{k}(w). Thus Φ_{k}(w)⋆ = w′′, so that

( \begin{matrix}… \\ Φ_{k}(w) \end{matrix} ) = ( \begin{matrix}1^{c_{1}} & … & j^{c_{j}} & (j + 1)^{d_{1}} … r^{d_{k}} \\ w_{1} & … & w_{j} & w_{⋆}z̃_{1} … ỹ_{k} \end{matrix} ) .

Note that w_{⋆}z̃_{1} is of length (d_{1} + 1) and ỹ_{k} is of length (d_{k} − 1). Accordingly, the bottom word has the required length.

For example, suppose j = 2, k = 4, r = 6 and let w be the word

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

The steps (a) – (g) for w are the following:

(a)  w⋆ =2, 1, 1, 3, 1, 3, 3, 5, 5, 2, 3, 3, 2, 1, 4, 5, 4, 6, 6, 1, 3, ⋆;
(b)  w⋆ = | 2, 1, 1 | 3, 1 | 3 | 3 | 5 | 5, 2, 3, 3, 2, 1, 4 | 5, 4 | 6 | 6, 1, 3, ⋆ |;
(c)  w′ = | 2, 1, 1 | 3 | 3 | 3, 1 | 5, 4 | 5, 2, 3, 3, 2, 1, 4 | 5 | 6, 1, 3, ⋆ | 6 |;
(d) \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) ( \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) ( \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} );
( \begin{matrix}… \\ Φ_{4}(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} ) . (g)

Let us verify that Φ_{k} is a bijection of R(c, d) onto itself. First, steps (a) and (b) make up a bijection of the latter set onto R(c, d)⋆. Next, step (c) maps this new set onto the set, say R′, of all the rearrangements of 1^{c_{1}} … j^{c_{j}}⋆(j + 1)^{d_{1}} … r^{d_{k}} whose first factor (when read from left to right) in its left to right dominated factorization beginning with r ends with ⋆. This step makes up a true bijection, since the forementioned factorization is unique.

Next steps (d) and (e) are nothing but the definition of the bijection Φ. Therefore, Φ maps R′, in a one-to-one manner, onto the set, say R^{(e)}, of rearrangements w^{(e)} such that the d_{k}-th letter of w^{(e)}, when read from right to left is ⋆. Clearly, step (f) is a bijection of R^{(e)} onto R(c, d)⋆ and step (g) is straightforward.

Thus Φ_{k} is a well-defined bijection. All the steps are reversible and rather simple to describe with the exception of the reverse of step (e). However this step is simply the inverse of the first fundamental transformation, a description of which may be found in [Lo83, p. 199].

It remains to verify the property: des_{k} w = exc_{k} Φ_{k}(w). To achieve this goal introduce the following notations. For each word w and each large letter b let rf_{b}(w) = 1, if the single letter word b occurs as a factor in the left to right factorization of w and is the rightmost factor starting with b. Otherwise, let rf_{b}(w) = 0. For instance, with the notations of step (b), rf_{b_{i}}(w⋆) = 1, if and only if v_{i,m_{i}} is empty (1 ≤ i ≤ q). Also with our previous example we have rf_{3}(w⋆) = 1, rf_{4}(w⋆) = rf_{5}(w⋆) = rf_{6}(w⋆) = 0.

When a word is written as a biword \binom{u}{v}, with a non-decreasing top row u (as in steps (e), (f), (g)), let rf_{b} \binom{u}{v} = 1, if the rightmost biletter \binom{x}{y} such that x = b is equal to \binom{b}{b}. Otherwise, let rf_{b} \binom{u}{v} = 0. For instance, rf_{j+i} \binom{...}{w′′} = 1 (in step (f)), if and only if the last letter of the word z̃_{i} is equal to (j + i) (1 ≤ i ≤ k). Also with our previous example we have rf_{3} \binom{...}{w′′} = 1, rf_{4} \binom{...}{w′′} = rf_{5} \binom{...}{w′′} = rf_{6} \binom{...}{w′′} = 0.

Let us examine step by step how the k-descents in w are mapped onto the k-excedences in Φ_{k}(w). To stress the fact that the statistic “exc_{k} w” depends on the “vertical” pairs \binom{x}{y} we will also write exc_{k} \binom{...}{w}. We also make use of the notation introduced just before (1.5).

(a) → (b) : first, note that the k-descents of w are the k-descents of w⋆, as ⋆ cannot create any k-descent at the end. Therefore

des_{k} w = des_{k}(w⋆).

(b) → (d) : when x > y all the k-descents of the form xy in w⋆ (or in w′) occur inside the factors of the left to right dominated factorization.

Therefore

\left[{y \atop x}\right]\binom{Δw′}{w′} = [x, y](w⋆) (whenever x > y).

On the other hand, the number of biletters \binom{b}{b} occurring in \binom{Δw′}{w′} is equal to one plus the number of factors bb in w⋆, if the rightmost factor of w⋆ starting with b is the single letter word b. Otherwise, the former numbers are equal. Thus

\left[{b \atop b}\right]\binom{Δw′}{w′} = [b, b](w⋆) + rf_{b}(w⋆) (b large).

Therefore

exc_{k} \binom{Δw′}{w′} = des_{k}(w⋆) + ∑_{b large} rf_{b}(w⋆).

(d) → (f) : as the biwords \binom{...}{Φ(w′)} and \binom{...}{w′′} in steps (e) and (f) are

derived from \binom{Δw′}{w′} by permuting the columns of the biwords, we have :

exc_{k} \binom{…}{w′′} = exc_{k} \binom{Δw′}{w′},

and therefore

(5.2)  exc_{k} \binom{…}{w′′} = des_{k}(w⋆) + ∑_{b large} rf_{b}(w⋆).

(f) → (g) : first, we have the relations

(5.3)  rf_{b} \binom{…}{w′′} = rf_{b}(w⋆)  (b large),

because if the rightmost factor of w⋆ starting with b is a single letter word, the leftmost factor starting with b in w′ is b. Hence the leftmost biletter \binom{x}{y} in \binom{Δw′}{w′} such that x = b is \binom{b}{b} (step (d)). It is also true in \binom{...}{Φ(w′)} (step (e)), when the commutation rules (4.1) are applied. Therefore rf_{b} \binom{...}{w′′} = 1 (step (f)). In the same manner rf_{b} \binom{...}{w′′} = 0, if rf_{b}(w⋆) = 0.

It remains to examine the effect of the (g)-shift on the biword \binom{...}{w′′}. If y is small and different from ⋆, each column of the form \binom{y}{x} remains alike in step (g) (no shift in the first (c_{1} + ⋯ + c_{j}) columns), so that all the k-excedences in those columns are preserved.

Next the column \binom{⋆}{w_{⋆}} in \binom{...}{w′′} is mapped onto the column \binom{j+1}{w_{⋆}} in \binom{...}{Φ_{k}(w)}. Hence that column provides a k-excedence, iff \binom{⋆}{w_{⋆}} was one.

Finally, when the shift is made on the rightmost (d_{1} +⋯+d_{k}) columns, all the k-excedences are preserved, except those of the form \binom{b}{b} followed by a column of the form \binom{(b+1)}{x}. The column \binom{b}{b} is transformed into \binom{(b+1)}{b} and the k-excedence is killed by the shift. By definition of “rf_{b}” the number of those columns is exactly ∑ rf_{b} \binom{...}{w′′} (b large). Therefore

(5.4)  exc_{k} \binom{…}{Φ_{k}(w)} = exc_{k} \binom{…}{w′′} − ∑_{b large} rf_{b} \binom{…}{w′′}.

From (5.2), (5.3) and (5.4) we then conclude that

exc_{k} \binom{…}{Φ_{k}(w)} = des_{k}(w⋆) = des_{k} w.

Let D be a total ordering of [ r] compatible with k. By means of the present transformation Φ_{k} and the bijections derived in Theorems 3.1 and 3.2 we can set up a bijection of R(c, d) that maps the statistic “des_{D}” onto “exc_{D}.” Thus the following theorem is proved.

THEOREM 5.1. Let D be a total ordering of [ r] compatible with k. Then there is a bijection Φ_{k} of R(c, d) onto itself such that for all w ∈ R(c, d),

des_{D} w = exc_{D} Φ_{k}(w).

REMARK. By examining the forementioned argument in detail we see that the transformation Φ_{k} satisfies the identity

(5.5)  \left[{y \atop x}\right]\binom{…}{Φ_{k}(w)} = [x, y](w⋆)  (x > y, y small),

and also the following property :

If the last letter w_{⋆} of w is small, then for every large letter x :

(5.6)  ∑_{y} \left[{y \atop x}\right]\binom{…}{Φ_{k}(w)} = ∑_{y}[x, y](w)  (y large ≤ x).

If w_{⋆} is large, identity (5.7) always holds for every large letter x different from w_{⋆}. When x = w_{⋆}, (5.7) must be replaced by :

(5.7)  1 + ∑_{y} \left[{y \atop x}\right]\binom{…}{Φ_{k}(w)} = ∑_{y}[x, y](w)  (y large ≤ x).

Let us illustrate the latest result by means of the example already used in this section. Define the matrix D_{k}(w) as the r × r-matrix whose (y, x)- entry (y row index and x column index) is the number [x, y](w), except for the (y = j + 1, x = w_{⋆})-entry that is equal to 1 + [x, y](w). Also define E_{k}(w) to be the r×r-matrix whose (y, x)-entry (y row index and x column index) is the number \left[{y \atop x}\right](w).

Then (5.5) says that the entries in the cells (y, x) with 1 ≤ y ≤ j and y < x in the matrices D_{k}(w) and E_{k}(Φ_{k}(w)) coincide (i.e., the entries in the shape ). Identities (5.6) and (5.7) say that only the column sums in the areas (j + 1 ≤ y ≤ x) of the two matrices D_{k}(w) and E_{k}(Φ_{k}(w))

coincide (i.e., the entries in the shape ).

The two matrices D_{4}(w) and E_{4}(Φ(w)) resulting from the previous example are shown below.

[figure: x; y; D_{4}(w) =; 1 2 1 0 0 1 0 0 1 0 1 0 3 1 3 0 0 0 1 0 0 0 1 0 0 0 1 1 1 0 0 0 0 1 0 1 3 0 2 1; x; y; E_{4}(Φ_{4}(w)) =; 1 2 1 0 0 1 1 0 1 0 1 0 2 1 3 0 0 0 1 0 1 0 0 0 0 0 0 1 2 0 0 0 0 1 0 1 3 0 2 1]

6. THE PERMUTATION CASE

Suppose c_{1} = ⋯ = c_{j} = 1, d_{1} = ⋯ = d_{k} = 1 and still j + k = r. Then the rearrangement class R(c, d) becomes the symmetric group S_{r} of order r. As the length l(d) of d is k, we will write

A_{c,d}(t) = A_{r}^{k}(t) = ∑_{s=0}^{r} A_{r,s}^{k}t^{s} = ∑_{w} t^{des_{k} w} = ∑_{w} t^{exc_{k} w} (w ∈ S_{r}).

The statistic “des_{k}” applied to each permutation w = x_{1}x_{2} … x_{r} ∈ S_{r} has the following simple form:

(6.1)  des_{k} w = \{ \begin{matrix}des w, & if x_{r} ≤ j; \\ 1 + des w, & if x_{r} ≥ j + 1. \end{matrix}

When k = 0, the polynomial A_{r}^{k}(t) is the usual Eulerian polynomial, denoted by A_{r}(t). Moreover, A_{r}^{r}(t) = t A_{r}(t). As it is well-known (see, e.g., [Ri58, p. 211]), the exponential generating functions for those polynomials are given by

(6.2)  1 + ∑_{r≥1} \frac{u^{r}}{r!} A_{r}(t) = \frac{1 − t}{−t + exp((t − 1)u)};

(6.3)  1 + ∑_{r≥1} \frac{u^{r}}{r!} t A_{r}(t) = \frac{(1 − t) exp(u(t − 1))}{−t + exp((t − 1)u)}.

The “des_{k}” interpretation given above for A_{r}^{k}(t) provides the following recurrence relation for the polynomials A_{r}^{k}(t), namely

(6.4)  A_{r}^{k}(t) = A_{r}^{k−1}(t) + (t − 1)A_{r−1}^{k−1}(t)  (1 ≤ k ≤ r).

For the proof we just have to verify that t A_{r−1}^{k−1}(t) is the generating polynomial for the permutations ending with (j + 1) by “des_{k},” while A_{r}^{k−1}(t) − A_{r−1}^{k−1}(t) is the generating polynomials for the other permutations.

By iteration the recurrence (6.4) leads to:

(6.5) A_{r}^{k}(t) = A_{r}^{0}(t) + \binom{k}{1}(t − 1)A_{r−1}^{0}(t) + \binom{k}{2}(t − 1)^{2}A_{r−2}^{0}(t)

+ ⋯ + \binom{k}{k}(t − 1)^{k}A_{r−k}^{0}(t).

Using the umbral notation A^{r} ≡ A_{r} ≡ A_{r}^{0}(t) and A^{0} ≡ 1, formula (6.5) may be rewritten as

(6.6)  A_{r}^{k}(t) = A^{r−k}((t − 1) + A)^{k}.

The two complementary exponents k and r − k in (6.6) suggest the introduction of the following polynomials in the three variables x, y, t:

(6.7)  A_{r}(x, y, t) = ∑_{k=0}^{r} \binom{r}{k}x^{k}y^{r−k}A_{r}^{k}(t),

so that

(6.8)  A_{r}(x, y, t) = (x(t − 1) + (x + y)A)^{r},  A^{r} ≡ A_{r}.

Now the familiar exponential generating function (6.2) for the Eulerian polynomials may be rewritten as

exp(uA) = \frac{1 − t}{−t + exp((t − 1)u)},

so that

∑_{r≥0} \frac{u^{r}}{r!} A_{r}(x, y, t) = ∑_{r≥0} \frac{u^{r}}{r!} (x(t − 1) + (x + y)A)^{r}

= exp(ux(t − 1)) exp(u(x + y)A)

= \frac{(1 − t) exp(ux(t − 1))}{−t + exp(u(x + y)(t − 1))}

(6.9)  ∑_{r≥0} \frac{u^{r}}{r!} A_{r}(x, y, t) = \frac{(1 − t) exp(uy(1 − t))}{1 − t exp(u(x + y)(1 − t))},

which in its turn specializes to (6.2) and (6.3) for x = 0, y = 1, and x = 1, y = 0, respectively.

For the sake of completeness, we mention several formulas on the polynomials A_{r}(x, y, t) that can be derived from (6.9) or even from the polynomials A_{c,d}(t) of section 2 by various (and classical) methods. First, let

A_{r}(x, y, t) = ∑_{s=0}^{r} A_{r,s}(x, y)t^{s},

so that

(6.10)  A_{r,s}(x, y) = ∑_{k} \binom{r}{k}x^{k}y^{r−k}A_{r,s}^{k}.

Then, a standard calculation (see, e.g., [Ri58, p. 39]) transforms (6.9) into

(6.11)  \frac{A_{r}(x, y, t)}{(1 − t)^{r+1}} = ∑_{s≥0} t^{s}(xs + y(1 + s))^{r}.

Formula (6.11) has an inverse formula, usually called the Worpitzky identity (see, e.g., [Ri58, p. 236])

(6.12)  ∑_{i=0}^{r} \binom{z + i}{r}A_{r,i}(x, y) = (xz + y(1 + z))^{r},

that can be derived from (6.11) by expanding (1 − t)^{r+1}:

∑_{s} A_{r,s}t^{s} ∑_{l} \binom{r + l}{r}t^{l} = ∑_{s≥0} t^{s}(xs + y(1 + s))^{r}

and by looking for the coefficients of the same power of t in both members.

Now the recurrence formulas (2.7) and (2.10) for the coefficients of the polynomials A_{c,d}(t) specialize to

(6.13)  A_{r,s}^{k} = (r − s + 1)A_{r−1,s−1}^{k−1} + sA_{r−1,s}^{k−1};
(6.14)  A_{r,s}^{k} = (r − s)A_{r−1,s−1}^{k} + (s + 1)A_{r−1,s}^{k}.

In their turn, those two formulas imply (easy derivation)

(6.15) A_{r,s}(x, y) = ((r − s + 1)x + (r − s)y)A_{r−1,s−1}

+ (sx + (s + 1)y)A_{r−1,s}(x, y),

a formula that can also be expressed as: (6.16) A_{r}(x, y, t) = (y(1 + (r − 1)t) + xrt)A_{r−1}(x, y, t)

+ t(1 − t)(x + y)A′_{r−1}(x, y, t).

REMARK 1. Notice that (6.16) was derived from the recurrence formulas (2.7) and (2.10) that were given true combinatorial interpretations in terms of “des_{k}.” It is also possible to derive the exponential generating function for the polynomials A_{r}(x, y, t), say A = A(u), given in (6.9), from (6.16) by using the same method that was utilized in section 2. In fact, (6.16) is equivalent to the differential equation

yA + t(x + y)D_{t}A = D_{u}A,

whose solution in A is precisely given by (6.9).

REMARK 2. The exponential generating function (6.9) has already been derived by several authors: Stembridge [Stem91], Steingrìmsson [Ste93] and apparently Brenti [Br93] in a paper to come. They all have worked in a different context from the one discussed in this paper.

Steingrìmsson [Ste93] has recently generalized the definitions of “des” and “exc” from permutations to so-called “indexed permutations”, i.e., elements of the wreath product Z_{n} ≀ S_{r}, where Z_{n} stands for the group of the integers mod n. The elements of Z_{n} ≀ S_{r} are pairs (w, p), where w ∈ S_{r} and p is a mapping of [ r] into Z_{n}. In his model, a indexed permutation (w, p) has a descent at i, if 1 ≤ i ≤ r, and if, either p(i) > p(i + 1), or p(i) = p(i + 1) and x_{i} > x_{i+1}. (By convention, x_{r+1} = r + 1 and p(r + 1) = 0.) The indexed permutation (w, p) has an excedance at i, if, either x_{i} > i, or x_{i} = i and p(i) ≥ 1.

He does construct a bijection of Z_{n} ≀ S_{r} onto itself that maps his “des” onto his “exc.” For each mapping p let Pos p = {x ∈ Z_{n} : p(x) ≥ 1}. Steingrìmsson shows that if #Pos p = #Pos p′, then the two polynomials ∑_{w} t^{des(w,p)} and ∑_{w} t^{des(w,p′)} (w ∈ S_{r}) are identical. When p(x) = 0 for x ≤ j = r−k and p(x) ≥ 1 for j+1 ≤ x ≤ r, the corresponding polynomial ∑_{w} t^{des(w,p)} is equal to our polynomial A_{r}^{k}(t), since des(w, p) = des_{k} w in this case.

The generating polynomial D_{r}^{n}(t) for Z_{n} ≀ S_{r} by “des” can then be evaluated as follows

D_{r}^{n}(t) = ∑_{w,p} t^{des(w,p)} = ∑_{k=0}^{r} ∑_{p, #Pos p=k} ∑_{w} t^{des(w,p)}

= ∑_{k=0}^{r} A_{r}^{k}(t) × #\{p : Pos p = k\} = ∑_{k=0}^{r} A_{r}^{k}(t)\binom{r}{k}(n − 1)^{k}

= A(x, y, t) |{x = n − 1, y = 1} .

Notice that the indexed permutation model coincides partly with ours in the permutation case and has not been extended to the case of arbitrary words (with repetitions). However we give credit to Steingrìmsson to have stated and proved analogues of our theorems 3.1, 3.2 and 5.1 in his indexed permutation set-up.

AACKNOWLEDGEMENT. The authors should like to thank Guo-Niu Han for a careful reading of a former version of the paper and for his helpful remarks.

REFERENCES

[Br93] F. Brenti. Combinatorial properties of Betti numbers of some toric varieties, In-

situt Mittag-Leffler, Report no. 9, 1991-1992.

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

[ClFo93b] Robert J. Clarke and Dominique Foata. Eulerian Calculus, II: An extension of Han’s fundamental transformation, preprint, 1993.

[ClFo93c] Robert J. Clarke and Dominique Foata. Eulerian Calculus, III: the ubiquitous Cauchy formula, preprint, 1993.

[FoSc70] Dominique Foata and Marcel-Paul Schützenberger. Théorie géométrique des po-

lynômes eulériens. Berlin, Springer-Verlag, 1970 (Lecture Notes in Math., 138).

[Ga79] Adriano M. Garsia. On the “maj” and “inv” q-analogues of Eulerian Polynomials, Linear and Multilinear Algebra, vol. 8, 1979, p. 21–34.

[Lo83] M. Lothaire. Combinatorics on words. Addison-Wesley, Reading, 1983 (Encyclopedia of Math. and its Appl., 17).

[Mac15] (Major) P.A. MacMahon. Combinatory Analysis, vol. 1. Cambridge, Cambridge

Univ. Press, 1915 (Reprinted by Chelsea, New York, 1955).

[Ri58] John Riordan. An Introduction to Combinatorial Analysis. New York, J. Wiley,

1958.

[Stem92] John Stembridge. Some Permutation Representations of Weyl Groups Associated

with the Cohomology of Toric Varieties, preprint 1992.

[Ste93] Einar Steingrìmsson. Permutation Statistics of Indexed Permutations, to appear in Europ. J. Combinatorics, 1994.

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