DENERT’S PERMUTATION STATISTIC

IS INDEED EULER-MAHONIAN

BY

Dominique FOATA (^{∗}) AND Doron ZEILBERGER (^{∗∗})

ABSTRACT. — A conjecture by Marleen Denert concerning a bivariate statistic on the permutation group is proved. The statistic has the same distribution as the pair consisting of the number of descents and the major index.

1. Introduction

In this paper we prove a conjecture of Marleen Denert ([De1], [De2]) concerning a new permutation statistic that she has recently discovered. Namely we will prove that her statistic when taken jointly with the number of excedences, has the same joint distribution as that of the pair of classical permutation statistics that consists of the major index and the number of descents.

Let us start with a little history and background. The Hebrew book of Creation, Sepher Yetsira (c. 300 C.E., [SU], p. 109, see also [Kn], p. 23), stated the number of permutations of n objects for n ≤ 7. Saadia Gaon (882-942 C.E.) gave the general rule that the number of permutations of n objects is n times the number of permutations of (n − 1) objects by stating it explicitly for n ≤ 11, and then saying that “if you want to know the [permutations] of still larger numbers, you may operate according to the same method” ([Ga], p. 496). Saadia, however, was only interested in these numbers up to n = 11, since the largest word to be found in the Bible contains eleven letters, like the word “ve ha a kh sh de r pa n i m.”

(^{∗}) Department of Mathematics, Drexel University, Philadelphia, PA 19104, USA.

Supported in part by NSF grant DMS 8901610. On leave (1989) from Département de mathématique, Université Louis-Pasteur, 7, Rue René-Descartes, F-67084 Strasbourg, France.

(^{∗∗}) Department of Mathematics, Drexel University, Philadelphia, PA 19104, USA.

Supported in part by NSF grant DMS 8800663.

D. FOATA AND D. ZEILBERGER

The general formula was proved rigorously in 1321 by Levi Ben Gerson, by what may have been the first use of complete mathematical induction ([Le], see also [Carle]).

More recently, more refined counts of permutations, according to various statistics, have been undertaken. The naive count of a family of sets A_{n} is simply a formula for the number of elements in A_{n} :

a_{n} := ∑_{a} 1 (a ∈ A_{n}),

where every element carries weight 1. Often, however, the elements of A_{n} possess several significant numerical attributes, called statistics (like age, height, weight for people), say, f_{1}(a), …, f_{r}(a). Then one is interested in the refined count according to these statistics

a_{n}(t_{1}, …, t_{r}) := ∑_{a} t_{1}^{f_{1}(a)} … t_{r}^{f_{r}(a)} (a ∈ A_{n}),

where every element of A_{n} carries weight t_{1}^{f_{1}(a)} … t_{r}^{f_{r}(a)} rather than 1. It is then desired to find explicit formulas, and properties of the polynomials a_{n}(t_{1}, …, t_{r}).

Various statistics on permutations have been discussed in the past. Netto considered the number of inversions, and MacMahon considered the major index. Another important statistic is the number of descents. These statistics are defined on the symmetric group S_{n} as follows :

inv π := #{i < j; π(i) > π(j)}, maj π := ∑_{i} i (π(i) > π(i + 1)),

des π := #{i; π(i) > π(i + 1)}.

The generating functions according to these statistics are well known (see, for example, [Fo2]) and due to Netto, MacMahon and Euler, respectively. Using the notation [n]_{q} = (1 − q^{n})/(1 − q) we have

∑_{π∈S_{n}} q^{maj π} = [1]_{q} [2]_{q} … [n]_{q};  (MAJ)
∑_{π∈S_{n}} q^{inv π} = [1]_{q} [2]_{q} … [n]_{q};  (INV)
∑_{π∈S_{n}} t^{des π} = A_{n}(t) ;  (DES)

where A_{n}(t) are the so-called Eulerian polynomials, that do not have closed forms by themselves, but do have a nice generating function (see [Fo2]).

DENERT’S PERMUTATION STATISTIC

Carlitz [Carli] considered the bi-variate refined counting of S_{n} according to the pair (des, maj). Namely he defined (in a slightly different notation):

B_{n}(t) = ∑_{π∈S_{n}} t^{des π}q^{maj π},

and proved that if one writes

B_{n}(t) = ∑_{k=0}^{n} B_{n,k}(q) t^{k},

then the coefficients B_{n,k}(q) satisfy the recurrence :

B_{n,k}(q) = [k + 1]_{q}B_{n−1,k}(q) + q^{k}[n − k]_{q}B_{n−1,k−1}(q),  (CARLITZ)

subject to the initial conditions B_{0,k}(q) = δ_{0,k}.

Refined permutation-counting reached new heights with the papers by Garsia and Gessel [G-G] and Rawlings [Ra], who found the generating function for the quadruple (des, ides, maj, imaj), where ides π = des π^{−1} and imaj π = maj π^{−1}. This work was extended to colored permutations, and shown to find its natural habitat in the theory of tableaux and Schur functions by Désarménien and Foata [D-F1], [D-F2].

Two statistics that have the same generating function are said to be equi-distributed, and a natural question then is whether there is a“natural” reason for this, i.e., whether there is a bijection of the set to itself that sends one statistic to the other. For example, since the right sides of (INV) and (MAJ) are identical, the two statistics inv and maj are equi-distributed, as was first noticed by MacMahon [Ma]. In 1968 a natural bijection that sends inv to maj was given ([Fo1], see also [Kn], ex. 5.1.1.19), that explained in a direct manner why inv and maj are equi-distributed. A permutation statistic that is equi-distributed with maj (or, equivalently, inv), is called Mahonian, and one that is equi-distributed with des is called Eulerian ([Fo2]). Furthermore, if a pair of statistics has the same joint distribution as (des, maj) that pair is called Euler-Mahonian. Many examples of equidistributed pairs are given in [Fo2].

In studying the genus zeta function, Denert ([De1], [De2]) introduced a new permutation statistic, that we will christen “den.” Her statistic, in a somewhat simpler form, reads :

\begin{aligned}den π & := #\{1 ≤ l < k ≤ n; π(k) < π(l) ≤ k\} \\ & + #\{1 ≤ l < k ≤ n; π(l) ≤ k < π(k)\} \\ & + #\{1 ≤ l < k ≤ n; k < π(k) < π(l)\}. \end{aligned}  (DEN)

The companion statistic to den in Denert’s conjecture is simple and well known. It is simply the number of excedences of a permutation, defined by

exc π := #{1 ≤ i ≤ n; π(i) > i}.  (EXC)

We are now ready to state the main result of this paper, that was conjectured by Denert ([De1], [De2]).

Theorem 1. — The pairs of permutation statistics (exc, den) and (des, maj) are equi-distributed. In other words, if B_{n}(t, q) are Carlitz’s q-Eulerian polynomials introduced above, then

∑_{π∈S_{n}} t^{exc π}q^{den π} = B_{n}(t, q).

The most natural proof of this result would be in terms of a bijection from S_{n} to itself that sends the pair (des, maj) simultaneously to the pair (exc, den). Although it is rather easy to find a bijection that sends maj to den (see next section), and it is now trivial (see, e.g., [Lo], chap. 10.2) to find a bijection that sends exc to des, we are unable, at present, to find a bijection that does both at the same time. Instead, we will have to make do with an indirect proof. We really hope that such a bijective proof of Denert’s conjecture will be found, and that it will take less than the fifty-five years that elapsed between MacMahon’s [Ma] first proof of (MAJ) and Foata’s [Fo1] bijective proof.

The organization of the paper is as follows. In section 2 we give a coding for Denert’s statistic that shows that the one-variable “den” is Mahonian.

In section 3 we work out a natural definition for the Denert statistic in terms of the positions of the excedences and the inversion tables for the so-called excedence and non-excedence subwords of the permutation (theorem 2). It is very conceivable that more and more mathematicians will rely on computer-based proofs, especially for proofs that require basic and lengthy verifications, as in theorem 2. In section 4 we then sketch another way of proving theorem 2 that is based on the calculus of the partial derivatives for the permutation group.

The key object in our derivation is the weighted bracketing whose properties are developed in section 5. A weighted bracketing can be viewed as a lattice path in the N × N-quadrant that goes from the origin to a certain point and whose elementary steps are weighted. For each pair of integers (a, b) such that a ≥ b there is a set U_{n,a,b} of such weighted bracketings and the generating function D(n, a, b) for U_{n,a,b} according to a certain weight (“ind”) can be evaluated (theorem 3).

More interesting for our study is the fact that we can find another recurrence relation for D(n, a, b) that specializes to the (CARLITZ) recurrence formula for the q-Eulerian numbers when a = b = k (see Theorem 4). This then proves that D(n, k, k) = B_{n,k}(q).

To prove theorem 1 it remains to find a bijection of the set U_{n,k,k} onto the subset S_{n,k} of the permutations having k excedences that sends the ind-statistic of the weighted bracketing onto the den-statistic of the permutation. This is done in section 7 (theorem 5).

We end the paper by constructing another bijection of the set U_{n,a,b} into a set of objects called gravid permutations. Again, when a = b = k, the bijection sends the weighted bracketings onto the (ordinary) permutations having k descents. The Mahonian statistic “ind” is then sent over a new Mahonian statistic involving the values of the descents, that we have baptized mak (see section 8). As a companion to the Eulerian statistic des, we now have two Mahonian statistics, maj and mak. The former one depends on the positions of the descents, the latter one on its values.

The paper ends with a table of the polynomials D(n, a, b) for n ≤ 6 and with a description of all the bijections used in the paper for the permutation group S_{4}.

2. A coding for Denert’s statistic that proves that it is Mahonian

Like the clasical “inversion table” (e.g., Knuth [Kn], p. 21), it is possible to use the definition (DEN) to introduce the Denert table b_{k}, where for k = 1, …, n the integer b_{k} is the contribution that came to den from the k-th entry π(k) :

b_{k}(π) := \{ \begin{matrix}#\{l < k; π(k) < π(l) ≤ k \}, & if π(k) ≤ k; \\ #\{l < k; π(l) ≤ k \} + #\{l < k; π(k) < π(l) \}, & if π(k) > k. \end{matrix}

Of course, den π is the sum of the b_{k}(π)’s.

For instance, for the following permutation we have :

π = ( \begin{matrix}1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 \\ 7 & 1 & 5 & 4 & 9 & 2 & 6 & 3 & 8 \end{matrix} )
Denert table = 0 0 2 0 3 2 1 4 1

In particular, den π = 13. It is obvious that b_{k} ≤ k − 1, and it is easy to see that the mapping π ↦ (b_{k}(π)) is injective, and thus a bijection.

To recover π from its Denert table (b_{k}), first let π(n) = n−b_{n}. Suppose that π(k + 1), …, π(n) have been determined from the sequence b_{k+1}, …, b_{n}. Then write the sequence

k, (k − 1), …, 2, 1, n, (n − 1), …, (k + 1),

and delete all the elements in this list that are equal to π(l) for some l ≥ k + 1. Then π(k) is the (b_{k} + 1)-st term in the resulting list when scanned from left to right.

It follows that the Denert statistic is Mahonian :

∑_{π∈S_{n}} q^{den π} = [1]_{q} [2]_{q} … [n]_{q}.

The bijection of [Fo1] implies a natural mapping between permutations π and sequences a_{k} such that 0 ≤ a_{k} ≤ k − 1 such that maj goes to the sum of the sequence : maj π = a_{1} + ⋯ + a_{n}. Composing with the present correspondence we get a natural mapping from S_{n} to itself that sends maj to den.

3. A less unwieldy definition for Denert’s statistic

We will now give an alternative definition of den in terms of a more familiar objects. Let π = π(1)π(2) … π(n) be a permutation of order n. If 1 ≤ i ≤ n−1 and π(i) > i, say that i is an excedence-place for π, and π(i) is an excedence-letter for π [to paraphrase the celebrated letter-place algebras dear to our bon Maître Gian-Carlo Rota [DRS]]. Let i_{1} < i_{2} < ⋯ < i_{k} be the increasing sequence of the excedence places and j_{1} < j_{2} < ⋯ < j_{n−k} the increasing sequence of non-excedence places.

The subwords Exc σ = σ(i_{1}) … σ(i_{k}) and Nexc σ = σ(j_{1}) … σ(j_{n−k}) are referred to as the excedence-letter and non-excedence-letter subwords.

A permutation σ is said to be bi-increasing if both subwords Exc σ and Nexc σ are increasing. For instance

σ = ( \begin{matrix}1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 \\ 4 & 1 & 5 & 2 & 6 & 9 & 3 & 7 & 8 \end{matrix} )

is bi-increasing, since Exc σ = 4, 5, 6, 9 and Nexc σ = 1, 2, 3, 7, 8 are both increasing.

Theorem 2. — Let σ = σ(1)σ(2) … σ(n) be a permutation. Let i_{1}, …, i_{k} be its excedence-place sequence. Then

den σ = i_{1} + i_{2} + ⋯ + i_{k} + inv Exc σ + inv Nexc σ.

For instance, for the permutation π shown in section 2 we have i_{1} = 1, i_{2} = 3, i_{3} = 5, Exc π = 7, 5, 9, Nexc π = 1, 4, 2, 6, 3, 8, inv Exc π = 1, inv Nexc π = 3, and then den π = 1 + 3 + 5 + 1 + 3 = 13.

Proof. — First we prove the theorem for bi-increasing permutations. In such a case inv Exc σ = inv Nexc σ = 0 and we have to show that

den σ = i_{1} + i_{2} + ⋯ + i_{k}.

For n = 1 there is nothing to prove. Suppose n ≥ 2 and let σ = σ(1)σ(2) … σ(n) be a bi-increasing permutation whose excedence-place sequence is i_{1} < i_{2} < ⋯ < i_{k}. Again we can assume that σ(i_{k}) = n, for otherwise we would have σ(n) = n and the result would follow by induction.

Denote by (b_{1}(σ), b_{2}(σ), …, b_{n}(σ)) the Denert table of σ. In particular b_{i_{k}}(σ) is equal to the number of occurrences of the letters ≤ i_{k} in the left factor σ(1)σ(2) … σ(i_{k−1}). For j = i_{k} + 1, i_{k} + 2, …, n, let ϵ_{j} be equal 1 or 0, according as j does or does not occur in σ(1)σ(2) … σ(i_{k−1}). We then have

b_{i_{k}}(σ) = i_{k} − 1 − (ϵ_{i_{k}+1} + ϵ_{i_{k}+2} + ⋯ + ϵ_{n}).

Note that ϵ_{n} = 0. Define a permutation σ′ in S_{n−1} by

σ′(j) = \{ \begin{matrix}σ(j), & if j < i_{k}; \\ σ(j + 1), & if i_{k} ≤ j ≤ n − 1. \end{matrix}

Note that i_{k} + 1, …, n − 1, n are non-excedence places for σ, so that

σ(i_{k} + 1) < σ(i_{k} + 2) < ⋯ < σ(n − 1) < σ(n) < n,

and thus σ(i_{k} + 1) ≤ i_{k}, σ(i_{k} + 2) ≤ i_{k} + 1, …, σ(n − 1) ≤ n − 2, σ(n) ≤ n − 1.

Thus σ′ is also a bi-increasing permutation whose excedence-place sequence is i_{1}, i_{2}, …, i_{k−1}. Now b_{1}(σ) = b_{1}(σ′), …, b_{i_{k−1}}(σ) = b_{i_{k−1}}(σ′). Let j = i_{k}, i_{k} + 1, …, n − 2. The component b_{j}(σ′) is equal to the number of l such that 1 ≤ l ≤ j − 1 and σ′(j) < σ′(l) ≤ j. But if i_{k} ≤ l ≤ j − 1, we have σ′(l) < σ′(j), since the word σ(i_{k} + 1)σ(i_{k} + 2) … σ(n) = σ′(i_{k})σ′(i_{k} + 1) … σ′(n − 1) is increasing. Hence b_{j}(σ′) is equal to the number of l such 1 ≤ l ≤ i_{k} − 1 and σ′(j) < σ′(l) ≤ j, i.e., 1 ≤ l ≤ i_{k} − 1 and σ(j + 1) < σ(l) ≤ j. Hence, for each j = i_{k}, i_{k−1}, …, n − 2 we have

b_{j}(σ′) = b_{j+1}(σ) − ϵ_{j+1}.

Finally, b_{n−1}(σ′) = n − 1 − σ′(n − 1) = n − 1 − σ(n) = (n − σ(n)) − 1 = b_{n}(σ) − 1. Altogether,

den σ = b_{1}(σ) + b_{2}(σ) + ⋯ + b_{n}(σ)
= b_{1}(σ′) + ⋯ + b_{i_{k}−1}(σ′)
+ i_{k} − 1 − ϵ_{i_{k}+1} − ϵ_{i_{k}+2} − ⋯ − ϵ_{n−1}
+ (b_{i_{k}}(σ′) + ϵ_{i_{k}+1}) + (b_{i_{k}+1}(σ′) + ϵ_{i_{k}+2}) + ⋯
+ (b_{n−2}(σ′) + ϵ_{n−1}) + b_{n−1}(σ′) + 1.

This is equal to

b_{1}(σ′) + ⋯ + b_{n−1}(σ′) + i_{k},

which by induction equals

i_{1} + ⋯ + i_{k−1} + i_{k}.

This completes the proof for bi-increasing permutations.

To prove the general case let inv Exc σ = a, inv Nexc σ = b. We prove it by induction on c(σ) := a + b. Keep the same notation as above. In particular, let Exc σ = σ(i_{1})σ(i_{2}) … σ(i_{k}) and Nexc σ = σ(j_{1}) … σ(j_{n−k}). If Exc σ is not increasing, let m be the smallest integer satisfying 1 ≤ m ≤ k − 1 and σ(i_{m}) > σ(i_{m+1}). Define a new permutation τ by letting τ(k) = σ(k) for all k except k = i_{m}, i_{m+1}, and τ(i_{m}) = σ(i_{m+1}), and τ(i_{m+1}) = σ(i_{m}). By definition of Exc σ we have i_{m} < i_{m+1}, σ(i_{m}) > σ(i_{m+1}), and i_{m} < σ(i_{m}), i_{m+1} ≥ σ(i_{m+1}), …, i_{m+1} − 1 ≥ σ(i_{m+1} − 1), i_{m+1} < σ(i_{m+1}). Hence i_{m} < i_{m+1} < σ(i_{m+1}) = τ(i_{m}) and i_{m+1} < σ(i_{m+1}) < σ(i_{m}) = τ(i_{m+1}). Thus i_{1}i_{2} … i_{k} is also the excedence place sequence for τ. Furthermore Exc τ = σ(i_{1}) … σ(i_{m+1})σ(i_{m}) … σ(i_{k}), Nexc τ = σ(j_{1})σ(j_{2}) … σ(j_{n−k}) = Nexc σ, and inv τ = inv Exc σ−1. Hence c(τ) = c(σ) − 1.

On the other hand, b_{k}(τ) = b_{k}(σ) for every k ≠ i_{m}, i_{m+1}. But b_{i_{m}}(τ) = b_{i_{m}}(σ), and b_{i_{m+1}}(τ) = b_{i_{m+1}}(σ) − 1. Hence,

den σ = b_{1}(σ) + ⋯ + b_{n}(σ)
= b_{1}(τ) + ⋯ + b_{n}(τ) + 1

= (i_{1} + ⋯ + i_{k}) + inv Exc τ + inv Nexc τ + 1 [by induction]

= (i_{1} + ⋯ + i_{k}) + inv Exc σ + inv Nexc σ.

Now suppose that Exc σ is increasing and let m be the smallest integer satisfying σ(j_{m}) > σ(j_{m+1}). Again define the permutation τ to be σ with σ(j_{m}) and σ(j_{m+1}) trading places. Once again j_{m} < j_{m+1}, j_{m} ≥ σ(j_{m}), j_{m+1} ≥ σ(j_{m+1}). Hence j_{m} ≥ σ(j_{m}) > σ(j_{m+1}) = τ(j_{m}), and j_{m+1} > j_{m} ≥ σ(j_{m}) = τ(j_{m+1}). This shows that Exc τ = Exc σ. In particular the excedence place sequence i_{1} … i_{k} is the same for both permutations. Also

Nexc τ = σ(j_{1})σ(j_{m+1})σ(j_{m}) … σ(j_{n−k})

and thus inv Nexc τ = inv Nexc σ − 1.

Now let’s compare the Denert tables of τ and σ. First b_{r}(τ) = b_{r}(σ) for r = 1, …, j_{m} − 1 and r = j_{m+1} + 1, …, n. By definition of j_{m} we have σ(j_{1}) < σ(j_{2}) < ⋯ < σ(j_{m}) ≤ j_{m}. Hence b_{j_{m}}(σ) = 0. Also b_{j_{m+1}}(σ) is equal to the number of l such that 1 ≤ l ≤ j_{m+1} − 1 and σ(j_{m+1}) < σ(l) ≤ j_{m+1}, i.e., such that 1 ≤ l ≤ j_{m} and σ(j_{m+1}) < σ(l) ≤ j_{m}. As σ(j_{m+1}) < σ(j_{m}), that number is one plus the number of l such that 1 ≤ l ≤ j_{m} − 1 and σ(j_{m+1}) < σ(l) ≤ j_{m}. Hence b_{j_{m+1}}(σ) = b_{j_{m}}(τ) + 1. Now b_{j_{m}+1}(τ) = 0 since σ(j_{1}) < σ(j_{2}) < ⋯ < σ(j_{m+1}) < σ(j_{m}).

If i_{h} is an excedence place between j_{m} and j_{m+1}, the number of l such that 1 ≤ l ≤ i_{h} − 1 and 1 ≤ σ(l) ≤ i_{h} is equal to the number of l such that 1 ≤ l ≤ j_{m} and 1 ≤ σ(l) ≤ j_{m}, i.e., m. The number of l such that 1 ≤ l ≤ j_{m} and 1 ≤ τ(l) ≤ j_{m} is also m. Hence b_{h}(τ) = b_{h}(σ) for j_{n} < h < j_{m+1}.

Altogether den σ = den τ + 1, to be compared with c(σ) = c(τ) + 1. We conclude, as above, that the identity of the theorem also holds for σ.

4. A “short” proof of Theorem 2

We will now give an alternative proof of theorem 2 that in some sense is longer (and less elegant) than the preceding proof, but in another sense is shorter (and more elegant!). Up to purely routine calculations (that can be easily programmed and done by computer) the new proof is shorter. On the other hand, readers who refuse to use computers can still easily follow the new proof and fill in all the details by hand, but then the resulting proof is messier, longer, and “uglier.” In fact the new proof is in a sense a condensation of the previous proof, but since we are no longer afraid of messy (but routine) calculations, we are not obligated to be “clever.”

Often in analysis it is required to prove that two functions F (z) and G(z) are identical, but it is hard, or impossible, to do it directly. Then one tries to prove that their derivatives are equal: F′(z) = G′(z), form which follows, of course that F and G differ by a constant, which is easily evaluated by plugging in an easy value. This is, for example, the way the Weierstrass elliptic function is proved to be doubly periodic ([Rai], p. 309). We will use a permutation group analog of this method. But first we must define the notion of partial derivatives on permutation statistics.

Given any permutation statistic f(π), define ∂_{a}f(π) := f((a, a+1)π)− f(π). Here (a, a + 1) is the transposition that exchanges a and (a + 1). In other words ∂_{a}f(π) measures the difference in f(π) resulting from swapping π(a) and π(a + 1) in π. For example, ∂_{a} inv(π) = 2χ(π(a) > π(a + 1)) − 1, and consequently div inv(π) = 2 des(π) − (n − 1), where “div” is the sum of all the partial derivatives ∂_{a}, a = 1, …, n − 1.

Let us denote the right side of the identity of theorem 2 by denbis. It is easy to see that denbis may be defined as follows

denbis π = #{1 ≤ l < k ≤ n; k < π(k) < π(l)}
+ #{1 ≤ l < k ≤ n; π(k) < π(l) ≤ l}
+ #{1 ≤ l ≤ k ≤ n; k < π(k)}.

We have to prove that den(π) = denbis(π), for every permutation π. Since the definitions of den and denbis are so close, it seems at first sight that it would be trivial to prove that they are identical, using elementary (and routine) Boolean algebra. However, we see immediately that the difference g(π) := den(π) − denbis(π) does not disappear by simply manipulating sets. However some cancellation occurs and leads to

g(π) := #{1 ≤ l < k ≤ n; π(k) < π(l) ≤ k}
+ #{1 ≤ l < k ≤ n; π(l) ≤ k < π(k)}
− #{1 ≤ l < k ≤ n; π(k) < π(l) ≤ k}
− #{1 ≤ l ≤ k ≤ n; k < π(k)}.

Looking at the “fundamental events” and expressing the above as a linear combination of cardinalities of certain intersections of these fundamental sets, does not give 0. In other words, the fact that den ≡ denbis is not a tautology, and depends on complex dependence between these sets. It would be futile to try and study these complex dependencies, since they differ from permutation to permutation.

However the partial derivatives ∂_{a}g all vanish identically! It is a completely routine matter to find an expression for ∂_{a}g(π). When we express it in terms of sums of cardinalities of intersections of “elementary events,” all these elementary events turn out to be independent. It follows that if ∂_{a}g(π) is indeed 0 it must necessarily be so for a tautologous reason.

A long and tedious calculation (that, however takes a few seconds on a computer) then shows that indeed ∂_{a}g ≡ 0, for a = 1, …, n − 1. It follows that g(π) = g((a, a + 1)π), and since the transpositions (a, a + 1) generate the permutation group, it follows that g is identically constant. The “convenient” point is, of course, the identity permutation, for which g vanishes, and so the constant is 0. It follows that g is identically zero, and thus that den ≡ denbis, proving theorem 2.

5. Weighted bracketings

Those bracketings will serve in section 7 to code permutations. First consider the four-letter alphabet A = {[⟨, [ ], ⟩], ⟩⟨}, whose letters will be designated by “kappa,” “Oh,” “reverse kappa” and “Khi,” respectively. Of course, those four letters are simply made of left and right angle parentheses and left and right brackets. We have preferred to keep this typographical design, rather than adopt the usual font designs for kappa, O and chi for reasons that will appear to be clear in section 7.

If w = x_{1}x_{2} … x_{n} is a word whose letters are taken from A and if y is one of the letters [⟨, [ ], ⟩], ⟩⟨, we denote, as usual, by |x_{1}x_{2} … x_{n}|_{y} the number of occurrences of y in the word w = x_{1}x_{2} … x_{n}.

A word w = x_{1}x_{2} … x_{n} is said to be legal, if the following two properties hold :

(i) |x_{1}x_{2} … x_{r}|[⟨ − |x_{1}x_{2} … x_{r}|⟩] ≥ 0 for each r = 1, 2, …, n;

(ii) whenever |x_{1}x_{2} … x_{r}|[⟨−|x_{1}x_{2} … x_{r}|⟩] = 0 and r < n, then x_{r+1} = [⟨ or [ ]. (In particular, x_{1} = [⟨ or [ ].)

When a ≥ b, the set of all legal words w of length n such that

(5.1)  |w|⟩⟨ + |w|[⟨ = a;  |w|⟩⟨ + |w|⟩] = b;

will be denoted by W_{n,a,b}.

Each letter x_{r} of a word w = x_{1}x_{2} … x_{n} belonging to W_{n,a,b} is given the following maximum weight ν_{r} defined by

(5.2)  ν_{r} = \{ \begin{matrix}|x_{1} … x_{r−1}|[⟨ − |x_{1} … x_{r−1}|⟩] , & if x_{r} = [⟨ or [ ]; \\ |x_{1} … x_{r−1}|[⟨ − |x_{1} … x_{r−1}|⟩] − 1, & if x_{r} = ⟩⟨ or ⟩]. \end{matrix}

Finally, for each triple (n, a, b) we introduce the set U_{n,a,b} of all pairs u = (w, t), where w = x_{1}x_{2} … x_{n} belongs to W_{n,a,b} and t = t_{1}t_{2} … t_{n} is a sequence of integers satisfying the inequalities :

(5.3)  0 ≤ t_{r} ≤ ν_{r},  for each r = 1, 2, …, n.

The elements of U_{n,a,b} will be referred to as weighted bracketings.

A weighted bracketing can also be viewed as a weighted path defined as follows. In the N × N-quadrant consider the lattice paths going from (0, 0) to (n, a − b) whose basic steps are one of the four kinds :

(i) North-East steps (NE) joining vertices (i, j) and (i + 1, j + 1) :

(ii) blue horizontal steps (blue) joining vertices (i, j) and (i + 1, j); (iii) red horizontal steps (red) joining vertices (i, j) and (i + 1, j); (iv) South-East steps (SE) joining vertices (i, j) and (i + 1, j − 1).

Notice that there are two kinds of horizontal steps. With the correspondence NE ↔ [⟨, blue ↔ [ ], red ↔ ⟩⟨, SE ↔ ⟩], we see that each element w in W_{n,a,b} corresponds to a lattice path going from (0, 0) to (n, a − b). The fact that w is legal insures the fact that the lattice path always remains in the N × N-quadrant.

For instance the word

w = [⟨, [ ], [⟨, [ ], ⟩⟨, [ ], ⟩], [ ], ⟩]

that belongs to W_{9,3,3} corresponds to the lattice path drawn in Fig. 1, where the red step has been represented by a dotted line.

It is readily seen from (5.2) and the forementioned correspondence between bracketings and lattice paths that the maximum weight ν_{r} can also be defined in terms of lattice paths as follows. Let s_{r} be the basic step whose origin is the point (r − 1, j). Then

(5.4)  ν_{r} = \{ \begin{matrix}j, & if s_{r} is NE or blue; \\ j − 1, & if s_{r} is red or SE. \end{matrix}

A pair u = (w, t), where w is such a lattice path and t = t_{1} …, t_{n} is a word satisfying (5.3) is called a weighted path.

\begin{aligned}r & = & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 \\ ν_{r} & = & 0 & 1 & 1 & 2 & 1 & 2 & 1 & 1 & 0 \end{aligned} Fig. 1

Such weighted paths have been considered by Viennot [Vi] in his combinatorial study of the general orthogonal polynomial. Viennot [Vi] constructed a 1-1 correspondence between the set ⋃_{a} U_{n,a,a} of weighted paths and S_{n}. In section 7 we will give a completely different 1-1 correspondence that will serve to prove Denert’s conjecture. Another correspondence between weighted paths and permutations will lead in section 8 to the discovery of another Euler-Mahonian statistic (des, mak).

Now let u = (w, t) be a weighted bracketing belonging to U_{n,a,b}. Furthermore, let w = x_{1}x_{2} … x_{n}, t = t_{1}t_{2} … t_{n} and ν_{r} be defined as in (5.2). Finally, let i_{1}, i_{2}, …, i_{k} be the places where the letters [⟨ and ⟩⟨ occur in w. In other words, let x_{i_{1}}, x_{i_{2}}, …, x_{i_{k}} be the letters in w that are equal either to [⟨ or ⟩⟨. The index ind u of u = (w, t) is defined by :

(5.5)  ind u = i_{1} + i_{2} + ⋯ + i_{k} + t_{1} + t_{2} + ⋯ + t_{n}.

For convenience, we will write

poids u = q^{ind u}.

Furthermore, we will denote by D(n, a, b) the generating function

D(n, a, b) = ∑_{u} poids u (u ∈ U_{n,a,b}).

To compute D(n, a, b) we first evaluate the total contribution to ∑ poids u (u ∈ U_{n,a,b}) arising from all the weighted bracketings u = (w, t) having the same first component w. This contribution is clearly :

(5.6)  poids w = q^{i_{1}+i_{2}+···+i_{k}}[ν_{1} + 1]_{q} [ν_{2} + 1]_{q} … [ν_{n} + 1]_{q},

in virtue of (5.3).

Theorem 3. — The generating function D(n, a, b) satisfies the following recurrence for n, a, b ≥ 0, except for n = a = b = 0 :

(5.7) D(n, a, b) = [a − b + 1]_{q} D(n − 1, a, b) + q^{n}[a − b]_{q} D(n − 1, a − 1, b) + [a − b + 1]_{q} D(n − 1, a, b − 1) + q^{n}[a − b]_{q} D(n − 1, a − 1, b − 1).

Note that the recurrence is true for all n, a, b ≥ 0 (except n = a = b = 0) if one defines

(5.8)  D(n, a, b) ≡ 0  for a − b < 0.

It can be used to compute D(n, a, b) uniquely in n, a, b ≥ 0 subject to the boundary conditions

(5.9)  D(n, a, b) = 0 on {n = −1} ∪ {a = −1} ∪ {b = −1};
D(0, 0, 0) = 1.

Proof. — Consider a weighted bracketing u = (w, t) in U_{n,a,b} and write w = x_{1}x_{2} … x_{n}. From (5.1) and (5.2) it follows that ν_{n} = |w|[⟨ − |x_{n}|[⟨ − |w|⟩] − |x_{n}|⟩] if x_{n} = [⟨ or [ ], i.e.,

ν_{n} = \{ \begin{matrix}a − b − 1, & if x_{n} = [⟨; \\ a − b, & if x_{n} = [ ]. \end{matrix}

In the same manner, ν_{n} = |w|[⟨ − |x_{n}|[⟨ − |w|⟩] − |x_{n}|⟩] − 1, if x_{n} = ⟩⟨ or ⟩], i.e.,

ν_{n} = \{ \begin{matrix}a − b − 1, & if x_{n} = ⟩⟨; \\ a − b, & if x_{n} = ⟩]. \end{matrix}

Write w′ = x_{1}x_{2} … x_{n−1}, so that w = w′x_{n}. Thus depending on the value of x_{n} we have in view of (5.6) :

if x_{n} = [ ], then w′ ∈ U_{n−1,a,b} and poids w = poids w′.[a − b + 1]_{q}; if x_{n} = [⟨, then w′ ∈ U_{n−1,a−1,b} and poids w = poids w′.q^{n}[a − b]_{q}; if x_{n} = ⟩], then w′ ∈ U_{n−1,a,b−1} and poids w = poids w′.[a − b]_{q}; if x_{n} = ⟩⟨, then w′ ∈ U_{n−1,a−1,b−1} and poids w = poids w′.q^{n}[a − b]_{q}. Summing D(n, a, b) = ∑ poids(w′x_{n}) according to the value of x_{n}

yields the desired recurrence relation.

6. Another recurrence for the weighted bracketings

Our goal is to establish that D(n, k, k) satisfies the (CARLITZ) recurrence. A natural way is to find a recurrence for D(n, a, b) that will reduce to (CARLITZ) on the diagonal a = b = k. Unfortunately this is not true for the recurrence of theorem 3. However the very fact that D(n, a, b) satisfies some linear partial recurrence equation with polynomial coefficients (in q^{n}, q^{a}, q^{b}, q) is good news.

Most discrete functions F (n, a, b) are not solutions of any linear partial recurrence equation with polynomial coefficients. However, those that are solutions of such equations, are annihilated by a whole ideal of operators in the algebra of linear operators with polynomial coefficients, i.e., are solutions of an infinite number of such equations ([Ze2], see also [Staf]). All we have to do is to find the one that suits us. A natural step therefore is to conjecture a partial linear recurrence that will reduce to (CARLITZ) upon plugging a = b = k. Since D(n − 1, k − 1, k) is zero, a reasonable form would be:

\begin{aligned}D(n, a, b) & = c_{1}(q^{n}, q^{a}, q^{b}, q)D(n − 1, a, b) \\ & + c_{2}(q^{n}, q^{a}, q^{b}, q)D(n − 1, a − 1, b − 1) \\ & + c_{3}(q^{n}, q^{a}, q^{b}, q)D(n − 1, a − 1, b), \end{aligned}  (TRY)

where c_{1}, c_{2} should reduce to [k + 1] and q^{k}[n − k] respectively when a = b = k. By compiling a short table of D(n, a, b) and trying the generic form of linear polynomials c_{1}, c_{2}, c_{3} as above, we easily obtained empirically that D(n, a, b) satisfies the recurrence of theorem 4 below, for small values of n, a, b. All that remains to do is to prove it rigorously for all values of n, a, b.

Theorem 4. — The polynomials D(n, a, b) also satisfy the following recurrence, for n, a, b ≥ 1 :

D(n, a, b) = [a + 1]_{q} D(n − 1, a, b) + q^{a}[n − b]_{q} D(n − 1, a − 1, b − 1) + q^{n}[a − b]_{q} D(n − 1, a − 1, b).

Proof. — It is convenient to introduce operator notation. We refer the reader to [Ze] for the general methodology of linear partial recurrence operators and its rôle in combinatorics. For any discrete function F (n, a, b) let

N^{−1}F (n, a, b) := F (n − 1, a, b) ; A^{−1}F (n, a, b) := F (n, a − 1, b) ; B^{−1}F (n, a, b) := F (n, a, b − 1).

Let P and R be the following linear partial recurrence operators :

P := I − [a − b + 1]_{q} N^{−1}(I + B^{−1}) − q^{n}[a − b]_{q} N^{−1}A^{−1}(I + B^{−1}) ; R := I − [a + 1]_{q} N^{−1} − q^{a}[n − b]_{q} N^{−1}A^{−1}B^{−1} − q^{n}[a − b]_{q} N^{−1}A^{−1}.

In operator notation, theorems 3 and 4 can be paraphrased as :

Theorem 3′. — We have the identity :

P(D(n, a, b)) ≡ δ_{n,0}δ_{a,0}δ_{b,0}.

Theorem 4′. — We have the identity :

R(D(n, a, b)) ≡ 0 in {n, a, b ≥ 1}.

We know that D(n, a, b) is annihilated by a certain operator P in the region {n, a, b ≥ 1} and we want to prove that it is also annihilated by the operator R. A general algorithm goes as follows.

Find the “simplest” operator in the ideal generated by {P, R}, i.e., find operators A and B such that Q := AP + BR is “as simple as possible.” In particular, if Q = 0 but A and B are not zero, than it is ideal (sic!). Then, if necessary, try to use the method recursively to prove that given that P annihilates D(n, a, b), then so does Q. Assuming that we were successful in proving that Q(D(n, a, b)) = 0, we have

B(R(D(n, a, b))) = −A(P(D(n, a, b))) = 0.

Then one proves that R(D(n, a, b)) = 0 on the boundary of the region of interest. This would imply that R(D(n, a, b)) ≡ 0 throughout the region for the following reason.

For any “reasonable” linear recurrence operator B and any “reasonable” region, F (n, a, b) = 0 on the boundary (appropriately defined) of the region and B(F (n, a, b)) = 0 in the interior of the region implies that F (n, a, b) ≡ 0 throughout the region.

One way to find such A and B is to take successive commutators of R and P. In our case we were lucky, the commutator of P and R is zero, i.e., P and R commute! (Note that this is a minor miracle, since the algebra of linear partial recurrence operators with variable coefficients is not commutative!) In other words, in the above discussion A = R, B = −P and Q = 0 works.

Proof of Theorem 4′ (and hence of Theorem 4). — A tedious, but completely mechanical, calculation shows that P and R commute. Now apply operator R to the identity of theorem 3′ :

R(P D(n, a, b)) = R δ_{n,0}δ_{a,0}δ_{b,0}.

It is easily seen that the right side is zero at {n ≥ 0, a ≥ 0, b ≥ 0} except for (n, a, b) = (0, 0, 0), (1, 0, 0), (1, 1, 0). Since R P = P R, we then have

(6.1)  P(R D(n, a, b)) ≡ 0 in {n ≥ 0, a ≥ 0, b ≥ 0} \ {n = 0, 1}.

On the other hand, RD(0, a, b) = RD(n, 0, b) = 0, except for n = a = b = 0 by (5.8) and (5.9). Moreover, when b = 0, we have RD(n, a, b) = PD(n, a, b) = δ_{n,0}δ_{a,0}δ_{b,0} by theorem 3′. Hence

(6.2) R D(n, a, b) = 0 on {n = 0} ∪ {a = 0} ∪ {b = 0} \ {(0, 0, 0)}. Now by (5.7)

(6.3)  D(1, a, b) = 0  for a + b ≥ 2.

Thus (6.2) and (6.3) imply that R D(n, a, b) is zero on the boundary of the region {n ≥ 1, a ≥ 0, b ≥ 0}. It follows by induction, using (6.1), that R D(n, a, b) ≡ 0 throughout the region {n, a, b ≥ 1}.

Putting a = b = k and using the fact that D(n − 1, k − 1, k) ≡ 0, we see that D(n, k, k) satisfies the same recurrence (CARLITZ) satisfied by the B_{n,k}. Since obviously D(0, 0, k) = δ_{0,k}, we have proved, as a corollary, the following result conjectured by Denert [De1] :

Corollary. — For any k, n ≥ 0 we have : D(n, k, k) = B_{n,k}(q).

7. Coding permutations by weighted bracketings

Every permutation π in S_{n} induces two partitions of {1, 2, 3, …, n } : F ∪ G and F′ ∪ G′, such that |F′| = |F |, |G′| = |G|, as well as two bijections f : F → F′ and g : G → G′, that satisfy i < f(i) for i in F and i ≥ g(i) for i in G. Namely, F is the excedence-place set {i_{1}, …, i_{k} }, while G is its complement. Moreover F′ = π(F) and G′ = π(G). Finally, f and g are the restrictions of π to F and G respectively. Thus there is a 1-1 correspondence between S_{n} and the set of pairs of bijections (f : F → F′, g : G → G′) as above. Furthermore, by theorem 2,

(7.1)  den π = inv f + inv g + sum of elements of F.

Let us fix the sets F and F′ and let us consider the set of bijections f : F → F′ that satisfy i < f(i) for every i in F. We will represent such a mapping in terms of a subscripted angle parenthesizing as follows.

Write all the integers {1, 2, 3, …, n} in a line. For each i in F put a left angle parenthesis “⟨”, also called a langle for short, to the right of i. Analogously, for each j in F′ put a right angle parenthesis, i.e., a rangle, “⟩” to the left of j. For example, if n = 9, F = {1, 3, 5 }, and F′ = {5, 7, 9 }, then the angle parenthesizing corresponding to the pair (F, F′) (observe that we have not introduced f yet) is :

1⟨ 2 3⟨ 4 ⟩5⟨ 6 ⟩7 8 ⟩9.

Note that there exists a bijection f : F → F′ such that i < f(i) for every i in F, iff the induced angle parenthesizing is legal. Now to represent such a bijection f, we indicate the fact f(i) = j by having the rangle that lies after i point to the langle that lies before j. For example, with f(1) = 7, f(3) = 5, f(6) = 9, we have

1⟨ 2 3⟨ 4 ⟩5⟨ 6 ⟩7 8 ⟩9.

The condition that i < f(i) translates to the requirement that every rangle should be matched with a certain langle to its left.

(7.2) Definition. — If a rangle belongs to the integer r, denote by ν_{r} the difference between the number of langles and the number of rangles that lie to the left of r. [Note that the rangle belonging to r is counted in the difference.]

As each rangle can be matched with a langle to its left, we have ν_{r} ≥ 0. If r is the i-th integer that possesses a rangle (when 1, 2, …, n is read from left to right), we label it r_{i}. In the previous example, r_{1} = 5, r_{2} = 7, r_{3} = 9, and ν_{5} = 1, ν_{7} = 1, ν_{9} = 0.

Next let us label all the langles to the left of the first rangle 0, 1, …, ν_{r_{1}} when reading them from left to right. If the arrow pointing to this first rangle comes from a langle labeled, say, t_{r_{1}}, give the first rangle the rank t_{r_{1}}. The langle labeled t_{r_{1}} will then be called committed. Next erase this first labeling and relabel 0, 1, …, ν_{r_{2}} the uncommitted langles to the left of the second rangle. If the arrow pointing to this second rangle comess from a langle labeled t_{r_{2}}, give the second rangle the rank t_{r_{2}}. Furthermore, declare the langle labeled t_{r_{2}} committed and erase this second labeling. Continue this procedure until the last rangle is reached and ranked. With the previous example, the letter c meaning “committed,” we have :

1⟨ 2 3⟨ 4 ⟩5⟨ 6 ⟩7 8 ⟩9
label 0 1
rank  1
label 0 c 1
rank  0
label c c 0
rank  0

So the final output for f is the following subscripted angle parenthesizing

(7.3)  1⟨ 2 3⟨ 4 ⟩_{1}5⟨ 6 ⟩_{0}7 8 ⟩_{0}9.

It is easy to see that the sequence of rangle ranks is nothing but the left to right inversion table of f. With the same example we have :

f = ( \begin{matrix}1 & 3 & 5 \\ 7 & 5 & 9 \end{matrix} )
inversion table = 0 1 0

We will now subject the bijection g : G → G′ to an analogous treatment. To distinguish it from the former case, we will use square brackets “[” and “]”, later referred to as lbracks and rbracks. Now each element of G′ receives an lbrack immediately before it, while each element of G receives an rbrack right after. With the above F and F′ we are forced to have G = {2, 4, 6, 7, 8, 9 } and G′ = {1, 2, 3, 4, 6, 8 }. The bracketing corresponding to this pair (G, G′) is then :

[1 [2] [3 [4] 5 [6] 7] [8] 9].

To represent g we make each point j = g(i) point to i. For example if g(2) = 1, g(4) = 4, g(6) = 2, g(7) = 6, g(8) = 3, g(9) = 8, we get :

[1 [2] [3 [4] 5 [6] 7] [8] 9].

(7.4) Definition. — If an lbrack belongs to the integer s, denote by ν_{s} the difference between the number of rbracks and the number of lbracks that lie to the right of [s of the bracketed word. [In this difference we include the lbrack and the rbrack (if any) belonging to s.]

When 1, 2, …, n is scanned from right to left, the integers that possess an lbrack are denoted by s_{1}, s_{2}, … In the previous example we have : s_{1} = 8, s_{2} = 6, s_{3} = 4, s_{4} = 3, s_{5} = 2, s_{6} = 1, and ν_{8} = 1, ν_{6} = 2, ν_{4} = 2, ν_{3} = 1, ν_{2} = 1, ν_{1} = 0.

The ranking on the lbracks is defined in the same way as the ranking on the langles with the major difference that the word 1, 2, …, n is now scanned from right to left. The rbracks to the right of the lbrack s_{1} belonging to s_{1} are labeled 0, 1, …, ν_{s_{1}} when reading them from right to left. If the arrow going out of that lbrack points to an rbrack labeled, say, t_{s_{1}}, give the lbrack belonging to s_{1} the rank t_{s_{1}}. The rbrack labeled t_{s_{1}} is now committed. Next erase this first labeling and relabel 0, 1, …, ν_{s_{2}} the uncommitted rbracks to the right of s_{2}. If the arrow going out of the lbrack belonging to s_{2} points to an rbrack labeled t_{s_{2}}, give the lbrack belonging to s_{2} the rank t_{s_{2}}. Furthermore, declare the rbrack labeled t_{s_{2}} committed and erase this second labeling. Continue this procedure until the last lbrack is reached and ranked. With the previous example

[1 [2] [3 [4] 5 [6] 7] [8] 9]
label  1 0
rank  0
label  2 1 0 c
rank  1
label 2 1 c 0 c
rank  2
label c 1 c 0 c
rank  0
label 1 c 0 c c c
rank  0
label 0 c c c c c
rank 0

The final output for g is the following subscripted bracketing

(7.5)  [_{0}1 [_{0}2] [_{0}3 [_{2}4] 5 [_{1}6] 7] [_{0}8] 9].

It is readily seen that the sequence of subscripts is nothing but the right to left inversion table of g.

With the same example we have :

g = ( \begin{matrix}2 & 4 & 6 & 7 & 8 & 9 \\ 1 & 4 & 2 & 6 & 3 & 8 \end{matrix} )
right to left inversion table = 0 2 0 1 0 0

Consider a typical permutation π in S_{n}. The excedence part, materialized by f, corresponds to a subscripted angle parenthesizing, where the subscripted are on the rangles. The non-excedence part, described by g corresponds to a subscripted bracketing, where the subscripts are on the lbracks. As each integer from 1 to n belongs to exactly one of the four subsets F ∩ F′, F ∩ G′, F′ ∩ G, G ∩ G′, it possesses exactly one of the four pairs :

(7.6)  ⟩⟨, [⟨, ⟩], [ ],

that we now consider as real letters as in section 5. However only the rangles and the lbracks are subscripted. Accordingly, each symbol listed in (7.6) is given one and only one subscript, when the angle parenthesizing and the bracketing are superimposed on the sequence 1, 2, …, n. If we write the subscripts as a separate word t = t_{1}t_{2} … t_{n}, we see that each permutation or order n corresponds to a pair u = (w, t), where w is a word w = x_{1}x_{2} … x_{n} in the four-letter alphabet (7.6) and t = t_{1}t_{2} … t_{n} is a sequence of positive integers satisfying 0 ≤ t_{r} ≤ ν_{r} for all r = 1, 2, …, n.

As both angle parenthesizing and bracketing are legal, the word w is also legal, as was defined in the beginning of section 5.

Now as F has k elements i_{1}, i_{2}, …, i_{k}, the word w has exactly k letters equal to [⟨ or ⟩⟨ and k letters equal to ⟩] or ⟩⟨. Hence, w belongs to W_{n,k,k}, as defined in (5.2).

After superimposition the rangles occur in the symbols ⟩] and ⟩⟨. If r possesses a rangle, the letter x_{r} is either ⟩] or ⟩⟨. Hence, definition (7.2) implies

\begin{aligned}ν_{r} & = |x_{1} … x_{r}|[⟨ + |x_{1} … x_{r}|⟩⟨ − |x_{1} … x_{r}|⟩] − |x_{1} … x_{r}|⟩⟨ − 1 \\ & = |x_{1} … x_{r−1}|[⟨ − |x_{1} … x_{r−1}|⟩] − 1, \end{aligned}

which agrees with the definition of ν_{r} given in (5.2).

In the same manner, if s possesses an lbrack, then x_{s} = [⟨ or ⟩⟨. Hence, by definition (7.4)

\begin{aligned}ν_{s} & = |x_{s} … x_{n}|⟩] + |x_{s} … x_{n}|⟩⟨ − |x_{s} … x_{n}|[⟨ − |x_{s} … x_{n}|⟩⟨ \\ & = |x_{1} … x_{s−1}|[⟨ − |x_{1} … x_{s−1}|⟩] , \end{aligned}

since |w|[⟨ = |w|⟩]. Again this agrees with (5.2). Hence

(7.7)  u = (w, t) ∈ U_{n,k,k}.

Furthermore, the elements of F are those that possess a langle. Accordingly,

(7.8)  F = {i; x_{i} = [⟨ or ⟩⟨ } = {i_{1}, i_{2}, …, i_{k} }.

Finally, let p be the juxtaposition product of the inversion table of f and the left to right inversion table of g. As the word t is a rearrangement of the word p, we have :

(7.9)  inv f + inv g = t_{1} + t_{2} + ⋯ + t_{n}.

It then follows from (7.1), (7.8) and (7.9) that

(7.10)  den π = i_{1} + i_{2} + ⋯ + i_{k} + t_{1} + t_{2} + ⋯ + t_{n},

i.e., den π = ind u, by (5.5). Clearly each step in the construction can be reversed. We have just proved the following theorem.

Theorem 5. — For each k = 0, 1, …, (n − 1) the above construction sets up a bijection π ↦ u between the set S_{n,k} of the permutations having k excedences and the set U_{n,k,k} of the weighted bracketings having exactly k letters equal to [⟨ or ⟩⟨ and k letters equal to ⟩] or ⟩⟨.

Furthermore, if u = (w, t) with w = x_{1}x_{2} … x_{n} and t = t_{1}t_{2} … t_{n}, then

(7.11)  den π = ind u,

and so

q^{den π} = poids u.

By theorem 5 we have

∑_{π} q^{den π} = ∑_{u} poids u  (π ∈ S_{n}, exc π = k; u ∈ U_{n,k,k})
= D(n, k, k) = B_{n,k}(q),

by the corollary of section 5. This then proves theorem 1.

Epilogue. — The construction of the bijection π ↦ u can be summarized and illustrated as follows :

(i) start with a permutation, e.g.,

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

(ii) determine the excedence place set F = {i_{1}, …, i_{k}} and the nonexcedence place set G = {j_{1}, …, j_{n−k}}; here F = {1, 3, 5 }, and G = {2, 4, 6, 7, 8, 9 }.

(iii) set up the bijections f : F → F′ and g : G → G′ and determine the inversion table p_{f(i_{1})} … p_{f(i_{k})} for f(i_{1}) … f(i_{k}) and the right to left inversion table p_{g(j_{1})} … p_{g(j_{n−k})} for g(j_{1}) … g(j_{n−k}). Here

\begin{aligned}f & = ( \begin{matrix}1 & 3 & 5 \\ 7 & 5 & 9 \end{matrix} ) \\ p_{f} & = 0 1 0 \end{aligned}  \begin{aligned}g & = ( \begin{matrix}2 & 4 & 6 & 7 & 8 & 9 \\ 1 & 4 & 2 & 6 & 3 & 8 \end{matrix} ) \\ p_{g} & = 0 2 0 1 0 0 \end{aligned}

(iv) form the words w = x_{1} … x_{n} and t = t_{1} … t_{n} as follows : if c ∈ F ∩ F′, let x_{c} = ⟩⟨, t_{c} = p_{c}; if c ∈ F′ ∩ G, let x_{c} = ⟩], t_{c} = p_{c}; if c ∈ F ∩ G′, let x_{c} = [⟨, t_{c} = p_{c}; if c ∈ G ∩ G′, let x_{c} = [ ], t_{c} = p_{c}.

Here

\begin{matrix}w = & [⟨ & [ ] & [⟨ & [ ] & ⟩⟨ & [ ] & ⟩] & [ ] & ⟩] \\ t = & 0 & 0 & 0 & 2 & 1 & 1 & 0 & 0 & 0 \end{matrix}

8. Another Mahonian mate for the number of descents

We have just seen that there is a natural bijection between weighted (complete) bracketings and permutations, and used the latter to prove Denert’s conjecture. However, in order to prove the conjecture, we had to colonize the more general set of incomplete bracketings, in which in general there are more left parentheses than right parentheses. Unfortunately, the bijection does not seem to extend, and it is not at all clear what are the permutation counterparts of incomplete bracketings. In this final section, we will introduce another bijection, for which incomplete bracketings correspond to so-called gravid permutations. This, in turn, will induce another Mahonian statistic, mak, on gravid permutations, and in particular, on regular permutations. By theorem 5, we then know right away that the pair (des, mak) is also Euler-Mahonian.

A gravid permutation of order n is a usual permutation of order n with one or more ∞ symbols inserted in the middle, such that there are never two consecutive infinities, and there is always an ∞ at the end. The class of regular permutations is in 1-1 correspondence with gravid permutations that only have a single infinity, that is necessarily at the end. For example σ = 6, 3, 1, ∞, 4, ∞, 2, 5, ∞ is a gravid permutation with n = 6 and 3 infinities.

Clearly a gravid permutation of order n has at most (n + 1) infinities and at most n descents. We denote by G_{n,l,k} the set of gravid permutations of order n with l infinities and k descents. Then G_{n,l,k} is empty, unless 1 ≤ l ≤ n + 1 and l − 1 ≤ k ≤ n.

Let σ = σ(1)σ(2) … σ(n + l) be a gravid permutation of order n with l infinities. Let 1 ≤ i ≤ n + l; if either i = 1 and σ(1) > σ(2), or 2 ≤ i ≤ n + l − 2 and σ(i − 1) < σ(i) > σ(i + 1), we say that i is a peak-place and σ(i) a peak-letter. In the same manner, if 2 ≤ i ≤ n + l − 1 and σ(i − 1) > σ(i) < σ(i + 1), we say that i is a trough-place and σ(i) a trough-letter. If 2 ≤ i ≤ n + l − 1 and σ(i − 1) > σ(i), we say that (i − 1) is a descent-place and σ(i) is a descent bottom value. The letter σ(i − 1) would be the the descent top value, but the notion will not be used here.

When read from left to right the gravid permutation σ has a succession of peak and trough places, say, pk_{1}, tr_{1}, pk_{2}, tr_{2}, . . .. If σ(f_{m}) is the m-th letter of σ that is not equal to ∞, we denote by t_{m} the number of pairs (σ(pk_{j}), σ(tr_{j})) to the left of σ(f_{m}) such that

(8.1)  σ(pk_{j}) > σ(f_{m}) > σ(tr_{j}).

Now if i_{1}, i_{2}, …, i_{k} are the descent bottom values of σ, the mak-statistic of σ is defined by :

(8.2)  mak σ := i_{1} + i_{2} + ⋯ + i_{k} + t_{1} + t_{2} + ⋯ + t_{n}.

This definition is to be compared with the definition of den recalled in (7.10).

For the following gravid permutation we have :

i = 1 2 3 4 5 6 7 8 9
σ(i) = 6 3 1 ∞ 4 ∞ 2 5 ∞
(i_{1}, …, i_{k}) = 3 1  4  2
(t_{1}, …, t_{n}) = 0 0 0  1  1 3

so that mak σ = 3 + 1 + 4 + 2 + 1 + 1 + 3 = 15.

As in the previous sections we denote by U_{n,a,b} the set of the weighted bracketings u = (w, t), where w has exactly a letters equal to [⟨ or ⟩⟨, and b letters equal to ⟩⟨ or ⟩], and where 0 ≤ t_{r} ≤ ν_{r} (1 ≤ r ≤ n).

We now define a bijection B between U_{n,a,b} and G_{n,b−a+1,b}, by recursion, as follows. The map B applied to the empty word is the gravid permutation ∞ of G_{0,1,0}. Let u = (w, t) be a typical pair in U_{n,a,b}. Let x_{n} be the last letter of w, and t_{n} the last component of t, and let w′ and t′ be the words obtained by chopping the last letters from w and t respectively : i.e., w = w′x_{n}, s = s′t_{n}. Let σ′ := B(w′, t′) be the gravid permutation assumed to be obtained by induction. We now define σ := B(w, t) in the following manner :

Case I : x_{n} = [⟨. Let σ be the permutation obtained from σ′ by inserting the two-letter word n∞ right after the (t_{n} + 1)-st infinity.

Case II : x_{n} = ⟩]. Let σ be the permutation obtained from σ′ by replacing the (t_{n} + 1)-st infinity by n.

Case III : x_{n} = [ ]. Let σ be the permutation obtained from σ′ by inserting n right before the (t_{n} + 1)-st infinity.

Case IV : x_{n} = ⟩⟨. Let σ be the permutation obtained from σ′ by inserting n right after the (t_{n} + 1)-st infinity.

Example. — The construction of B is illustrated as follows :

i = 1 2 3 4 5 6
w = [⟨ [⟨ ⟩⟨ [⟨ [ ] ⟩]
t = 0 1 0 1 3 0
∞
x_{1} = [⟨; t_{1} = 0 ;  ∞ 1 ∞
x_{2} = [⟨; t_{2} = 1 ;  ∞ 1 ∞ 2 ∞
x_{3} = ⟩⟨; t_{3} = 0 ;  ∞ 3 1 ∞ 2 ∞
x_{4} = [⟨; t_{4} = 1 ;  ∞ 3 1 ∞ 4 ∞ 2 ∞
x_{5} = [ ] ; t_{5} = 3 ;  ∞ 3 1 ∞ 4 ∞ 2 5 ∞
x_{6} = ⟩] ; t_{6} = 0 ;  6 3 1 ∞ 4 ∞ 2 5 ∞

Hence σ = 6, 3, 1, ∞, 4, ∞, 2, 5, ∞. Furthermore, u ∈ U_{6,4,2}, σ ∈ G_{6,4,3} and ind u = (1 + 2 + 3 + 4) + 1 + 1 + 3 = 15, that agrees with den σ calculated above.

Theorem 6. — The map B : u ↦ σ is a bijection of U_{n,a,b} onto G_{n,b−a+1,b} having the following property

(8.3)  ind u = mak σ.

Corollary. — The map B sends each set U_{n,a,a} of weighted complete bracketings onto the set G_{n,a} = G_{n,1,a} of the permutations of order n having a descents in such a way that (8.3) holds.

Proof. — It is easy to prove that this bijection is well defined, and that it is indeed a bijection, by writing down explicitly the inverse bijection B^{−1} and proving that it is also well defined. We do not give the details. However we should like to make some comments about the mak-statistic.

In the construction of B we see that x_{n} is a descent bottom value whenever x_{n} = [⟨ or ⟩⟨ (cases I and IV) and remains so for the further insertions. On the other hand, x_{n} has exactly t_{n} infinity symbols to its left, if and only if x_{n} has exactly t_{n} pairs (∞, trough-letters) to its left. All those trough-letters are less than x_{n} and if for the further insertions some ∞’s are replaced by integers (case II), the pairs (∞, trough-letters) will be replaced by, say, (σ(pk_{j}), σ(tr_{j})) that satisfy σ(pk_{j}) > x_{m} > σ(tr_{j}). Thus (8.1) holds.

Theorem 6 translates, via the bijection B, to the following theorem

Theorem 7. — The pair of permutation statistics (des, mak), on regular permutations, is Euler-Mahonian.

Tables

In the first table we give the list of the polynomials D(n, a, b) up to n = 6.

The second table illustrates, for n = 4, the construction of the first bijection π ↦ u (of section 7). We found it convenient to list the weighted paths instead of the weighted bracketings. Recall that we have the correspondence : NE ↔ [⟨, blue ↔ [ ], red ↔ ⟩⟨, SE ↔ ⟩].

The second bijection (section 8) u ↦ π′ is described in the fourth and fifth columns. The rightmost column simply contains the major index maj π′ of π′.

D. FOATA AND D. ZEILBERGER

Table of D(n, a, b) for 0 ≤ b ≤ a ≤ n = 6

\begin{matrix}n = 1 \\ b= & 0 \\ a=0 & 1 \\ 1 & q \end{matrix} \begin{aligned}& n = 2 \\ b= & 0 & 1 \\ a=0 & 1 \\ 1 & (2q+1)q & q \\ 2 & (q+1)q^{3} & q^{3} \end{aligned}  \begin{aligned}& n = 3 \\ b= & 0 & 1 & 2 \\ a=0 & 1 \\ 1 & (3q^{2}+3q+1)q & 2(q+1)q \\ 2 & (3q^{3}+5q^{2}+3q+1)q^{3} & (3q^{2}+5q+2)q^{3} & q^{3} \\ 3 & (q^{2}+q+1)(q+1)q^{6} & (q+2)(q+1)q^{6} & q^{6} \end{aligned}

n = 4

b= 0 1 2 3
a=0  1
1  (4q^{3}+6q^{2}+4q+1)q  (3q^{2}+5q+3)q
2 (6q^{5}+14q^{4}+15q^{3}+10q^{2}+4q+1)q^{3}  (6q^{4}+16q^{3}+19q^{2}+11q+3)q^{3}  (3q^{2}+5q+3)q^{3}
3 (4q^{6}+11q^{5}+16q^{4}+15q^{3}+9q^{2}+4q+1)q^{6} (4q^{5}+15q^{4}+25q^{3}+22q^{2}+11q+3)q^{6} (4q^{3}+9q^{2}+9q+3)q^{6} q^{6}
4 (q^{3}+q^{2}+q+1)(q^{2}+q+1)(q+1)q^{10}  (q^{2}+2q+3)(q^{2}+q+1)(q+1)q^{10} (q^{2}+3q+3)(q+1)q^{10} q^{10}

n = 5

b= 0 1
a=0 1
1 (5q^{4} + 10q^{3} + 10q^{2} + 5q + 1)q (4q^{3} + 9q^{2} + 9q + 4)q
2 (10q^{7} +30q^{6} +45q^{5} +44q^{4} +30q^{3} +15q^{2} +5q +1)q^{3} (10q^{6} + 35q^{5} + 60q^{4} + 64q^{3} + 44q^{2} + 19q + 4)q^{3}
3 {(10q^{9} + 35q^{8} + 66q^{7} + 85q^{6} + 80q^{5} + 59q^{4} + 34q^{3} + \atop 15q^{2} + 5q + 1)q^{6}} {(10q^{8} + 45q^{7} + 101q^{6} + 146q^{5} + 146q^{4} + 105q^{3} + \atop 54q^{2} + 19q + 4)q^{6}}
4 {(5q^{10} + 19q^{9} + 40q^{8} + 61q^{7} + 71q^{6} + 66q^{5} + 49q^{4} + \atop 29q^{3} + 14q^{2} + 5q + 1)q^{10}} {(5q^{9} +24q^{8} +64q^{7} +115q^{6} +146q^{5} +137q^{4} +96q^{3} + \atop 50q^{2} + 19q + 4)q^{10}}
5 {(q^{4} + q^{3} + q^{2} + q + 1)(q^{3} + q^{2} + q + 1)(q^{2} + q + \atop 1)(q + 1)q^{15}} (q^{3}+2q^{2}+3q+4)(q^{3}+q^{2}+q+1)(q^{2}+q+1)(q+1)q^{15}

n = 5

b= 2 3 4
a=2  2(3q^{4} + 8q^{3} + 11q^{2} + 8q + 3)q^{3}
3 (10q^{6} + 35q^{5} + 66q^{4} + 76q^{3} + 57q^{2} + 26q + 6)q^{6} (4q^{3} + 9q^{2} + 9q + 4)q^{6}
4 (5q^{7} + 24q^{6} + 59q^{5} + 89q^{4} + 90q^{3} + 61q^{2} + 26q + 6)q^{10} (5q^{4} + 14q^{3} + 19q^{2} + 14q + 4)q^{10} q^{10}
5  (q^{4} + 3q^{3} + 7q^{2} + 8q + 6)(q^{2} + q + 1)(q + 1)q^{15}  (q^{3} + 4q^{2} + 6q + 4)(q + 1)q^{15} q^{15}

DENERT’S PERMUTATION STATISTIC

n = 6

b= 0 1
a=0 1
1 (6q^{5} + 15q^{4} + 20q^{3} + 15q^{2} + 6q + 1)q (5q^{4} + 14q^{3} + 19q^{2} + 14q + 5)q
2 {(15q^{9} + 55q^{8} + 105q^{7} + 134q^{6} + 125q^{5} + 90q^{4} + \atop 50q^{3} + 21q^{2} + 6q + 1)q^{3}} {(15q^{8} + 64q^{7} + 139q^{6} + 198q^{5} + 203q^{4} + 153q^{3} + \atop 83q^{2} + 29q + 5)q^{3}}
3 {(20q^{12} + 85q^{11} + 196q^{10} + 315q^{9} + 385q^{8} + 379q^{7} + \atop 308q^{6} + 209q^{5} + 119q^{4} + 56q^{3} + 21q^{2} + 6q + 1)q^{6}} {(20q^{11} + 105q^{10} + 286q^{9} + 526q^{8} + 721q^{7} + 770q^{6} + \atop 653q^{5} + 442q^{4} + 237q^{3} + 98q^{2} + 29q + 5)q^{6}}
4 (15q^{14} +69q^{13} +175q^{12} +321q^{11} +462q^{10} +547q^{9} + ; 545q^{8} + 464q^{7} + 342q^{6} + 218q^{5} + 119q^{4} + 55q^{3} + ; 21q^{2} + 6q + 1)q^{10} (15q^{13}+84q^{12}+259q^{11}+560q^{10}+922q^{9}+1204q^{8}+ ; 1279q^{7} + 1122q^{6} + 819q^{5} + 497q^{4} + 247q^{3} + 98q^{2} + ; 29q + 5)q^{10}
5 (6q^{15} +29q^{14} +78q^{13} +154q^{12} +245q^{11} +328q^{10} + ; 377q^{9} + 377q^{8} + 330q^{7} + 253q^{6} + 169q^{5} + 98q^{4} + ; 49q^{3} + 20q^{2} + 6q + 1)q^{15} (6q^{14} +35q^{13} +113q^{12} +267q^{11} +497q^{10} +750q^{9} + ; 938q^{8} + 985q^{7} + 874q^{6} + 656q^{5} + 414q^{4} + 218q^{3} + ; 93q^{2} + 29q + 5)q^{15}
6 {(q^{5} +q^{4} +q^{3} +q^{2} +q +1)(q^{4} +q^{3} +q^{2} +q +1)(q^{3} + \atop q^{2} + q + 1)(q^{2} + q + 1)(q + 1)q^{21}} {(q^{4} + 2q^{3} + 3q^{2} + 4q + 5)(q^{4} + q^{3} + q^{2} + q + 1)(q^{3} + \atop q^{2} + q + 1)(q^{2} + q + 1)(q + 1)q^{21}}

n = 6

b= 2 3
a=2 (10q^{6} + 35q^{5} + 66q^{4} + 80q^{3} + 66q^{2} + 35q + 10)q^{3}
3 {(20q^{9} + 90q^{8} + 222q^{7} + 372q^{6} + 459q^{5} + 428q^{4} + \atop 302q^{3} + 156q^{2} + 55q + 10)q^{6}} (10q^{6} + 35q^{5} + 66q^{4} + 80q^{3} + 66q^{2} + 35q + 10)q^{6}
4 {(15q^{11} + 84q^{10} + 254q^{9} + 524q^{8} + 806q^{7} + 963q^{6} + \atop 909q^{5} + 679q^{4} + 397q^{3} + 176q^{2} + 55q + 10)q^{10}} {(15q^{8} + 64q^{7} + 149q^{6} + 233q^{5} + 264q^{4} + 219q^{3} + \atop 130q^{2} + 50q + 10)q^{10}}
5 {(6q^{12} + 35q^{11} + 119q^{10} + 287q^{9} + 526q^{8} + 758q^{7} + \atop 875q^{6}+813q^{5}+608q^{4}+362q^{3}+166q^{2}+55q+10)q^{15}} {(6q^{9} + 35q^{8} + 104q^{7} + 203q^{6} + 287q^{5} + 303q^{4} + \atop 239q^{3} + 135q^{2} + 50q + 10)q^{15}}
6 {(q^{6} + 3q^{5} + 7q^{4} + 13q^{3} + 16q^{2} + 15q + 10)(q^{3} + q^{2} + \atop q + 1)(q^{2} + q + 1)(q + 1)q^{21}} {(q^{6} + 4q^{5} + 11q^{4} + 19q^{3} + 25q^{2} + 20q + 10)(q^{2} + \atop q + 1)(q + 1)q^{21}}

n = 6

b= 4 5
a=4  (5q^{4} + 14q^{3} + 19q^{2} + 14q + 5)q^{10}
5 (6q^{5} + 20q^{4} + 34q^{3} + 34q^{2} + 20q + 5)q^{15} q^{15}
6 (q^{4} + 5q^{3} + 10q^{2} + 10q + 5)(q + 1)q^{21} q^{21}

D. FOATA AND D. ZEILBERGER The bijections for n = 4

exc den π weighted path π′ des mak maj
0 0 1, 2, 3, 4 0 0 0 0 1, 2, 3, 4 0 0  0
1 1 2, 1, 3, 4 0 0 0 0 2, 1, 3, , 4 1 1  1
1 1 3, 1, 2, 4 0 0 0 0 2, 3, 1, 4 1 1  2
1 2 3, 2, 1, 4 0 1 0 0 3, 1, 2, 4 1 2  1
1 1 4, 1, 2, 3 0 0 0 0 2, 3, 4, 1 1 1  3
1 2 4, 2, 1, 3 0 1 0 0 3, 4, 1, 2 1 2  2
1 2 4, 1, 3, 2 0 0 1 0 2, 4, 1, 3 1 2  2
1 3 4, 2, 3, 1 0 1 1 0 4, 1, 2, 3 1 3  1
1 2 1, 3, 2, 4 0 0 0 0 1, 3, 2, 4 1 2  2
1 2 1, 4, 2, 3 0 0 0 0 1, 3, 4, 2 1 2  3
1 3 1, 4, 3, 2 0 0 1 0 1, 4, 2, 3 1 3  2
1 3 1, 2, 4, 3 0 0 0 0 1, 2, 4, 3 1 3  3
2 3 2, 3, 1, 4 0 0 0 0 3, 2, 1, 4 2 3  3
2 3 2, 4, 1, 3 0 0 0 0 3, 4, 2, 1 2 3  5
2 4 2, 4, 3, 1 0 0 1 0 4, 2, 1, 3 2 4  3
2 3 3, 4, 1, 2 0 0 0 0 3, 2, 4, 1 2 3  4
2 4 3, 4, 2, 1 0 1 0 0 3, 1, 4, 2 2 4  4
2 4 4, 3, 1, 2 0 0 1 0 4, 2, 3, 1 2 4  4
2 5 4, 3, 2, 1 0 1 1 0 4, 1, 3, 2 2 5  4
2 4 2, 1, 4, 3 0 0 0 0 2, 1, 4, 3 2 4  4
2 4 3, 1, 4, 2 0 0 0 0 2, 4, 3, 1 2 4  5
2 5 3, 2, 4, 1 0 1 0 0 4, 3, 1, 2 2 5  3
2 5 1, 3, 4, 2 0 0 0 0 1, 4, 3, 2 2 5  5
3 6 2, 3, 4, 1 0 0 0 0 4, 3, 2, 1 3 6  6

REFERENCES

[Carle] (Dr.) J. Carlebach. — Lewi ben Gerson als Mathematiker. — Louis Lamm, Berlin, 1910.

[Carli] L. Carlitz. — q-Bernouli and Eulerian numbers, Trans. Amer. Math. Soc., v. 76, 1954, p. 332–350.

[De1] M. Denert. — Private communication.

[De2] M. Denert. — The genus zeta function of hereditary orders in central simple algebras over global fields, preprint.

[D-F1] J. Désarménien and D. Foata. — Fonctions symétriques et séries hypergéomé-

triques basiques multivariées, Bull. Soc. Math. France, v. 113, 1985, p. 3–22.

[D-F2] J. Désarménien and D. Foata. — Fonctions symétriques et séries hypergéométriques basiques multivariées, II, in : Combinatoire énumérative [Proceedings, Montréal. 1985; G. Labelle and P. Leroux, eds.], p. 68–90. — Springer, Berlin (Lecture Notes in Math., 1234).

[DRS] P. Doubilet, G.-C. Rota and J. Stein. — On the foundations of combinatorial theory, IX. Combinatorial methods in invariant theory, Studies in Appl. Math., v. 53, 1974, p. 185–216.

[Fo1] D. Foata. — On the Netto inversion number of a sequence, Proc. Amer. Math. Soc., v. 19, 1968, p. 236–240.

[Fo2] D. Foata. — Distributions eulériennes et mahonniennes sur le groupe des permutations, in Higher Combinatorics [M. Aigner, ed., Berlin. 1976], p. 27-49. — D. Reidel, Amsterdam, 1977 (Proc. NATO Adv. Study Inst.).

[Ga] S. Gandz. — Studies in Hebrew Astronomy and Mathematics. — Ktav, New York, 1970.

[G-G] A. Garsia and I. Gessel. — Permutations Statistics and Partitions, Adv. in Math.,

v. 31, 1979, p. 288–305.

[Kn] D. E. Knuth. — The Art of Computer Programming, vol. 3, Sorting and Searching. — Addison-Wesley, Reading, 1973.

[Le] (Rabbi) Levi Ben Gerson (”RALBAG”). — Ma’asse Khoshev (≡ “Sepher Hamispar”). — Orange, France, 1321. (A German translation appears in [Carle], p. 151–179).

[Lo] M. Lothaire. — Combinatorics on Words. — Addison-Wesley, Reading, (Enclycopedia of Math. and its Appl., 17), 1983.

[Ma] (Major) 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., v. 35, 1913, p. 314-321.

[Rai] E. D. Rainville. — Special Functions. — MacMillan, New York, 1960 [Reprinted : Chelsea, Bronx, N.Y., 1971].

[Ra] D. Rawlings. — Generalized Worpitzki identities with applications to permutation enumeration, Europ. J. Comb., v. 2, 1981, p. 67-78.

[Staf] J.T. Stafford. — Module structure of Weyl algebras, J. London Math. Soc., v. 18, 1978, p. 429–442.

[Su] C. Suarès. — The Sepher Yetsira, translated from the French by M. and V. Stuart. — Shambhala, London and Boulder, 1976.

[Vi] G. Viennot. — Une théorie combinatoire des polynômes orthogonaux généraux, Notes conf., Univ. Québec à Montréal, 1984.

[Ze] D. Zeilberger. — Partial difference equations in m_{1} ≥ m_{2} ≥ ⋯ ≥ m_{n} and their applications to combinatorics, Discrete Math., v. 31, 1980, p. 65-77.

[Ze2] D. Zeilberger. — A holonomic systems approach to special functions identities, preprint, 1988, 51. p.