Eulerian Calculus, II : An Extension of Han’s Fundamental Transformation

Robert J. CLARKE AND Dominique FOATA †

In our first Eulerian Calculus paper, we introduced the k-descent and k-excedance statistics on words, considered various bijections associated with them and calculated their distributions. In this paper we consider the k-major and k-den statistics and show that the joint des-maj and excden distributions of that k-extension are identical. We also consider the generating functions for these statistics. Dans notre premier article sur le Calcul Eulérien, nous avons introduit les statistiques k-descentes et k-excédances sur les mots, construit les différentes bijections associées et calculé leurs distributions. Dans le présent article nous considérons l’indice k-majeur et la statistique k-den et montrons que les distributions jointes des-maj et exc-den de cette kextension sont identiques. Nous considérons aussi les fonctions génératrices de ces statistiques.

1. Introduction

This paper is the second one of a series of three articles (see [6] and [7] 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.

We use the same notations as in the previous paper, but for convenience sake we recall them here. First, X is a fixed non-empty set, referred to as an alphabet, on which a total ordering D is defined. If x, y ∈ X and (x, y) ∈ D we will write x <_{D} y or simply x < y if no confusion can arise. We will normally take X to be the subset [ r] = {1, 2, …, r} (r ≥ 1), but D need not be the standard ordering on [ r]. We also have a fixed integer, k, such that 0 ≤ k ≤ r and j = r − k. The letters 1, …, j will be called small and the letters j + 1, …, r large. We say that D is compatible with k if, for all x large and y small, we have x > y. We also introduce a small letter ⋆ which is greater than any small letter of X.

Robert J. Clarke and Dominique Foata

The free monoid generated by X will be denoted by X^{∗}. The elements of X^{∗} are finite words w = x_{1}x_{2} … x_{m} with letters x_{i} taken from X. When we wish to stress the fact that a word has both small and large letters, we will speak of weighted word. 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.

† Supported in part by a grant of the Australian Research Council, 1993, while the author was on leave at the University of Adelaide and the guest of Kathleen Lumley College, Adelaide, and also by the E.E.C. network programme on Algebraic Combinatorics, while the author revised the paper in Strasbourg.

Let c = (c_{1}, …, c_{j}) and d = (d_{1}, …, d_{k}) be two vectors with positive integer components. Also let c = c_{1} + ⋯ + c_{j}, d = d_{1} + ⋯ + d_{k} and c + d = m. The class of all m!/(c_{1}! … c_{j}! d_{1}! … d_{k}!) rearrangements of the word 1^{c_{1}} … j^{c_{j}}(j + 1)^{d_{1}} … r^{d_{k}} will be denoted by R(c, d) or by C(v), where v is a given word in R(c, d).

Let w = x_{1}x_{2} … x_{m} and let \overline{w} = y_{1}y_{2} … y_{m} be its non-decreasing rearrangement (with respect to a given ordering D). As in the previous paper, we say that the word w has a k-excedance at i (1 ≤ i ≤ m), if either x_{i} > y_{i}, or x_{i} = y_{i} and x_{i} large. We also say that w has a k-descent at i (1 ≤ i ≤ m), if either x_{i} > x_{i+1}, or x_{i} = x_{i+1} and x_{i} large. (By convention, x_{m+1} = ⋆.) The numbers of k-excedances and k-descents of a word w are denoted by exc_{k} w and des_{k} w. We will sometimes use the notations exc_{k,D} and des_{k,D} if we need to draw attention to the ordering D.

In our first paper [6] we showed that for each ordering D compatible with k ≥ 0 the statistics “des_{k}” and “exc_{k}” were equidistributed on each rearrangement class R(c, d) and proved certain invariance properties on the distributions of those statistics. Actually, we constructed a bijection Φ_{k} of each rearrangement class R(c, d) onto itself that satisfied des_{k} w = exc_{k} Φ_{k}(w), identically. Hence for each rearrangement class R(c, d) the generating polynomials ∑_{w} t^{des_{k} w} and ∑_{w} t^{exc_{k} w} (w ∈ R(c, d)) are equal. Let A_{c}(t) be their common value. It was also shown that the generating function for those polynomials could be expressed as

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

where u^{c} = u_{1}^{c_{1}} … u_{j}^{c_{j}} and v^{d} = v_{1}^{d_{1}} … v_{k}^{d_{k}}. The object of this paper is to extend those results to joint statistics involving “des_{k}” and “exc_{k}” and thereby propose a natural q-extension of all of those results.

As usual, 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}

Then, a natural q-analogue of (1.1) can read

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

Eulerian Calculus, II

One of the purposes of this paper to show that the coefficient A_{c,d}(t, q) on the left-hand side of (1.2) is actually a polynomial with integral coefficients ; more essentially, to show that A_{c,d}(t, q) is the generating polynomial for a bivariate statistic (des_{k}, maj_{k}) over the rearrangement class R(c, d). The statistic “maj_{k}” will be defined shortly.

The main motivation of the paper is, however, to extend Han’s construction [14] to weighted words. This consists, first, of finding an appropriate extension “den_{k}” of the Denert statistic “den,” defined by Han, then, of constructing an explicit bijection ρ of each rearrangement class R(c, d) onto itself such that (des_{k}, maj_{k})(w) = (exc_{k}, den_{k})ρ(w) holds identically.

In his treatise on Combinatory Analysis, MacMahon [16] defined the major index, maj w, of a word w = x_{1}x_{2} … x_{m} as the sum of the i’s such that 1 ≤ i ≤ m − 1 and x_{i} > x_{i+1}. As this statistic has been the ideal companion to “des” for deriving q-analogues of the Eulerian numbers (see [2, 3, 4, 9, 13, 17, 19, 20]), it is natural to look for a statistic related to “maj” to obtain a q-extension of the distribution of “des_{k}.” Here we define the k-major index, maj_{k} w, of w = x_{1}x_{2} … x_{m} to be the sum of all i’s (1 ≤ i ≤ m) such that i is a k-descent in w.

The crucial problem is to define the appropriate statistic “den_{k},” the companion of “exc_{k}.” The Mahonian statistic “den” was introduced by Denert [8] on permutations and it was shown by Foata and Zeilberger [10] that the joint distribution of “exc” and “den” was Euler-Mahonian. To be more exact, it was shown that over any rearrangement class C(v) the two polynomials ∑_{w} t^{exc w}q^{den w} and ∑_{w} t^{des w}q^{maj w} were equal. The definition of “den” was extended in [14] to the case of words with possible repetition of letters. Han constructed an explicit bijection that transformed the pair (exc, den) to (des, maj). Our definition of the new statistic “den_{k}” (or “den_{k,D}” when we wish to stress the role of the ordering D) rests upon an extension of the notion of “cyclic intervals” already introduced by Han [14] in his definition of “den.” That extension, called k-cyclic interval, is defined as follows.

Let S = {1, …, j} be the set of small elements of X and let L = {j + 1, …, r} be the set of large elements of X. Let s_{max} be the largest small letter of X (under the ordering D). Besides the small letter ⋆ that satisfies s_{max} <_{D} ⋆ <_{D} b for any letter b greater than s_{max}, we also adjoin to X a large letter ∞ that is greater than every letter of X. Define X^{+} to be X ∪ {⋆, ∞}. Similarly, L^{+} = L ∪ {∞} and S^{+} = S ∪ {⋆}.

If Y is any totally ordered set and a, b ∈ Y, the cyclic interval ]]a, b]] has been defined in [14] as

(1.3)  ]]a, b]] = \{ \begin{matrix}(a, b], & if a ≤ b; \\ Y \ (b, a], & otherwise. \end{matrix}

Thus ]]a, a]] = ∅.

In our context it is necessary to modify the definition. Let a and b be elements of X^{+}. Then we define ]]a, b]] by equation (1.3), where Y = X^{+}. Further, we define ]]a, b]]_{k} by

(1.4)  ]]a, b]]_{k} = \{ \begin{matrix}]]a, b]], & if a, b ∈ S^{+} ; \\ ]]a, b]] ∪ \{a\}, & if a ∈ L^{+}, b ∈ S^{+} ; \\ ]]a, b]] \ \{b\}, & if a ∈ S^{+}, b ∈ L^{+} ; \\ ]]a, b]] ∪ \{a\} \ \{b\}, & if a, b ∈ L^{+}, a ≠ b; \\ X^{+}, & if a = b ∈ L^{+}. \end{matrix}

The elements of X^{+} can be visualized as points on a circle (or a square !) as shown on Fig. 1. The k-cyclic intervals ]]a, b]]_{k} must be read counterclockwise. The path ⟶ on the S^{+}-part shows that whenever a is small, the interval ]]a, b]]_{k} is of the form “(a, …” (or “]a, …” in the French notation) so that a ∉ ]]a, b]]_{k}; also whenever b is small, ]]a, b]]_{k} = ⋯, b] and then b ∈ ]]a, b]]_{k}. On the contrary, the path ⟶ on the L^{+}-part shows that ]]a, b]]_{k} = [a, … and so a ∈ ]]a, b]]_{k} whenever a is large ; but ]]a, b]]_{k} = ⋯, b) (or …, b[ ) whenever b is large and then b ∉ ]]a, b]]_{k}. When D is compatible with k, the small letters lie between ∞ and ⋆, and the large ones between ⋆ and ∞, still reading the square counterclockwise ; also ]]⋆, ∞]]_{k} = L.

[figure: ∞; ⋆; a; b; S^{+}; b; a; L^{+}; Fig. 1]

Let w = x_{1}x_{2} … x_{m} be a word on the letters in X. Put x_{m+1} = ⋆, x_{m+2} = ∞. For i = 1, …, m + 2 let Fact_{i} w be the left factor x_{1} … x_{i−1} of w and for each subset B of X let Fact_{i} w ∩ B be the subword of Fact_{i} w consisting only of those letters of Fact_{i} w that are in B. Furthermore, let |Fact_{i} w ∩ B| denote the length of that subword.

Now let \overline{w} = y_{1}y_{2} … y_{m} the non-decreasing rearrangement of a word w = x_{1}x_{2} … x_{m}. The den_{k}-coding of w is defined to be the sequence (s_{i})_{1≤i≤m+1}, where

(1.5)  s_{i} = \{ \begin{matrix}|Fact_{i} w ∩ ]]x_{i}, y_{i}]]_{k}| , & if 1 ≤ i ≤ m; \\ |w ∩ L|, & if i = m + 1 ; \end{matrix}

and the statistic den_{k} w to be

(1.6)  den_{k} w = ∑_{i=1}^{m+1} s_{i}.

Consider the the set X = {1, 2, 3, 4, 5} with the ordering 1 < 2 < 4 < 3 < 5 and assume that 1, 2 and 3 are small, while 4 and 5 are large (i.e., j = 3, k = 2, r = 5). Then den_{k} w for k = 2

and \binom{\overline{w}}{w} = ( \begin{matrix}1 1 2 4 4 3 3 5 5 \\ 3 5 1 3 1 4 2 4 5 \end{matrix} ) is easily calculated using Fig. 1. For

instance, |Fact_{4} w ∩ ]]3, 4]]_{2}| = |3, 5, 1 ∩ {5, 1, 2}| = 2. Hence (s_{i}) = (0, 0, 0, 2, 0, 2, 3, 3, 8, 4) and den_{2} w = 22.

Our first result is the invariance principle for “maj”, a simple extension of the corresponding result for the case k = 0 proved in [9, Proposition 2.1]. This result includes of course Theorem 3.1 of [6].

Theorem 1.1. Let v be a fixed word in X^{∗} and let D and E be total orderings on X = [ r]. Assume that both D and E are compatible with k. Then there is a bijection μ on C(v) = R(c, d) such that for all w ∈ C(v),

(des_{k,D}, maj_{k,D}) w = (des_{k,E}, maj_{k,E}) μ(w).

The proof of this Theorem occupies section 2. As explained earlier, our main result is the following theorem, proved in section 4.

Theorem 1.2. Let v be a fixed word in X^{∗} and let D be an ordering on X compatible with k. Then there is a bijection ρ of C(v) onto itself such that for all w ∈ C(v),

(1.5)  (des_{k}, maj_{k}) (w) = (exc_{k}, den_{k}) ρ(w).

To complete this circle of results, we must prove the invariance principle for “den” which may be stated in the following form.

Theorem 1.3. Let v be a fixed word in X^{∗} and let D and E be total orderings on X = [ r]. Then there is a bijection δ on C(v) = R(c, d) such that for all w ∈ C(v),

(exc_{k,D}, den_{k,D}) w = (exc_{k,E}, den_{k,E}) δ(w).

This result is proved in section 5 of the current paper. It includes Theorem 3.3 of [6]

There are essentially two parts in the paper. The first sections 2, 3, 4 and 5 are of algorithmic nature and rest upon non-commutative algebraic techniques developed by Schützenberger [18] and discussed in the book by Lothaire [15]. For the constructions of the bijection ρ in section 4 and of ξ_{D} and ξ_{E} in section 5 we need two tools : an appropriate word factorization and a commutation rule. It is noteworthy that the k-factorisation introduced in section 4 suggests that further classical word factorizations should be reconsidered in the context of bi-alphabets with two classes of letters, large and small. The second tool is the Han transposition discussed in the next section, that is mainly an adaptation of what Han [14] has developed in his seminal paper.

The last sections 6, 7 and 8 deal with classical techniques in the context of q-series. We first calculate the distribution of (des_{k}, maj_{k}) (and then that of (exc_{k}, den_{k}) by Theorem 1.2). More precisely, let

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

be the generating function for the pair (des_{k}, maj_{k}) over the class R(c, d). In section 6 we first calculate the recurrence relations for A_{c,d}(t, q). Then, in section 7, we successfully integrate a system of partial q-difference equations to prove the following theorem.

Theorem 1.4. The factorial generating function for the polynomials A_{c,d}(t, q) satisfies identity (1.2).

In section 8 we specialize the calculation of A_{c,d}(t, q) to the symmetric group and develop an algebra of q-polynomials that interpolate the classical q-Eulerian polynomials in a very natural manner.

An alternate set-up for sections 2–5 would have been to keep the natural ordering on X, construct the bijection ρ on each rearrangement class R(c, d) and study the invariance of the distributions of the statistics under the action of the permutations of the multiplicities (c_{1}, …, c_{j}, d_{1}, …, d_{k}) of the letters 1, 2,…, r. We have preferred to state and prove our results in the context of total orderings on X, i.e., under the action of the permutations of the letters of X.

2. The invariance principle for the k-major index

Let w = x_{1}x_{2} … x_{m} be a word in X^{∗}. Then the k-major index maj_{k,D} w is defined by

maj_{k,D} w = ∑{i : 1 ≤ i ≤ m, w has a k-descent at i}.

Proof of Theorem 1.1. We simplify the notation by suppressing the subscript k from “des” and “maj”, and we refer to D-descents and E-descents of a word w in the obvious way. Without loss of generality, we may assume that D is the standard ordering on X = [r] and that E is obtained from D by interchanging the order of two adjacent letters i and i + 1. Since E is compatible with k, either i + 1 ≤ j, i.e., both i and i + 1 are small, or i > j, i.e., both i and i + 1 are large.

Case (a) : suppose that i + 1 ≤ j. Let w be a word in C(v). Write w in the form w = u_{1}v_{1}u_{2}v_{2} … u_{n}v_{n}, where each u_{l} is a word in the letters i, i + 1 and each v_{i} is a word in X \ {i, i + 1}. (Note that either or both of u_{1}, v_{n} may be empty.)

Consider any one of the subwords u_{l}. Write in bold-face all the factors of u_{l} of form (i + 1)i. Replace each maximal factor of u_{l} of form i^{p}(i + 1)^{q} that does not involve any bold-face letters by the factor (i+1)^{q}i^{p}. Finally, replace each bold-face factor (i + 1)i by the factor i(i + 1), to obtain a word u′_{l}. Then the factor (i + 1)i occurs in u_{l} in exactly those places in which the factor i(i + 1) occurs in u′_{l}. Thus u_{l} has a D-descent in exactly those places at which u′_{l} has an E-descent.

Now put μ(w) = u′_{1}v_{1}u′_{2}v_{2} … u′_{n}v_{n}. Clearly μ(w) ∈ C(v) and

(des_{D}, maj_{D}) w = (des_{E}, maj_{E}) μ(w).

Since μ is obviously a bijection, the result follows.

Case (b) : suppose on the other hand that i > j. Let w = u_{1}v_{1}u_{2}v_{2} … u_{n}v_{n} as before. For each factor u_{l}, form u′_{l} in exactly the same way as in Case (a), except that the places of i and i + 1 in the algorithm should be interchanged. Thus the factor i(i + 1) will occur in u_{l} in exactly those places in which the factor (i + 1)i occurs in u′_{l}. Thus u_{l} will fail to have a D-descent in exactly those places at which u′_{l} fails to have an E-descent. Now, putting μ(w) = u′_{1}v_{1}u′_{2}v_{2} … u′_{n}v_{n}, the proof proceeds as before.

Remark. Define the D-ligne of route of w to be the set, ligne_{D} w, of all i such that 1 ≤ i ≤ m and w has a k-descent at i. The above proof shows that under the same assumptions we also have

ligne_{D} w = ligne_{E} μ(w).

3. The den statistic

In this section we derive an alternate definition of maj_{k}, involving the k-cyclic intervals as in the definition of den_{k} (given in (1.3) and (1.4)). Then we define the statistic “den” on biwords and describe the “Han transposition”, a way of manipulating biwords that preserves the statistics “den” and “exc”.

3.1. The k-major index. Let w = x_{1}x_{2} … x_{m} be a word on the letters in X. As in section 1, put x_{m+1} = ⋆, x_{m+2} = ∞ and for i = 1, …, m + 2 let Fact_{i} w be the left factor x_{1} … x_{i−1} of w and let |Fact_{i} w ∩ B| denote the length of the subword of Fact_{i} w the letters of which belong to a subset B of X.

Our purpose is to give the following extension of a result of Han [14, Theorem 2.1(i)] that was derived for the case k = 0.

Theorem 3.1. If D is compatible with k, then for each word w = x_{1}x_{2} … x_{m},

(3.1)  maj_{k} w = ∑_{i=1}^{m+1} |Fact_{i} w ∩ ]]x_{i}, x_{i+1}]]_{k}| .

Theorem 3.1 rests upon the next two lemmas 3.2 and 3.3. In the first one the notation A ⊎ B denotes the union of the multisets A and B. For example, {1, 1, 2} ⊎ {2, 3} = {1, 1, 2, 2, 3}.

Lemma 3.2. Let a, b ∈ X^{+}. Then

(i)  ]]a, b]]_{k} = X^{+} \ ]]b, a]]_{k}, whenever a ≠ b
(ii) ]]a, b]]_{k} ⊎ ]]b, ∞]]_{k} = \{ \begin{matrix}]]a, ∞]]_{k} ⊎ X^{+}, & if a > b or a = b ∈ L^{+} ; \\ ]]a, ∞]]_{k}, & otherwise. \end{matrix}

Proof. Both parts of this Lemma are easily verified by considering the various possible cases. For part (ii), recall that ]]a, a]]_{k} equals X^{+} if a is large and is empty otherwise.

Now let w = x_{1}x_{2} … x_{n} be a word on X ∪ {⋆} and define

maj′ w = ∑{i : 1 ≤ i ≤ n − 1, w has a k-descent at i };

(i.e., in “maj′” we do not count any descent at the end of w.)

Lemma 3.3. Let w = x_{1}x_{2} … x_{n} be a word on X ∪ {⋆}. Then

(3.2) maj′ w = ∑_{i=1}^{n−1} |Fact_{i} w ∩ ]]x_{i}, x_{i+1}]]_{k}| + | Fact_{n} w ∩ ]]x_{n}, ∞]]_{k}|.

Proof. We use induction on n. The result is clearly true for n = 1, so suppose it is true for n − 1. Then

maj′ w − maj′ x_{1} … x_{n−1} = \{ \begin{matrix}n − 1, & if w has a k-descent at n − 1 ; \\ 0, & otherwise. \end{matrix} Let S_{n} denote the right-hand side of equation (3.2). Then

S_{n} − S_{n−1} = |Fact_{n−1} w ∩ ]]x_{n−1}, x_{n}]]_{k}| + |Fact_{n} w ∩ ]]x_{n}, ∞]]_{k}|
− |Fact_{n−1} w ∩ ]]x_{n−1}, ∞]]_{k}|

= |Fact_{n−1} w ∩ ]]x_{n−1}, x_{n}]]_{k}| + |Fact_{n−1} w ∩ ]]x_{n}, ∞]]_{k}|

− |Fact_{n−1} w ∩ ]]x_{n−1}, ∞]]_{k}| + |x_{n−1} ∩ ]]x_{n}, ∞]]_{k}|

= |Fact_{n−1} w ∩ (]]x_{n−1}, x_{n}]]_{k} ⊎ ]]x_{n}, ∞]]_{k})|

− |Fact_{n−1} w ∩ ]]x_{n−1}, ∞]]_{k}| + |x_{n−1} ∩ ]]x_{n}, ∞]]_{k}|

= \{ \begin{matrix}|Fact_{n−1} ∩X^{+}| \\ + |x_{n−1} ∩ ]]x_{n}, ∞]]_{k}| , & if w has a k-descent at n − 1 ; \\ |x_{n−1} ∩ ]]x_{n}, ∞]]_{k}| , & otherwise ; \end{matrix}

= \{ \begin{matrix}n − 1, & if w has a k-descent at n − 1 ; \\ 0, & otherwise, \end{matrix}

by Lemma 3.2. Hence the result follows.

The proof of Theorem 3.1 is now completed as follows. Assume without loss of generality that D is the usual ordering on X. Let w′ = x_{1}x_{2} … x_{m} ⋆. Then

maj_{k} w = maj′ w′

= ∑_{i=1}^{m} |Fact_{i} w′ ∩ ]]x_{i}, x_{i+1}]]_{k}| + | Fact_{m+1} w ∩ ]]x_{m+1}, ∞]]_{k}|

= ∑_{i=1}^{m+1} |Fact_{i} w ∩ ]]x_{i}, x_{i+1}]]_{k}| ,

since by convention we put x_{m+1} = ⋆, x_{m+2} = ∞.

The above result is not true without the assumption of compatibility.

3.2. Biwords and words. A biword is a two rowed matrix α = \binom{u}{w}, where u and w are words in X^{∗} of the same length. The biword α is called

a circuit if u is a rearrangement of w. A circuit α = ( \begin{matrix}y_{1} & y_{2} & … & y_{m} \\ x_{1} & x_{2} & … & x_{m} \end{matrix} ) is a

cycle, if y_{m} = x_{1} and y_{i} = x_{i+1} for i = 1, …, m − 1. We will write this cycle as α = [x_{1}x_{2} … x_{m}] = [w], where w = x_{1}x_{2} … x_{m}.

Consider the biword \binom{u}{w}, where u = y_{1}y_{2} … y_{m} and w = x_{1}x_{2} … x_{m}. An ordering D of X being given, we define

(3.3) exc_{k} \binom{u}{w} = |\{i : 1 ≤ i ≤ m and x_{i} > y_{i} or x_{i} = y_{i} ∈ L^{+}\}|;
(3.4) den_{k} \binom{u}{w} = ∑_{i=1}^{m} |Fact_{i} w ∩ ]]x_{i}, y_{i}]]_{k}| .

If \overline{w} is the non-decreasing rearrangement of w, then clearly

(3.5)  exc_{k} \binom{\overline{w}}{w} = exc_{k} w;

and by (1.5) and (1.6)

(3.6)  den_{k} w = den_{k} \binom{\overline{w}}{w} + |w ∩ L|.

Note that if D is compatible with k,

(3.7)  den_{k} w = den_{k} ( \begin{matrix}\overline{w} & ∞ \\ w & ⋆ \end{matrix} ) .

3.3. The Han Transposition. Let x, y, a, b ∈ X ∪ {⋆}. Then a and b are neighbours with respect to (x, y) if both a and b are in ]]y, x]]_{k} or neither in ]]y, x]]_{k}. Otherwise, a and b are strangers with respect to (x, y).

Lemma 3.4. The following conditions are equivalent.

(i) a and b are neighbours with respect to (x, y) ; (ii) |a ∩ ]]y, x]]_{k}| = |b ∩ ]]y, x]]_{k}|; (iii) a and b are neighbours with respect to (y, x) ; (iv) |a ∩ ]]b, y]]_{k}| = |a ∩ ]]b, x]]_{k}|;

(v) ]]a, x]]_{k} ⊎ ]]b, y]]_{k} = ]]a, y]]_{k} ⊎ ]]b, x]]_{k}.

Lemma 3.5. The following conditions are equivalent.

(i) a and b are strangers with respect to (x, y) ; (ii) |a ∩ ]]y, x]]_{k}| = 1 − |b ∩ ]]y, x]]_{k}|; (iii) a and b are strangers with respect to (y, x) ; (iv) |a ∩ ]]b, y]]_{k}| = |b ∩ ]]a, x]]_{k}|.

Proof. These two lemmas follow from the similar results [14, Lemma 3.2 and Lemma 3.3]. The only special cases that arise are when two of a, b, x, y are equal and large.

1. If a = b ∈ L then a and b are neighbours and the results are trivial.

2. If x = y ∈ L then ]]y, x]]_{k} = X^{+} and a and b are neighbours. The results now follow.

3. Suppose that a = x ∈ L and b, y ≠ a. Then a ∉ ]]y, a]]_{k}. So a and b are neighbours if and only if b ∉ ]]y, a]]_{k}. But b ∉ ]]y, a]]_{k} if and only if a ∉ ]]b, y]]_{k}, as b ≠ a. Hence a and b are neighbours if and only if |a ∩ ]]b, y]]_{k}| = 0 = |a ∩ ]]b, x]]_{k}|, as a ∉ ]]b, x]]_{k} = ]]b, a]]_{k}. Now let a and b be neighbours and suppose that b < y < a. Then

]]a, x]]_{k} ⊎ ]]b, y]]_{k} = (X ∪ {⋆}) ⊎ ]]b, y]]_{k},

and

]]a, y]]_{k} ⊎ ]]b, x]]_{k} = ]]a, y]]_{k} ⊎ ]]b, a]]_{k} = (X ∪ {⋆}) ⊎ ]]b, y]]_{k}.

The other cases may be treated similarly.

Now let ( \begin{matrix}x y \\ a b \end{matrix} ) be a biword of length two. Following [14] we define the

Han transposition T by

(3.8)  T ( \begin{matrix}x y \\ a b \end{matrix} ) = \{ \begin{matrix}( \begin{matrix}y x \\ a b \end{matrix} ) , & if a and b are neighbours ; \\ ( \begin{matrix}y x \\ b a \end{matrix} ) , & if a and b are strangers \end{matrix}

with respect to (x, y). If α = \binom{u}{w} = \binom{y_{1} y_{2} … y_{m}}{x_{1} x_{2} … x_{m}} is a biword of

length m and 1 ≤ i < m, we define T_{i}α to be the biword obtained when

the biword β = \binom{y_{i} y_{i+1}}{x_{i} x_{i+1}} consisting of the i-th and i + 1-st columns of

α is replaced by T β.

For instance, using the ordering 1 < 2 < 3 < ⋆ < 4 < 5 < ∞ with 1, 2, 3

small and 4, 5 large we have T \binom{3 4}{4 1} = \binom{4 3}{4 1}, since 1, 4 ∉ ]]3, 4]]_{2} = \{⋆\},

while T \binom{2 5}{1 3} = \binom{5 2}{3 1}, for ]]2, 5]]_{2} = \{3, ⋆, 4\}.

Lemma 3.6. Let α = \binom{u}{w} be a biword of length m and let 1 ≤ i < m. Then (exc_{k}, den_{k}) T_{i}α = (exc_{k}, den_{k}) α.

Proof. This follows from Lemmas 3.4 and 3.5, exactly as in [14, Lemma 5.2].

3.4. The transformation T_{z_{2}}. Let z_{1}, z_{2} be two distinct letters of X∪{⋆} and v be a word of length (m − 1) (m ≥ 1) in the alphabet X ∪ {⋆} \ {z_{2}}. Denote by C(v, z_{1}, z_{2}) the set of all biwords α = ({u \atop w} ), where u is the nondecreasing rearrangement of vz_{2} and w is any rearrangement of vz_{1}. Thus u has one occurrence of z_{2}, while w has none. However the occurrences of the other letters are the same, except for z_{1} that occurs one more time in w than in u.

If z_{2} is the i-th letter in the word u, the product T_{m−1} ⋯ T_{i+1}T_{i} will

transform α into a biword of the form α′ = ({u′z_{2} \atop w′y_{1}} ). Then, either u′

and has no occurrence of y_{1}, in which case y_{1} = z_{1} and w′ must be a rearrangement of u′, or y_{1} does occur in u′. In the former case, define

T_{z_{2}}(α) = ({u′z_{2} \atop w′z_{1}} ). In the latter case, the rightmost occurrence of y_{1} in

u′ is, say, its i′-th letter. Then the product T_{m−2} ⋯ T_{i′+1}T_{i′} transforms

α′ into a biword of the form α′′ = ({u′′y_{1}z_{2} \atop w′′y_{2}y_{1}} ). Again, either u′′ and has no occurrence of y_{2}, in which case y_{2} = z_{1} and w′′ must be a rearrangement of u′′, or y_{2} does occur in u′′. In the former case, define

T_{z_{2}}(α) = ({u′′y_{1}z_{2} \atop w′′z_{1}y_{1}} ). In the latter case, we continue the same procedure

as before by moving the rightmost occurrence of y_{2} in u′′ to the right of u′′.

After finitely many steps we reach a biword α^{(l)} = ({u^{(l)}y_{l−1} … y_{1}z_{2} \atop w^{(l)} y_{l} … y_{2}y_{1}} ),

where u^{(l)} has no occurrence of y_{l}. Then necessarily y_{l} = z_{1} and w^{(l)} is a rearrangement of u^{(l)}. (Note that u^{(l)} may be empty.) Define u_{1} = u^{(l)}, w_{1} = w^{(l)}, v_{1} = y_{l−1} … y_{2}y_{1} and

(3.9)  T_{z_{2}}(α) = α^{(l)} = ({u^{(l)}y_{l−1} … y_{1}z_{2} \atop w^{(l)} y_{l} … y_{2}y_{1}} ) = ({u_{1}v_{1}z_{2} \atop w_{1}z_{1}v_{1}} ).

Thus for each α in C(v, z_{1}, z_{2}) there is a well-defined product of Han transpositions that maps α onto a biword of the form ({u_{1}v_{1}z_{2} \atop w_{1}z_{1}v_{1}} ), where

u_{1} is the non-decreasing rearrangement of w_{1} with no occurrence of z_{1}. Denote by D(v, z_{1}, z_{2}) the set of biwords of the previous form ({u_{1}v_{1}z_{2} \atop w_{1}z_{1}v_{1}} ).

Lemma 3.7. The mapping T_{z_{2}} : C(v, z_{1}, z_{2}) → D(v, z_{1}, z_{2}) is a bijection.

Proof. Let C(vz_{1}) the set of all rearrangements of vz_{1}. Then the mapping w ↦ ({u \atop w} ) is evidently a bijection of C(vz_{1}) onto C(v, z_{1}, z_{2}). On the other hand, each word w in C(vz_{1}) has a unique factorization of the form (w_{1}, z_{1}v_{1}) where w_{1} has no occurrence of z_{1}. Hence the mapping w ↦ ({u_{1}v_{1}z_{2} \atop w_{1}z_{2}v_{1}} ), where u_{1} is the non-decreasing rearrangement of w_{1}, is

also a bijection of C(vz_{1}) onto D(v, z_{1}, z_{2}). Thus, those two sets, as well as C(v, z_{1}, z_{2}), have the same cardinalities.

Keeping the same notations we see that T_{z_{2}} is the product of Han transpositions of the form

(T_{m−l} ⋯ T_{i^{(l)}+1}T_{i^{(l)}}) ⋯ (T_{m−2} ⋯ T_{i′+1}T_{i′})(T_{m−1} ⋯ T_{i+1}T_{i}).

To reverse T_{z_{2}} it suffices to determine l and the indices i^{(l)}, …, i′, i directly from the biword ({u_{1}v_{1}z_{2} \atop w_{1}z_{1}v_{1}} ) in D(v, z_{1}, z_{2}). But l is the length

of v_{1}z_{2}. Next, when the first letter of v_{1} is moved just before the i^{(l)}- th letter of u_{1}, the resulting word u^{(l−1)} is non-decreasing. In the same manner, the other indices, in particular, i′, i, indicate where to move the other letters of v_{1} and finally z_{2} to the left to obtain a non-decreasing word on the top row.

Remark 3.8. The inverse mapping applied to the biword ({u_{1}v_{1}z_{2} \atop w_{1}z_{1}v_{1}} ) in

D(u_{1}v_{1}, z_{1}, z_{2}) is derived by moving to the left, to the first position where the resulting word is not-decreasing, successively the first, the second, …, the last letter z_{2} of the word v_{1}z_{2}, the moves being made by means of the Han transpositions as defined in (3.8). The inverse mapping is then independent of z_{2} and will be denoted by T^{−1}.

4. The den-maj bijection

In this section we prove Theorem 1.2. We assume that the ordering D is compatible with k, and in fact that D is the standard ordering on X = [ r]. It will be convenient to use the terminology of words (see, e.g., [15]) : for instance, if w is the juxtaposition product w = w_{1}w_{2}w_{3}, then each w_{i} (i = 1, 2, 3) is a factor of w; w_{1} (resp. w_{3}) is a left factor (resp. right factor) of w. If y is a letter and w a non-decreasing word, we will write y < w (resp. y ≤ w), if y is less than (resp. less than or equal to) all the letters in w.

As for the first fundamental transformation described in [5 or 15, chap. 10] and Han’s fundamental bijection [14] we need an appropriate word factorization besides the Han transposition described in the previous section. That factorization can be built as follows.

Let z ∈ X ∪ {⋆} and let v be a word in that alphabet ; then the word zv is said to be k-dominant, if z is large and all letters in v are greater than or equal to z, or if z is small and all small letters in v are less than or equal to z.

Every word in the alphabet X ∪ {⋆} has a unique factorization (z_{1}v_{1}, z_{2}v_{2}, …, z_{n}v_{n}) (the z_{i}’s are letters and the v_{i}’s words), called its k-factorization, having the following properties :

(i) w = z_{1}v_{1}z_{2}v_{2} … z_{n}v_{n};

(ii) each factor z_{i}v_{i} is k-dominant (1 ≤ i ≤ n) ;

(iii) there exists an integer l (1 ≤ l ≤ n) such that z_{1} > z_{2} > ⋯ > z_{l} > ⋆ and z_{l+1} < z_{l+2} < ⋯ < z_{n} ≤ ⋆.

The k-factorization of a word w may be obtained as follows : a letter z of w is called a k-record, if either z is large and all letters to the left of z are larger than z, or z is small and all small letters to the left of z are smaller than z. The k-factorization of w is then obtained by cutting w before each k-record.

The notions of k-factorization and k-records are illustrated in Fig. 2. The alphabet consists of five small letters 1, 2, 3, 4, ⋆ and k = 5 large letters 5, 6, 7, 8, 9 with the ordering 1 < 2 < 3 < 4 < ⋆ < 5 < 6 < 7 < 8 < 9. The k-factorization of the word w consists of seven factors materialized by continuous polygonal lines, the rightmost one being a single point. Each k-record is the beginning of a continuous polygonal line and is represented by a “bullet” •.

[figure: w =; 7; 8; 9; 7; 9; 6; 8; 6; 2; 1; 2; 5; 7; 2; 3; 2; 6; 9; 5; 2; 1; 2; 4; 6; 5; ⋆; •; •; •; •; •; •; 1; 2; 3; 4; ⋆; 5; 6; 7; 8; 9; Fig. 2]

The k-factorization appears to be the product (in a sense that can be precised) of two factorizations, the decreasing factorization (the first two factors in the previous example) by the increasing factorization (the next five factors), the large letters playing no role in the definitions of those rightmost five factors.

The main property of the k-factorization on which our transformation is based is the following : let (z_{1}v_{1}, z_{2}v_{2}, …, z_{n}v_{n}) be the k-factorization of a word w. Then,

(4.1) for each i = 1, …, n−1 no letter in the left factor z_{1}v_{1} … z_{i}v_{i} is equal to z_{i+1} or is strictly between z_{i} and z_{i+1}. Let w_{1} be any rearrangement of that factor ; then the k-factorization of w_{1}z_{i+1}v_{i+1} … z_{n}v_{n} has the same rightmost (n − i) factors z_{i+1}v_{i+1}, …, z_{n}v_{n} as w and the same rightmost (n − i + 1) k-records z_{i}, z_{i+1}, …, z_{n} as w.

Consider a biword α = ( \begin{matrix}u_{1} & u_{2}∞ \\ w_{1} & z u_{2} \end{matrix} ), where : (1) u_{1}, u_{2}, w_{1} are words in

the alphabet X ∪ {⋆}; (2) u_{1} is the non-decreasing rearrangement of w_{1} ;

(3) z is a k-record of the word w_{1}zu_{2}. Such a biword is called a supercycle. A supercycle is said to be initial, if u_{1} and w_{1} are empty. The notion of final supercycle will be defined shortly.

Lemma 4.1. If α is a supercycle, the factorization

(4.2)  α = ( \begin{matrix}u_{1} \\ w_{1} \end{matrix} | \begin{matrix}u_{2}∞ \\ z u_{2} \end{matrix} ) ,

where u_{1} is the non-decreasing rearrangement of some left factor of the bottom word of α and where z is a k-record of the bottom word, is unique. The factorization (4.2) is called the canonical form of α.

Proof. If there were two factorizations

( \begin{matrix}u_{1} \\ w_{1} \end{matrix} | \begin{matrix}u_{2}∞ \\ z u_{2} \end{matrix} )  and  ( \begin{matrix}u′_{1} \\ w′_{1} \end{matrix} | \begin{matrix}u′_{2}∞ \\ z′ u′_{2} \end{matrix} ) ,

we could suppose |u_{1}| < |u′_{1}|. Then u_{2} = vz′u′_{2} and zu_{2} = zvz′u′_{2} for some

k-dominant factor zv and α could be written as α = ( \begin{matrix}u_{1} \\ w_{1} \end{matrix} | \begin{matrix}vz′ \\ zv \end{matrix} | \begin{matrix}u′_{2}∞ \\ z′ u′_{2} \end{matrix} ). As

z ≠ z′ by (4.1), the left factor u′_{1} = u_{1}vz′ would not be a rearrangement of w′_{1} = w_{1}zv.

Let α = ( \begin{matrix}u_{1} \\ w_{1} \end{matrix} | \begin{matrix}u_{2}∞ \\ z u_{2} \end{matrix} ) be a supercycle written in its canonical form and

let (z_{1}v_{1}, z_{2}v_{2}, …, z_{n}v_{n}) be the k-factorization of zu_{2}. Then the following factorization of α, indicated by vertical bars,

(4.3)  α = ( \begin{matrix}u_{1} \\ w_{1} \end{matrix} | \begin{matrix}v_{1}z_{2} \\ z_{1}v_{1} \end{matrix} | \begin{matrix}v_{2}z_{3} \\ z_{2}v_{2} \end{matrix} | \begin{matrix}… \\ … \end{matrix} | \begin{matrix}v_{n}∞ \\ z_{n}v_{n} \end{matrix} )

is well defined. Call it the k-factorization of the supercycle α. The (positive) integer n, which is the number of factors in the k-factorization of zu_{2}, is called the index of α and denoted by index(α). A supercycle α is said to be final, if its index is equal to 1.

We first describe a transformation τ on supercycles that decreases their indices whenever they are not final. Let α be a supercycle as shown in (4.3), supposed to be not final, so that n ≥ 2. With the notations of (3.9) the left factor ({u_{1}v_{1}z_{2} \atop w_{1}z_{1}v_{1}} ) of the supercycle α is an element of D(u_{1}v_{1}, z_{1}, z_{2}).

Apply the inverse transformation T^{−1}, as described in Remark 3.8, to

that left factor. We get a biword ({u′′_{1} \atop w′_{1}} ) ∈ C(u_{1}v_{1}, z_{1}, z_{2}), i.e., a biword

such that u′′_{1} is the non-decreasing rearrangement of u_{1}v_{1}z_{2} and w′_{1} is a rearrangement of u_{1}v_{1}z_{1}. Then form the supercycle

(4.4)  α′′ = ( \begin{matrix}u′′_{1} \\ w′_{1} \end{matrix} | \begin{matrix}v_{2}z_{3} \\ z_{2}v_{2} \end{matrix} | \begin{matrix}… \\ … \end{matrix} | \begin{matrix}v_{n}∞ \\ z_{n}v_{n} \end{matrix} ) .

Replacing the only occurrence of z_{2} in u′′_{1} by z_{1} transforms u′′_{1} into a true rearrangement u′_{1} of w′_{1}. Furthermore, u′_{1} is non-decreasing because of property (4.1). We then obtain a supercycle

(4.5)  α′ = ( \begin{matrix}u′_{1} \\ w′_{1} \end{matrix} | \begin{matrix}v_{2}z_{3} \\ z_{2}v_{2} \end{matrix} | \begin{matrix}… \\ … \end{matrix} | \begin{matrix}v_{n}∞ \\ z_{n}v_{n} \end{matrix} ) .

Moreover, the above expression derived from the k-factorization of α is precisely the k-factorization of α′ and the rightmost k-record of w′_{1} is equal to z_{1} (by (4.1)). Finally, index(α′) = n − 1. Thus the mapping τ : α ↦ α′ is well defined and satisfies

(4.6)  index(τ(α)) < index(α),

if α is not final.

To derive the reverse transformation α′ ↦ α, the k-record z_{1} to the left of z_{2} in w′ = w′_{1}z_{2}v_{2} … z_{n}v_{n} is to be found first, then the replacement z_{1} ← z_{2} that maps u′_{1} onto u′′_{1} (and therefore α′ onto α′′) can be defined without ambiguity. But that k-record is necessarily equal to the left-most occurrence of the smallest letter y in w′_{1}, if all the letters in w′_{1} are large, and equal to the left-most occurrence of the greatest small letter y in w′_{1}, if some letters of w′_{1} are small.

In the former case we have u′_{1} = yw′_{3} with z_{2} < y ≤ w′_{3} ; in the latter case, u′_{1} = w′_{2}yw′_{3}, with y < z_{2} and w′_{2} ≤ y < w′_{3}. Then u′′_{1} can be recovered by

(4.7)  u′′_{1} = \{ \begin{matrix}z_{2}w′_{3}, & (in the former case) ; \\ w′_{2}z_{2}w′_{3}, & (in the latter case). \end{matrix}

Thus the mapping α′′ ↦ α′ is perfectly reversible and defined by (4.7). Now to go from α′′ to α we simply have to apply the transformation T_{z_{2}}

to the leftmost factor ({u′′_{1} \atop w′_{1}} ) of α′′. The index z_{2} of the transformation T_{z_{2}}

is well-defined, as z_{2} is the first letter of the second factor of the kfactorization of α′′. We then recover α, as written in (4.3). We also have the following property.

Property 4.2. Let v be a non-decreasing word in the alphabet X∪{⋆}

and let S(v) be the set of the supercycles α = ( \begin{matrix}u_{1} & u_{2}∞ \\ w_{1} & z u_{2} \end{matrix} ), whose bottom

word w_{1}zu_{2} is a rearrangement of v. If α is not initial, there is a unique β ∈ S(v) such that τ(β) = α and index(α) < index(β).

The statistics “exc_{k}” and “den_{k}” on biwords have been defined in (3.3) and (3.4).

Property 4.3. For each supercycle α which is not final, we have

(exc_{k}, den_{k}) τ(α) = (exc_{k}, den_{k}) α.

Proof. Use the same notations as in (4.3), (4.4) and (4.5). Lemma 3.6 implies that (exc_{k}, den_{k}) α′′ = (exc_{k}, den_{k}) α, since α′′ is obtained from α by a sequence of Han transpositions.

Let \binom{y}{x} be the (unique) biletter of \binom{u′′_{1}}{w′_{1}} whose top letter y is equal to

z_{2} and suppose that \binom{y}{x} is the l-th biletter of the word. That biletter is transformed into \binom{z_{1}}{x} when going from α′′ to α. If x ≠ z_{1}, then \binom{z_{1}}{x} is a k-excedance, if and only if \binom{z_{2}}{x} is one because of property (4.1). If x = z_{1}, consider the two cases : (i) z_{1} > z_{2} and necessarily z_{1} is large ; (ii) z_{1} < z_{2} and necessarily z_{1} is small. In case (i) (resp. (ii)) \binom{z_{1}}{z_{1}} and \binom{z_{2}}{z_{1}} are both k-excedances (resp. both non-k-excedances). Hence exc_{k} α′′ = exc_{k} α′.

Finally, Fact_{l} w′_{1} ∩ ]]x, z_{1}]]_{k} = Fact_{l} w′_{1} ∩ ]]x, z_{2}]]_{k}, as Fact_{l} w′_{1} ∩ (z_{1}, z_{2}] is empty if z_{1} is small and Fact_{l} w ∩ [z_{2}, z_{1}) is empty if z_{1} is large. Hence den_{k} α′′ = den_{k} α′.

Now consider an initial supercycle of the form α = ( \begin{matrix}u⋆ & ∞ \\ w & ⋆ \end{matrix} ), where

w is a word in the alphabet X. Then w = zu for some z ∈ X and ⋆ is the right-most factor in the k-factorization of w⋆. For such a supercycle α define

(4.8)  (des_{k}, maj_{k}) α = (des_{k}, maj_{k}) w (= (des_{k}, maj_{k})(w⋆)).

Property 4.4. If w is a word in the alphabet X and α = ( \begin{matrix}u⋆ & ∞ \\ w & ⋆ \end{matrix} ) is an initial supercycle, then

(exc_{k}, den_{k}) α = (des_{k}, maj_{k}) α = (des_{k}, maj_{k}) w.

Proof. Let w = x_{1}x_{2} … x_{m} and put x_{m+1} = ⋆, x_{m+2} = ∞. Then

exc_{k} ( \begin{matrix}x_{2} & x_{3} & … & x_{m} & ⋆ & ∞ \\ x_{1} & x_{2} & … & x_{m−1} & x_{m} & ⋆ \end{matrix} )

= |{i : 1 ≤ i ≤ m, x_{i} > x_{i+1} or x_{i} = x_{i+1} ∈ L}| = des_{k} x_{1}x_{2} … x_{m};

den_{k} ( \begin{matrix}x_{2} & x_{3} & … & x_{m} & ⋆ & ∞ \\ x_{1} & x_{2} & … & x_{m−1} & x_{m} & ⋆ \end{matrix} )

= ∑_{i=1}^{m+1} |Fact_{i}(x_{1}x_{2} … x_{m}⋆) ∩ ]]x_{i}, x_{i+1}]]_{k}| = maj_{k} x_{1}x_{2} … x_{m}.

The bijection of Theorem 1.2 is constructed as follows :

(a) Let w = x_{1}x_{2} … x_{m} = x_{1}u be a word in the alphabet X = [ r] ;

form the (initial) supercycle α = ( \begin{matrix}u⋆ & ∞ \\ w & ⋆ \end{matrix} ).

(b) Apply the mapping τ to α iteratively until a final supercycle is reached. This makes sense because of (4.6). Furthermore, when applying τ iteratively, the letter ⋆ remains the rightmost letter in all the super-

cycles within the iteration. Denote by α̃ = ( \begin{matrix}\overline{w} & ∞ \\ w̃ & ⋆ \end{matrix} ) the final supercycle

obtained. [Then \overline{w} is the non-decreasing rearrangement of w and w̃.]

(c) Define ρ by ρ(w) = w̃.

The proof of Theorem 1.2 is now completed as follows. First, to each word w ∈ C(v) there corresponds one and only one initial supercycle defined by (a). Next the mapping α ↦ α̃ is bijective by Property 4.2, as we go from α to α̃ by applying τ iteratively until a final supercycle is reached. Finally, the mapping α̃ ↦ w̃ is obviously bijective. On the other hand, the property (exc_{k}, den_{k}) ρ(w) = (des_{k}, maj_{k}) w follows from Properties 4.4 and 4.3 and from (3.5) and (3.7).

Example. Again consider the order 1 < 2 < 3 < ⋆ < 4 < 5 < ∞ (k = 2 and 4, 5 large) and start with the word w = 4, 4, 5, 1, 3, 1, 2, 3, 5, so

that the initial supercycle is α = (| \begin{matrix}4 & 5 & 1 \\ 4 & 4 & 5 \end{matrix} | \begin{matrix}3 \\ 1 \end{matrix} | \begin{matrix}1 & 2 & 3 & 5 & ⋆ \\ 3 & 1 & 2 & 3 & 5 \end{matrix} | \begin{matrix}∞ \\ ⋆ \end{matrix} ) (indicating

its k-factorization by vertical bars).

First, T^{−1} ( \begin{matrix}4 & 5 & 1 \\ 4 & 4 & 5 \end{matrix} ) = T_{1}T_{2} ( \begin{matrix}4 & 5 & 1 \\ 4 & 4 & 5 \end{matrix} ) = ( \begin{matrix}1 & 4 & 5 \\ 4 & 5 & 4 \end{matrix} ), so that α′′ =

(| \begin{matrix}1 & 4 & 5 \\ 4 & 5 & 4 \end{matrix} | \begin{matrix}3 \\ 1 \end{matrix} | \begin{matrix}1 & 2 & 3 & 5 & ⋆ \\ 3 & 1 & 2 & 3 & 5 \end{matrix} | \begin{matrix}∞ \\ ⋆ \end{matrix} ) (in the notations of (4.4)). To obtain α′ =

τ(α) we have to replace z_{2} = 1 by z_{1} = 4, so that α_{2} = α′ =

( \begin{matrix}4 & 4 & 5 \\ 4 & 5 & 4 \end{matrix} | \begin{matrix}3 \\ 1 \end{matrix} | \begin{matrix}1 & 2 & 3 & 5 & ⋆ \\ 3 & 1 & 2 & 3 & 5 \end{matrix} | \begin{matrix}∞ \\ ⋆ \end{matrix} ). Next T^{−1} ( \begin{matrix}4 & 4 & 5 & 3 \\ 4 & 5 & 4 & 1 \end{matrix} ) = T_{1}T_{2}T_{3} ( \begin{matrix}4 & 4 & 5 & 3 \\ 4 & 5 & 4 & 1 \end{matrix} ) =

( \begin{matrix}3 & 4 & 4 & 5 \\ 4 & 5 & 1 & 4 \end{matrix} ) and α′′ = ( \begin{matrix}3 & 4 & 4 & 5 \\ 4 & 5 & 1 & 4 \end{matrix} | \begin{matrix}1 & 2 & 3 & 5 & ⋆ \\ 3 & 1 & 2 & 3 & 5 \end{matrix} | \begin{matrix}∞ \\ ⋆ \end{matrix} ). To get the next su-

percycle we have to replace z_{2} = 3 by z_{1} = 1, so that α_{3} =

( \begin{matrix}1 & 4 & 4 & 5 \\ 4 & 5 & 1 & 4 \end{matrix} | \begin{matrix}1 & 2 & 3 & 5 & ⋆ \\ 3 & 1 & 2 & 3 & 5 \end{matrix} | \begin{matrix}∞ \\ ⋆ \end{matrix} ). Next the transformation T^{−1} to be applied

to ( \begin{matrix}1 & 4 & 4 & 5 & 1 & 2 & 3 & 5 & ⋆ \\ 4 & 5 & 1 & 4 & 3 & 1 & 2 & 3 & 5 \end{matrix} ) is (T_{5}T_{6}T_{7}T_{8})(T_{4}T_{5}T_{6})(T_{3}T_{4}T_{5})(T_{2}T_{3}T_{4}), as we

have to move the second “1”, the “2”, the “3” and the “⋆” to the

left. We then get T^{−1} ( \begin{matrix}1 & 4 & 4 & 5 & 1 & 2 & 3 & 5 & ⋆ \\ 4 & 5 & 1 & 4 & 3 & 1 & 2 & 3 & 5 \end{matrix} ) = ( \begin{matrix}1 & 1 & 2 & 3 & ⋆ & 4 & 4 & 5 & 5 \\ 4 & 5 & 1 & 4 & 1 & 3 & 2 & 3 & 5 \end{matrix} ), so

that α′′ = ( \begin{matrix}1 & 1 & 2 & 3 & ⋆ & 4 & 4 & 5 & 5 \\ 4 & 5 & 1 & 4 & 1 & 3 & 2 & 3 & 5 \end{matrix} | \begin{matrix}∞ \\ ⋆ \end{matrix} ). Finally, the “⋆” on the top row

is to be replaced by the penultimate k-record, i.e., “3.” We get α̃ =

( \begin{matrix}1 & 1 & 2 & 3 & 3 & 4 & 4 & 5 & 5 \\ 4 & 5 & 1 & 4 & 1 & 3 & 2 & 3 & 5 \end{matrix} | \begin{matrix}∞ \\ ⋆ \end{matrix} ). Thus ρ(w) = 4, 5, 1, 4, 1, 3, 2, 3, 5. We can verify

that (des_{k}, maj_{k}) w = (des_{k}, maj_{k}) α = (exc_{k}, den_{k}) α = (exc_{k}, den_{k}) α̃ = (exc_{k}, den_{k}) ρ(w) = (4, 18).

5. The invariance principle for den

We now turn to the proof of Theorem 1.3. As before, we use the notations exc_{D}, exc_{E}, etc., instead of exc_{k,D}, exc_{k,E}, etc.

Definition. Let D and E be total orderings on X. We say that E is obtained from D by a vital transposition if there exist letters a and b in X such that

(i) b <_{D} a and a covers b (i.e., there is no letter x such that b <_{D} x <_{D} a) ;

(ii) a <_{E} b and b covers a; (iii) for all x, y ∈ X, if {x, y} ≠ {a, b} then x <_{D} y if and only if x <_{E} y; (iv) one of a and b is large and the other is small.

In other words, E is obtained from D by simply interchanging the order of two successive letters, one large and one small.

Now let D be any total ordering on X. It is easy to see that there is a total ordering D′ on X, compatible with k, that can be obtained from D by a sequence of vital transpositions. By using the bijection ρ of the previous section, and Theorem 1.1, we can verify that it suffices to prove Theorem 1.3 on the assumption that E can be obtained from D by a vital transposition.

Thus for the remainder of this section we assume that E can be obtained from D by a vital transposition that interchanges the order of b and a. We will assume that b <_{D} a and a <_{E} b, and that b is small and a is large. In general, x, y, z will designate elements of X, while u, v, w will denote words in the alphabet X. We also denote cyclic intervals by ]]x, y]]_{D} or ]]x, y]]_{E} according as the ordering D or E is used, i.e., we suppress the

usual subscript k. If α and β are biwords, we write α ∼^{D} β (resp. α ∼^{E} β) to mean that α can be transformed into β by a sequence of D-transpositions (resp. E-transpositions), i.e., Han transpositions defined by means of the ordering D (resp. E).

5.1. A study of cycles. The following relations on cyclic intervals based upon orderings D and E are easily checked by looking at Fig. 3, where cyclic intervals are materialized by oriented rectangles.

(5.1) ]]b, a]]_{D} = ∅; ]]a, b]]_{D} = X; ]]x, b]]_{D} = ]]x, a]]_{D} (x ∈ X);

(5.2) ]]b, a]]_{E} = X \ {a, b}; ]]a, b]]_{E} = {a, b};

]]x, b]]_{E} = ]]x, a]]_{E} ⊎ {a, b} (x ≠ a, b);

(5.3) ]]x, a]]_{D} = ]]x, a]]_{E} ∪ {b}; ]]x, b]]_{E} = ]]x, b]]_{D} ∪ {a};

]]x, y]]_{D} = ]]x, y]]_{E} (x, y ≠ a, b).

We will use the notions of a-cycle, a \ b-cycle, (a, b)-free biword, defined as follows : an a-cycle on X is a biword γ = ( \begin{matrix}u & a \\ a & u \end{matrix} ) = [a u], such that a

does not occur in the word u. The a-cycle γ = [a u] is called an a \ b-cycle if furthermore b does not occur in u. The notions of b-cycle and b \ a-cycle are defined in a similar way. A biword is said to be (a, b)-free, if it does not involve the letters a or b.

[figure: x; b; a; D; b; a; x; D]

[figure: x; a; b; E; a; b; x; E]

Fig. 3

Lemma 5.1. If α is an (a, b)-free biword, or an a \ b-cycle, or a b \ acycle, then

(5.4)  (exc_{D}, den_{D}) α = (exc_{E}, den_{E}) α.

Proof. Let α = ( \begin{matrix}u \\ v \end{matrix} ) = ( \begin{matrix}y_{1} … y_{m} \\ x_{1} … x_{m} \end{matrix} ) be any one of the forementioned

three biwords. If m = 1, relation (5.4) is trivial. When m ≥ 2, the definition of exc_{k} (given in (3.3)) requires the comparison of the elements in each pair (x_{i}, y_{i}) (1 ≤ i ≤ m). But such pairs involve at most one of the letters a or b. Accordingly, x_{i} ≥_{D} y_{i} if and only if x_{i} ≥_{E} y_{i} and then exc_{D} α = exc_{E} α.

For the same reason, z ∈ ]]x_{i}, y_{i}]]_{D} if and only if z ∈ ]]x_{i}, y_{i}]]_{E}. From the definition of den_{k} (given in (3.4)) it follows that den_{D} α = den_{E} α.

Lemma 5.2. Let α be a biword of the form ( \begin{matrix}w_{1} \\ w_{2} \end{matrix} )γ, where γ is a cycle. Then (5.5) exc_{D} α = exc_{D}( \begin{matrix}w_{1} \\ w_{2} \end{matrix} ) + exc_{D} γ;

(5.6) den_{D} α = den_{D}( \begin{matrix}w_{1} \\ w_{2} \end{matrix} ) + den_{D} γ + l(w_{2}) exc_{D} γ;

where l(w_{2}) stands for the length of w_{2}.

Proof. This result is essentially [14, lemma 5.5]. Again we just have to

verify that if γ = ( \begin{matrix}y_{1} … y_{n} \\ x_{1} … x_{n} \end{matrix} ) is a cycle, then ]]x_{1}, y_{1}]]_{D} ⊎ ⋯ ⊎ ]]x_{n}, y_{n}]]_{D}

is the multiset containing each letter of X^{+} with multiplicity exc_{D} γ.

Definition. An (a, b)-sequence is defined to be a sequence of biwords

σ = (w̃_{0}, γ_{1}, …, γ_{h}) (h ≥ 0),

where w̃_{0} is an (a, b)-free biword (possibly empty) of the form ( \begin{matrix}\overline{w} & 0 \\ w_{0} \end{matrix} ) (\overline{w}_{0}

being the non-decreasing rearrangement of the word w_{0}), and where each γ_{i} is either an a \ b-cycle or a b \ a-cycle.

If σ = (w̃_{0}, γ_{1}, …, γ_{h}) is an (a, b)-sequence, the juxtaposition product of the biwords w̃_{0}γ_{1} … γ_{h} will be denoted by {σ}.

Lemma 5.3. If σ is an (a, b)-sequence, then

(5.7)  (exc_{D}, den_{D}){σ} = (exc_{E}, exc_{E}){σ}.

Proof. If σ = (w̃_{0}, γ_{1}, …, γ_{h}), then

exc_{D}{σ} = exc_{D} w̃_{0} + exc_{D} γ_{1} + ⋯ + exc_{D} γ_{h}  [by Lemma 5.2]
= exc_{E} w̃_{0} + exc_{E} γ_{1} + ⋯ + exc_{E} γ_{h}  [by Lemma 5.1]
= exc_{E}{σ}.  [by Lemma 5.2]

In the same manner

den_{D}{σ} = den_{D} w̃_{0} + den_{D} γ_{1} + l(w_{0}) exc_{D} γ_{1}
+ ⋯ + den_{D} γ_{h} + l(w_{0}γ_{2} … γ_{h−1}) exc_{D} γ_{h} [by (5.6)]
= den_{E} w̃_{0} + den_{E} γ_{1} + l(w_{0}) exc_{E} γ_{1}
+ ⋯ + den_{E} γ_{h} + l(w_{0}γ_{2} … γ_{h−1}) exc_{E} γ_{h} [by (5.4)]
= den_{E}{σ}.

Denote by Σ(c,d; a, b) the set of all (a, b)-sequences σ = (w̃_{0}, γ_{1}, …, γ_{h}),

such that w̃_{0} = ( \begin{matrix}\overline{w} & 0 \\ w_{0} \end{matrix} ), γ_{1} = [w_{1}], …, γ_{h} = [w_{h}], and the juxtaposition

product of the words w_{0}w_{1} … w_{h} belongs to R(c, d). The (a, b)-sequences in Σ(c,d; a, b) may be regarded as cycle decompositions of biwords based on the two letters a, b. To see that Σ(c, d; a, b) is equinumerous with R(c, d), we can start with a word w ∈ R(c, d) and set up a factorization (u_{0}, c_{1}u_{1}, c_{2}u_{2}, …, c_{n}u_{n}) of w, where the c_{i}’s are letters either equal to a or b, and the u_{i}’s are words with no a’s and no b’s. We simply get the previous factorization by cutting w just before each occurrence of a or b.

Clearly, σ = (( \begin{matrix}\overline{u} & 0 \\ u_{0} \end{matrix} ), [c_{1}u_{1}], [c_{2}u_{2}], …, [c_{n}u_{n}] ) belongs to Σ(c,d; a, b) and

the mapping w ↦ σ is bijective.

More elaborate bijections will be needed to prove our theorem 1.3.

Denote by R̃(c, d) the set of all biwords w̃ = ( \overline{w} ; w ), where w ∈ R(c, d).

The first bijection

(5.8)  ξ_{D} : w̃ ↦ ξ_{D}(w̃) = (w̃_{0}, γ_{1}, …, γ_{h})

of R̃(c, d) onto Σ(c, d; a; b), constructed in the next subsection 5.2, will have the property that the juxtaposition product {ξ_{D}(w̃)} = w̃_{0}γ_{1} … γ_{h}

can be derived from the biword w̃ = ( \overline{w} ; w ) by a well-defined sequence of

Han D-transpositions (i.e., Han transpositions defined by means of the ordering D). Therefore, by Lemma 3.6

(5.9)  (exc_{D}, den_{D}) w̃ = (exc_{D}, den_{D}) {ξ_{D}(w̃)}.

In the last subsection 5.3 another bijection

(5.10)  ξ_{E} : w̃ ↦ ξ_{E}(w̃)

of R̃(c, d) onto Σ(c, d; a; b) will be constructed. This time the juxtaposition product {ξ_{E}(w̃)} will be obtainable from w̃ by a sequence of Han Etranspositions. Therefore

(5.11)  (exc_{E}, den_{E}) w̃ = (exc_{E}, den_{E}) {ξ_{E}(w̃)}.

The bijection δ of Theorem 3.1 will then be defined by

(5.12)  δ̃(w) = ξ_{E}^{−1}ξ_{D}(w̃).

It satisfies our requirements, as

(exc_{E}, den_{E})δ(w) = (exc_{E}, den_{E}) δ̃(w) + |δ(w) ∩ L|  [by (3.6)]
= (exc_{E}, den_{E}) {ξ_{E}δ̃(w)} + |δ(w) ∩ L| [by (5.11)]
= (exc_{E}, den_{E}) {ξ_{D}(w̃)} + |δ(w) ∩ L| [by (5.12)]
= (exc_{D}, den_{D}) {ξ_{D}(w̃)} + |δ(w) ∩ L| [by (5.7)]
= (exc_{D}, den_{D}) w̃ + |δ(w) ∩ L|  [by (5.9)]
= (exc_{D}, den_{D}) w.  [by (3.6)]

5.2. Transforming biwords under D. Throughout this subsection, we use the total ordering D on X and give the construction of ξ_{D} announced in (5.8).

Let w be a word in R(c, d), and let x be any letter occurring in w.

Next, form the biword w̃ = ( \overline{w} ; w ). Using the least possible number of Han

D-transpositions, move the right-most x in the top row of w̃ to the righthand end of that row, forming the biword α. Suppose that the biletter

( \begin{matrix}x \\ y \end{matrix} ) occurs at the right-hand end of α. If y = x then put γ = [x]. If not,

use Han transpositions to move the right-most y in the top row of α to the penultimate position in that row, forming a new biword β with the biword

( \begin{matrix}y & x \\ z & y \end{matrix} ) occupying its right-most two columns. Continue in this way until

a cycle γ is obtained. That cycle is necessarily an x-cycle ; denote it by γ_{1}. Thus w̃ has been transformed into a product δγ_{1} for some biword δ. Since the letters in the top row of δ will still be non-decreasing, it follows that δ = w̃′ for some word w′. (Actually, the present algorithm is described in detail in [14, Algorithme 4.2] in the context of (k = 0)-cyclic intervals.) If w′ has no occurrence of x, put η_{D,x}(w̃) = (w̃′, γ_{1}). Otherwise, apply the above algorithm to w̃′. After finitely many steps w̃ is transformed into a sequence of the form (ũ, γ_{n}, …, γ_{2}, γ_{1}), where u has no occurrence of x and the γ_{i}’s are all x-cycles. Again, put

(5.13)  η_{D,x}(w̃) = (ũ, γ_{n}, …, γ_{2}, γ_{1}).

Finally, let η_{D,x}(w̃) = w̃ if w has no occurrence of x. Clearly, η_{D,x} has a well-defined inverse mapping η_{D,x}^{−1} that maps each forementioned sequence onto a biword w̃.

Now if γ is a a-cycle, written as γ = [au_{1}bu_{2}b … u_{n−1}bu_{n}], where all the u_{i}’s have no occurrences of b (and of course of a!), define ζ_{D}(γ) to be the sequence

(5.14)  ζ_{D}(γ) = ( [au_{1}], [bu_{2}], …, [bu_{n−1}], [bu_{n}] ).

If γ has no occurences of b, i.e., γ is an a\b-cycle, then we define ζ_{D}(γ) = γ. Again the inverse mapping ζ_{D}^{−1} is obviously defined.

Lemma 5.4. Let u be a word and y, z be letters. Then

(5.15)  ( \begin{matrix}b & u & a \\ y & z & u \end{matrix} ) ∼^{D} ( \begin{matrix}a & u & b \\ y & z & u \end{matrix} ).

Proof. If u is empty, then ( \begin{matrix}b & a \\ y & z \end{matrix} ) ∼^{D} ( \begin{matrix}a & b \\ y & z \end{matrix} ) since ]]b, a]]_{D} = ∅. Suppose

that (5.15) is true when the length of u is l ≥ 0. Assume first that y and z are neighbours with respect to (b, x). Then ( \begin{matrix}b & x & u & a \\ y & z & x & u \end{matrix} ) ∼^{D} ( \begin{matrix}x & b & u & a \\ y & z & x & u \end{matrix} ) ∼^{D}

( \begin{matrix}x & a & u & b \\ y & z & x & u \end{matrix} ), by the inductive hypothesis. As y and z are neighbours with

respect to (a, x), since ]]b, x]]_{D} = ]]a, x]]_{D}, we have ( \begin{matrix}x & a \\ y & z \end{matrix} ) ∼^{D} ( \begin{matrix}a & x \\ y & z \end{matrix} ) and

so ( \begin{matrix}b & x & u & a \\ y & z & x & u \end{matrix} ) ∼^{D} ( \begin{matrix}a & x & u & b \\ y & z & x & u \end{matrix} ). The case in which y and z are strangers with

respect to (b, x) is treated similarly.

Let γ be an a-cycle and ζ_{D}(γ) = (δ_{0}, δ_{1}, …, δ_{m}) as in (5.14). Denote by {ζ_{D}(γ)} the juxtaposition product δ_{0}δ_{1} … δ_{m}.

Proposition 5.5. If γ is an a-cycle, then

(5.16)  γ ∼^{D} {ζ_{D}(γ)}.

Proof. Let γ = [au_{1}bu_{2}] with no occurrences of b in u_{2}. Write

au_{1} = v_{1}y for y ∈ X. Then γ = ( \begin{matrix}u_{1} & b & u_{2} & a \\ a & u_{1} & b & u_{2} \end{matrix} ) = ( \begin{matrix}u_{1} & b & u_{2} & a \\ v_{1} & y & b & u_{2} \end{matrix} ) ∼^{D}

( \begin{matrix}u_{1} & a & u_{2} & b \\ v_{1} & y & b & u_{2} \end{matrix} ) = [au_{1}][bu_{2}], by using (5.15). We then conclude by induc-

tion on the number of b’s in [au_{1}].

The construction of ξ_{D}.

(1) Start with w ∈ R(c, d) and form w̃ as before.

(2) Form η_{D,a}(w̃) = (ũ, γ_{n}, …, γ_{2}, γ_{1}), as in (5.13) with x = a. Note that the sequence reduces to ũ = w̃, if there is no occurrence of a in w. Otherwise, the sequence involves the a-cycles (γ_{n}, …, γ_{2}, γ_{1}).

(3) If necessary, apply ζ_{D} to each of the a-cycles γ_{n}, …, γ_{2}, γ_{1}, to obtain

ζ_{D}(γ_{i}) = ( δ_{i,0}, δ_{i,1}, …, δ_{i,m_{i}−1}, δ_{i,m_{i}} ) (i = n, …, 2, 1).

As each γ_{i} is an a-sequence, each δ_{i,0} will be an a \ b-cycle and the other δ_{i,1}, …, δ_{i,m_{i}−1}, δ_{i,m_{i}} will be b \ a-cycles.

(4) Apply η_{D,b} to the biword ũ that contains no a, to obtain η_{D,b}(ũ) = (u′, γ′′_{n′′}, …, γ′′_{2}, γ′′_{1}), as in (5.13) with x = b. Note that the sequence reduces to u′ = ũ, if there is no occurrence of b in u.

(5) Then ξ_{D}(w̃) is the juxtaposition product of the sequences :

ξ_{D}(w̃) = (η_{D,b}(ũ), ζ_{D}(γ_{n}), …, ζ_{D}(γ_{1}))

= (u′, γ′′_{n′′}, …, γ′′_{2}, γ′′_{1}, δ_{n,0}, δ_{n,1}, …, δ_{n,m_{n}−1}, δ_{n,m_{n}}, …, δ_{1,0}, δ_{1,1}, …, δ_{1,m_{1}−1}, δ_{1,m_{1}}).

Property (5.9) holds since η_{D,b}(ũ) can be obtained from w̃ by a sequence of D-transpositions, as well as the ζ_{D}(γ_{i})’s by Proposition 5.5.

To recover the biword w̃ from an (a, b)-sequence σ = (w̃_{0}, γ_{1}, …, γ_{h}), (5′) cut the sequence (γ_{1}, …, γ_{h}) before each a \ b-cycle to obtain

(ω_{0} | ω_{1} | … | ω_{l}), where each ω_{0} is empty or is a (juxtaposition) product of b \ a-cycles and the other ω_{i} (i ≥ 1) are juxtaposition products of one a \ b-cycle followed by b \ a-cycles.

(4′) Determine η_{D,b}^{−1}(w̃_{0}, ω_{0}).

(3′) Determine ζ_{D}^{−1}(ω_{i}) for i = 1, …, l.

(2′) The biword w̃ is the image by η_{D,a}^{−1} of the sequence

(η_{D,b}^{−1}(w̃_{0}, ω_{0}), ζ_{D}^{−1}(ω_{1}), …, ζ_{D}^{−1}(ω_{l})). (1′) The bottom row of the latter biword is the word w.

Example. Let X = [ 5 ] and let D be the natural ordering on X. Let 1, 2 and 3 be small and 4 and 5 be large. Thus a = 4, b = 3. Let w = 3, 2, 2, 4, 3, 5, 1, 5, 3, 1. Then

(1) \overline{w} = 1, 1, 2, 2, 3, 3, 3, 4, 5, 5 and w̃ = ( \begin{matrix}1 & 1 & 2 & 2 & 3 & 3 & 3 & 4 & 5 & 5 \\ 3 & 2 & 2 & 4 & 3 & 5 & 1 & 5 & 3 & 1 \end{matrix} ).

(2) Sort out the 4-cycle : η_{D,4}(w̃) = (( \begin{matrix}2 & 2 & 3 & 5 \\ 2 & 3 & 2 & 5 \end{matrix} ), [4, 1, 5, 3, 3, 1]).

(3) Then break that 4-cycle : ζ_{D}([4, 1, 5, 3, 3, 1] = [4, 1, 5][3][3, 1].

(4) Sort out the 3-cycles : η_{D,3}(ũ) = η_{D,3}( \begin{matrix}2 & 2 & 3 & 5 \\ 2 & 3 & 2 & 5 \end{matrix} ) = ( \begin{matrix}2 \\ 2 \end{matrix} )[3, 2, 5].

(5) Thus ξ_{D}(w̃) = (˜2, [3, 2, 5], [4, 1, 5], [3], [3, 1]).

5.3. Transforming biwords under E. Throughout this section, we use the total ordering E on X. Our aim is to show that the algorithm described above for the construction of ξ_{D} also applies to ξ_{E}, once the subscript D is replaced by E. Accordingly, the mappings η_{E,x} and ζ_{E} are to be defined, as well as their inverses.

The definition of η_{E,x} is the same as the definition of η_{D,x} shown in (5.13), the Han E-transpositions replacing the Han D-transpositions. The reverse mapping η_{E,x}^{−1} is also derived in the same way.

The definition of ζ_{E} requires a more detailed analysis of the ordering E. For x, y ∉ {a, b} define x ≺ y if and only if a and x are neighbours with respect to (a, y). Then x ≺ x if x is small, while x ⊀ x if x is large. Next, we have x ≺ y and x ≠ y if and only if one of the three conditions holds :

(i) x <_{E} y <_{E} a <_{E} b; (ii) a <_{E} b <_{E} x <_{E} y; (iii) y <_{E} a <_{E} b <_{E} x. Note that by (5.2), x ≺ y if and only if a and x are strangers with respect to (b, y).

Let w = x_{1}x_{2} … x_{m} be a non-empty word in the alphabet X \ {a, b}. We define a bijection h ↦ l of the interval {0, 1, …, m} onto {0, 1, …, m} as follows [by convention : x_{0} = x_{m+1} = ∞] :

(i) if h = 0, or if 1 ≤ h ≤ m − 1 and x_{h} ≺ x_{h+1}, define l to be the smallest integer such that h + 1 ≤ l and x_{l} ≺ x_{l+1}.

(ii) if 1 ≤ h ≤ m − 1 and x_{h} ⊀ x_{h+1}, or if h = m, define l to be the greatest integer such that l + 1 ≤ h and x_{l} ⊀ x_{l+1}.

On Fig. 4 part of the word w is represented as a polygonal line in the Euclidean plane joining the points (h, x_{h}) to (h + 1, x_{h+1}), etc. In case (i) the integer l is the abscissa of the nearest rise x_{l} ≺ x_{l+1} to the right of the rise x_{h} ≺ x_{h+1}, while in case (ii) l is the abscissa of the nearest descent x_{l} ⊀ x_{l+1} to the left of the descent x_{h} ⊀ x_{h+1}. This suffices to show that h ↦ l is bijective, and the inverse l ↦ h is defined in the same way, using the forementioned geometric representation, i.e.,

[figure: x_{h}; x_{h+1}; x_{l}; x_{l+1}; h; h+1; l; l+1; case (i); x_{l}; x_{l+1}; x_{h}; x_{h+1}; l; l+1; h; h+1; case (ii)]

Fig. 4

(i) if l = m, or if 1 ≤ l ≤ m − 1 and x_{l} ≺ x_{l+1}, define h to be the greatest integer such that h + 1 ≤ l and x_{h} ≺ x_{h+1} ;

(ii) if 1 ≤ h ≤ m − 1 and x_{l} ⊀ x_{l+1}, or if l = 0, define h to be the smallest integer such that l + 1 ≤ h and x_{h} ⊀ x_{h+1}.

Let φ be the bijection that maps the ordered pair of words determined by h onto the pair of words determined by l, i.e.,

(5.17)  φ(x_{1} … x_{h}, x_{h+1} … x_{m}) = (x_{1} … x_{l}, x_{l+1} … x_{m})

and denote by φ^{−1} its inverse. The bijection φ is used in the definition of the following transformation Φ. Let n ≥ 0 and U = (u_{0}, u_{1}, …, u_{n}) be a sequence of words in the alphabet X \ {a, b} (some possibly empty). If n = 0, define Φ(U) = (u_{0}). Suppose n ≥ 1 ; then Φ(U) is defined recursively by :

φ(u_{n−1}, u_{n}) = (u′_{n−1}, v_{n});
(5.18)  Φ(u_{0}, u_{1}, …, u_{n−2}, u′_{n−1}) = (v_{0}, v_{1}, …, v_{n−1});
Φ(U) = Φ(u_{0}, u_{1}, …, u_{n−2}, u_{n−1}, u_{n}) = (v_{0}, v_{1}, …, v_{n−1}, v_{n}).

As φ is bijective, Φ is also bijective with Φ^{−1} given by :

if Φ^{−1}(v_{0}, v_{1}, …, v_{n−2}, v_{n−1}) = (u_{0}, u_{1}, …, u_{n−2}, u′_{n−1}), and φ^{−1}(u′_{n−1}, v_{n}) = (u_{n−1}, u_{n}), then Φ^{−1}(v_{0}, v_{1}, …, v_{n−1}, v_{n}) = (u_{0}, u_{1}, …, u_{n−2}, u_{n−1}, u_{n}).

Example. Consider the ordering 1 <_{E} 2 <_{E} 4 <_{E} 3 <_{E} 5, where 1, 2, 3 are small, while 4, 5 are large. Let a = 4 and b = 3, so that 5 ≺ 1 ≺ 2. Next consider the sequence of words U = (1, 2, 2, 5 ; 5, 5, 2 ; 1, 2, 5 ; e; 2, 1, 5, 1) separated by semi-colons, with e denoting the empty word. We have successively :

φ(e; 2 ⊀ 1 ⊀ 5 ≺ 1) = (2, 1, 5 ; 1), so that u′_{3} = 2, 1, 5 and v_{4} = 1 ; as 5 ≺ 2, φ(1, 2, 5 ; 2 ⊀ 1 ⊀ 5) = (1, 2, 5, 2, 1, 5 ; e) and v_{3} = e; as 2 ⊀ 1, φ(5 ⊀ 5 ≺ 2 ; 1, 2, 5, 2, 1, 5) = (5 ; 5, 2, 1, 2, 5, 2, 1, 5) and

v_{2} = 5, 2, 1, 2, 5, 2, 1, 5 ;

as 5 ⊀ 5, φ(1 ≺ 2 ≺ 2 ⊀ 5 ; 5) = (1, 2, 2 ; 5, 5) and v_{1} = 5, 5, v_{0} = 1, 2, 2. Thus V = (1, 2, 2 ; 5, 5 ; 5, 2, 1, 2, 5, 2, 1, 5 ; e; 1).

We are now ready to define the bijection ζ_{E}. Let γ = [bu_{0}au_{1}a … au_{n}] be a b-cycle, the words u_{i}’s having no occurrences of a and b. Let Φ(u_{0}, u_{1}, …, u_{n}) = (v_{0}, v_{1}, …, v_{n}). Then put

(5.19)  ζ_{E}(γ) = ([bv_{0}], [av_{1}], …, [av_{n}]).

Following the recursive definition of Φ we can also write when n ≥ 1 : if φ(u_{n−1}, u_{n}) = (u′_{n−1}, v_{n}) and γ′ = [bu_{0}au_{1} … au_{n−2}au′_{n−1}], then

(5.20)  ζ_{E}(γ) = (ζ_{E}(γ′), [av_{n}]).

From what has been said about φ and Φ the mapping ζ_{E} is clearly bijective and its inverse ζ_{E}^{−1} well-defined. The crucial point is to prove the analogue of Proposition 5.5, i.e., Proposition 5.7 that we will state after the following lemma.

Lemma 5.6. Let u be a word with no occurrences of a and b and y, z ≠ a, b. Then

(5.21)  ( \begin{matrix}a & u & b \\ y & z & u \end{matrix} ) ∼^{E} ( \begin{matrix}b & u & a \\ y & z & u \end{matrix} ).

Proof. The proof is very similar to the proof of Lemma 5.4 with the sole difference that ]]a, b]]_{E} = {a, b}, while ]]a, b]]_{D} = ∅, but the same steps hold, because u has no occurrences of a and b and y, z ≠ a, b.

Proposition 5.7. If γ is a b-cycle, then

(5.22)  γ ∼^{E} {ζ_{E}(γ)}.

Proof. Let γ = [bu_{0}au_{1}a … au_{n}] with no occurrences of a and b in the u_{i}’s. If n = 0, there is nothing to prove since ζ_{E}(γ) = (γ). Suppose n ≥ 1 and take up again the notations of (5.19). Also, let u_{n−1} = x_{1} … x_{h}, u_{n} = x_{h+1} … x_{m}, v′_{n−1} = x_{1} … x_{l}, v_{n} = x_{l+1} … x_{m}. Finally, let w_{n−2} = u_{0}au_{1}a … au_{n−2}, if n ≥ 2 and w_{n−2} = e, if n = 1. Consider the two cases (i) and (ii) introduced in the definition of φ :

Case (i) reads either h = 0, i.e., u_{n−1} empty, or 1 ≤ h ≤ m − 1 and x_{h} ≺ x_{h+1} ; furthermore l satisfies the relations : h + 1 ≤ l, x_{h+1} ⊀ x_{h+2} ⊀ ⋯ ⊀ x_{l−1} ⊀ x_{l}, but x_{l} ≺ x_{l+1}. If h = 0 and z = a

or b, we have ( \begin{matrix}a & x_{h+1} \\ z & a \end{matrix} ) ∼^{E} ( \begin{matrix}x_{h+1} & a \\ z & a \end{matrix} ); also ( \begin{matrix}a & x_{h+1} \\ x_{h} & a \end{matrix} ) ∼^{E} ( \begin{matrix}x_{h+1} & a \\ x_{h} & a \end{matrix} ) if

1 ≤ h. Moreover, as ( \begin{matrix}a & x_{h+2} \\ a & x_{h+1} \end{matrix} ) ∼^{E} ( \begin{matrix}x_{h+2} & a \\ x_{h+1} & a \end{matrix} ), …, ( \begin{matrix}a & x_{l} \\ a & x_{l−1} \end{matrix} ) ∼^{E} ( \begin{matrix}x_{l} & a \\ x_{l−1} & a \end{matrix} ),

but ( \begin{matrix}a & x_{l+1} \\ a & x_{l} \end{matrix} ) ∼^{E} ( \begin{matrix}x_{l+1} & a \\ a & x_{l} \end{matrix} ), moving a (using Han E-transpositions) to

the right, just after x_{l+1}, transforms γ into the biword :

γ′′ = ( \begin{matrix}w_{n−2} & x_{1} & … & x_{h} & x_{h+1} & x_{h+2} & … & x_{l} & x_{l+1} & a & x_{l+2} & … & b \\ b & w_{n−2} & … & x_{h−1} & x_{h} & x_{h+1} & … & x_{l−1} & a & x_{l} & x_{l+1} & … & x_{m} \end{matrix} ).

Finally,

γ′′ ∼^{E} ( \begin{matrix}w_{n−2} & x_{1} & … & x_{l} & x_{l+1} & b & x_{l+2} & … & a \\ b & w_{n−2} & … & x_{l−1} & a & x_{l} & x_{l+1} & … & x_{m} \end{matrix} )  [by Lemma 5.6]
∼^{E} ( \begin{matrix}w_{n−2} & x_{1} & … & x_{l} & b & x_{l+1} & x_{l+2} & … & a \\ b & w_{n−2} & … & x_{l−1} & x_{l} & a & x_{l+1} & … & x_{m} \end{matrix} )  [as x_{l} ≺ x_{l+1}]

= [bw_{n−2}v′_{n−1}][av_{n}] = γ′[av_{n}] ∼^{E} {ζ_{E}(γ′)[av_{n}]} = {ζ_{E}(γ)},

by induction on n (see (5.20) and (5.22)).

Case (ii) reads either h = m, i.e., u_{n} empty, or 1 ≤ h ≤ m − 1 and x_{h} ⊀ x_{h+1} ; this time l satisfies the relations : l ≤ h − 1, x_{l+1} ≺ x_{l+2} ≺

⋯ ≺ x_{h−1} ≺ x_{h}, but x_{l} ⊀ x_{l+1}. If h = m, then ( \begin{matrix}a & b \\ x_{h} & a \end{matrix} ) ∼^{E} ( \begin{matrix}b & a \\ a & x_{h} \end{matrix} ), but

( \begin{matrix}a & x_{h+1} \\ x_{h} & a \end{matrix} ) ∼^{E} ( \begin{matrix}x_{h+1} & a \\ a & x_{h} \end{matrix} ) if h ≤ m − 1. First we apply either one of those

Han transpositions on γ and make use of Lemma 5.6 to get the biword

γ′′ = ( \begin{matrix}w_{n−2} & x_{1} & … & x_{h} & x_{h+1} & b & x_{h+2} & … & x_{m} & a \\ b & w_{n−2} & … & x_{h−1} & a & x_{h} & x_{h+1} & … & x_{m−1} & x_{m} \end{matrix} ).

Now, as x_{h} ⊀ x_{h+1}, we have ( \begin{matrix}x_{h+1} & b \\ a & x_{h} \end{matrix} ) ∼^{E} ( \begin{matrix}b & x_{h+1} \\ a & x_{h} \end{matrix} ). Also the relations

x_{h−1} ≺ x_{h}, …, x_{l+1} ≺ x_{l+2} imply : ( \begin{matrix}x_{h} & b \\ x_{h−1} & a \end{matrix} ) ∼^{E} ( \begin{matrix}b & x_{h} \\ a & x_{h−1} \end{matrix} ), …,

( \begin{matrix}x_{l+2} & b \\ x_{l+1} & a \end{matrix} ) ∼^{E} ( \begin{matrix}b & x_{l+2} \\ a & x_{l+1} \end{matrix} ). Thus γ′′ is transformed into the biword

γ′′′ = ( \begin{matrix}w_{n−2} & x_{1} & … & x_{l} & x_{l+1} & b & x_{l+2} & … & x_{m} & a \\ b & w_{n−2} & … & x_{l−1} & x_{l} & a & x_{l+1} & … & x_{m−1} & x_{m} \end{matrix} )

∼^{E} ( \begin{matrix}w_{n−2} & x_{1} & … & x_{l} & b & x_{l+1} & x_{l+2} & … & x_{m} & a \\ b & w_{n−2} & … & x_{l−1} & x_{l} & a & x_{l+1} & … & x_{m−1} & x_{m} \end{matrix} )

= γ′[av_{n}] ∼^{E} {ζ_{E}(γ′)[av_{n}]} = {ζ_{E}(γ)},

using the fact that x_{l} ⊀ x_{l+1} in the second step.

The construction of ξ_{E}.

(1) Start with w ∈ R(c, d) and form w̃.

(2) Form η_{E,b}(w̃) = (ũ, γ_{n}, …, γ_{2}, γ_{1}), as in (5.13) with x = b using Han E-transpositions instead of Han D-transpositions.

(3) If necessary, apply ζ_{E} to each of the b-cycles γ_{n}, …, γ_{2}, γ_{1}.

(4) Apply η_{E,a} to the biword ũ.

(5) Then ξ_{E}(w̃) is the juxtaposition product of the sequences : ξ_{E}(w̃) = (η_{E,a}(ũ), ζ_{E}(γ_{n}), …, ζ_{D}(γ_{1})).

Property (5.11) holds since η_{E,a}(ũ) can be obtained from w̃ by a sequence of E-transpositions, as well as the ζ_{E}(γ_{i})’s by Proposition 5.7.

We recover the biword w̃ from each (a, b)-sequence σ by reversing the previous steps, as was explained after the definition of ξ_{D} given in the previous subsection.

Example. Let X = [ 5 ] and let D be the natural ordering on X. Let 1, 2 and 3 be small and 4 and 5 be large. Thus a = 4, b = 3. It was shown in the previous subsection that the word w = 3, 2, 2, 4, 3, 5, 1, 5, 3, 1 was mapped onto the (a, b)-sequence : ξ_{D}(w̃) = (˜2, [3, 2, 5], [4, 1, 5], [3], [3, 1]).

Reverse the orders of 3 and 4 to obtain the E-ordering as in the previous example. The construction of ξ_{E}^{−1}ξ_{D}(w̃) is made as follows :

(5′) Cut the sequence of a- or b-cycles just before each b \ a-cycle : | [3, 2, 5], [4, 1, 5] | [3] | [3, 1].

(4′) The sequence of cycles does not start with an a-cycle : η_{E,4}^{−1}(˜2) = ˜2. (3′) Apply ζ_{E}^{−1} to each sequence determined by the factorization in (5′) :

as 5 ≺ 1, φ^{−1}(2, 5 ; 1, 5) = (e; 2, 5, 1, 5), so that ζ_{E}^{−1}([3, 2, 5], [4, 1, 5]) = [3, 4, 2, 5, 1, 5] ; also ζ_{E}^{−1}([3]) = [3] and ζ_{E}^{−1}([3, 1]) = [3, 1].

(2′) Determine η_{E,3}^{−1}(˜2, [3, 4, 2, 5, 1, 5], [3], [3, 1]), i.e., form the juxtapo-

sition product ( \begin{matrix}2 & 4 & 2 & 5 & 1 & 5 & 3 & 3 & 1 & 3 \\ 2 & 3 & 4 & 2 & 5 & 1 & 5 & 3 & 3 & 1 \end{matrix} ) and transform the top row into a

non-decreasing row using as few Han E-transpositions as possible (move the second leftmost 2 to the second position, then the leftmost 1 to the

first position, …) to obtain the biword ( \begin{matrix}1 & 1 & 2 & 2 & 4 & 3 & 3 & 3 & 5 & 5 \\ 3 & 2 & 2 & 4 & 5 & 3 & 1 & 5 & 3 & 1 \end{matrix} ).

(1′) Then, as defined in (5.12), δ(w) = 3, 2, 2, 4, 5, 3, 1, 5, 3, 1. We can verify that (exc_{D}, den_{D})(w) = (exc_{E}, den_{E})(δ(w)) = (5, 24).

6. Recurrence relations

In this section we give recurrence relations for the generating function A_{c,d}(t, q). Write

(6.1)  A_{c,d}(t, q) = ∑_{s≥0} A_{c,d,s}(q)t^{s},

so that A_{c,d,s}(q) is the generating polynomial for the words w ∈ R(c, d) such that des_{k} w = s by the k-major index. We will use the notation [s]_{q} for 1 + q + q^{2} + ⋯ + q^{s−1}.

Proposition 6.1. With m = c + d the following relations hold

(6.2) (1 − q^{c_{j}+1})A_{c+1_{j},d}(t, q)

= (1 − tq^{1+m})A_{c,d}(t, q) − q^{c_{j}+1}(1 − t)A_{c,d}(tq, q);

(6.3) (1 − q^{−d_{k}−1})A_{c,d+1_{k}}(t, q)

= −(1 − tq^{1+m})A_{c,d}(t, q) + q^{−d_{k}}(1 − t)A_{c,d}(tq, q);

(6.4) [c_{j} + 1]_{q}A_{c+1_{j},d,s}(q)

= [c_{j} + 1 + s]_{q}A_{c,d,s}(q) + q^{s+c_{j}}[1 + m − s − c_{j}]_{q}A_{c,d,s−1}(q);

(6.5) [d_{k} + 1]_{q}A_{c,d+1_{k},s}(q)

= q^{d_{k}+1}[s − d_{k}]_{q}A_{c,d,s}(q) + q^{s}[2 + m − s + d_{k}]_{q}A_{c,d,s−1}(q);

Proof. The latter two identities are equivalent to the former two ones. Consider relation (6.4) first. By the invariance principle for maj, this relation is equivalent to the relation formed when j is replaced by any i such that 1 ≤ i ≤ j. It is convenient to prove the relation for i = 1, and we rewrite the relation in the form

(6.6) (1 + q + ⋯ + q^{c_{1}})A_{c+1_{1},d,s}(q)

= (1 + q + ⋯ + q^{c_{1}+s})A_{c,d,s}(q) + (q^{c_{1}+s} + ⋯ + q^{m})A_{c,d,s−1}(q).

Consider the set R^{∗}(c+1_{1}, d, s) of 1-marked words, i.e., rearrangements w^{∗} of 1^{c_{1}+1} … r^{d_{k}} with s k-descents such that exactly one letter equal to 1 has been marked. Each word w ∈ R(c + 1_{1}, d) that has s k-descents gives rise to c_{1} + 1 marked words w^{(0)}, …, w^{(c_{1})}. Define

maj^{∗} w^{(i)} = maj_{k} w + n_{1},

where n_{1} is the number of letters equal to 1 to the right of the marked 1. Then clearly

∑_{i=0}^{c_{1}} maj^{∗} w^{(i)} = (1 + q + ⋯ + q^{c_{1}}) maj_{k} w.

Hence

(1 + q + ⋯ + q^{c_{1}})A_{c+1_{1},d,s}(q) = ∑_{w∈R^{∗}(c+1_{1},d,s)} q^{maj^{∗} w}.

Let the word w = x_{1}x_{2} … x_{m} ∈ R(c, d) have s k-descents. We say that w has m + 1 slots x_{i}x_{i+1}, i = 0, …, m (where we put x_{0} = ∅ and x_{m+1} = ⋆). Call the slot x_{i}x_{i+1} green if either x_{i}x_{i+1} is a k-descent, x_{i} = 1 or i = 0. Call the other slots red. Then there are 1 + s + c_{1} green slots and m − s − c_{1} red slots. Label the green slots 0, 1, …, c_{1} + s from right to left, and label the red slots c_{1} + s + 1, …, m from left to right.

For example, with X = [3], j = 2 and k = 1, the word w = 2 2 1 3 2 1 2 3 3 has 5 1-descents and 10 slots. As c_{1} = 2, there are 8 green slots and 2 red slots, labelled as follows

slot  | 2 | 2 | 1 | 3 | 2 | 1 | 2 | 3 | 3 | ⋆
label  7 8 6 5 4 3 2 9 1 0

Denote by w^{(i)} the word obtained from w by inserting a marked 1 into the i-th slot. Then it may be verified that

(6.7)  des_{k} w^{(i)} = \{ \begin{matrix}des_{k} w, & if i ≤ c_{1} + s; \\ des_{k} w + 1, & otherwise. \end{matrix}
(6.8)  maj^{∗} w^{(i)} = maj_{k} w + i.

Example. Consider the above word w. The following table shows the values of des_{k} and maj^{∗} on w^{(i)}. We show k-descents thus : 2^{⌢}1. The marked 1 is shown in italics.

\begin{matrix}i & w^{(i)} & des_{1} w^{(i)} & maj^{∗} w^{(i)} \\ 0 & 2 2^{⌢}1 3^{⌢}2^{⌢}1 2 3^{⌢}3^{⌢}1 & 5 & 28 \\ 1 & 2 2^{⌢}1 3^{⌢}2^{⌢}1 2 3^{⌢}1 3^{⌢} & 5 & 29 \\ 2 & 2 2^{⌢}1 3^{⌢}2^{⌢}1 1 2 3^{⌢}3^{⌢} & 5 & 30 \\ 3 & 2 2^{⌢}1 3^{⌢}2^{⌢}1 1 2 3^{⌢}3^{⌢} & 5 & 31 \\ 4 & 2 2^{⌢}1 3^{⌢}1 2^{⌢}1 2 3^{⌢}3^{⌢} & 5 & 32 \\ 5 & 2 2^{⌢}1 1 3^{⌢}2^{⌢}1 2 3^{⌢}3^{⌢} & 5 & 33 \\ 6 & 2 2^{⌢}1 1 3^{⌢}2^{⌢}1 2 3^{⌢}3^{⌢} & 5 & 34 \\ 7 & 1 2 2^{⌢}1 3^{⌢}2^{⌢}1 2 3^{⌢}3^{⌢} & 5 & 35 \\ 8 & 2^{⌢}1 2^{⌢}1 3^{⌢}2^{⌢}1 2 3^{⌢}3^{⌢} & 6 & 36 \\ 9 & 2 2^{⌢}1 3^{⌢}2^{⌢}1 2^{⌢}1 3^{⌢}3^{⌢} & 6 & 37 \end{matrix}

So each word w ∈ R(c, d) with s k-descents and maj_{k} w = n gives rise to c_{1} + s + 1 marked words in R^{∗}(c + 1_{1}, d, s) with maj^{∗} equal to n, n+1, …, n+c_{1}+s; and to m−s−c_{1} marked words in R^{∗}(c+1_{1}, d, s+1) with maj^{∗} equal to n+c_{1}+s+1, …, n+m. Hence a word w in R(c, d) with s−1 k-descents gives rise to m−s+1−c_{1} marked words in R^{∗}(c+1_{1}, d, s) with maj^{∗} equal to maj_{k} w+c_{1}+s, …, maj_{k} w+c. This now proves relation (6.6).

We now consider relation (6.5), which we will rewrite in the form

(6.9) (1 + q + ⋯ + q^{d_{k}})A_{c,d+1_{k},s}(q)

= (q^{d_{k}+1} + ⋯ + q^{s})A_{c,d,s}(q) + (q^{s} + ⋯ + q^{1+m+d_{k}})A_{c,d,s−1}(q).

Consider the set R^{∗}(c, d + 1_{k}, s) of r-marked words, i.e., rearrangements w^{∗} of 1^{c_{1}} … r^{d_{k}+1} with s k-descents such that exactly one letter equal to r has been marked. Each word w ∈ R(c, d + 1_{k}) that has s k-descents gives rise to d_{k} + 1 marked words w^{(0)}, …, w^{(d_{k})}. Define

maj^{∗} w^{(i)} = maj_{k} w + n_{r},

where n_{r} is the number of letters equal to r to the left of the marked r. Then clearly

∑_{i=0}^{d_{k}} maj^{∗} w^{(i)} = (1 + q + ⋯ + q^{d_{k}}) maj_{k} w.

Hence

(1 + q + ⋯ + q^{d_{k}})A_{c,d+1_{k},s}(q) = ∑_{w∈R^{∗}(c,d+1_{k},s)} q^{maj^{∗} w}.

Let the word w = x_{1}x_{2} … x_{m} ∈ R(c, d) have s k-descents. Then, as before, w has m + 1 slots x_{i}x_{i+1}, i = 0, …, m (where we put x_{0} = ∅ and x_{m+1} = ⋆). Call the slot x_{i}x_{i+1} green if x_{i}x_{i+1} is a k-descent and x_{i} < r. Call the other slots red. Then there are s−d_{k} geen slots and m+1−s+d_{k} red slots. Label the green slots 0, 1, …, s − d_{k} − 1 from right to left, and label the red slots d_{k} − s, …, m from left to right.

For example, with X = [3], j = 2 and k = 1, the word w = 2 2 1 3 2 1 2 3 3 has 5 1-descents and 10 slots. As d_{1} = 3, there are 2 green slots and 8 red slots, labelled as follows

slot  | 2 | 2 | 1 | 3 | 2 | 1 | 2 | 3 | 3 | ⋆
label  2 3 1 4 5 0 6 7 8 9

Denote by w^{(i)} the word obtained from w by inserting a marked r into the i-th slot. Then it may be verified that

(6.10)  des_{k} w^{(i)} = \{ \begin{matrix}des_{k} w, & if i ≤ s − d_{k} − 1 ; \\ des_{k} w + 1, & otherwise. \end{matrix}
(6.11)  maj^{∗} w^{(i)} = maj_{k} w + i + d_{k} + 1.

Each word w ∈ R(c, d) with s k-descents and maj_{k} w = n gives rise to s−d_{k} marked words in R^{∗}(c, d+1_{k}, s) with maj^{∗} equal to n, n+1, …, n+ s − d_{k} − 1 ; and to m + 1 − s + d_{k} marked words in R^{∗}(c, d + 1_{k}, s + 1) with maj^{∗} equal to n + s + 1, …, n + m + d_{k} + 1. Hence a word w in R(c, d) with s − 1 k-descents gives rise to m + 2 − s − d_{k} marked words in R^{∗}(c, d + 1_{k}, s) with maj^{∗} equal to maj_{k} w + s, …, maj_{k} w + m + d_{k} + 1. This now proves relation (6.7).

Example. The following table shows as before the values of des_{k} and maj^{∗} when r = 3 is inserted in w.

\begin{matrix}i & w^{(i)} & des_{1} w^{(i)} & maj^{∗} w^{(i)} \\ 0 & 2 2^{⌢}1 3^{⌢}2 3^{⌢}1 2 3^{⌢}3^{⌢} & 5 & 32 \\ 1 & 2 2 3^{⌢}1 3^{⌢}2^{⌢}1 2 3^{⌢}3^{⌢} & 5 & 33 \\ 2 & 3^{⌢}2 2^{⌢}1 3^{⌢}2^{⌢}1 2 3^{⌢}3^{⌢} & 6 & 34 \\ 3 & 2 3^{⌢}2^{⌢}1 3^{⌢}2^{⌢}1 2 3^{⌢}3^{⌢} & 6 & 35 \\ 4 & 2 2^{⌢}1 3^{⌢}3^{⌢}2^{⌢}1 2 3^{⌢}3^{⌢} & 6 & 36 \\ 5 & 2 2^{⌢}1 3^{⌢}3^{⌢}2^{⌢}1 2 3^{⌢}3^{⌢} & 6 & 37 \\ 6 & 2 2^{⌢}1 3^{⌢}2^{⌢}1 3^{⌢}2 3^{⌢}3^{⌢} & 6 & 38 \\ 7 & 2 2^{⌢}1 3^{⌢}2^{⌢}1 2 3^{⌢}3^{⌢}3^{⌢} & 6 & 39 \\ 8 & 2 2^{⌢}1 3^{⌢}2^{⌢}1 2 3^{⌢}3^{⌢}3^{⌢} & 6 & 40 \\ 9 & 2 2^{⌢}1 3^{⌢}2^{⌢}1 2 3^{⌢}3^{⌢}3^{⌢} & 6 & 41 \end{matrix}

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

7. Generating functions

In this section we use the recurrence relations (6.2) and (6.3) to prove Theorem 1.4. Thus let

(7.1)  A(t, q; u, v) := ∑_{c,d} \frac{u^{c}v^{d}}{(t; q)_{1+m}} A_{c,d}(t, q).

Robert J. Clarke and Dominique Foata

We will consider the partial q-difference

D_{u_{j}} = A(t, q; u_{1}, …, u_{j}; v) − A(t, q; u_{1}, …, u_{j−1}, u_{j}q; v). Directly from equation (7.1) we obtain

D_{u_{j}} = ∑_{c,d}(1 − q^{c_{j}+1})\frac{u^{c+1_{j}}v^{d}}{(t; q)_{2+m}} A_{c+1_{j},d}(t, q)

= ∑_{c,d}(1 − tq^{m+1})\frac{u^{c+1_{j}}v^{d}}{(t; q)_{2+m}} A_{c,d}(t, q)

− ∑_{c,d} q^{c_{j}+1}(1 − t)\frac{u^{c+1_{j}}v^{d}}{(t; q)_{2+m}} A_{c,d}(tq, q)

using relation (6.2). Now

∑_{c,d}(1 − tq^{m+1})\frac{u^{c+1_{j}}v^{d}}{(t; q)_{2+m}} A_{c,d}(t, q) = ∑_{c,d} \frac{u^{c+1_{j}}v^{d}}{(t; q)_{1+m}} A_{c,d}(t, q)
= u_{j}A(t, q; u, v)

and

∑_{c,d} q^{c_{j}+1}(1 − t)\frac{u^{c+1_{j}}v^{d}}{(t; q)_{2+m}} A_{c,d}(tq, q) = ∑_{c,d} \frac{u^{c+1_{j}}q^{c_{j}+1}v^{d}}{(tq; q)_{1+m}} A_{c,d}(tq, q)
= u_{j}qA(tq, q; u_{1}, …, u_{j−1}, u_{j}q, v).

Hence (7.2) A(t, q; u, v) − A(t, q; u_{1}, …, u_{j−1}, u_{j}q, v)

= u_{j}A(t, q; u, v) − u_{j}qA(tq, q; u_{1}, …, u_{j−1}, u_{j}q, v).

The (partial) q-difference equation with respect to each u_{i} (i = 1, …, j) has the form (7.3) A(t, q; u, v) − A(t, q; u_{1}, …, u_{i}q, …, u_{j}, v)

= u_{i}A(t, q; u, v) − u_{i}qA(tq, q; u_{1}, …, u_{i}q, …, u_{j}, v).

In the same way, (6.3) leads to the q-difference equation (7.4) A(t, q; u, v_{1}, …, v_{l}q, …, v_{k}) − A(t, q; u, v)

= −v_{l}qA(t, q; u, v_{1}, …, v_{l}q, …, v_{k}) + v_{l}qA(tq, q; u, v), for l = 1, …, k. Now let

A(t, q; u, v) = ∑_{s≥0} t^{s}G_{s}(u, v, q).

From (7.3) we get

∑_{s≥0} t^{s}(1 − u_{i})G_{s}(u, v, q) = ∑_{s≥0} t^{s}(1 − u_{i}q^{s+1})G_{s}(u_{1}, …, u_{i}q, …, u_{j}, v, q).

Taking the coefficient of t^{s} in both members yields the relation

(7.5)  G_{s}(u, v, q) = \frac{1 − u_{i}q^{s+1}}{1 − u_{i}} G_{s}(u_{1}, …, u_{i}q, …, u_{j}, v, q),

for i = 1, …, j. Similarly, from equation (7.4) we get the relation

(7.6)  G_{s}(u, v, q) = \frac{1 + v_{l}q}{1 + v_{l}q^{s+1}} G_{s}(u, v_{1}, …, v_{l}q, …, v_{k}, q)

for l = 1, …, k.

Now put

(7.7)  F_{s}(u, v, q) = G_{s}(u, v, q)\frac{(u; q)_{s+1}}{(−vq; q)_{s}} ,

where we have used the notation (u; q)_{s+1} = (u_{1}; q)_{s+1} … (u_{j}; q)_{s+1} and a similar notation for (−vq; q)_{s}. Then from equations (7.5) and (7.6) we deduce that for i = 1, …, j and l = 1, …, k,

(7.8)  \begin{aligned}F_{s}(u, v, q) & = F_{s}(u_{1}, …, u_{i}q, …, u_{j}, v, q) \\ F_{s}(u, v, q) & = F_{s}(u, v_{1}, …, v_{l}q, …, v_{k}, q) \end{aligned}

But F_{s}(u, v, q) can be expressed as F_{s}(u, v, q) = ∑_{c,d} u^{c}v^{d}F_{s,c,d}(q), where

F_{s,c,d}(q) is a power series in non-negative powers of q. Fix a non-zero pair (c, d) and let a be a non-zero component of (c, d). Then relation (7.8) implies that F_{s,c,d}(q) = q^{a}F_{s,c,d}(q). Therefore, F_{s,c,d}(q) = 0. Hence F_{s}(u, v, q) = F_{s,0,0}(q). It remains to evaluate F_{s,0,0}(q).

From (7.7)

F_{s,0,0}(q) = F_{s}(u, v, q) |u = 0, v = 0

= G_{s}(u, v, q)\frac{(u; q)_{s+1}}{(−vq; q)_{s}} |u = 0, v = 0= G_{s}(0, 0, q) = 1,

as ∑_{s≥0} t^{s}G_{s}(0, 0, q) = A(t, q; 0, 0) = 1/(t; q)_{1} = ∑_{s≥0} t^{s}. Thus G_{s}(u, v, q) =

\frac{(−vq; q)_{s}}{(u; q)_{s+1}} by (7.7). This proves theorem 1.4.

8. Interpolating q-Eulerian polynomials

Let A_{r}^{k}(t, q) = A_{1^{j},1^{k}}(t, q) (j + k = r), which is the generating polynomial for the symmetric group S_{r} by the two-variable statistic (des_{k}, maj_{k}). We wish to derive the following equation.

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

First, let

(8.2)  A_{r}^{k}(t, q) = ∑_{s=0}^{r} A_{r,s}^{k}(q)t^{s}  (0 ≤ k ≤ r).

Then relations (6.4) and (6.5) are rewritten, the first one with c = 1^{j−1}, c_{j} = 0, m = r − 1 and d = 1^{k},

(8.3)  A_{r,s}^{k}(q) = [1 + s]_{q}A_{r−1,s}^{k} + q^{s}[r − s]_{q}A_{r−1,s−1}^{k}(q);

the second one with c = 1^{j}, d_{k} = 0, m = r − 1 and d = 1^{k−1},

(8.4)  A_{r,s}^{k}(q) = q[s]_{q}A_{r−1,s}^{k−1}(q) + q^{s}[1 + r − s]_{q}A_{r−1,s−1}^{k−1}(q).

As the polynomial A_{r}^{k}(t, q) is also the generating polynomial for S_{r} by any pair (des_{k,D}, maj_{k,D}), where D is an arbitrary total order on [ r] (see [6]), it makes sense to consider the polynomial

(8.5) A_{r}(x, y; t, q) = ∑_{s} A_{r,s}(x, y; q)t^{s} = ∑_{k} \binom{r}{k}x^{k}y^{r−k}A_{r}^{k}(t, q)

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

Using (8.3) and (8.4) it is easy to derive the following recurrence relation for the polynomials A_{r,s}(x, y; q). We find

(8.6) A_{r,s}(x, y; q) = (q[s]_{q}x + [s + 1]_{q}y)A_{r−1,s}(x, y; q)

+ q^{s}([r − s + 1]_{q}x + [r − s]_{q}y)A_{r−1,s−1}(x, y; q).

Following Garsia’s method [11] introduce the Eulerian differential operator δ_{t} (see also [1]) defined by

δ_{t}P (t) = \frac{P (qt) − P (t)}{t(q − 1)}.

In particular, δ_{t}t^{s} = [s]_{q}t^{s−1} and δ_{t}(1/(t; q)_{r}) = [s]/(t; q)_{r+1}. Also note the rule for δ_{t}-differentiating a product :

δ_{t}(P (t)Q(t)) = δ_{t}P (t).Q(qt) + P (t).δ_{t}Q(t).

Using this operator (8.6) may be rewritten as

(8.7) A_{r}(x, y; t, q) = A_{r−1}(x, y; tq, q)(y + ytq[r − 1]_{q} + xtq[r]_{q}) + δ_{t}A_{r−1}(x, y; t, q)t(1 − tq^{r})(qx + y).

Next introduce (8.8)

G = G(x, y; t, q; u) = ∑_{r≥0} ∑_{s≥0} \frac{u^{r}}{r!} t^{s}G_{r,s}(x, y; q) = ∑_{r≥0} \frac{u^{r}}{r!} \frac{A_{r}(x, y; t, q)}{(t; q)_{r+1}}.

The forementioned relation (8.7) may be expressed as

t(qx + y)(1 − tq^{r+1})δ_{t}A_{r}(x, y; t, q) = A_{r+1}(x, y; t, q) − A_{r}(x, y; tq, q)(y + ytq[r]_{q} + xtq[r + 1]_{q}).

Nw δ_{t}-differentiate (8.8) and make use of the previous relation. An easy calculation leads to

(8.9) t(qx + y)δ_{t}G(x, y; t, q; u) + yG(x, y; tq, q; u) = D_{u}G(x, y; t, q; u),

where “D_{u}” is the usual derivative with respect to u. Consider the coefficients of u^{r}t^{s}/r! in both members of (8.9). We get

(qx + y)[s]_{q}G_{r,s}(x, y; q) + yq^{s}G_{r,s}(x, y; q) = G_{r+1}(x, y; q).

On the other hand, G(x, y; t, q; u = 0) = A_{0}(x, y; t, q)/(t; q)_{1} = 1/(1 − t). Therefore, G_{0,s}(x, y; q) = 1 for all s ≥ 0. Hence G_{r+1,s}(x, y; q) = (qx[s]_{q} + y[s]_{q} + yq^{s})G_{r,s}(x, y; q) = (xq[s]_{q} + y[s + 1]_{q})G_{r,s}(x, y; q) and G_{r,s}(x, y; q) = (xq[s]_{q} + y[s + 1]_{q})^{s} (r ≥ 0). Thus

(8.10) ∑_{r≥0} \frac{u^{r}}{r!} \frac{A_{r}(x, y; t, q)}{(t; q)_{r+1}} = ∑_{r≥0} ∑_{s≥0} \frac{u^{r}}{r!} t^{s}(xq[s]_{q} + y[s + 1]_{q})^{r}

= ∑_{s≥0} t^{s} exp(u(xq[s]_{q} + y[s + 1]_{q})). (8.11)

Note that (8.1) is equivalent to (8.10).

Remark. For k = 0 the polynomial A_{r}^{k}(t, q) is the usual q-Eulerian polynomial (see, e.g. [2], [3], [4], [11], [12], [13])

A_{r}^{0}(t, q) = ∑_{w} t^{des w}q^{maj w} (w ∈ S_{r}),

which is the generating polynomial for S_{r} by the usual number of descents “des” and the major index “maj.” The generating function for those polynomials is given by (see op. cit.)

(8.12)  ∑_{r≥0} \frac{u^{r}}{r!} \frac{A_{r}^{0}(t, q)}{(t; q)_{r+1}} = ∑_{s≥0} t^{s} exp(u[s + 1]_{q}).

Also the polynomials tA_{r}^{0}(t, q) have the generating function

(8.13)  ∑_{r≥0} \frac{u^{r}}{r!} \frac{tA_{r}^{0}(t, q)}{(t; q)_{r+1}} = ∑_{s≥0} t^{s} exp(u[s]_{q}).

Comparing (8.12) and (8.13) with (8.11) we see that the polynomials A_{r}(x, y; t, q) interpolate the usual q-Eulerian polynomials A_{r}^{0}(t, q) = A_{r}(x = 0, y = 1; t, q) and q^{r}tA_{r}^{0}(t, q) = A_{r}(x = 1, y = 0; t, q).

There is also a method of deriving the generating function for the polynomials A_{r}(x, y; t, q), i.e., (8.10)–(8.11), directly from (8.12). From the combinatorial interpretation of A_{r}^{k}(t, q) as a generating polynomial for S_{r} by (des_{k}, maj_{k}), it is easy to obtain the identity

A_{r}^{k}(t, q) = A_{r}^{k−1}(t, q) + (tq^{r} − 1)A_{r−1}^{k−1}(t, q) (1 ≤ k ≤ r) By iteration we get

A_{r}^{k}(t, q) = ∑_{s=0}^{k} \binom{k}{s}(tq^{r} − 1)(tq^{r−1} − 1) … (tq^{r−s+1} − 1)A_{r−s}^{0}(t, q).

Hence

A_{r}(x, y; t, q) = ∑_{0≤s≤k≤r} \frac{r!}{(r − k)! s! (k − s)!}x^{k}y^{r−k}

× (tq^{r} − 1)(tq^{r−1} − 1) … (tq^{r−s+1} − 1)A_{r−s}^{0}(t, q)

and

∑_{r≥0} \frac{u^{r}}{r!} \frac{A_{r}(x, y; t, q)}{(t; q)_{r+1}} = ∑_{s,n,m≥0} \frac{u^{s+n+m}x^{s+n}y^{m}}{s! n! m!} \frac{(−1)^{s}}{(t; q)_{n+m+1}} A_{n+m}^{0}(t, q)

= exp(−ux) ∑_{s≥0} \frac{(u(x + y))^{s}}{s!} \frac{1}{(t; q)_{s+1}} A_{s}^{0}(t, q)

= ∑_{r≥0} t^{s} exp(u(xq[s]_{q} + y[s + 1]_{q})),

using (8.12) in the last step.

Acknowledgements. The authors should like to thank Guo-Niu Han and Raymond Seroul for their helpful remarks.

REFERENCES

1. George E. Andrews. On the Foundations of Combinatorial Theory V, Eulerian Differential Operators, Studies in Appl. Math., v. 50, 1971, p. 345–375.

2. L. Carlitz. q-Bernoulli and Eulerian numbers, Trans. Amer. Math. Soc., v. 76, 1954, p. 332–350.

3. L. Carlitz. Eulerian numbers and polynomials, Math. Magazine, v. 33, 1959, p. 247–260.

4. L. Carlitz. A combinatorial property of q-Eulerian numbers, Amer. Math. Monthly, v. 82, 1975, p. 51–54.

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

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

7. Robert J. Clarke and Dominique Foata. Eulerian Calculus, III : the ubiquitous Cauchy formula, to appear in Europ. J. Combinatorics 1994.

8. Marlene Denert. The genus zeta function of hereditary orders in central simple algebras over global fields,, Math. Comp., v. 54, 1990, p. 449–465.

9. Dominique Foata. Les distributions Euler-Mahoniennes sur les mots, to appear in the Proceedings of the Conference on Formal Series and Algebraic Combinatorics, Montréal, 1992, published by Discrete Math., 1994.

10. Dominique Foata and Doron Zeilberger. Denert’s permutation statistic is indeed Euler-Mahonian, Studies in Appl. Math., v. 83, 1990, p. 31–59.

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

12. Adriano M. Garsia and Ira Gessel. Permutation Statistics and Partitions, Advances in Math., v. 31, 1979, p. 288–305.

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

14. Guo-Niu Han. Une transformation fondamentale sur les réarrangements de mots, Advances in Math., v. 105, 1994, p. 26–41.

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

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

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

18. Marcel-Paul Schützenberger. On a factorization of free monoids, Proc. Amer. Math. Soc., v. 16, 1965, p. 21–24.

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

20. Richard P. Stanley. Binomial posets, Möbius inversion, and permutation enumeration, J. Combinatorial Theory Ser. A, v. 20, 1976, p. 336–356.

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