December 9, 2003

TRANSFORMATIONS ON WORDS

By

Dominique FOATA Département de mathématique

Université Louis Pasteur 7, rue René-Descartes,

F-67084 Strasbourg, France

email: foata@math.u-strasbg.fr

and

Guo-Niu HAN

I.R.M.A.

Université Louis Pasteur et C.N.R.S.

7, rue René-Descartes F-67084 Strasbourg, France

email: guoniu@math.u-strasbg.fr

DOMINIQUE FOATA AND GUONIU HAN

Abstract

The purpose of this paper is to give the description of a single algorithm that specializes into several classical transformations derived on words, namely the Cartier-Foata transform, its contextual extension due to Han and the two k-extensions proposed by Clarke and Foata.

TRANSFORMATIONS ON WORDS

1. Introduction. — When sorting was systematically studied in the sixties and seventies, in particular for comparing the different methods used in practice (see, e.g. [14]), it was essential to go back to the classics, to the works by MacMahon and especially to his treatise on Combinatory Analysis [19]. He had made an extensive study of the distributions of several statistics on permutations, or more generally, on permutations with repeated elements, simply called words in the sequel. The most celebrated of those statistics is probably the classical number of inversions which stands for a very natural measurement of how far a permutation is from the identity. There are several other statistics relevant to sorting or to statistical theory, such as the number of descents, the number of excedances, the major index, and more recently the Denert statistic.

MacMahon [19] had already calculated the distributions of the early statistics and proved that some of them were equally distributed on each class of rearrangements of a given word. Let us state one of his basic results. To this end suppose that X is a finite non-empty set, referred to as an alphabet. For convenience, take X to be the subset [ r] = {1, 2, …, r} (r ≥ 1) of the positive integers, equipped with its standard ordering. Let c = (c_{1}, c_{2}, …, c_{r}) be a sequence of r nonnegative integers and v be the nondecreasing word v = 1^{c_{1}}2^{c_{2}} … r^{c_{r}}, i.e., v = y_{1}y_{2} … y_{m} with m = c_{1} + c_{2} + ⋯ + c_{r} and y_{1} = ⋯ = y_{c_{1}} = 1, y_{c_{1}+1} = ⋯ = y_{c_{1}+c_{2}} = 2, …, y_{c_{1}+···+c_{r−1}+1} = ⋯ = y_{m} = r. The class of all rearrangements of v, i.e., the class of all the words w that can be obtained from v by permuting its letters in some order will be denoted by R(c).

If w = x_{1}x_{2} … x_{m} is such a word, the number of excedances, exc w, and the number of descents, des w, of w are classically defined as

\begin{aligned}exc w & = #\{i : 1 ≤ i ≤ m, x_{i} > y_{i}\}, \\ des w & = #\{i : 1 ≤ i ≤ m − 1, x_{i} > x_{i+1}\}. \end{aligned}  (1.1)

Let A_{c}^{exc}(t) (resp. A_{c}^{des}(t)) be the generating polynomial for the class R(c) by the statistic “exc” (resp. “des”), i.e.,

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

MacMahon [17] showed that those two polynomials were equal for every c. Accordingly, the two statistics “exc” and “des” are equidistributed on each rearrangement class R(c). MacMahon also derived an explicit formula for the generating function for those polynomials.

Back in the sixties, when it was natural to prove such equidistribution properties in a bijective manner, the late Schützenberger asked whether a bijection Φ could be constructed on each rearrangement class R(c) with the property that

exc w = des Φ(w)  (1.2)

holds for every w. Such a transformation Φ was devised in [10]. A further presentation was made in [14, p. 24–29], a more algebraic version appeared in [4] and also in [16, chap. 10].

In the nineties three extensions of that equidistribution property have been derived. First, by taking pairs of statistics into account, second, by extending the property to the case of an alphabet with two classes of letters; third, by combining those two extensions.

In (1.1) when the number of the i’s is replaced by the sum of the i’s we define respectively

excindex w = ∑{i : 1 ≤ i ≤ m, x_{i} > y_{i}},
maj w = ∑{i : 1 ≤ i ≤ m − 1, x_{i} > x_{i+1}},

(1.3)

i.e., the excedance index and the major index (also called the greater index and already studied by MacMahon (op. cit.)). The major index has been often associated with the number of descents, for instance in the study of the q-Eulerian polynomials [1, 2, 3]. Moreover, the joint distribution of the pair (des, maj) was already derived by MacMahon [19, vol. 2, p. 211]. It was then natural to try to introduce a statistic “stat” on words, such that the pair (des, maj) was equidistributed with the pair (exc, stat) on each rearrangement class R(c). We could imagine that “excindex” would be the appropriate statistic “stat.” However a careful study of the generating polynomials for small values of c showed that that assumption was not correct. However by adding a correcting term to “excindex” a new statistic, “den,” called the Denert statistic, could be formed and fitted the requirements of “stat.”

Surprisingly, “den” was discovered in a very different context, by Denert [9] for the calculation of the genus zeta function of hereditary orders in some simple algebras. Its explicit definition is given in (8.4). The construction of a bijection Φ^{q} that maps every rearrangement class R(c) onto itself and satisfies

(exc, den) w = (des, maj) Φ^{q}(w)  (1.4)

was derived in [12].

The previous results were further extended to the case of an alphabet with two kinds of letters. Keep the same alphabet {1, …, r} as above, but suppose given two nonnegative integers s and ℓ such that s + ℓ = r. A letter x in [ r] is said to be small (resp. large) if x ≤ s (resp. if x ≥ s + 1). Whenever such an alphabet is considered we will use the notation _{s}X_{ℓ}.

Let w = x_{1}x_{2} … x_{m} be a word in the alphabet_{s}X_{ℓ} whose nondecreasing rearrangement is v = y_{1}y_{2} … y_{m}. An integer i such that 1 ≤ i ≤ m is said to be a ℓ-excedance of w if either x_{i} > y_{i}, or x_{i} = y_{i} and x_{i} large; it is said to be a ℓ-descent of w, if either x_{i} > x_{i+1}, or x_{i} = x_{i+1} and x_{i} large (by convention, x_{m+1} = s + \frac{1}{2}.) The number of ℓ-excedances (resp. of ℓ-descents) of the word w will be denoted by exc_{ℓ} w (resp. by des_{ℓ} w).

Again when we add the integers i which are ℓ-excedances (resp. ℓdescents) of w, we define the ℓ-excedance index, excindex_{ℓ} w (resp. the ℓ-major index, maj_{ℓ} w), of w.

The extension of the equidistribution property (1.2) consists of constructing a bijection _{s}Φ_{ℓ} of each rearrangement class onto itself satisfying

exc_{ℓ} w = des_{ℓ} _{s}Φ_{ℓ}(w).  (1.5)

Such a bijection was derived in [6].

Finally, an extension of the previous result to bivariate statistics (or, equivalently, an extension of (1.4) to the alphabet with two classes of letters) was proposed in [7] in the following way. When adding a “correcting term” (see section 6) to the statistic “excindex_{ℓ}” we can form the ℓ-Denert statistic “den_{ℓ}.” We can then show that the two pairs (des_{ℓ}, maj_{ℓ}) and (exc_{ℓ}, den_{ℓ}) are equidistributed on each rearrangement class, by constructing a bijection _{s}Φ_{ℓ}^{q} of each rearrangement class onto itself satisfying

(exc_{ℓ}, den_{ℓ}) w = (des_{ℓ}, maj_{ℓ})_{s}Φ_{ℓ}^{q}(w).  (1.6)

Such a transformation _{s}Φ_{ℓ}^{q} was constructed in [7].

The constructions of bijections having properties (1.2), (1.4), (1.5), (1.6) have been given in four papers, namely [4, 12, 6, 7], respectively. Each time the notations used have been different. It was also unclear whether there was a general principle presiding over all those constructions. The purpose of this paper is to give the description of a single algorithm (the algorithm T in section 5) which, once a commutation rule on pairs of letters is given and once a linear ordering on the alphabet X is defined, gives the description of each of the four transformations Φ, Φ^{q}, _{s}Φ_{ℓ}, _{s}Φ_{ℓ}^{q}.

There is no special device to introduce for the constructions of _{s}Φ_{ℓ} and sΦ_{ℓ}^{q}, as it was done in [6] and [7], where a subsidiary letter “⋆” was added to the initial alphabet X to make the algorithms work. Also, as was noticed by Knuth [15] in a private communication, there is no need to derive the cancellation law [12, Theorem 3.1] for the contextual multiplication in the construction of Φ^{q}.

First, we introduce the notion of biword and give the description of the straightening algorithm of a biword based upon a given sequence of commutations (section 3). Although any commutation rule can be integrated into our main algorithm, the two commutations that yield the constructions of our four bijections are the so-called Cartier-Foata commutation and the contextual commutation. Both are described in section 4. Our main algorithm T and its reverse U = T^{−1} are presented in sections 5 and 6. In sections 7 and 8 we have gathered the definitions of all the statistics involved. We conclude the paper by giving the main properties of the bijections constructed by means of algorithm T.

2. Words and biwords. — In the sequel the alphabet X will be equipped either with its standard ordering, or with a well-defined ordering. A biword is an ordered pair of words of the same length, written as α = (h, b) (“h” stands for “high” and “b” for “bottom”) or as

α = ( \begin{matrix}h \\ b \end{matrix} ) = ( \begin{matrix}h_{1}h_{2} … h_{m} \\ b_{1}b_{2} … b_{m} \end{matrix} ) .

For easy reference we shall sometimes indicate the places 1, 2, …, m of the letters on the top of the biword:

[ \begin{matrix}id \\ h \\ b \end{matrix} ] = [ \begin{matrix}1 & 2 & … & m \\ h_{1} & h_{2} & … & h_{m} \\ b_{1} & b_{2} & … & b_{m} \end{matrix} ] .

The word h (resp. b) is the top (resp. bottom) word of the biword (h, b). Each biword \binom{h}{b} can also be seen as a word whose letters are the biletters \binom{h_{1}}{b_{1}}, …, \binom{h_{m}}{b_{m}}. The integer m is the length of the biword w. A triple (h, b; i) where i is an integer satisfying 1 ≤ i ≤ m − 1 is called a pointed biword. When h and b are rearrangements of each other, the biword (h, b) is said to be a circuit.

Two classes of circuits will play a special role in the paper. First, we introduce the standard circuits Γ(b) which are circuits of the form \binom{\overline{b}}{b}, where \overline{b} is the nondecreasing rearrangement of the word b with respect to the standard ordering. Clearly Γ maps each word onto a standard circuit in a bijective manner.

For the second class of circuits we fix a total order “⪯” on X, not necessarily identical with the standard order and make use of the obvious notations: “≺,” “≻,” “⪰.” A nonempty word h = h_{m}h_{1} … h_{m−2}h_{m−1} is said to be ⪯-dominated, if h_{m} ≻ h_{1}, h_{m} ≻ h_{2}, …, h_{m} ≻ h_{m−1}. The right to left cyclic shift of h is defined to be the word δh = h_{1}h_{2} … h_{m−1}h_{m}. A biword of the form \binom{δh}{h} with h ⪯-dominated is called a ⪯-dominated cycle.

As is known (see, e.g. [16, Lemma 10.2.1]) or easily verified, each word b is the juxtaposition product u^{1}u^{2} … of ⪯-dominated words whose first letters pre(u^{1}), pre(u^{2}), … are in nondecreasing order with respect to “⪯” :

pre(u^{1}) ⪯ pre(u^{2}) ⪯ ⋯  (2.1)

This factorization, called the increasing factorization of b, is unique.

Given the increasing factorization u^{1}u^{2} … of a word b with respect of an order “⪯,” we can form the juxtaposition product

Δ(b) = ( \begin{matrix}δu^{1} & δu^{2} & … \\ u^{1} & u^{2} & … \end{matrix} )  (2.2)

of the ⪯-dominated cycles. Clearly Δ maps each word onto a product of ⪯-dominated cycles satisfying inequalities (2.1), in a bijective manner. Such a product, written as a biword (2.2), will be called a well-factorized circuit.

For instance, 4 | 4 5 | 1 | 3 1 2 | 3 5 is such an increasing factorization of a word b with respect to the ordering 5 ≺ 4 ≺ 1 ≺ 2 ≺ 3. The corresponding well-factorized circuit reads:

Δ(b) = ( \begin{matrix}4 \\ 4 \end{matrix} | \begin{matrix}5 & 4 \\ 4 & 5 \end{matrix} | \begin{matrix}1 \\ 1 \end{matrix} | \begin{matrix}1 & 2 & 3 \\ 3 & 1 & 2 \end{matrix} | \begin{matrix}5 & 3 \\ 3 & 5 \end{matrix} ) .

3. Commutations. — Suppose given a four-variable Boolean func-

tion Q(x, y; z, t) (also written as Q\binom{x, y}{z, t}) defined on quadruples of let-

ters in X. The commutation “Com” induced by the Boolean function Q(x, y; z, t) is defined to be a mapping that maps each pointed biword (h, b; i) onto a biword (h′, b′) = Com(h, b; i) with the following properties: if

( \begin{matrix}h \\ b \end{matrix} ) = ( \begin{matrix}h_{1}h_{2} … h_{m} \\ b_{1}b_{2} … b_{m} \end{matrix} ) and ( \begin{matrix}h′ \\ b′ \end{matrix} ) = ( \begin{matrix}h′_{1}h′_{2} … h′_{m′} \\ b′_{1}b′_{2} … b′_{m′} \end{matrix} ) ,

then (C0) m′ = m ; (C1) h′_{j} = h_{j}, b′_{j} = b_{j} for every j ≠ i, i + 1; (C2) h′_{i+1} = h_{i}, h′_{i} = h_{i+1} (the i-th and (i + 1)-st letters of the top

word are transposed);

(C3) b′_{i} = b_{i} and b′_{i+1} = b_{i+1} if Q(h_{i}, h_{i+1}; b_{i}, b_{i+1}) true ; b′_{i} = b_{i+1} and b′_{i+1} = b_{i} if Q(h_{i}, h_{i+1}; b_{i}, b_{i+1}) false.

We can also describe the commutation by the following pair of mappings

\begin{matrix}h = h_{1} … h_{i−1}h_{i}h_{i+1}h_{i+2} … h_{m} & ↦ h′ = h_{1} … h_{i−1}h_{i+1}h_{i}h_{i+2} … h_{m}; \\ b = b_{1} … b_{i−1}b_{i}b_{i+1}b_{i+2} … b_{m} & ↦ b′ = b_{1} … b_{i−1} z t b_{i+2} … b_{m}; \end{matrix}

where either z = b_{i}, t = b_{i+1} if Q(h_{i}, h_{i+1}; b_{i}, b_{i+1}) true, or z = b_{i+1}, t = b_{i} if Q(h_{i}, h_{i+1}; b_{i}, b_{i+1}) false.

Definition. — A Boolean function Q(x, y; z, t) is said to be bi-symmetric if it is symmetric in the two sets of parameters {x, y}, {z, t}.

Lemma 3.1. — Let “Com” be the commutation induced by a bisymmetric Boolean function Q(x, y; z, t). Then the mapping (h, b; i) ↦ Com(h, b; i) is involutive.

The proof of the lemma is a simple verification and will be omitted.

In the rest of the paper we will assume that all the four-variable Boolean functions Q(x, y; z, t) are bi-symmetric.

Two extreme cases are worth being mentioned, when Q is the Boolean function Q_{true} “always true” (resp. Q_{false} “always false”). The commutation Com_{true}, associated with Q_{true}, permutes only the i-th and (i + 1)-st letters of the top word b, while Com_{false}, associated with Q_{false}, permutes the i-th and (i + 1)-st biletters of the biword (h, b).

Sorting a biword is defined as follows. Again consider a biword (h, b) of length m and let (h′, b′) = Com(h, b; i) with 1 ≤ i ≤ m−1. If 1 ≤ j ≤ m−1, we can form the pointed biword (h′, b′; j) and further apply the commutation “Com” to (h′, b′; j). We obtain the biword Com(h′, b′; j) = Com(Com(h, b; i); j), which we shall denote by Com(h, b; i, j). By induction we can define Com(h, b; i_{1}, …, i_{n}), where (i_{1}, …, i_{n}) is a given sequence of integers less than m.

As each commutation always permutes two adjacent letters within the top word (condition (C2)), we can transform each biword (h, b) into a biword (h′, b′) whose top word h′ is non-decreasing by applying a sequence of commutations. We can also say that for each biword (h, b) there exists a sequence (i_{1}, …, i_{n}) of integers such that the top word in the resulting biword Com(h, b; i_{1}, …, i_{n}) is non-decreasing. Such a biword is called a minimal biword and the sequence (i_{1}, …, i_{n}) a commutation sequence.

When using the commutations Com_{true} or Com_{false} we always reach the same minimal biword, but the commutation sequence is not unique. With an arbitrary commutation “Com” neither the minimal biword, nor the commutation sequence are necessarily unique. We then define a particular commutation sequence (i_{1}, …, i_{n}) called the minimal sequence by the following two conditions:

(i) it is of minimum length;

(ii) it is minimal with respect to the lexicographic order. Clearly the minimal sequence is uniquely defined by those two conditions and depends only on the top word h in (h, b). The minimal biword derived from (h, b) by using the minimal sequence is called the straightening of the biword (h, b). The derivation is described in the following algorithm

SORTB.

Algorithm SORTB: sorting a biword. — Given a biword (h, b) and a commutation “Com” the following algorithm transforms (h, b) into its straightening (h′, b′).

Prototype (h′, b′) := SORTB(h, b, Com).

(1) Let (h′, b′) := (h, b).

(2) If h′ is non-decreasing, RETURN (h′, b′).

(3) Else, let j be the smallest integer such that h′(j) > h′(j + 1). Then let (h′, b′) := Com(h′, b′; j). Go to (2).

4. The two commutations. — We shall introduce two commutations associated with two specific Boolean functions Q.

4.1. The Cartier-Foata commutation. — We denote by Com_{CF} the commutation induced by the following Boolean function Q_{CF}:

Q_{CF} \binom{x, y}{z, t} true if and only if x = y.  (4.1)

4.2. The contextual commutation. — We now take the alphabet _{s}X_{ℓ} (see the Introduction) and denote by Com_{H} the commutation induced by the following Boolean function Q_{H}: let x^{±} = x + \frac{1}{2} if x is small and x^{±} = x − \frac{1}{2} if x is large; then

Q_{H} \binom{x, y}{z, t} true

if and only if (z − x^{±})(z − y^{±})(t − x^{±})(t − y^{±}) > 0.  (4.2)

Remarks.

a) Notice that those two commutations are bi-symmetric, so that the mapping (h, b; i) ↦ Com(h, b; i) is involutive when Com is equal either to Com_{CF}, or Com_{H}.

b) Cyclic intervals. — The second commutation was introduced in the case ℓ = 0 (no large letters) in [12] and for an arbitrary ℓ (0 ≤ ℓ ≤ r) in [7]. In both papers the commutations were defined by means of so-called “cyclic intervals” that can be defined as follows. Place the r elements 1, 2, …, s, s + 1, …, (r − 1), r on a circle counterclockwise and place a bracket on each of those elements as shown in Fig. 1. For x, y ∈ X (x ≠ y) the cyclic interval ]]x, y]] is the subset of all the elements that lie between x and y when the circle is read counterclockwise. The brackets (in the French notation) indicate if the ends of the interval are to be included or not.

For instance, suppose 1 < s < s + 1 < r. Then ]]1, s]] = {2, …, s} (the origin 1 excluded, but the end s included), while ]]1, s + 1]] = {2, …, s}

DOMINIQUE FOATA AND GUONIU HAN

[figure: 1; 2; s; r; (r − 1); (s + 1); Fig. 1]

(both ends are excluded); also ]]r, s]] = {r, 1, …, s} (both ends are included) and ]]r, s + 1]] = {r, 1, …, s} (the origin r included, but the end (s + 1) excluded). Finally, define ]]x, x]] = ∅ or X depending on whether x is small or large.

Then Q_{H} \binom{x, y}{z, t} true if both z, t are in ]]x, y]] or neither in ]]x, y]].

Example. — Consider the alphabet _{s}X_{ℓ} with s = 3 and ℓ = 2,

and the biword α = [ \begin{matrix}1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 \\ 4 & 5 & 4 & 1 & 1 & 2 & 3 & 5 & 3 \\ 4 & 4 & 5 & 1 & 3 & 1 & 2 & 3 & 5 \end{matrix} ]. The minimal sequence is then

2, 3, 2, 1, 4, 3, 2, 5, 4, 3, 6, 5, 4, 8, 7, 6, 5. By using Com_{H} in SORTB we obtain the sequence of commutations

α = [ \begin{matrix}1 & 2 & 3 … \\ 4 & 5 & 4 … \\ 4 & 4 & 5 … \end{matrix} ] ↦ [ \begin{matrix}1 & 2 & 3 & 4 … \\ 4 & 4 & 5 & 1 … \\ 4 & 5 & 4 & 1 … \end{matrix} ] ↦ [ \begin{matrix}1 & 2 & 3 & 4 … \\ 4 & 4 & 1 & 5 … \\ 4 & 5 & 1 & 4 … \end{matrix} ] ↦ [ \begin{matrix}1 & 2 & 3 & 4 … \\ 4 & 1 & 4 & 5 … \\ 4 & 5 & 1 & 4 … \end{matrix} ]

⋯ ↦ [ \begin{matrix}1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 \\ 1 & 1 & 2 & 3 & 4 & 3 & 4 & 5 & 5 \\ 4 & 5 & 1 & 4 & 1 & 3 & 2 & 3 & 5 \end{matrix} ] ↦ [ \begin{matrix}1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 \\ 1 & 1 & 2 & 3 & 3 & 4 & 4 & 5 & 5 \\ 4 & 5 & 1 & 4 & 1 & 3 & 2 & 3 & 5 \end{matrix} ] = SORTB(α, Com_{H})

5. The main algorithm. — In the description of the following algorithm we take the alphabet _{s}X_{ℓ} having s small letters 1, 2, …, s and ℓ large letters (s + 1), …, r (s + ℓ = r).

The total order used on the places will always be the natural order of the integers. However the order “⪯” used on the letters of the words will be the order “⪯” defined by

r ≺ (r − 1) ≺ ⋯ ≺ (s + 1) ≺ 1 ≺ 2 ≺ ⋯ ≺ s.  (5.1)

If there are no large letters so that ℓ = 0 and s = r, the order “⪯” is identical with the usual order “≤.” To avoid any kind of ambiguity we make precise each time which one of the orderings is involved by using notations such as “⪯-greatest” or “≤-nondecreasing”…

Algorithm T. — Let Com be a commutation induced by a fourvariable Boolean function Q. The following algorithm transforms each word b into a rearrangement c of b.

Prototype c := T(b, Com).

(1) Let h be the ≤-nondecreasing rearrangement of b. Form the standard circuit Γ(b) = (h, b):

[ \begin{matrix}id \\ h \\ b \end{matrix} ] = [ \begin{matrix}1 & 2 & … & m \\ h_{1} & h_{2} & … & h_{m} \\ b_{1} & b_{2} & … & b_{m} \end{matrix} ] ,

let c := b and α be the empty cycle α = ( ⋮ ).

(2a) If all the places 1, 2, …, m occur in α, RETURN c (the juxtaposition

product of the bottom words in α.) (2b) Else, let D be the ≤-greatest place not occurring in α. (2c) Let M be the ⪯-greatest letter in h not in α. Let i be the ≤-rightmost

place such that M = h_{i} and i ≤ D. If i ≤ D−1 apply the commutation

(h, c) := Com(h, c; i, i + 1, …, D − 1).

[If there are no large letters in h, we always have i = D and the above commutation is bypassed.] At the end of (2c) we have h_{D} = M so that the initial biword has been changed into:

α

[ \begin{matrix}id \\ h \\ c \end{matrix} ] = [ \begin{matrix}∗ & … & ∗ & D \\ ∗ & … & ∗ & M \\ ∗ & … & ∗ & ∗ \end{matrix} ] ( \begin{matrix}∗ & … & ∗ \\ ∗ & … & ∗ \\ ∗ & … & ∗ \end{matrix} ) ⋯ ( \begin{matrix}∗ & … & ∗ \\ ∗ & … & ∗ \\ ∗ & … & ∗ \end{matrix} ) .

(3a) Let B := c_{D}.

(3b) If B = M, terminate the ⪯-dominated cycle ( \begin{matrix}∗ & … & ∗ \\ ∗ & … & M \\ M & … & ∗ \end{matrix} ) (possibly

of length 1) and add it to the left of α, so that the new α reads

( \begin{matrix}∗ & … & ∗ \\ ∗ & … & M \\ M & … & ∗ \end{matrix} ) α. Go to (2a).

(3c) Else, look for the ≤-greatest place j ≤ D − 1 such that B = h_{j}; in short

[ \begin{matrix}id \\ h \\ c \end{matrix} ] = [ \begin{matrix}… & j & … & D & … & ∗ \\ … & B & … & ∗ & … & M \\ … & ∗ & … & B & … & ∗ \end{matrix} ] ( \begin{matrix}∗ & … & ∗ \\ ∗ & … & ∗ \\ ∗ & … & ∗ \end{matrix} ) ⋯ ( \begin{matrix}∗ & … & ∗ \\ ∗ & … & ∗ \\ ∗ & … & ∗ \end{matrix} ) .

If j ≤ D − 2, apply the commutation:

(h, c) = Com(h, c; j, j + 1, …, D − 2),

so that h_{D−1} = B after running the commutation; in short:

[ \begin{matrix}id \\ h \\ c \end{matrix} ] = [ \begin{matrix}… & j & … & D − 1 & D & … & ∗ \\ … & ∗ & … & B & ∗ & … & M \\ … & ∗ & … & ∗ & B & … & ∗ \end{matrix} ] ( \begin{matrix}∗ & … & ∗ \\ ∗ & … & ∗ \\ ∗ & … & ∗ \end{matrix} ) ⋯ ( \begin{matrix}∗ & … & ∗ \\ ∗ & … & ∗ \\ ∗ & … & ∗ \end{matrix} ) .

(3d) Let D := D − 1 and go to (3a).

We can verify that each step in the previous algorithm is feasible. For example, the place j in step (3c) is well-defined: at this stage \binom{h}{c} is the product of the left factor (in square brackets) \left[{h′ \atop c′}\right] by α and h′ is necessarily a rearrangement of c′.

The algorithm T will also be denoted by _{s}T_{ℓ} when we want to emphasize that it is applied to words in the alphabet _{s}X_{ℓ}. With r = s + ℓ and using the two commutations Com_{CF} and Com_{H} we can derive four different transformations:

Φ(b) = _{r}T_{0}(b, Com_{CF}), Φ^{q}(b) = _{r}T_{0}(b, Com_{H}),
sΦ_{ℓ}(b) = _{s}T_{ℓ}(b, Com_{CF}), _{s}Φ_{ℓ}^{q}(b) = _{s}T_{ℓ}(b, Com_{H}).

(5.2)

Example. — Consider the biword

[ \begin{matrix}id \\ h \\ b \end{matrix} ] = [ \begin{matrix}1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 \\ 1 & 1 & 2 & 3 & 3 & 4 & 4 & 5 & 5 \\ 4 & 5 & 1 & 4 & 1 & 3 & 2 & 3 & 5 \end{matrix} ] .

We calculate the image of b under the four transformations defined in (5.2).

For Φ(b) = _{r}T_{0}(b, Com_{CF}) we obtain

[ \begin{matrix}id \\ h \\ c \end{matrix} ] ↦ ( \begin{matrix}1 & 2 \\ 3 & 4 \\ 4 & 3 \end{matrix} ) ( \begin{matrix}3 & 4 & 5 \\ 1 & 2 & 4 \\ 4 & 1 & 2 \end{matrix} ) ( \begin{matrix}6 & 7 & 8 \\ 1 & 3 & 5 \\ 5 & 1 & 3 \end{matrix} ) ( \begin{matrix}9 \\ 5 \\ 5 \end{matrix} ) ,

so that c = Φ(b) = 4 3 4 1 2 5 1 3 5.

We next calculate Φ^{q}(b) = _{r}T_{0}(b, Com_{H}). We get

[ \begin{matrix}id \\ h \\ c \end{matrix} ] ↦ ( \begin{matrix}1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 \\ 4 & 4 & 1 & 1 & 3 & 2 & 3 & 5 \\ 5 & 4 & 4 & 1 & 1 & 3 & 2 & 3 \end{matrix} ) ( \begin{matrix}9 \\ 5 \\ 5 \end{matrix} ) ,

so that c = Φ^{q}(b) = _{r}T_{0}(b, Com_{H}) = 5 4 4 1 1 3 2 3 5.

For the next two transformations assume that 1, 2, 3 are small letters, while 4, 5 are large letters, so that s = 3 and ℓ = 2. The total order “⪯” is then: 5 ≺ 4 ≺ 1 ≺ 2 ≺ 3. The calculation of _{s}Φ_{ℓ}(b) = _{s}T_{ℓ}(b, Com_{CF}) yields:

[ \begin{matrix}id \\ h \\ c \end{matrix} ] ↦ ( \begin{matrix}1 & 2 & 3 & 4 & 5 \\ 4 & 1 & 2 & 4 & 3 \\ 3 & 4 & 1 & 2 & 4 \end{matrix} ) ( \begin{matrix}6 & 7 & 8 & 9 \\ 5 & 5 & 1 & 3 \\ 3 & 5 & 5 & 1 \end{matrix} ) ,

so that c = _{s}Φ_{ℓ}(b) = _{s}T_{ℓ}(b, Com_{CF}) = 3 4 1 2 4 3 5 5 1.

Finally, _{s}Φ_{ℓ}^{q}(b) = _{s}T_{ℓ}(b, Com_{H}) is then

[ \begin{matrix}id \\ h \\ c \end{matrix} ] ↦ ( \begin{matrix}1 \\ 4 \\ 4 \end{matrix} ) ( \begin{matrix}2 & 3 \\ 5 & 4 \\ 4 & 5 \end{matrix} ) ( \begin{matrix}4 \\ 1 \\ 1 \end{matrix} ) ( \begin{matrix}5 & 6 & 7 \\ 1 & 2 & 3 \\ 3 & 1 & 2 \end{matrix} ) ( \begin{matrix}8 & 9 \\ 5 & 3 \\ 3 & 5 \end{matrix} ) ,

so that c = _{s}Φ_{ℓ}^{q}(b) = _{s}T_{ℓ}(b, Com_{H}) = 4 4 5 1 3 1 2 3 5.

6. The algorithm U. — Again we take the alphabet _{s}X_{ℓ} and the order defined in (4.1).

Algorithm U. — Given a commutation Com, the following algorithm transforms a word c into a word b such that b = U(c, Com).

Prototype b := U(c, Com).

(1) Let i := 1, S := c_{1}; (2a) If i = length(c), let h_{i} := S, (h, b) := SORTB(h, c, Com). RETURN b. (2b) Else, let B := c_{i+1}. (2c) If B ⪰ S, let h_{i} := S, S := B. Else, let h_{i} := B.

(3) Let i := i + 1. Go to (2a).

Property. — Algorithm U is the inverse of algorithm T, i.e., for each word b we have

U(T(b, Com), Com) = T(U(b, Com), Com) = b.

Proof. — First examine algorithm T. Before returning c in step (2a) the algorithm provides the juxtaposition product α = γ^{1}γ^{2} … of cycles. Let u^{1}, u^{2}, … be the bottom words of those cycles and let pre(u^{1}), pre(u^{2}), … be the first letters of those bottom words. Steps (2c) and (3b) say that each cycle γ^{i} was terminated as soon as pre(u^{i}) was ⪯-greater than all the other letters in the cycle. Accordingly, all the cycles γ^{i} are ⪯-dominated. Furthermore, pre(u^{1}) ⪯ pre(u^{2}) ⪯ ⋯

Thus u^{1}u^{2} … is the increasing factorization of c (in the terminology of

section 2), while α = γ^{1}γ^{2} … = ( \begin{matrix}δu^{1} & δu^{2} & … \\ u^{1} & u^{2} & … \end{matrix} ) is the increasing product of ⪯-dominated cycles, i.e., α is equal to the well-factorized circuit Δ(c) We can say that the algorithm T transforms each standard circuit Γ(b) into a well-factorized circuit Δ(c), the word c being a rearrangement of b. As each commutation applied to a pointed biword is involutive, T is a bijection.

Now examine Algorithm U and let u^{1}u^{2} ⋯ be the increasing factorization of c as a product of ⪯-dominated words. Once we have reached step (2a), verified that the test i = length(c) was positive and executed h_{i} := S, the biword (h, c) is exactly the well-factorized circuit

Δ(c) = ( \begin{matrix}h \\ c \end{matrix} ) = ( \begin{matrix}δu^{1} & δu^{2} & … \\ u^{1} & u^{2} & … \end{matrix} ) .

Thus Algorithm U first builds up the well-factorized circuit Δ(c) and applies algorithm SORTB to Δ(c) to produce a standard circuit Γ(b). Again as each local commutation applied to a pointed biword is involutive, U is a bijection.

Finally, to prove that T and U are inverse of each other, we simply examine algorithm T. The commutations are made only in steps (2c) and (3c). In both steps the reverse operation can be written as

(h, c) := SORTB(h, c, Com).

7. Statistics on circuits. — We keep the alphabet _{s}X_{ℓ} and consider the class of circuits with letters in _{s}X_{ℓ}. Remember that a circuit is a pair of words α = \binom{v}{w}, where v = y_{1}y_{2} … y_{m} and w = x_{1}x_{2} … x_{m} are rearrangements of each other and v is not necessarily non-decreasing. For each circuit α = \binom{v}{w}, we define exc_{ℓ} \binom{v}{w} to be the number of integers i such that 1 ≤ i ≤ m and either x_{i} > y_{i}, or x_{i} = y_{i} and x_{i} large.

The definition of den_{ℓ} \binom{v}{w} is based on the notion of cyclic interval, as introduced in section 4. For each place i (1 ≤ i ≤ m) define p_{i} to be the number of j such that 1 ≤ j ≤ i − 1 and x_{j} ∈ ]]x_{i}, y_{i}]]. Also let p_{m+1} be the number of large letters in w. The sequence (p_{1}, p_{2}, …, p_{m+1}) is said to be the ℓ-den-coding of \binom{v}{w}. Furthermore, define

den_{ℓ} \binom{v}{w} = p_{1} + p_{2} + ⋯ + p_{m} + p_{m+1}.  (7.1)

Example. — Consider an alphabet with s = 3 small letters 1, 2, 3 and ℓ = 2 large letters 4, 5 and form the circuit

α = [ \begin{matrix}id \\ v \\ w \end{matrix} ] = [ \begin{matrix}1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 \\ 4 & 5 & 4 & 1 & 1 & 2 & 3 & 5 & 3 \\ 4 & 4 & 5 & 1 & 3 & 1 & 2 & 3 & 5 \end{matrix} ] .

It has a ℓ-excedence at places 1, 3, 5, 9, so that exc_{ℓ} α = 4. For its ℓ-Denert coding we first have p_{1} = 0. As 4 ∈ ]]4, 5]] = {4}, we have p_{2} = 1. As 4 ∉ ]]5, 4]] = {5, 1, 2, 3}, we have p_{3} = 0. Also p_{4} = 0 as ]]1, 1]] is empty. As 4, 4, 5, 1 belong to ]]3, 1]] = {4, 5, 1}, p_{5} = 4. As ]]1, 2]] = {2}, we have p_{6} = 0. Also ]]2, 3]] = {3}, so that p_{7} = 1 and ]]3, 5]] = {4}, so that p_{8} = 2. As ]]5, 3]] = {5, 1, 2, 3}, we get p_{9} = 6. Finally, as there are 4 large letters in w, we get p_{10} = 4. Thus den_{ℓ} α = 0+1+0+0+4+0+1+2+6+4 = 18.

The definitions of des_{ℓ} \binom{v}{w} and of maj_{ℓ} \binom{v}{w} depend only on the bottom word w. Put x_{m+1} = s (the largest small letter) and x_{m+2} = ∞ (an auxiliary letter greater than every letter of X). Then for each i = 1, 2, …, m + 1 define q_{i} to be the number of j such that 1 ≤ j ≤ i − 1 and x_{j} ∈ ]]x_{i}, x_{i+1}]]. The sequence (q_{1}, q_{2}, …, q_{m}, q_{m+1}) is said to be the ℓ-maj-coding of α. Define

maj_{ℓ} \binom{v}{w} = q_{1} + q_{2} + ⋯ + q_{m} + q_{m+1}.  (7.2)

Taking the same example as above we can verify that (des_{ℓ}, maj_{ℓ}) α = (4, 18), which is also the value of (exc_{ℓ}, den_{ℓ}) α. In fact the above circuit is well-factorized and for that class of circuits the two pairs of statistics have the same values, as proved in the next theorem.

Theorem 7.1. — If α = \binom{v}{w} is a well-factorized circuit, then

(exc_{ℓ}, den_{ℓ}) α = (des_{ℓ}, maj_{ℓ}) α.  (7.3)

Proof. — Let ( \begin{matrix}a_{2} & … & a_{i+1} & a_{i+2} & … & a_{k} & a_{1} \\ a_{1} & … & a_{i} & a_{i+1} & … & a_{k−1} & a_{k} \end{matrix} ) and ( \begin{matrix}b_{2} & … \\ b_{1} & … \end{matrix} ) be two

successive ⪯-dominated cycles in the increasing factorization of α, so that

α = ( \begin{matrix}… & a_{2} & … & \overline{a_{i+1}} & a_{i+2} & … & a_{k} & \overline{a_{1}} & b_{2} & … \\ … & a_{1} & … & \underline{a_{i}} & \underline{\overline{a_{i+1}}} & … & a_{k−1} & \underline{a_{k}} & \underline{\overline{b_{1}}} & … \end{matrix} ) .

Inside each ⪯-dominated cycle a pair like (a_{i}, a_{i+1}) occurs horizontally and vertically, so that there is a ℓ-descent a_{i}a_{i+1} if and only if there is a ℓ-excedance \binom{a_{i+1}}{a_{i}}. Furthermore, the letters in w to the left of a_{i} that fall into the cyclic interval ]]a_{i}, a_{i+1}]] bring the same contribution in both maj_{ℓ} α and den_{ℓ} α. If \binom{a_{i+1}}{a_{i}} is the j-th biletter of α (when read from left to right), we have p_{j} = q_{j} in the notations used in (7.2) and (7.3).

At the end of a ⪯-dominated cycle we have to compare the contributions of the horizontal pair (a_{k}, b_{1}) with the contribution of the vertical pair \binom{a_{1}}{a_{k}}. But a_{k} ≺ a_{1} ⪯ b_{1} by definition of the increasing factorization. If b_{1} is large, then a_{k} and a_{1} are also large and we have a_{k} > a_{1} ≥ b_{1}, so that the letter a_{k} creates an ℓ-excedence and an ℓ-descent. If b_{1} is small, then a_{k} > a_{1} is an ℓ-excedance if and only if a_{k} is large. This is also equivalent to saying that a_{k} > b_{1} is an ℓ-descent.

Now if a_{1} = b_{1}, the two cyclic intervals ]]a_{k}, b_{1}]] and ]]a_{k}, a_{1}]] that serve in the calculation of maj_{ℓ} α and den_{ℓ} α are identical. If a_{1} ≺ b_{1}, there is no letter x in w to the left of b_{1} such that a_{1} ≺ x ⪯ b_{1}. Four cases are to be considered: (1) a_{1}, b_{1}, a_{k} all small; (2) a_{1}, b_{1} small, a_{k} large; (3) a_{1}, b_{1}, a_{k} all large; (4) a_{1} large, b_{1} small, a_{k} large. For any two sets A, B let A + B denote the union of A and B when the intersection A ∩ B is empty. In cases (1) and (2) we have

]]a_{k}, b_{1}]] = ]]a_{k}, a_{1}]] + {x : a_{1} ≺ x ⪯ b_{1}},

while

]]a_{k}, a_{1}]] = ]]a_{k}, b_{1}]] + {x : a_{1} ≺ x ⪯ b_{1}}

in cases (3) and (4). Consequently there are as many letters to the left of a_{k} falling into the interval ]]a_{k}, b_{1}]] as letters falling into ]]a_{k}, a_{1}]].

Suppose that α is of length m and take up again the notations of (7.1) and (7.2). We still have to compare the pairs (q_{m}, q_{m+1}) and (p_{m}, p_{m+1}). Let \binom{y_{m}}{x_{m}} be the rightmost biletter of α. If w contains small letters, the letter y_{m} is necessarily equal to the greatest small letter occurring in w. Hence the cyclic intervals ]]x_{m}, s]] used for evaluating q_{m} and ]]x_{m}, y_{m}]] for evaluating p_{m} are equal. If w contains only large letters, y_{m} is equal to the smallest large letter in w and again the previous two cyclic intervals are equal. Finally, p_{m+1} = q_{m+1}, as both coefficients count the large letters in w.

8. Statistics on words. — To get the definitions of des_{ℓ} w, maj_{ℓ} w, exc_{ℓ} w and den_{ℓ} w for a word w in the alphabet _{s}X_{ℓ} we simply form the standard circuit Γ(w) and put

des_{ℓ} w = des_{ℓ} Γ(w), maj_{ℓ} w = maj_{ℓ} Γ(w),
exc_{ℓ} w = exc_{ℓ} Γ(w), den_{ℓ} w = den_{ℓ} Γ(w).

(8.1)

The definitions given for des_{ℓ} w and exc_{ℓ} w are identical with the definitions given in the introduction. The definition of den_{ℓ} w is new, while that of maj_{ℓ} w differs from the definition given in the introduction.

Theorem 8.1. — The statistic maj_{ℓ} w given in (8.1) and the statistic maj_{ℓ} w given in the introduction are identical.

As can be found in [12] for ℓ = 0 and in [7] for an arbitrary ℓ, Theorem 8.1 is easy to prove by induction on the length of the word.

The ℓ-excedance index of w was defined in the introduction as the sum, excindex_{ℓ} w, of all i such that i is a ℓ-excedance in w. When a certain correcting term is added to excindex_{ℓ} w, we get the second definition of den_{ℓ} w. To fully describe that correcting term we need the further definitions. For each word w = x_{1}x_{2} … x_{m} let

inv_{ℓ} w = #{1 ≤ i < j ≤ m : x_{i} > x_{j} or x_{i} = x_{j} ≥ s + 1}
+ #{1 ≤ i ≤ m : x_{i} ≥ s + 1},
imv_{ℓ} w = #{1 ≤ i < j ≤ m : x_{i} > x_{j} or x_{i} = x_{j} ≤ s}.

(8.2)

Notice that inv_{0} = inv (the usual number of inversions) and imv_{0} = imv (the number of weak inversions).

Now if exc_{ℓ} w = e, let i_{1} < i_{2} < ⋯ < i_{e} be the increasing sequence of the ℓ-excedances of w and let j_{1} < j_{2} < ⋯ < j_{m−e} be the complementary sequence. Form the two subwords

Exc_{ℓ} w = x_{i_{1}}x_{i_{2}} … x_{i_{e}} ; Nexc_{ℓ} w = x_{j_{1}}x_{j_{2}} … x_{j_{m−e}}.

Then the ℓ-Denert statistic of w is also defined to be

den_{ℓ} w = excindex_{ℓ} w + imv_{ℓ} Exc_{ℓ} w + inv_{ℓ} Nexc_{ℓ} w. (8.3)

For ℓ = 0 we simply speak of the Denert statistic den w = den_{0} w. (8.4)

Theorem 8.2. — For every word w the two definitions of den_{ℓ} w occurring in (8.1) and (8.3) are identical.

The concept of the Denert statistic is due to Denert [9]. The equivalence between definitions (8.1) and (8.3) when ℓ = 0 and when w is a permutation (without repetitions) was already given in [11]. Another proof of that result appeared in [5]. Theorem 8.2 that states the equivalence of those two definitions for arbitrary words was proved in [12] for ℓ = 0 and in [13] for an arbitrary ℓ.

9. Equidistribution properties. — The fundamental properties of the commutations Com_{CF} and Com_{H} introduced in section 4 are stated in the next theorem. The underlying alphabet is _{s}X_{ℓ}.

Theorem 9.1. — The commutation “Com” being given, let α = (v, w) be a circuit of length m and let α′ = (v′, w′) = Com(v, w; i) (1 ≤ i ≤ m−1) be the image of that pointed circuit under the commutation “Com.”

If Com = Com_{CF}, then

exc_{ℓ} \binom{v′}{w′} = exc_{ℓ} \binom{v}{w}. (9.1)

If Com = Com_{H}, then

(exc_{ℓ}, den_{ℓ}) \binom{v′}{w′} = (exc_{ℓ}, den_{ℓ}) \binom{v}{w}. (9.2)

Property (9.1) is evident, as biletters are preserved when the commutation “Com_{CF} ” is applied. With notations slightly different (9.2) has been proved in [12, Lemma 5.2] in the case ℓ = 0 and for arbitrary ℓ in [7, Lemma 3.6]. We do not reproduce the proof here, as it essentially consists of a lengthy but easy verification.

Theorem 9.2. — The transformations

Φ : b ↦ _{r}T_{0}(b, Com_{CF}), Φ^{q} : b ↦ _{r}T_{0}(b, Com_{H}),
sΦ_{ℓ} : b ↦ _{s}T_{ℓ}(b, Com_{CF}), _{s}Φ_{ℓ}^{q} : b ↦ _{s}T_{ℓ}(b, Com_{H}).

defined in (5.2) have the equidistribution properties

exc(w) = des Φ(w),  (exc, den) w = (des, maj) Φ^{q}(w),
exc_{ℓ}(w) = des_{ℓ} _{s}Φ_{ℓ}(w), (exc_{ℓ}, den_{ℓ}) w = (des_{ℓ}, maj_{ℓ})_{s}Φ_{ℓ}^{q}(w).

Proof. — With each of those transformations we start with a word b, form the standard circuit Γ(b) = \binom{\overline{b}}{b} and apply a well-defined sequence of Cartier-Foata commutations (resp. of contextual commutations) to reach a well-factorized circuit Δ(c).

If the commutation used is the Cartier-Foata commutation, we have

exc_{ℓ}(b) = exc_{ℓ} \binom{\overline{b}}{b}  [by definition of “exc_{ℓ}”]
= exc_{ℓ} Δ(c)  [because of (9.1)]
= des_{ℓ} Δ(c)  [by Theorem 7.1]
= des_{ℓ}(c).  [by definition of “des_{ℓ}.”]

If we use the contextual commutation, we have the properties

(exc_{ℓ}, den_{ℓ}) (b) = (exc_{ℓ}, den_{ℓ}) \binom{\overline{b}}{b} [by definition of “(exc_{ℓ}, den_{ℓ})”]
= (exc_{ℓ}, den_{ℓ}) Δ(c)  [because of (9.2)]
= (des_{ℓ}, maj_{ℓ}) Δ(c)  [by Theorem 7.1]
= (des_{ℓ}, maj_{ℓ}) (c).  [by definition of “maj_{ℓ}.”]

Acknowledgements. — The authors should like to thank the referee for his careful reading.

REFERENCES

1. L. Carlitz, q-Bernoulli and Eulerian numbers, Trans. Amer. Math. Soc. 76 (1954), 332–350.

2. L. Carlitz, Eulerian numbers and polynomials, Math. Magazine 33 (1959), 247–260.

3. L. Carlitz, A combinatorial property of q-Eulerian numbers, Amer. Math. Monthly 82 (1975), 51–54.

4. P. Cartier and D. Foata, “Problèmes combinatoires de permutations et réarrangements,” Berlin, Springer-Verlag, 1969 (Lecture Notes in Math., 85).

5. R. J. Clarke, A short proof of a result of Foata and Zeilberger, Adv. Appl. Math. 16 (1995), 129–131.

6. R. J. Clarke and D. Foata, Eulerian Calculus, I: Univariable Statistics, Europ. J. Combinatorics 15 (1994), 345–362.

7. R. J. Clarke and D. Foata, Eulerian Calculus, II: An Extension of Han’s Fundamental Transformation, Europ. J. Combinatorics 16 (1995), 221–252.

8. R. J. Clarke and D. Foata, Eulerian Calculus, III: The Ubiquitous Cauchy Formula, Europ. J. Combinatorics 16 (1995), 329–355.

9. M. Denert, The genus zeta function of hereditary orders in central simple algebras over global fields, Math. Comp. 54 (1990), 449–465.

10. D. Foata, Etude algébrique de certains problèmes d’analyse combinatoire et du calcul des probabilités, Publ. Inst. Statist. Univ. Paris 14 (1965), 81–241.

11. D. Foata and D. Zeilberger, Denert’s permutation statistic is indeed Euler-Mahonian, Studies in Appl. Math. 83 (1990), 31–59.

12. G. N. Han, Une transformation fondamentale sur les réarrangements de mots, Advances in Math. 105 (1994), 26–41.

13. G. N. Han, The k-Extension of a Mahonian Statistic, Adv. Appl. Math. 16 (1995), 297–305.

14. D. E. Knuth, “The Art of Computer Programming, vol. 3, Sorting and Searching,” Addison-Wesley, Reading, 1973.

15. D. E. Knuth, Private communication, 1996.

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

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

18. P. A. MacMahon, “Collected Papers, vol. 1” [G.E. Andrews, ed.], Cambridge, Mass., The M.I.T. Press, 1978.

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