New Euler–Mahonian permutation statistics

Robert J. Clarke^{∗}  Einar Steingrímsson^{†}  Jiang Zeng^{‡}

(All correspondence to Einar Steingrímsson)

Abstract

We define or redefine new Mahonian permutation statistics, called mad, mak and env. Of these, env is shown to equal the classical inv, that is the number of inversions, while mak has been defined in a slightly different way by Foata and Zeilberger. It is shown that the triple statistics (des, mak, mad) and (exc, den, env) are equidistributed over S_{n}. Here den is Denert’s statistic. In particular, this implies the equidistribution of (exc, inv) and (des, mad). These bistatistics are not equidistributed with the classical Euler-Mahonian statistic (des,maj). The proof of the main result is by means of a bijection which is essentially equivalent to several bijections in the literature (or inverses of these). These include bijections defined by Foata and Zeilberger, by Françon and Viennot and by Biane, between the symmetric group and sets of weighted Motzkin paths. These bijections are used to give a continued fraction expression for the generating function of (exc, inv) or (des, mad) on the symmetric group. All of the main results extend to the rearrangement class of an arbitrary word with repeated letters.

(The entire paper can be obtained at http://www.math.chalmers.se/~einar/)

1 Introduction

The subject of permutation statistics, it is frequently claimed, dates back at least to Euler [?]. However, it was not until MacMahon’s extensive study [?] at the turn of the century that this became an established discipline of mathematics, and it was to take a long time before it developed into the vast field that it is today.

In the last three decades or so much progress has been made in discovering and analyzing new statistics. See for example [?, ?, ?, ?, ?, ?, ?, ?, ?]. Inroads have also been made in connecting permutation statistics to various geometric structures and to the classical theory of hypergeometric functions, as in [?, ?, ?, ?, ?].

MacMahon considered four different statistics for a permutation π: The number of descents (des π), the number of excedances (exc π), the number of inversions (inv π), and the major index (maj π). These are defined as follows: A descent in a permutation π = a_{1}a_{2} ⋯ a_{n} is an i such that a_{i} > a_{i+1}, an excedance is an i such that a_{i} > i, an inversion is a pair (i, j) such that i < j and a_{i} > a_{j}, and the major index of π is the sum of the descents in π. In fact, MacMahon studied these statistics in greater generality, namely over the rearrangement class of an arbitrary word w with possibly repeated letters. All of our present results except those of section ?? can be generalized to words, and this will be done in a subsequent publication [?]. In this abstract we mention these generalizations, but the presentation is centered on permutations. Moreover, there is a further generalization, to words in which the letters are divided into two classes, small and large. This is treated in a forthcoming paper [?].

∗This work was carried out while the author was Visiting Professor at the Université Louis-Pasteur in Strasbourg during summer and autumn of 1995.

†Partially supported by a grant from The Icelandic Council of Science and partially supported by the EU Network in Algebraic Combinatorics while visiting Université Louis-Pasteur in Strasbourg.

‡Partially supported by the EU Network in Algebraic Combinatorics.

In the present paper, we define some new Mahonian statistics and redefine many of the existing ones, with an eye to illuminating their common properties and thus also their differences. Doing this allows us to recover some of the known instances of equidistribution among Euler-Mahonian pairs, and to prove the equidistribution of two new pairs introduced, as well as that of some similiar, but not equal, pairs of bistatistics. We do this simultaneously for all the statistics involved, by means of a single, simply described bijection.

All of our constructions, and some of our statistics, have appeared previously, in the work of several authors and in many different guises. They have involved Motzkin paths, binary trees, and even more exotic structures. As we will show, the bijections in the literature pertaining to these statistics, those of Foata–Zeilberger, Françon–Viennot [?], de Médicis–Viennot [?], Simion–Stanton [?] and Biane [?], defined in different ways and for different purposes, are all essentially the same, or inverses of each other. These bijections are equivalent to the bijection of this paper, but their relationships with each other have not before been elucidated. Moreover, the extensions of the above statistics and bijections to words have not appeared before.

Perhaps the most interesting fact to emerge is the equidistribution of the two bistatistics (des, mad) and (exc, inv), where mad is one of our new statistics. The latter bistatistic, whose components are classical, is not equidistributed with (des, maj) and might therefore, together with its equidistributed mates, be classified as an “Euler-Mahonian pair of the second kind.”

2 Definitions and main results

We consider the set S_{A} of all permutations π = a_{1}a_{2} ⋯ a_{n} on a totally ordered alphabet A. Although it is not necessary, we always take A to be the interval [n] = {1, 2, …, n}. Thus, we consider permutations in S_{n}.

The biword associated to a permutation π is π̃ = ( \begin{matrix}id \\ π \end{matrix} ), where id is the identity

permutation id = 123 ⋯ n. In what follows, π̃ will always have this meaning.

Definition 1 Let π ∈ S_{n}. A descent in π is an integer i with 1 ≤ i < n such that a_{i} > a_{i+1}. Here a_{i} is called the descent top and a_{i+1} is called the descent bottom. An excedance in w is an integer i with 1 ≤ i ≤ n such that and a_{i} > i. Here a_{i} is called the excedance top. The number of descents in π is denoted by des π, and the number of excedances is denoted by exc π.

The descent set of π, D(π), is the set of descents. The excedance set of π, E(π), is the set of excedances.

Given a permutation π = a_{1}a_{2} ⋯ a_{n}, we separate π into its descent blocks by putting in dashes between a_{i} and a_{i+1} whenever a_{i} ≤ a_{i+1}. A maximal contiguous subword of π which lies between two dashes is a descent block. A descent block is an outsider if it has only one letter, otherwise it is a proper descent block. The leftmost letter of a proper descent block is its closer and the rightmost letter is its opener. A letter which lies strictly inside a descent block is an insider. For example, the permutation 1 8 5 2 6 7 9 3 4 has descent block decomposition 1−8 5 2−6−7−9 3−4, with closers 8, 9, corresponding openers 2, 3, outsiders 1, 6, 7, 4 and insider 5.

Let B be a proper descent block of the permutation π and let c(B) and o(B) be the closer and opener, respectively, of B. If a is a letter of w, we say that a is embraced by B if c(B) > a > o(B).

Definition 2 Let π = a_{1}a_{2} ⋯ a_{n} be a permutation. The (right) embracing numbers of π are the numbers e_{1}, e_{2}, …, e_{n}, where e_{i} is the number of descent blocks in π that are strictly to the right of a_{i} and that embrace a_{i}. The right embracing sum of π, denoted by Res π, is defined by

Res π = e_{1} + e_{2} + ⋯ + e_{n}.

For instance, the embracing numbers of π = 4 1 − 7 − 8 2 − 5 − 6 3 are 2 0 − 1 − 0 0 − 1 − 0 0, so Res w = 4.

Definition 3 The descent bottoms sum of a permutation π = a_{1}a_{2} ⋯ a_{n}, denoted by Dbot π, is the sum of the descent bottoms of π. The descent tops sum of π, denoted Dtop π, is the sum of the descent tops of π. The descent difference of π is

Ddif π = Dtop π − Dbot π.

Otherwise expressed, Ddif π is the sum of closers minus the sum of openers of descent blocks. As an example, for π = 4 1 − 2 − 6 5 3 − 7, Dbot w = 1 + 5 + 3 = 9, Dtop w = 4 + 6 + 5 = 15 and Ddif w = 15 − 9 = (4 + 6) − (1 + 3) = 6.

Definition 4 The excedance bottoms sum of a permutation π = a_{1}a_{2} ⋯ a_{n}, denoted by Ebot π, is the sum of the excedances of π. The excedance tops sum of π, denoted Etop w, is the sum of the excedance tops of π. The excedance difference of π is

Edif π = Etop π − Ebot π.

The excedance subword of π, denoted by π_{E}, is the permutation consisting of all the excedance tops of π, in the order induced by π. The non-excedance subword of π, denoted by π_{N}, consists of those letters of π that are not excedance tops.

For example, let π = 6 5 4 3 7 1 2, so w̃ = ( \begin{matrix}1 & 2 & 3 & 4 & 5 & 6 & 7 \\ 6 & 5 & 4 & 3 & 7 & 1 & 2 \end{matrix} ); then π_{E} =

6 5 4 7 and π_{N} = 3 1 2. Also, Ebot π = 1+2+3+5 = 11, Etop π = 6+5+4+7 = 22 and Edif π = 22 − 11 = 11.

Definition 5 An inversion in a permutation π = a_{1}a_{2} ⋯ a_{n} is a pair (i, j) such that i < j and a_{i} > a_{j}. The number of inversions in π is denoted by inv π.

The reason we spell inv with all capital letters is that inv is a Mahonian statistic. We do this consistently throughout the paper, that is, all Mahonian statistics are spelled with uppercase letters. The two Eulerian statistics, exc and des, are spelled with lowercase letters, while “partial statistics” (such as Res), used in the definitions of Mahonian statistics, are merely capitalized.

Definition 6 Let π = a_{1}a_{2} ⋯ a_{n} be a permutation and i an excedance in π. We say that a_{i} is the bottom of d inversions if there are exactly d letters in π to the left of a_{i} that are greater than a_{i}, and we call d the inversion bottom number of i. Similarly, if i is a non-excedance in π and there are exactly d letters smaller than a_{i} and to the right of a_{i} in π, then we say that d is the inversion top number of i. The side number of i in π is the inversion bottom number or the inversion top number of i in π, according as i is an excedance or not in π. The sequence of side numbers of π is the sequence s_{1}, s_{2}, …, s_{n} where s_{i} is the side number of i.

For example, let π = 6 5 4 3 7 1 2 as before, with π_{E} = 6 5 4 7 and π_{N} = 3 1 2. Then the inversion bottom numbers of the excedances in π are 0, 1, 2, 0 and the inversion top numbers of the non-excedances in π are 2, 0, 0. Hence the sequence of side numbers of π is 0, 1, 2, 2, 0, 0, 0.

Note that if i is an excedance of the permutation π, then any letter in π that is to the left of a_{i} and greater than a_{i} must also be an excedance. Hence, the sum of the inversion bottom numbers of the letters in w_{E} equals the total number of inversions in w_{E}, that is, inv w_{E}. Similarly, the sum of the inversion top numbers of the letters in w_{N} equals inv w_{N}.

Definition 7 Let π be a permutation. Then Ine π = inv π_{E} + inv π_{N}.

Hence, from the remark preceding definition ??, we have

Ine w = s_{1} + ⋯ + s_{n}.  (1)

We now define the four Mahonian statistics central to this paper.

Definition 8 mak π = Dbot π + Res π.

mad π = Ddif π + Res π.
den π = Ebot π + Ine π.
env π = Edif π + Ine π.

As it turns out, our statistic env equals the classical inv. It may seem superfluous to redefine inv in this way, but it turns out that env’s similarity in definition to mad is crucial in proving our main results.

Theorem 1 For any permutation π = a_{1}a_{2} ⋯ a_{n}, we have env π = inv π.

We now describe the main results of the paper, the proofs of which are omitted in this abstract.

In section ?? we will define a mapping Φ on S_{n} and prove the following result.

Proposition 2 For any permutation π, we have

(des, Dbot, Ddif, Res) π = (exc, Ebot, Edif, Ine) Φ(π),
(des, mad, mak) π = (exc, inv, den) Φ(π).

By showing that Φ is a bijection, we deduce the following theorem.

Theorem 3 The quadristatistics

(des, Dbot, Ddif, Res) and (exc, Ebot, Edif, Ine)

are equidistributed over the symmetric group S_{n}. That is,

∑_{π∈S_{n}} t^{^{des}π}x^{^{Dbot}π}y^{^{Ddif} π}q^{^{Res}π} = ∑_{π∈S_{n}} t^{^{exc}π}x^{^{Ebot}π}y^{^{Edif} π}q^{^{Ine}π}.

Hence the triple (des, mad, mak) is equidistributed with (exc, inv, den) over S_{n}.

In section ??, we shall make evident the relation between our bijection Φ and some well-known bijections between the symmetric group S_{n} and weighted Motzkin paths. As a by-product, we will obtain a continued fraction expansion (equation ??) for the ordinary generating function of

D_{n}(x, q) = ∑_{π∈S_{n}} x^{^{des}π}qmadπ.

3 The bijection Φ

We now describe the construction of a bijection Φ : S_{n} → S_{n} which takes a permutation π to a permutation τ such that the set of descent tops in π equals the set of excedance tops in τ and the set of descent bottoms in π equals the set of excedances in τ. Moreover, the embracing numbers of π are preserved in a way that we now describe.

Observe that, since the letters of a permutation are distinct, we can refer to the i-th embracing number e_{i} of the permutation π as the embracing number of the letter a_{i} in π, and we will then denote e_{i} by e(a_{i}). Similarly, we may if we wish denote the i-th side number of π by d(a_{i}).

We will construct τ = Φ(π) in such a way that the embracing number of a letter a_{i} in π is the side number of a_{i} in τ.

Given a permutation π, we first construct two biwords, ( \begin{matrix}f \\ f′ \end{matrix} ) and ( \begin{matrix}g \\ g′ \end{matrix} ), and then

form the biword τ′ = ( \begin{matrix}f g \\ f′ g′ \end{matrix} ) by concatenating f and g, and f′ and g′, respectively.

The permutation f is defined as the subword of descent bottoms in π, ordered increasingly, and g is defined as the subword of non-descent bottoms in π, also ordered increasingly. The permutation f′ is the subword of descent tops in π, ordered so that the inversion bottom number of a letter a in f′ is the embracing number of a in π, and g′ is the subword of non-descent tops in π, ordered so that the inversion top number of a letter b in g′ is the embracing number of b in π. Rearranging the columns of τ′, so that the top row is in increasing order, we obtain the permutation τ = Φ(π) as the bottom row of the rearranged biword.

Example 1 Let π = 4 1 − 2 − 7 − 9 6 5 − 8 3, with embracing numbers 1, 0, 0, 2, 0, 1, 1, 0, 0. Then

( \begin{matrix}f \\ f′ \end{matrix} ) = ( \begin{matrix}1 3 5 6 \\ 8 4 6 9 \end{matrix} ) , ( \begin{matrix}g \\ g′ \end{matrix} ) = ( \begin{matrix}2 4 7 8 9 \\ 1 2 7 5 3 \end{matrix} ) , τ′ = ( \begin{matrix}1 3 5 6 2 4 7 8 9 \\ 8 4 6 9 1 2 7 5 3 \end{matrix} )

and thus Φ(π) = τ = 8 1 4 2 6 9 7 5 3. It is easily checked that the descent tops and descent bottoms in π are the excedance tops and excedances in τ, respectively, and that the embracing number of each letter in π is the side number of the same letter in τ.

Remark In the case of words with repeated letters, presented in [?], the definitions of Ddif, Edif, Res and Ine are slightly modified. A word w is then “coded” into a permutation π by replacing the occurrences of equal letters with distinct integers in an increasing order from left to right. (As an example, the word 2 3 2 2 1 3 1 2 is coded into 3 7 4 5 1 8 2 6). Then Φ is applied to π and the resulting permutation “decoded” to obtain a word w′ such that (des, Dbot, Ddif, Res) w = (exc, Ebot, Edif, Ine) w′. This map is a bijection, which proves the equidistribution of (des, mad, mak) and (exc, inv, den) over the rearrangement class of an arbitrary word w.

4 Motzkin paths and a continued fraction expansion

In this section we shall make evident the relation between our bijection Φ and some well-known bijections between the symmetric group S_{n} and weighted Motzkin paths. As a by-product we get the continued fraction expansion for the generating function of S_{n} with respect to some of our statistics.

Informally, a Motzkin path is a connected sequence of n line segments, or “steps,” in the first quadrant of R^{2}, starting out from the origin in R^{2} and ending at (0, n) (see Figure 1 for an example).

Definition 9 A Motzkin path is a word w = c_{1}c_{2} ⋯ c_{n} on the alphabet {N, S, E, dE} such that for each i the level h_{i} of the i-th step, defined by

h_{i} = #{j|j < i, c_{j} = N} − #{j|j < i, c_{j} = S},

is non-negative, and equal to zero if i = n.

Definition 10 A weighted Motzkin path of length n is a pair (c, d), where c = c_{1} ⋯ c_{n} is a Motzkin path of length n, and d = (d_{1}, …, d_{n}) is a sequence of integers such that

0 ≤ d_{i} ≤ \{ \begin{matrix}h_{i} & if c_{i} ∈ \{N, E\}, \\ h_{i} − 1 & if c_{i} ∈ \{S, dE\}. \end{matrix}

The set of weighted Motzkin paths of length n is denoted by Γ_{n}.

Françon and Viennot [?] gave the first bijection Ψ_{FV} between S_{n} and Γ_{n}. Here we describe one variant of this bijection.

Definition 11 Let π = a_{1} ⋯ a_{n} ∈ S_{n} and set a_{0} = 0 and a_{n+1} = n + 1. For 1 ≤ i ≤ n we say that a_{i} is a

• linear double ascent (outsider) if a_{i−1} < a_{i} < a_{i+1};

• linear double descent (insider) if a_{i−1} > a_{i} > a_{i+1};

• linear peak (closer) if a_{i−1} < a_{i} > a_{i+1};

• linear valley (opener) if a_{i−1} > a_{i} < a_{i+1}.

The bijection Ψ_{FV} of Françon and Viennot

Given a permutation π ∈ S_{n}, determine the right embracing number e_{i} for each i ∈ [n]. Form the weighted Motzkin path (c, d) = Ψ_{FV}(π) by setting d_{i} = e_{i} and by defining c_{i} as follows:

• if i is a linear double descent, then c_{i} = dE;

• if i is a linear double ascent then c_{i} = E;

• if i is a linear peak then c_{i} = S;

• if i is a linear valley then c_{i} = N. For example, if π = 6 1−8 7 4 2−5−9 3, then the corresponding weighted Motzkin path Ψ_{FV}(π) = (c, d) is shown in Figure 1.

[figure: i; 1; 2; 3; 4; 5; 6; 7; 8; 9; 0; 0; 0; 1; 1; 2; 1; 1; 0; d_{i}] Figure 1

The bijection Ψ_{FZ} of Foata and Zeilberger

In [?] Foata and Zeilberger gave another bijection from S_{n} to Γ_{n}, which can be described by the following example. Let π = 9 4 7 6 1 2 8 5 3, so

π̃ = ( \begin{matrix}1 2 3 4 5 6 7 8 9 \\ 9 4 7 6 1 2 8 5 3 \end{matrix} ) .

As in section ??, separate π̃ into two biwords corresponding to π_{E} and π_{N} to get

( \begin{matrix}f \\ f′ \end{matrix} ) = ( \begin{matrix}1 & 2 & 3 & 4 & 7 \\ 9 & 4 & 7 & 6 & 8 \end{matrix} ) , ( \begin{matrix}g \\ g′ \end{matrix} ) = ( \begin{matrix}5 & 6 & 8 & 9 \\ 1 & 2 & 5 & 3 \end{matrix} ) .

Form the weighted Motzkin path (c, d) = Ψ_{FZ}(π) as follows: Let s_{1}, s_{2}, …, s_{n} be the sequence of side numbers of π (see Definition ??) and put

d_{π(i)} = s_{i} for i = 1, 2, …, n.  (2)

Let

c_{i} = \{ \begin{matrix}dE, & if i ∈ F ∩ F′, \\ E, & if i ∈ G ∩ G′, \\ S, & if i ∈ F′ ∩ G, \\ N, & if i ∈ F ∩ G′. \end{matrix}

Here we have d = (0, 0, 0, 1, 1, 2, 1, 1, 0) and

F ∩ F′ = {4, 7}, G ∩ G′ = {5}, F′ ∩ G = {6, 8, 9}, F ∩ G′ = {1, 2, 3}.

Definition 12 For π ∈ S_{n} and i ∈ [n], we say that i is a • cyclic double ascent if π^{−1}(i) < i < π(i);

• cyclic double descent if π^{−1}(i) ≥ i ≥ π(i);

• cyclic peak if π^{−1}(i) < i > π(i);

• cyclic valley if π^{−1}(i) > i < π(i).

Note that the four sets F ∩F′, G∩G′, F′ ∩G and F ∩G′ correspond respectively to cyclic double ascents, cyclic double descents, cyclic peaks and cyclic valleys of π. The corresponding weighted Motzkin path is the same as in Figure 1. We note that Ψ_{FV} = Ψ_{FZ} ∘ Φ.

Biane’s bijection

In [?], Biane gave a bijection similar to Ψ_{FZ} which we now describe.

Definition 13 A labeled path of length n is a pair (c, ξ), where c = c_{1} ⋯ c_{n} is a Motzkin path of length n, and ξ = (ξ_{1}, …, ξ_{n}) is a sequence such that

ξ_{i} ∈ \{ \begin{matrix}\{Δ\}, & if c_{i} = N, \\ \{0, …, h_{i}\}, & if c_{i} = dE or E, \\ \{0, …, h_{i} − 1\}^{2}, & if c_{i} = S. \end{matrix}

Biane’s bijection is from the labeled paths of length n to S_{n} . Using the same notation as in the description of Ψ_{FZ}, the inverse of Biane’s bijection can be summarized as follows. Let d_{1}, d_{2}, …, d_{n} be the sequence of numbers calculated using equation (??) from the side numbers of π. Note that Biane gave a recursive algorithm to compute these numbers but did not point out that they are actually the side numbers of π, that is the inversion bottom and inversion top numbers in f′ and g′ respectively. Form the labeled path (c, ξ) thus:

• if i ∈ F ∩ G′ (valley), let c_{i} = N and ξ_{i} = Δ;

• if i ∈ F ∩ F′ (double ascent), let c_{i} = dE and ξ_{i} = d_{i};

• if i ∈ G ∩ G′ (double descent), let c_{i} = E and ξ_{i} = d_{π(i)};

• if i ∈ F′ ∩ G (peak), let c_{i} = S and ξ_{i} = (d_{π(i)}, d_{i}). The path is the same as for Ψ_{FZ}, the only difference being the distribution of the side numbers associated to each step of the path.

In [?], Foata and Zeilberger’s purpose with the bijection Ψ_{FZ} was to code the den statistic by weighted Motzkin paths, in order to show that (exc, den) was equidistributed with (des, maj). That Ψ_{FZ} also keeps track of the inv statistic was first remarked by de Médicis and Viennot [?, Proposition 5.2]. They proved that

inv π = ∑_{i=1}^{n} h_{i} + ∑_{i=1}^{n} d_{i}.  (3)

In Biane’s bijection, on the other hand, the inv statistic is seen to satisfy

inv π = ∑_{i=1}^{n}(h_{i} + |ξ_{i}|),

where |ξ| = x + y if ξ = (x, y) and |ξ| = 0 if ξ = Δ. This is clearly equivalent to (??).

The proof of (??) given in [?] was based on a new definition of inv, similar to that of env. This statistic of de Médicis and Viennot’s, which we denote inv_{MV} can be defined in our notation by

inv_{MV} π = inv π_{E} + inv π_{N} + #{(i, j)|i ≤ j < π(i), π(j) > j}
+ #{(i, j)|π(i) < π(j) ≤ i, π(j) ≤ j}.  (4)

However, their proof that inv equals inv_{MV} is fairly complicated, and can be compared to that of the equivalence of the two definitions of den given in [?]. In [?], Clarke gave a short proof of the equivalence of the two definitions of den. Actually, the identity proved in [?] can also be used to prove the equivalence of the three definitions of inv mentioned above.

Using the connections between Motzkin paths and permutations we have described, we now give a continued fraction expansion for the generating function D_{n}(x, q) = ∑_{π∈S_{n}} x^{^{des}π}q^{^{MAD}π}.

For n ≥ 0 let [n]_{q} = 1 + q + ⋯ + q^{n−1} and let f_{n}(x, p, q) = ∑_{π∈S_{n}} x^{^{exc}π}q^{^{Edif} π}p^{^{Ine}π}.

Then, by Theorem ??, we also have f_{n}(x, p, q) = ∑_{π∈S_{n}} x^{^{des}π}q^{^{Ddif} π}p^{^{Res}π}. The follow-

ing theorem now follows by applying a result of Flajolet [?, Theorem 1].

Theorem 4 The ordinary generating function of f_{n}(x, p, q) has the following Jacobi continued fraction expansion:

∑_{n≥0} f_{n}(x, p, q)t^{n} = \frac{1}{1 − b_{0}t − \frac{λ_{1}t^{2}}{1 − b_{1}t − \frac{λ_{2}t^{2}}{\frac{...}{1 − b_{n}t − \frac{λ_{n+1}t^{2}}{...}}}}} ,

where b_{n} = q^{n}(x[n]_{p} + [n + 1]_{p}) and λ_{n+1} = xq^{2n+1}([n + 1]_{p})^{2} for n ≥ 0.

Corollary 5 We have

∑_{n≥0} f_{n}(x, p, q)t^{n} = \frac{1}{1 − \frac{t}{1 − \frac{xqt}{\frac{...}{1 − \frac{q^{n−1}[n]_{p}t}{1 − \frac{xq^{n}[n]_{p}t}{...}}}}}} .  (5)

In particular, if D_{n}(x, q) = ∑_{π∈S_{n}} x^{^{des}π}q^{^{MAD}π}, then it follows from Corollary ??, by

putting p = q in the above equation, that

∑_{n≥0} D_{n}(x, q)t^{n} = \frac{1}{1 − \frac{t}{1 − \frac{xqt}{\frac{...}{1 − \frac{q^{n−1}[n]_{q}t}{1 − \frac{xq^{n}[n]_{q}t}{...}}}}}} .  (6)

Note that the continued fraction expansion of the generating function of ∑_{π∈S_{n}} x^{^{des}π}qinvπ can also be derived from [?, Theorem 6.5].

Corollary 6 For 0 ≤ k ≤ n − 1 and 0 ≤ m ≤ \frac{n(n−1)}{2} we have

[x^{k}q^{k+m}]D_{n}(x, q) = [x^{n−1−k}q^{n−1−k+m}]D_{n}(x, q),  (7)

where [x^{k}q^{m}]D_{n}(x, q) is the coefficient of x^{k}q^{m} in the polynomial D_{n}(x, q).

References

[1] P. Biane: Permutations suivant le type d’excédance et le nombre d’inversions et interprétation combinatoire d’une fraction continue de Heine, Europ. J. Combinatorics 14 (1993), 277–284.

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

[3] R. J. Clarke, E. Steingrímsson and J. Zeng: The k-extensions of some new Mahonian statistics, Europ. J. Combinatorics, to appear.

[4] R. J. Clarke, E. Steingrímsson and J. Zeng: New Euler-Mahonian statistics on permutations and words, Adv. Appl. Math., to appear.

[5] L. Euler: Institutiones calculi differentialis, in Opera Omnia, Series Prima, vol. X, Verlag von B.G. Teubner, Leipzig, 1913.

[6] P. Flajolet: Combinatorial aspects of continued fractions, Disc. Math. 41 (1982), 145–153.

[7] D. Foata: Distribution Eulériennes et Mahoniennes sur le groupe des permutations, in M. Aigner (ed.), Higher Combinatorics, 27–49, D. Reidel, Boston, Berlin Combinatorics Symposium, 1976.

[8] D. Foata: Rearrangements of words, in M. Lothaire, Combinatorics on Words, (ed.) G.-C. Rota, Vol. 17, Encyclopedia of Math. and its Appl., Addison-Wesley Publishing Company, 1983.

[9] D. Foata and M.-P. Schützenberger: Théorie géométriques des poly-nômes eulériens, Lecture Notes in Math., vol. 138, Springer-Verlag, Berlin, 1970.

[10] D. Foata and M.-P. Schützenberger: Major index and inversion number of permutations, Math. Nachr. 83 (1978), 143–159.

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

[12] J. Françon and X. G. Viennot: Permutations selon les pics, creux, doubles montées, doubles descentes, nombres d’Euler, nombres de Genocchi, Disc. Math. 28 (1979), 21–35.

[13] J. Galovich and D. White: Recursive statistics on words, Preprint,

[14] A. M. Garsia and I. M. Gessel: Permutations statistics and partitions, Adv. in Math. 31 (1979), 288–305.

[15] P.A. MacMahon: Combinatory Analysis, vols. 1 and 2. Cambridge Univ. Press, Cambridge, 1915 (reprinted by Chelsea, New York, 1955).

[16] A. de Médicis and X. G. Viennot: Moments des q-Polynômes de Laguerre et la bijection de Foata-Zeilberger, Adv. Appl. Math. 15 (1994), 262–304.

[17] D. Rawlings: Permutation and multipermutation statistics, Europ. J. Comb., 2 (1981), 67-78.

[18] S. Simion and D. Stanton: Specializations of generalized Laguerre polynomials, SIAM J. Math. Anal. 25 (1994), 712–719.

[19] R. Stanley: Binomial posets, Möbius inversion and permutation enumeration, J. Comb. Theory, A, 20 (1976), 712–719.

Clarke: Pure Mathematics Department, University of Adelaide, Adelaide, South Australia 5005. Steingrímsson: Matematiska institutionen, CTH & GU, 412 96 Göteborg, Sweden. Zeng: Département de mathématique,Université Louis-Pasteur, 67084 Strasbourg Cedex, France