Contemporary Mathematics Volume 00, XXXX

Word straightening and q-Eulerian Calculus

Dominique Foata and Guoniu Han

This paper is dedicated to Richard Askey for his great scholarship and his successful savoir-faire in promoting the classical theory of Special Functions and making it accessible and useful to new areas of mathematics.

Abstract. This paper contains a new description of the straightening algorithm for pairs of finite words called circuits. The commutation rule underlying the straightening algorithm that keeps invariant a specific word bivariate statistic, is fully characterized. A methodology is developed that makes possible the calculation of the bivariate generating function for that pair of statistics. That generating function appears to be a generalized form of the classical q-Eulerian polynomial.

1. Introduction

The present paper has been motivated by a remark of Richard Askey who asked us to unveil the mysteries hidden in each combinatorial construction, to fully explain how an intricate bijection leading to an explicit calculation dealing with q-series was invented or discovered. We should like to try to match his expectations in this paper by going back to the study of a problem on multipermutation statistics that has kept several of us busy in the past eight years. In doing so we have been lucky to obtain the following new results we will now explain in full details.

In studying the genus zeta function of local minimal hereditary orders Denert [9] introduced a new permutation statistic, that was later christened “den.” When associated with the classical statistic “exc,” the number of excedances (all those terms will be fully redefined further in the paper), the generating function for the pair (exc, den) over the symmetric group S_{r} is equal to the q-Eulerian polynomial [2, 3, 4], a result proved in [12]. The definition of “den” for arbitrary words (with repetitions) whose letters belong to an alphabet X was imagined by Han [14]. He proved that the generating function for the pair (exc, den) over each class of

\begin{matrix}c \\ ◯ \end{matrix}XXXX American Mathematical Society

1991 Mathematics Subject Classification. Primary 05A15, 33A15; Secondary 05A17, 33A75.

Key words and phrases. Straightening algorithm, rearrangements, permutation statistics, q-Eulerian polynomials.

rearrangements of an arbitrary word was equal to the generalised q-Eulerian polynomial, i.e., the polynomial denoted by A_{c,d}(t, q) in formula (4.1) when d is the empty sequence.

When the underlying alphabet X is partitioned into two subalphabets S of small letters and L of large letters, the statistics “exc” and “den” can be further refined to take large inequalities into account [6, 7, 8]. Those statistics are denoted by exc_{ℓ}, den_{ℓ}. It was proved in [7] that the generating function for the pair (exc_{ℓ}, den_{ℓ}) over each class R(c, d) was equal to the further generalized q-Eulerian polynomial A_{c,d}(t, q), as it appears in (4.1).

It was not easy to prove those results. In each case a transformation on words Φ (resp. Φ_{ℓ} in the case of a bi-alphabet) was to be constructed. It maps each rearrangement class onto itself and has the further property that

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

Here “des,” “maj,” “des_{ℓ}” and “maj_{ℓ}” are more traditional word statistics, namely, the number of descents, the major index, the number of ℓ-descents, the ℓ-major index, respectively, for which it is more easy to calculate the generating functions for the pairs (des, maj) and (des_{ℓ}, maj_{ℓ}) over each rearrangement class (see, in particular, [8]). The derivation of the generating functions for the pairs (exc, den) and (exc_{ℓ}, den_{ℓ}) is then a consequence of what is already known for the pairs (des, maj) and (des_{ℓ}, maj_{ℓ}) using the transformations Φ (resp. Φ_{ℓ}).

In [10] it was shown that the following classical transformations on words, the Cartier-Foata transform [5], the transform Φ itself [14], as well as its two extensions derived in [6] and in [7] for Φ_{ℓ}, could be described by means of a single algorithm, the straightening algorithm.

In the present paper we will again describe the straightening algorithm (section 2), but we will prove (Theorem 2.1) that it can be further extended to provide a bijective transformation between two classes of special pairs of words, the wellfactorized circuits and the well-sorted circuits.

The straightening algorithm can be constructed for each commutation rule. Once the statistics “exc_{L}” and “den_{L}” are introduced (see section 3), it is shown that there is one and only one commutation rule that preserves the pair of statistics (exc_{L}, den_{L}) (Theorem 3.1), making the construction of the desired straightening algorithm unique.

Section 4 is devoted to the algebra of the generalized q-Eulerian polynomials A_{c,d}(t, q). To show in particular that A_{c,d}(t, q) is the generating polynomial for a pair of statistics (f, g) it suffices to construct an explicit bijection involving finite sequences of integers (see Criterion 4.1).

To apply Criterion 4.1 successfully for the pairs (exc_{L}, den_{L}) it is essential to find an appropriate partition of the alphabet X into small and large letters and further to derive a total ordering “⪯” such that the second statistic den_{L} depend only on the L-excedances of each ⪯-well-factorized circuit. Such a partition and such a total ordering, denoted by ⪯_{ℓ}, are characterized in Section 5.

Criterion 4.1 is fully applied in section 6 in which we show that the generating functions for the classes of ⪯_{ℓ}-well-sorted circuits by the pair (exc_{ℓ}, den_{ℓ}) are given by the generalized q-Eulerian polynomials presented in section 4.

WORD STRAIGHTENING AND q-EULERIAN CALCULUS 3

It will be noticed that all our q-calculations are made directly on the pairs (exc, den) and (exc_{ℓ}, den_{ℓ}) without any reference to the classical pairs (des, maj) and (des_{ℓ}, maj_{ℓ}). In section 7 we show how we can construct a transformation w ↦ w′ having the property that (des_{ℓ}, maj_{ℓ}) w = (exc_{ℓ}, den_{ℓ}) w′.

2. The straightening algorithm

The straightening algorithm in question acts on biwords, defined to be ordered pairs α = (v, w), preferably written as

α = (\begin{matrix}v \\ w \end{matrix}) = (\begin{matrix}y_{1} & … & y_{i−1} & y_{i} & y_{i+1} & y_{i+2} & … & y_{m} \\ x_{1} & … & x_{i−1} & x_{i} & x_{i+1} & x_{i+2} & … & x_{m} \end{matrix})

of words

v = y_{1} … y_{i−1}y_{i}y_{i+1}y_{i+2} … y_{m}, w = x_{1} … x_{i−1}x_{i}x_{i+1}x_{i+2} … x_{m},

of the same length. The letters x_{i}, y_{i} are taken from a finite alphabet X that for convenience we shall take as the subset {1, 2, …, r} of the integers, equipped with its standard ordering. The above integer m is said to be the length of the biword α. When the words v and w are rearrangements of each other, i.e., when each of them can be derived from the other by permuting the letters in some order, we say that the biword is a circuit.

The straightening algorithm is completely described once a Boolean function Q(x, y; z, t) has been defined on quadruples of letters. Starting with Q we define a commutation rule, Com_{Q}, that maps each pair (α, i), where α is a biword and i is an integer less than the length of α, onto a biword

α′ = Com_{Q}(α, i) = (\begin{matrix}v′ \\ w′ \end{matrix}) = (\begin{matrix}y_{1} & … & y_{i−1} & y_{i+1} & y_{i} & y_{i+2} & … & y_{m} \\ x_{1} & … & x_{i−1} & z & t & x_{i+2} & … & x_{m} \end{matrix}) ,

where z = x_{i} and t = x_{i+1} if Q(y_{i}, y_{i+1}; x_{i}, x_{i+1}) true; z = x_{i+1} and t = x_{i} if Q(y_{i}, y_{i+1}; x_{i}, x_{i+1}) false. Notice that the successive top letters y_{i}, y_{i+1} always commute under the action of Com_{Q}, but not necessarily the corresponding bottom letters x_{i}, x_{i+1}. Also notice that Com_{Q}(α, i) is a circuit if and only if α is a circuit.

It is convenient to call pointed biword each pair (α, i) where α is a biword of length m and 1 ≤ i ≤ m − 1. Now let α′ = Com_{Q}(α; i). If 1 ≤ j ≤ m − 1, we can form the pointed biword (α′, j) and further apply Com_{Q} to (α′, j). We obtain the biword Com_{Q}(α′, j) = Com_{Q}(Com_{Q}(α, i), j), we shall denote by Com_{Q}(α; i, j). By induction it makes sense to define Com_{Q}(α; 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, we can transform each biword α = \binom{v}{w} into a biword α′ = \binom{v′}{w′} whose top word v′ is non-decreasing by applying a sequence of commutations. We can also say that for each biword α = \binom{v}{w} there exists a sequence (i_{1}, …, i_{n}) of integers such that the top word in the resulting biword Com_{Q}(α; i_{1}, …, i_{n}) is non-decreasing. Such a biword is called a well-sorted biword. The sequence (i_{1}, …, i_{n}) is called a commutation sequence. We define a particular commutation sequence (i_{1}, …, i_{n}) called minimal 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 v in α = \binom{v}{w}. The minimal biword derived from α by using the minimal sequence is called the straightening of the biword α and will be denoted by SORT_{Q}(α).

Example 1. Consider the following Boolean function Q_{CF} defined by

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

Take α = \binom{4 4 5 1 3 1 2 3 5}{6 5 4 3 3 2 1 1 1}; then SORT_{Q_{CF}} (α) = \binom{1 1 2 3 3 4 4 5 5}{3 2 1 3 1 6 5 4 1}.

The “CF” subscript stands for “Cartier-Foata”, as those two authors introduced that commutation in [5]. The present description of Q_{CF} appeared in [10].

Now let c = (c_{1}, c_{2}, …, c_{r}) be a sequence of r nonnegative integers and consider the nondecreasing word y_{1}y_{2} … y_{m} = 1^{c_{1}}2^{c_{2}} … r^{c_{r}}, i.e., 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 the word y_{1}y_{2} … y_{m} will be denoted by R(c).

The set of the circuits α = \binom{v}{w}, where both words v and w belong to R(c) will be denoted by C(c). When v is the nondecreasing word 1^{c_{1}}2^{c_{2}} … r^{c_{r}}, we say that the circuit α is well-sorted. The subset of all well-sorted circuits in C(c) will be denoted by S(c). To each word w ∈ R(c) there corresponds a unique well-sorted circuit Γ(w) = \binom{\overline{w}}{w} ∈ S(c), where \overline{w} denotes the nondecreasing rearrangement 1^{c_{1}}2^{c_{2}} … r^{c_{r}} of w. The natural bijection Γ : R(c) → S(c) will be one of the ingredients in our derivation.

We consider a second class F_{⪯}(c) of circuits, called ⪯-well-factorized, that will also be in bijection with R(c). To this end we suppose given a total order “⪯” on X, not necessarily identical with the standard order and make use of the obvious notations: “≺,” “≻,” “⪰.” A nonempty word w = x_{1}x_{2}x_{3} … x_{m} is said to be ⪯- dominated, if x_{1} ≻ x_{2}, x_{1} ≻ x_{3}, …, x_{1} ≻ x_{m}. The right to left cyclic shift of w is defined to be the word δw = x_{2}x_{3} … x_{m}x_{1}. A circuit of the form \binom{δw}{w} with w ⪯-dominated is called a ⪯-dominated cycle.

As it is known (see, e.g. [15] (Lemma 10.2.1)) or easily verified, each word w 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 w, is unique.

Given the ⪯-increasing factorization u^{1}u^{2} … of a word w we can form the juxtaposition product

Δ(w) = (\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 ⪯-domi-nated cycles satisfying inequalities (2.1), in a bijective manner. Such a product, written as a circuit (2.2), will be called a ⪯-well-factorized circuit. The set of all ⪯-well-factorized circuits in C(c) will be denoted by F_{⪯}(c).

Example 2. Consider the total ordering 5 ≺ 4 ≺ 1 ≺ 2 ≺ 3 of the set X = {1, …, 5} and the word w = 4 4 5 1 3 1 2 3 5. To w there corresponds the well-sorted

ciruit Γ(w) = (\begin{matrix}1 & 1 & 2 & 3 & 3 & 4 & 4 & 5 & 5 \\ 4 & 4 & 5 & 1 & 3 & 1 & 2 & 3 & 5 \end{matrix}). On the other hand, the ⪯-increasing factorization

of w reads 4 | 4 5 | 1 | 3 1 2 | 3 5, so that the corresponding ⪯-well-factorized circuit is:

Δ(w) = (\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}) .

For every c the two classes F_{⪯}(c) and S(c) are equinumerous. For instance, ΓΔ^{−1} is a bijection between the two sets. However we want to build a bijection based on algorithm SORT_{Q} that, in general, maps F_{⪯}(c) into S(c). We then impose a condition on the Boolean function Q that will transform the “into” into an “onto”. The restriction of SORT_{Q} to F_{⪯}(c) will be denoted by SORT_{(⪯,Q)}.

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} and {z, t}, i.e., Q(x, y; z, t) = Q(y, x; z, t) and Q(x, y; z, t) = Q(x, y; t, z).

It is straightforward to verify that the commutation rule Com_{Q} induced by a bi-symmetric Boolean function Q is involutive, i.e., if α′ = Com_{Q}(α; i), then α = Com_{Q}(α′; i).

Theorem 2.1. Let Q be a bi-symmetric four-variable Boolean function. Then SORT_{(⪯,Q)} is a bijection of F_{⪯}(c) onto S(c).

Proof. The proof is essentially the description of the action of SORT_{(⪯,Q)} when it is applied to a well-factorized circuit. As will be seen, the bi-symmetry

property makes each step reversible. Let α′ = (\begin{matrix}z_{1} & … & z_{m−1} \\ t_{1} & … & t_{m−1} \end{matrix}) be a biword and

the juxtaposition product α = α′\binom{z_{m}}{t_{m}} be a ⪯-well-factorized circuit in F_{⪯}(c).

Then the letter z_{m} is necessarily the ⪯-greatest letter in the word z_{1} … z_{m} (or in t_{1} … t_{m}). To avoid cumbersome notation let f := SORT_{(⪯,Q)}. By definition of the straightening algorithm we have

f(α) = f(f(α′)\binom{z_{m}}{t_{m}}).

Now let f(α′) = (\begin{matrix}z′_{1} & … & z′_{m−1} \\ x′_{1} & … & x′_{m−1} \end{matrix}), so that z′_{1} ≤ ⋯ ≤ z′_{m−1}. There is a unique

integer i such that 1 ≤ i ≤ m − 1 and z′_{i} ≤ z_{m} < z′_{i+1}. To derive f(α) we only have to move z_{m} to the left (using the commutation rule Com_{Q}) until z_{m} lies between z′_{i} and z′_{i+1}. Using the previous notations we then have

f(α) = Com_{Q}(f(α′)\binom{z_{m}}{t_{m}}; m − 1, m − 2, …, i + 1).

Let f(α) = (\begin{matrix}y_{1} & … & y_{m−1} & y_{m} \\ x_{1} & … & x_{m−1} & x_{m} \end{matrix}), so that y_{1} ≤ ⋯ ≤ y_{m−1} ≤ y_{m}. To recover the pair

(f(α′), \binom{z_{m}}{t_{m}}) from f(α) we only have to locate the letter which is the rightmost

one in y_{1}y_{2} … y_{m} among those which are the ⪯-largest. This defines an integer i without ambiguity. We then define

f(α′)\binom{z_{m}}{t_{m}} = Com_{Q}(f(α); i + 1, …, m − 2, m − 1).

As the commutation rule Com_{Q} is involutive, this reverse procedure leads to the

initial pair (f(α′), \binom{z_{m}}{t_{m}}).

In the same manner, f(α′) = f(f(α′′)\binom{z_{m−1}}{t_{m−1}}), where α′′ is the biword

(\begin{matrix}z_{1} & … & z_{m−2} \\ t_{1} & … & t_{m−2} \end{matrix}). If z_{m} = t_{m}, then z_{m−1} is the ⪯-greatest letter in z_{1} … z_{m−1}. If

z_{m} ≠ t_{m}, then necessarily z_{m−1} = t_{m} as α is ⪯-well-factorized. As before, there is a unique sequence of commutations that bring z_{m−1} to a position where the resulting top word is nondecreasing.

Conversely, starting with f(α′) we know that the letter on the top word that must be brought to the right end is the rightmost letter equal to t_{m}. We also know that the product of the commutations involved will give back the pair

(f(α′′), \binom{z_{m−1}}{t_{m−1}}),

as the commutation rule is involutive. As each step has a well-defined reverse step uniquely defined, the mapping SORT_{(⪯,Q)} is truly bijective.

3. Unicity of the word transformation

Our next task is to characterize the transformations SORT_{(⪯,Q)} that preserves the pair of statistics (exc_{L}, den_{L}) that will be defined shortly. To this end we will suppose that the alphabet X = {1, 2, …, r} is made of two disjoint sets S and L of so-called small and large letters, respectively. Let s (resp. ℓ) be the cardinality of S (resp. of L), so that s + ℓ = r. With respect to the standard ordering of X the small letters are not necessarily smaller than the large ones. The features “small” and “large” refer to two different ways of considering inequalities, as we will explain below.

Let α = \binom{v}{w} = (\begin{matrix}y_{1} & y_{2} & … & y_{m} \\ x_{1} & x_{2} & … & x_{m} \end{matrix}) be a circuit. The number of L-excedances of α,

exc_{L} α, is defined 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_{L} α is based on the notion of cyclic interval defined as follows. Place the r elements 1, 2, …, r of X on a circle counterclockwise. If x is small (resp. large), place a bracket in the form ⟶ (resp. ⟶) on the vertex x. For x, y ∈ X (x ≠ y) the cyclic interval ]]x, y]]_{L} is defined to be 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.

Suppose x < y. If x, y are both small, then ]]x, y]]_{L} = x, y = {x + 1, …, y} (origin excluded and end included); if x small and y large, then ]]x, y]]_{L} = x, y = {x + 1, …, y − 1} (both ends are excluded); if x large and y small, then ]]x, y]]_{L} = x, y = {x, x + 1, …, y − 1, y} (both ends are included); if x and y are both large, then ]]x, y]]_{L} = x, y = {x, x + 1, …, y − 1} (the origin x included, but the end y excluded). Moreover ]]y, x]]_{L} = X \ ]]x, y]]_{L}. Finally, define ]]x, x]]_{L} = ∅ or X depending on whether x is small or large.

The L-Denert statistic, den_{L} α, of the circuit α is defined to be the number of pairs (i, j) such that 1 ≤ i < j ≤ m + 1 and x_{i} ∈ ]]x_{j}, y_{j}]]_{L} (by convention ]]x_{m+1}, y_{m+1}]]_{L} = L, the subset of all large letters). For each i = 1, 2, …, m let p_{i} be the number of j such that i + 1 ≤ j ≤ m + 1 and x_{i} ∈ ]]x_{j}, y_{j}]]_{L}. We also have den_{L} α = p_{1} + p_{2} + ⋯ + p_{m}. The sequence (p_{1}, p_{2}, …, p_{m}) is said to be the L-den-coding of α and is denoted by L-den-coding(α).

Example 3. Take r = 5 and suppose that 1, 2, 4 are small and 3, 5 are large, so that the brackets on the circle (here a square!) are displayed as in Fig. 1. There are s = 3 small letters and ℓ = 2 large letters. In particular the small letter 4 is larger than the large letter 3 with respect to the standard ordering.

[figure: 1; 2; 3; 5; 4; Fig. 1]

The following circuit α with letters in X is displayed in the first two rows of the matrix. The third row shows the content of each cyclic interval ]]x_{i}, y_{i}]]_{L} and the fourth row the L-den-coding of α:

(\begin{matrix}y_{i} \\ x_{i} \\ ]]x_{i}, y_{i}]]_{L} \\ p_{i} \end{matrix}) = (\begin{matrix}1 & 1 & 2 & 3 & 3 & 4 & 4 & 5 & 5 \\ 4 & 5 & 1 & 4 & 1 & 3 & 2 & 3 & 5 \\ \{5, 1\} & \{5, 1\} & \{2\} & \{5, 1, 2\} & \{2\} & \{3, 4\} & \{3, 4\} & \{3, 4\} & X \\ 4 & 3 & 2 & 4 & 1 & 4 & 1 & 2 & 1 \end{matrix})

and ]]x_{m+1}, y_{m+1}]]_{L} = L = {3, 5}. There are four excedences indicated in bold-face, so that exc_{L} α = 4 and den_{L} α = 4 + 3 + 2 + 4 + 1 + 4 + 1 + 2 + 1 = 22.

Our next task is the following: given a subset L of X of large letters, so that both statistics “exc_{L}” and “den_{L}” are well-defined, find a Boolean function Q_{L} having the property that

for every circuit α of length m and every place i (1 ≤ i ≤ m − 1), the following identity holds

(exc_{L}, den_{L}) α = (exc_{L}, den_{L}) Com_{Q_{L}}(α, i).  (3.1)

Suppose that such a Boolean function Q = Q_{L} exists and consider a circuit α of length m. Denote the image of the pointed circuit (α, i) under the corresponding commutation rule by α′ = Com_{Q}(α, i) and take again the notations of section 2 for the circuits α and α′. If (3.1) holds, it follows from the definitions of “exc_{L}” and “den_{L}” that

exc_{L} α − exc_{L} α′ = χ(x_{i} > y_{i}) + χ(x_{i+1} > y_{i+1})
+ χ(x_{i} = y_{i} large) + χ(x_{i+1} = y_{i+1} large)
− χ(z > y_{i+1}) − χ(t > y_{i})
− χ(z = y_{i+1} large) − χ(t = y_{i} large)

den_{L} α − den_{L} α′ = ∑_{1≤h≤i−1}(χ(x_{h} ∈ ]]x_{i}, y_{i}]]_{L}) + χ(x_{h} ∈ ]]x_{i+1}, y_{i+1}]]_{L})
− χ(x_{h} ∈ ]]z, y_{i+1}]]_{L}) − χ(x_{h} ∈ ]]t, y_{i}]]_{L}))
+ χ(x_{i} ∈ ]]x_{i+1}, y_{i+1}]]_{L}) − χ(z ∈ ]]t, y_{i}]]_{L}).

If condition Q(y_{i}, y_{i+1}, x_{i}, x_{i+1}) is true, we must have:

exc_{L} α − exc_{L} α′ = χ(x_{i} > y_{i}) + χ(x_{i+1} > y_{i+1})
+ χ(x_{i} = y_{i} large) + χ(x_{i+1} = y_{i+1} large)
− χ(x_{i} > y_{i+1}) − χ(x_{i+1} > y_{i})
− χ(x_{i} = y_{i+1} large) − χ(x_{i+1} = y_{i} large)  (3.2)
den_{L} α − den_{L} α′ = ∑_{1≤h≤i−1}(χ(x_{h} ∈ ]]x_{i}, y_{i}]]_{L}) + χ(x_{h} ∈ ]]x_{i+1}, y_{i+1}]]_{L})
− χ(x_{h} ∈ ]]x_{i}, y_{i+1}]]_{L}) − χ(x_{h} ∈ ]]x_{i+1}, y_{i}]]_{L}))
+ χ(x_{i} ∈ ]]x_{i+1}, y_{i+1}]]_{L}) − χ(x_{i} ∈ ]]x_{i+1}, y_{i}]]_{L}).  (3.3)

If condition Q(y_{i}, y_{i+1}, x_{i}, x_{i+1}) is false, we must have:

exc_{L} α − exc_{L} α′ = 0,  (3.4)
den_{L} α − den_{L} α′ = ∑_{1≤h≤i−1}(χ(x_{h} ∈ ]]x_{i}, y_{i}]]_{L}) + χ(x_{h} ∈ ]]x_{i+1}, y_{i+1}]]_{L})
− χ(x_{h} ∈ ]]x_{i+1}, y_{i+1}]]_{L}) − χ(x_{h} ∈ ]]x_{i}, y_{i}]]_{L}))
+ χ(x_{i} ∈ ]]x_{i+1}, y_{i+1}]]_{L}) − χ(x_{i+1} ∈ ]]x_{i}, y_{i}]]_{L})
= χ(x_{i} ∈ ]]x_{i+1}, y_{i+1}]]_{L}) − χ(x_{i+1} ∈ ]]x_{i}, y_{i}]]_{L}).  (3.5)

Now given four elements x, y, z, t of X we say that z, t are neighbors with respect to x, y, if both z and t are in ]]x, y]]_{L}, or neither in ]]x, y]]_{L}. Otherwise, z and t are said to be strangers with respect to x, y.

When expression (3.2) is zero, it is easy to see that x_{i} and x_{i+1} are neighbors with respect to ]]y_{i}, y_{i+1}]]_{L}. In that case expression (3.3) is also equal to zero. On the other hand, when (3.5) is zero, then x_{i} and x_{i+1} must be strangers with respect to ]]y_{i}, y_{i+1}]]_{L}. We have then proved the following theorem.

Theorem 3.1. Let Q_{L} be the Boolean function defined by:

Q_{L}(x, y, z, t) true if and only if z, t are neighbors with respect to x, y.

Then Q_{L} is the unique Boolean function such that for every circuit α and every place i the following identity holds

(exc_{L}, den_{L}) α = (exc_{L}, den_{L}) Com_{Q_{L}}(α, i).

The Boolean function Q_{L} here characterized was first introduced in [10] under the name of Q_{H}.

Now it is clear that the above four-variable Boolean function Q_{L} is bisymmetric. The combination of Theorems 1.1 and 2.1 yields the following result.

Theorem 3.2. For every total ordering “⪯” on the alphabet X, for every subset L of large letters of X and every sequence c, the mapping SORT_{(⪯,Q_{L})} is a bijection of F_{⪯}(c) onto S(c) that satisfies

(exc_{L}, den_{L}) α = (exc_{L}, den_{L}) SORT_{(⪯,Q_{L})}(α).

4. Generalized q-Eulerian polynomials

To introduce those polynomials it is convenient to use the traditional notations of q-calculus, first, 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 the q-binomial coefficient (or the Gaussian polynomial)

\left[{n \atop k}\right] := \{ \begin{matrix}\frac{(q; q)_{n}}{(q; q)_{k} (q; q)_{n−k}} , & if 0 ≤ k ≤ n; \\ 0, & otherwise. \end{matrix}

As before, r will denote a fixed positive integer and s, ℓ two nonnegative integers of sum r. Finally, if a = (a_{1}, …, a_{m}) is a sequence of nonnegative integers, we let ∥a∥ be the sum a_{1} + ⋯ + a_{m}.

The generalized q-Eulerian polynomials A_{c,d}(t, q), already introduced in [7], are polynomials in two variables t, q, indexed by pairs of sequences c = (c_{1}, …, c_{s}) and d = (d_{1}, …, d_{ℓ}) of nonnegative integers. They are defined by

\frac{1}{(t; q)_{1+∥c∥+∥d∥}} A_{c,d}(t, q) := ∑_{i≥0} t^{i}\left[{c_{1} + i \atop i}\right] ⋯ \left[{c_{s} + i \atop i}\right]

× q^{\binom{d_{1}+1}{2}}\left[{i \atop d_{1}}\right] ⋯ q^{\binom{d_{ℓ}+1}{2}}\left[{i \atop d_{ℓ}}\right]. (4.1)

There exist other extensions of q-Eulerian polynomials depending on more parameters, see, e.g. [11], but the previous polynomials indexed by pairs of sequences of integers will meet our present needs.

Now let u_{1}, …, u_{s}, v_{1}, …, v_{ℓ} be commuting variables. For convenience we will use the traditional notations u^{c} := u_{1}^{c_{1}} … u_{s}^{c_{s}}, v^{d} := v_{1}^{d_{1}} … v_{ℓ}^{d_{ℓ}} and

(u_{1}, …, u_{s}; q)_{i} := (u_{1}; q)_{i} ⋯ (u_{s}; q)_{i}.

By means of a simple manipulation on q-series it is readily seen that (4.1) is actually equivalent to the following identity involving the factorial generating function for the polynomials A_{c,d}(t, q), namely

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

Notice that the summation is over all pairs of sequences c = (c_{1}, …, c_{s}), d = (d_{1}, …, d_{ℓ}), including the null sequence. Also notice the occurrences of two different subscripts i and (i + 1) in the right-hand side of (4.2) that correspond to the two types of q-binomial coefficients in (4.1).

To be able to make use of identity (4.1) in combinatorial problems and especially in the present paper it is essential to express the q-ascending factorials and the qbinomial coefficients in terms of generating functions for finite sequences of integers. From the classial q-binomial theorem (see, e.g., [1], p. 17 or [13], § 1.3) we can easily derive the identities:

\frac{1}{(t; q)_{1+m}} = ∑_{i≥0} t^{i} ∑_{i≥a_{1}≥···≥a_{m}≥0} q^{∥a∥};  (4.3)

\left[{c + i \atop i}\right] = ∑_{i≥a_{1}≥···≥a_{c}≥0} q^{∥a∥};  (4.4)

q^{\binom{d+1}{2}}\left[{i \atop d}\right] = ∑_{i≥a_{1}>···>a_{d}≥1} q^{∥a∥}.  (4.5)

On the other hand, each polynomial A_{c,d}(t, q) defined by identity (4.1) has positive integral coefficients. Moreover, by multiplying that same identity by (1 − t) and making t = 1 then q = 1, the expression A_{c,d}(1, 1) is equal to the multinomial coefficient M(c, d) = \binom{c_{1}+···+c_{s}+d_{1}+···+d_{ℓ}}{c_{1},... ,c_{s},d_{1},... ,d_{ℓ}}. Consequently, if F (c, d) is a finite set of cardinality M(c, d) and if f, g are two integer-valued statistics defined on F (c, d), it makes sense to consider the generating polynomial

A_{F (c,d)}^{f,g}(t, q) := ∑_{α∈F (c,d)} t^{f(α)}q^{g(α)}.  (4.6)

Now the pair (f, g) has a generating function equal to A_{c,d}(t, q) over F (c, d), i.e., the following identity

A_{F (c,d)}^{f,g}(t, q) = A_{c,d}(t, q)

holds, if identity (4.1) is valid when A_{c,d}(t, q) is replaced by A_{F (c,d)}^{f,g}(t, q). By using the expansions (4.3)-(4.6) we can rewrite that condition as

∑_{(i′,a,α)} t^{i′+f(α)}q^{∥a∥+g(α)} = ∑_{(i,a^{(1)},... ,a^{(r)})} t^{i}q^{∥a^{(1)}∥+···+∥a^{(r)}∥}.  (4.7)

In (4.7) the first sum is over all triples (i′, a, α) such that

(4.8) {i′ is a nonnegative integer; a = (a_{1}, …, a_{∥c∥+∥d∥}) is a nonincreasing sequence of nonnegative inte- gers of length ∥c∥ + ∥d∥ satisfying i′ ≥ a_{1} ≥ ⋯ ≥ a_{∥c∥+∥d∥} ≥ 0; α is an element of F (c, d).

The second sum is over all sequences (i, a^{(1)}, …, a^{(r)}), where

(4.9) {i is a nonnegative integer; each a^{(j)} is a sequence a^{(j)} = (a_{j,1}, …, a_{1,c_{j}}) of integers satisfying i ≥ a_{j,1} ≥ ⋯ ≥ a_{j,c_{j}} ≥ 0 (1 ≤ j ≤ s); each a^{(s+j)} is a sequence a^{(s+j)} = (a_{s+j,1}, …, a_{s+j,d_{j}}) of integers sat- isfying i ≥ a_{s+j,1} > ⋯ > a_{s+j,d_{j}} ≥ 1 (1 ≤ j ≤ ℓ).

We then have the following criterion.

Criterion 4.1. For the identity A_{F (c,d)}^{f,g}(t, q) = A_{c,d}(t, q) to hold, it suffices to build a bijection (i′, a, α) ↦ (i, a^{(1)}, …, a^{(r)}) of triples having properties (4.8) onto sequences having properties (4.9) and satisfying

i′ + f(α) = i and ∥a∥ + g(α) = ∥a^{(1)}∥ + ⋯ + ∥a^{(r)}∥.  (4.10)

5. The well-factorized circuits

Take up again the notations of section 3 where the r elements of the alphabet X have been displayed on a circle. For convenience, insert a new element, called ∗, between the maximum letter r and the minimum 1. With this new convention and when x > y, we see that the cyclic interval ]]x, y]]_{L} will always contain ∗. Actually, ]]x, y]]_{L} is reduced to the singleton {∗} if and only if x = r, y = 1, r small and 1 large. We also see that there is an L-excedance at position i in the circuit

α = \binom{v}{w} = (\begin{matrix}y_{1} & y_{2} & … & y_{m} \\ x_{1} & x_{2} & … & x_{m} \end{matrix}) if and only if the cyclic interval ]]x_{i}, y_{i}]]_{L} contains ∗.

It is also convenient to introduce the cyclic sequence ⟩⟩x, y⟩⟩_{L} defined, when x, y ∈ X, x ≠ y, to be the sequence of the elements of X ∪ {∗} that occur when reading the interval ]]x, y]]_{L} counterclockwise. When x is small (resp. large), let ⟩⟩x, x⟩⟩_{L} be the empty sequence (resp. the sequence (x, x + 1, …, x − 1).)

For instance, if x > y and if both x, y are small, then

⟩⟩x, y⟩⟩_{L} = (x + 1, x + 2, …, r, ∗, 1, …, y − 1, y),

while if x < y and x is large, but y small, then

⟩⟩x, y⟩⟩_{L} = (x, x + 1, …, y − 1, y),

with the convention that x + 1 = ∗ and y − 1 = ∗ when x = r and y = 1. Using the notion of cyclic sequences we can also say that there is an L-excedance

at position i in the circuit α = \binom{v}{w} = (\begin{matrix}y_{1} & y_{2} & … & y_{m} \\ x_{1} & x_{2} & … & x_{m} \end{matrix}) if and only if the cyclic

sequence ⟩⟩x_{i}, y_{i}⟩⟩_{L} contains ∗.

Now as the words v and w are rearrangements of each other, there exists a permutation σ of the sequence (1, 2, …, m) such that y_{1}y_{2} … y_{m} =x_{σ(1)}x_{σ(2)} … x_{σ(m)}. Write σ as a product of disjoint cycles:

σ = ⋯ (a, b, …, z) ⋯

The juxtaposition product W = ⟩⟩x_{a}, y_{a}⟩⟩_{L}⟩⟩x_{b}, y_{b}⟩⟩_{L} ⋯ ⟩⟩x_{z}, y_{z}⟩⟩_{L} is then equal to

⟩⟩x_{a}, x_{b}⟩⟩_{L} ⋯ ⟩⟩x_{z}, x_{a}⟩⟩_{L}. It is empty only if \binom{x_{b} … x_{a}}{x_{a} … x_{z}} is equal to \binom{r … r}{r … r} and r

is a small letter. Otherwise, W is equal to the sequence (x_{a} + 1, …, r, ∗, 1, …, x_{a}) (resp. (x_{a}, …, r, ∗, 1, …, x_{a} − 1)), if x_{a} is small (resp. large), repeated as many times as there are L-excedances in the circuit

(\begin{matrix}y_{a} & y_{b} & … & y_{z} \\ x_{a} & x_{b} & … & x_{z} \end{matrix}) = (\begin{matrix}x_{b} & & … & x_{z} & x_{a} \\ x_{a} & x_{b} & … & & x_{z} \end{matrix}) .

Hence, for every x ∈ X we have:

∑_{j∈{a,b,... ,z}} χ(x ∈]]x_{j}, y_{j}]]_{L}) = ∑_{j∈{a,b,... ,z}} χ(L-excedance at j).  (5.1)

By summing the above identity over all the cycles of the permutation σ we deduce that

∑_{1≤j≤m} χ(x ∈]]x_{j}, y_{j}]]_{L}) = exc_{L} α.

Now if x_{1} is small (resp. large), then the cyclic interval ]]x_{1}, y_{1}]]_{L} does not contain (resp. contains) x_{1}. Hence x_{1} occurs in exactly exc_{L} α cyclic intervals ]]x_{j}, y_{j}]]_{L} for j = 2, …, m and not in ]]x_{m+1}, y_{m+1}]]_{L} (resp. in exactly exc_{L} α − 1 intervals ]]x_{j}, y_{j}]]_{L} for j = 2, …, m and once in ]]x_{m+1}, y_{m+1}]]_{L}). We have then proved the following proposition.

Proposition 5.1. Let (p_{1}, p_{2}, …, p_{m}) be the L-den-coding of a circuit α, then exc_{L} α = p_{1}.

Besides the L-den-coding of a circuit α = \binom{y_{1} … y_{m}}{x_{1} … x_{m}} we also introduce its L-

exc-coding, denoted by L-exc-coding(α) = (q_{1}, q_{2}, …, q_{m}), where each q_{i} is defined

to be the number of L-excedances in the right factor \binom{y_{i} … y_{m}}{x_{i} … x_{m}} of α. In particular,

p_{1} = q_{1} = exc_{L} α. We look for a necessary and sufficient condition for the L-den-coding to be identical with the L-exc-coding. As will be seen in the next section, when this property holds, the calculation of the distribution of (exc_{L}, den_{L}) can easily be made by using Criterion 4.1.

When the set L of large letters is the set of the largest letters in X with respect to the standard ordering, i.e., when S = {1, 2, …, s} and L = {s + 1, s + 2, …, r} (s + ℓ = r), we write S < L and we speak of “ℓ-den-coding,” “exc_{ℓ}” and “den_{ℓ}” instead of “L-den-coding,” “exc_{L}” and “den_{L}.” (Remember that ℓ is the number of elements in L.)

Next we introduce the following total ordering ⪯_{ℓ} on X defined by

r ≺_{ℓ} (r − 1) ≺_{ℓ} ⋯ ≺_{ℓ} (s + 1) ≺_{ℓ} 1 ≺_{ℓ} 2 ≺_{ℓ} ⋯ ≺_{ℓ} s.

Proposition 5.2. If S < L, then

L-den-coding(α) = L-exc-coding(α)  (5.2)

holds for every ⪯_{ℓ}-well-factorized circuit α.

Proof. From (5.1) it suffices to prove the property when α is a ⪯_{ℓ}-dominated

cycle \binom{y_{1}y_{2} … y_{m}}{x_{1}x_{2} … x_{m}} = \binom{x_{2}x_{3} … x_{1}}{x_{1}x_{2} … x_{m}}. Identity (5.2) holds if and only if for every

i = 1, …, m we have

∑_{i+1≤j≤m+1} χ(x_{i} ∈ ]]x_{j}, y_{j}]]_{L}) = ∑_{i≤j≤m} χ(L-excedance at j).  (5.3)

Let 1 ≤ i ≤ m. As we have noticed earlier, the number of ℓ-excedances in

α′ = (\begin{matrix}y_{i} & y_{i+1} & … & y_{m} \\ x_{i} & x_{i+1} & … & x_{m} \end{matrix}) = (\begin{matrix}x_{i+1} & x_{i+2} & … & x_{m} & x_{1} \\ x_{i} & x_{i+1} & … & x_{m−1} & x_{m} \end{matrix})

is equal to the number of occurrences of ∗ in the juxtaposition product

W′ := ⟩⟩x_{i}, x_{i+1}⟩⟩_{L} ⋯ ⟩⟩x_{m−1}, x_{m}⟩⟩_{L}⟩⟩x_{m}, x_{1}⟩⟩_{L}.

If x_{i} is small, then x_{1} = y_{m} is also small and x_{1} ≥ x_{i}. The product W′ is of the form

(x_{i} + 1, …, x_{1}, …, ∗, …, x_{i}, …, x_{1}).

In that sequence the number of occurrences of x_{i} is equal to the number of occurrences of ∗. As x_{i} does not occur in ]]x_{i}, y_{i}]]_{L}, identity (5.3) holds.

If x_{i} is large and x_{1} is small, then x_{i} > x_{1}. The product W′ is of the form

(x_{i}, …, ∗, …, x_{1}, …, x_{i}, …, ∗, …, x_{1}).

If x_{i} and x_{1} both large, then x_{i} ≥ x_{1}, and W′ is of the form

(x_{i}, …, ∗, …, x_{1}, …, x_{i}, …, ∗, …, x_{1} − 1).

In the last two cases the number of occurrences of x_{i} is still equal to the number of occurrences of ∗. Moreover, x_{i} occurs in both ]]x_{i}, y_{i}]]_{L}, ]]x_{m+1}, y_{m+1}]]_{L}, so that

∑_{i+1≤j≤m+1} χ(x_{i} ∈ ]]x_{j}, y_{j}]]_{L}) = ∑_{i≤j≤m} χ(x_{i} ∈ ]]x_{j}, y_{j}]]_{L}),

and (5.3) also holds.

Proposition 5.3. If there exists a total ordering ⪯ such that for every ⪯-well factorized circuit condition (5.2) holds, then S < L and the ordering ⪯ is identical with ⪯_{ℓ}.

The four columns in the table below refer to the four particular cases considered in the proof. For each circuit appearing in the fifth row the excedances have been indicated in bold-face. The last two rows show the values of the L-den-coding and the L-exc-coding of the circuits.

case 1  case 2  case 3  case 4
x ∈ L, y ∈ S,  x ∈ L, y ∈ S, x ∈ S, y ∈ S, x ∈ L, y ∈ L,
x < y, x ≺ y  x < y, x ≻ y x < y, y ≺ x  x > y, y ≺ x
x  y  x  y x  y  y  x

]]x, y]]_{L} = {x, y} ]]x, y]]_{L} = {x, y} ]]x, y]]_{L} = {y} ]]x, y]]_{L} = {x}
]]y, x]]_{L} = ∅  ]]y, x]]_{L} = ∅ ]]y, x]]_{L} = {x} ]]y, x]]_{L} = {y}

\begin{aligned}& x & y \\ ( & & ) \\ & y & x \\ & ∅ & \{x, y\} & \{x\} \end{aligned} \begin{matrix}y & x \\ ( & & ) \\ x & y \\ \{x, y\} & ∅ & \{x\} \end{matrix} \begin{matrix}y & x \\ ( & ) \\ x & y \\ \{y\} & \{x\} & ∅ \end{matrix} \begin{matrix}y & x \\ ( & ) \\ x & y \\ \{x\} & \{y\} & \{x, y\} \end{matrix}
1  1  1  0  1  0  1  1
1  0  1  1  1  1  1  0

Proof. If S < L does not hold, there exists a pair (x, y) of letters such that x < y with x large and y small. If x ≺ y (case 1), then for the ⪯-well-factorized circuit α = \binom{x y}{y x} we have L-den-coding(α) = (1, 1) ≠ (1, 0) = L-exc-coding(α), while if y ≺ x (case 2) by taking the ⪯-well-factorized circuit α = \binom{y x}{x y} we get L-den-coding(α) = (1, 0) ≠ (1, 1) = L-exc-coding(α).

Now suppose S < L and ⪯≠⪯_{ℓ}. There exists a pair (x, y) such that y ≺ x and x ≺_{ℓ} y and x, y are either both small, or both large. Consider the ⪯-well-factorized circuit \binom{y x}{x y}. If x, y are both small, then x < y (case 3). Its L-den-coding is (1, 0), while its L-exc-coding is (1, 1). If x, y are both large, then x > y (case 4). Its Lden-coding is (1, 1), while its L-exc-coding is (1, 0). See the explicit calculations of the L-den-coding and L-exc-coding in the preceding table.

6. A q-calculation

When S < L holds, we will adopt a new notation for the classes of the rearrangements of a given word. Let c = (c_{1}, …, c_{s}) and d = (d_{1}, …, d_{ℓ}) be two vectors with non negative integer components. The class of all rearrangements of the word 1^{c_{1}} … s^{c_{s}}(s + 1)^{d_{1}} … r^{d_{l}} will be denoted by R(c, d). Also C(c, d) (resp. S(c, d), resp. F_{⪯_{ℓ}}(c, d)) will denote the set of all circuits α = \binom{v}{w} (resp. the subset of well-sorted circuits, resp. the subset of ⪯_{ℓ}-well-factorized circuits) with v and w in R(c, d).

Let A_{F_{⪯_{ℓ}} (c,d)}^{exc_{ℓ},den_{ℓ}}(t, q) be the generating function for the set F_{⪯_{ℓ}}(c, d) by the pair (exc_{ℓ}, den_{ℓ}), i.e.,

A_{F_{⪯_{ℓ}} (c,d)}^{exc_{ℓ},den_{ℓ}}(t, q) = ∑_{α} t^{exc_{ℓ} α}q^{den_{ℓ} α} (α ∈ F_{⪯_{ℓ}}(c, d)).

Theorem 6.1. For each pair (c, d) we have

A_{F_{⪯_{ℓ}} (c,d)}^{exc_{ℓ},den_{ℓ}}(t, q) = A_{c,d}(t, q),

where A_{c,d}(t, q) is the generalized q-Eulerian polynomial defined in (4.1).

Proof. We will make use of Criterion 4.1 with F (c, d) replaced by F_{⪯_{ℓ}}(c, d), f by exc_{ℓ} and g by den_{ℓ}. On the other hand, keep the same notations as in (4.8)

and (4.9) and take α = \binom{y_{1} … y_{m}}{x_{1} … x_{m}} in F_{⪯_{ℓ}}(c, d). Let p = (p_{1}, …, p_{m}) be its ℓ-den-

coding which is also its ℓ-exc-coding. In particular, p_{1} = exc_{ℓ} α and the sequence p is nonincreasing, as well as b = (b_{1}, …, b_{m}) = a + p.

The construction of the bijection (i′, a, α) ↦ (i, a^{(1)}, …, a^{(r)}) can be described

as follows. Consider the biword (\begin{matrix}x_{1} & x_{2} & … & x_{m} \\ b_{1} & b_{2} & … & b_{m} \end{matrix}) to which we apply SORT_{Q_{CF}} (see

Example 1). Let (z_{1}, z_{2}, …, z_{m}) be the bottom word of SORT_{Q_{CF}} (\begin{matrix}x_{1} & x_{2} & … & x_{m} \\ b_{1} & b_{2} & … & b_{m} \end{matrix}).

Then define i := i′ + p_{1}, a^{(1)} := (z_{1}, …, z_{c_{1}}), a^{(2)} := (z_{c_{1}+1}, …, z_{c_{1}+c_{2}}), …, a^{(r)} := (z_{m−d_{ℓ}+1}, …, z_{m}). Then the two relations in (4.10) rewritten as

i = i′ + exc_{ℓ} α, ∥a∥ + den_{ℓ} α = ∥a^{(1)}∥ + ⋯ + ∥a^{(r)}∥

hold, as p_{1} = exc_{ℓ} α and ∥a^{(1)}∥ + ⋯ + ∥a^{(r)}∥ = ∥b∥ = ∥a∥ + ∥p∥ = ∥a∥ + den_{ℓ} α.

For instance, consider S = {1, 2, 3}, L = {4, 5} and take the ⪯_{ℓ}-well-factorized

circuit α := (\begin{matrix}v \\ w \end{matrix}) = (\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}) . First we get the ℓ-den-coding p =

(4, 3, 3, 2, 2, 1, 1, 1, 1). Now with a := (2, 2, 1, 1, 1, 1, 0, 0, 0) and i′ := 3 > a_{1} = 2 we obtain b = a + p = (6, 5, 4, 3, 3, 2, 1, 1, 1). Then

SORT_{Q_{CF}} \binom{4 4 5 1 3 1 2 3 5}{6 5 4 3 3 2 1 1 1} = \binom{1 1 2 3 3 4 4 5 5}{3 2 1 3 1 6 5 4 1}

and (z_{1}, …, z_{m}) = (3, 2, 1, 3, 1, 6, 5, 4, 1). We get i = i′ + exc_{ℓ} α = 3 + 4 = 7 and a^{(1)} = (3, 2), a^{(2)} = (1), a^{(3)} = (3, 1), a^{(4)} = (6, 5), a^{(5)} = (4, 1).

By construction all the sequences a^{(j)} are nonincreasing. Moreover, if x_{k}, x_{k′} (k < k′) are two occurrences of the same large letter s + j in the word w, there is

necessarily an ℓ-excedance in the factor (\begin{matrix}y_{k} & … & y_{k′} \\ x_{k} & … & x_{k′} \end{matrix}) of the circuit α, so that all the

sequences a^{(s+1)}, …, a^{(r)} are decreasing. Finally, if x_{k} is the rightmost occurrence

of a given large letter s + j in the word w, then the right factor (\begin{matrix}y_{k} & … & y_{m} \\ x_{k} & … & x_{m} \end{matrix}) of α

necessarily contains an ℓ-excedance, so that all the terms in the sequences a^{(s+1)}, …, a^{(r)} are greater than or equal to 1.

7. The transformations

Let w = x_{1}x_{2} … x_{m} be a word in R(c, d). Supposing S < L form the ⪯_{ℓ}- well-factorized circuit α = Δ(w) (see section 2). Next apply the transformation SORT_{(⪯,Q_{L})} to α (see section 3), where Q_{L} is the Boolean function derived when S < L. From Theorem 3.2 we know that

(exc_{L}, den_{L}) α = (exc_{L}, den_{L}) SORT_{(⪯,Q_{L})}(α).  (7.1)

The circuit α′ = SORT_{(⪯,Q_{L})}(α) is well-sorted. Using the transformation Γ (see section 2) we know that to α there corresponds a unique word w′ in R(c, d) such that Γ(w′) = α′. We then have the chain

w ↦ Δ(w) = α ↦ SORT_{(⪯,Q_{L})}(α) = α′ ↦ Γ^{−1}(α′) = w′.  (7.2)

Let w = x_{1}x_{2} … x_{m} be a word in R(c, d). The statistic des_{ℓ} w (resp. maj_{ℓ} w) is defined (see, e.g. [7]) as the number (resp. the sum) of the integers i such that 1 ≤ i ≤ m and either x_{i} > x_{i+1} or x_{i} = x_{i+1} and x_{i} large (by convention x_{m+1} = s). It is easy to verify that

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

On the other hand, the definitions of the number of ℓ-excedances and the ℓ-Denert statistic for the words w′ can be taken as

(exc_{ℓ}, den_{ℓ}) w′ := (exc_{ℓ}, den_{ℓ}) Γ(w′).  (5.4)

It then follows that the chain displayed in (7.2) provides a bijection w ↦ w′ of R(c, d) onto itself having the property that

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

Acknowledgements. The authors should like to thank one of the referees for his careful reading of the paper that improves the tenor of the final version.

References

1. G. E. Andrews, The Theory of Partitions, Addison–Wesley (Encyclopedia of Math. and its Appl., vol. 2), Reading, 1976.

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

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

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

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

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 and G.N. Han, Transformations on Words, J. Algorithms 28 (1998), 172–191.

11. D. Foata and C. Krattenthaler, Graphical Major Indices, II, Séminaire Lotharingien de Com-

binatoire (http://cartan.u-strasbg.fr/∼slc) B34k (1995), 16 pp.

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

13. G. Gasper and M. Rahman, Basic hypergeometric series, Cambridge Univ. Press (Encyclopedia of Math. and its Appl., vol. 35), Cambridge, 1990.

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

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

Département de mathématique, Université Louis Pasteur, 7, rue René-Descartes, F-67084 Strasbourg, France

 E-mail address: foata@math.u-strasbg.fr

I.R.M.A., Université Louis Pasteur et C.N.R.S., 7, rue René-Descartes, F-67084 Strasbourg, France

 E-mail address: guoniu@math.u-strasbg.fr