Séminaire Lotharingien de Combinatoire 46 (2001), Article B46d

AN EULERIAN PARTNER FOR INVERSIONS

MARK SKANDERA

Abstract. A number of researchers studying permutation statistics on the symmetric group S_{n} have considered pairs (x, Y), where x is an Eulerian statistic and Y is a Mahonian statistic. Of special interest are pairs such as (des, maj), whose joint distribution on S_{n} is given by Carlitz’s q-Eulerian polynomials. We present a natural Eulerian statistic stc such that the pair (stc, inv) is equally distributed with (des, maj) on S_{n}, and provide a simple bijective proof of this fact. This result solves the problem of finding an Eulerian partner for the Mahonian statistic inv. We conjecture several properties of the joint distributions of stc with the statistics des and maj.

1. Introduction

Let S_{n} be the symmetric group on n letters and let ℕ be the nonnegative integers. A function f : S_{n} → ℕ is called a permutation statistic. To define several permutation statistics it will be convenient to use the notation [a] = {1, …, a} for any positive integer a.

One important permutation statistic is des, which counts the descents of a permutation. Writing a permutation π in one-line notation, π = π_{1} ⋯ π_{n}, we call position i a descent of π if π_{i} > π_{i+1}. Thus,

des(π) = #{i ∈ [n − 1] | π_{i} > π_{i+1}}.

The number of permutations in S_{n} with k descents is commonly denoted A(n, k + 1),

A(n, k + 1) = #{π ∈ S_{n} | des(π) = k}.

The distribution of a permutation statistic f on S_{n} is the sequence (a_{0}, a_{1}, …), where a_{k} counts permutations π in S_{n} satisfying f(π) = k. Therefore the distribution of des on S_{n} is the sequence (A(n, 1), …, A(n, n)). The following table shows the distribution of des on S_{n} for n = 1, …, 6.

n\k + 1 1 2 3 4 5 6
1  1
2  1 1
3  1 4 1
4  1 11 11 1
5  1 26 66 26 1
6  1 57 302 302 57 1

The numbers {A(n, k + 1) | n ≥ 1; k + 1 ∈ [n]} are called the Eulerian numbers. It is easy to see (e.g. from Lemma 2.2) that the Eulerian numbers satisfy the recurrence

(1.1)  A(n, k + 1) = (k + 1)A(n − 1, k + 1) + (n − k)A(n − 1, k)

subject to the initial conditions

A(1, k + 1) = \begin{cases}1, & for k = 0, \\ 0, & otherwise. \end{cases}

For fixed n, the Eulerian numbers are often written as the coefficients of the nth Eulerian polynomial

A_{n}(x) = ∑_{k=0}^{n−1} A(n, k + 1)x^{k+1} = ∑_{π∈S_{n}} x^{1+des(π)}.

While no closed formula is known for the Eulerian polynomials, their generating function is given by

1 + ∑_{n≥1} \frac{A_{n}(x)u^{n}}{n!} = \frac{1}{1 − ∑_{n≥1} \frac{(x−1)^{n−1}u^{n}}{n!}} .

Any permutation statistic whose distribution on S_{n} is given by the nth Eulerian polynomial A_{n}(x) is called an Eulerian statistic. A second Eulerian statistic exc counts excedances of a permutation,

exc(π) = #{i ∈ [n − 1] | π_{i} > i}.

Thus,

∑_{π∈S_{n}} x^{1+exc(π)} = ∑_{π∈S_{n}} x^{1+des(π)} = A_{n}(x).

An important permutation statistic which is not Eulerian is maj, the major index of a permutation. maj is defined to be the sum of the descents of a permutation. Denoting the descent set of a permutation π by

D(π) = {i | π_{i} > π_{i+1}},

we have the definition

maj(π) = ∑_{i∈D(π)} i.

The following table shows the distribution of maj on S_{n} for n = 1, …, 5.

n\k 0 1 2 3 4 5 6 7 8 9 10
1  1
2  1 1
3  1 2 2 1
4  1 3 5 6 5 3 1
5  1 4 9 15 20 22 20 15 9 4 1

The generating function for the number of permutations in S_{n} with major index equal to k is the q-analog of n-factorial,

∑_{π∈S_{n}} q^{maj(π)} = (1 + q)(1 + q + q^{2}) ⋯ (1 + q + q^{2} + ⋯ + q^{n−1}).

The permutation statistics distributed this way on S_{n} have been named Mahonian statistics [14] in honor of MacMahon. Another Mahonian statistic inv counts the inversions of a permutation,

inv(π) = #{(π_{i}, π_{j}) | i < j and π_{i} > π_{j}}.

Following [10], we will write Eulerian statistics with lowercase letters and Mahonian statistics with capitals.

A natural extension of the study of permutation statistics and their distributions on S_{n} is the study of pairs of permutation statistics and their joint distributions on S_{n}. Of particular interest is the pair (des, maj) and its joint distribution. (See [1], [6], [7], [8], [9], [10], [14], [16], [18], [19], [20], [22].) The following table shows this joint distribution on S_{5}.

des\maj 0 1 2 3 4 5 6 7 8 9 10
0  1
1  4 9 9 4
2  6 16 22 16 6
3  4 9 9 4
4  1

The generating function for the joint distribution of (des, maj) on S_{n} is given by Carlitz’s q-Eulerian polynomial B_{n}(t) [4, 5],

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

(We follow the notation of [18].) Analogous to the Eulerian numbers, the coefficients B_{n,k}(q) of the q-Eulerian polynomial satisfy the recurrence [4]

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

subject to the initial conditions

B(0, k) = \begin{cases}1, & for k = 0, \\ 0, & otherwise. \end{cases}

A pair of statistics which has the same joint distribution on S_{n} as (des, maj) is sometimes called Euler-Mahonian. The Mahonian statistic with which exc forms an Euler-Mahonian pair is Denert’s statistic, den. (See [18].)

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

Equivalently,

#{π ∈ S_{n} | exc(π) = k; den(π) = p} = #{π ∈ S_{n} | des(π) = k; maj(π) = p}.

Denert [11] conjectured this equidistribution result, which was later proven by Foata and Zeilberger [18] and Han [24].

Since the statistic inv arises so often in combinatorics, one might hope for a natural Eulerian statistic x such that (x, inv) has this same joint distribution. There is in fact a natural Eulerian statistic with this property. We will call it stc, and will define it in Section 3.

In Section 2 we use the code and major index table of a permutation to give a simple bijective proof that inv and maj are equally distributed on S_{n}. The bijection is essentially due to Carlitz [5]. In Section 3 we define the statistic stc and give a bijective proof that the pairs (stc, inv) and (des, maj) are equally distributed on S_{n}. In Section 4 we define a set-valued function ST C : S_{n} → 2^{[n−1]} which associates a set of k numbers to each permutation π satisfying stc(π) = k. Analogous to the descent set D(π) which sums to maj(π), the set ST C(π) sums to inv(π). We conclude in Section 5 with some open problems.

2. The Equidistribution of inv and maj on S_{n}

Related to the symmetric group S_{n} is the set of words w = w_{1} ⋯ w_{n} on the letters [0, n − 1] = {0, …, n − 1} in which each letter w_{i} is at most n − i. We will denote this set by E_{n},

E_{n} = {w = w_{1} ⋯ w_{n} | w_{i} ∈ [0, n − i] for i = 1, …, n.}

The componentwise greatest word in E_{n} is the strictly decreasing word

(n − 1) · (n − 2) ⋯ 0.

We will refer to this word as the stair word of length n, and to the elements of E_{n} as sub-stair words of length n. Clearly there are n! sub-stair words of length n.

There are many known bijections between E_{n} and S_{n}, and by composing a certain pair of these we obtain a proof that inv and maj are distributed equally on S_{n}. This proof might reasonably be attributed to Carlitz [15], since it follows easily from his paper [5]. The first proof of this equidistribution is due to MacMahon [26], and the first bijective proof is due to Foata [13]. A second bijective proof by Foata and Schützenberger [17] shows that the two statistics are in fact distributed symmetrically on S_{n}. (See also [14] and [25, pp 200-203, 212].)

Let γ : S_{n} → E_{n} be the well known bijection which sends a permutation to its code. The code of a permutation π is the word

code(π) = c_{1} ⋯ c_{n}

defined by

c_{i} = #{j ∈ [n] | j > i; π_{j} < π_{i}}.

Example 2.1.

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

An important property of code(π) is that its components sum to inv(π).

Let μ : S_{n} → E_{n} be the bijection which sends a permutation to its major index table. To define the major index table, we will denote by π^{(i)} the restriction of π to the letters i, …, n. (e.g. if π = 284367951, then π^{(4)} = 846795, the restriction of π to the letters 4, …, 9.) Definition 2.2. Let π be a permuation in S_{n}. Define the major index table of π to be the word

majtable(π) = m_{1} ⋯ m_{n},

where

m_{i} = \begin{cases}0, & if i = n, \\ maj(π^{(i)}) − maj(π^{(i+1)}), & otherwise. \end{cases}

If we imagine building the permutation π from scratch by inserting the letters in the order n, …, 1, then m_{i} is the amount by which the major index increases with the insertion of i. Example 2.3. Let π = 284367951. To calculate the major index table we build π one letter at a time in the order 9, …, 1 and record each increase in the major index. (Slashes below indicate descents.)

\begin{matrix}i & π^{(i)} & maj(π^{(i)}) & m_{i} \\ 9 & 9 & 0 & 0 \\ 8 & 89 & 0 & 0 \\ 7 & 8/79 & 1 & 1 \\ 6 & 8/679 & 1 & 0 \\ 5 & 8/679/5 & 5 & 4 \\ 4 & 8/4679/5 & 6 & 1 \\ 3 & 8/4/3679/5 & 9 & 3 \\ 2 & 28/4/3679/5 & 12 & 3 \\ 1 & 28/4/3679/5/1 & 20 & 8 \end{matrix}

Thus we have majtable(π) = m_{1} ⋯ m_{9} = 833140100.

An important property of majtable(π) is that its components sum to maj(π).

We will compose the maps γ and μ to prove the equidistribution of maj and inv, but first let us prove that the map μ is indeed a bijection. Theorem 2.1. The map μ : S_{n} → E_{n} defined by μ(π) = majtable(π) is a bijection.

Proof. To invert μ we apply the following procedure to a word m = m_{1} ⋯ m_{n} in E_{n}.

(1) Define w^{(n)} to be the one-letter word n.

(2) For i = n − 1, …, 1, let w^{(i)} be the unique word obtained by inserting the letter i into the word w^{(i+1)} in such a way that maj(w^{(i)}) − maj(w^{(i+1)}) = m_{i}.

(3) Set π = w^{(1)}.

It is clear that if the word π exists, then it satisfies π^{(i)} = w^{(i)} for i = 1, …, n, so that majtable(π) = m. By the following lemma, π does exist and is unique. In particular, given any permutation w on the letters {i+1, …, n} and any integer ℓ in the interval {0, …, n − i}, then there is a unique permutation w′ obtained by inserting the letter i into w in such a way that maj(w′) − maj(w) = ℓ. □

Lemma 2.2. Let π = π_{1} ⋯ π_{n−i} be a permutation on the letters {i + 1, …, n}, and suppose that π has k descents. Let d_{k−1} < ⋯ < d_{0} be the positions of these k descents, let d_{k} = 0, and let a_{k+1} < ⋯ < a_{n−i} = n − i be the remaining positions of π.

Figure 2.1

(1) Let ℓ be an integer satisfying 0 ≤ ℓ ≤ k and define π′ to be the permutation obtained by inserting the letter i into position d_{ℓ} + 1 of π. Then,

des(π′) = des(π),
maj(π′) = maj(π) + ℓ.

(2) Let ℓ be an integer satisfying k < ℓ ≤ n−i and define π′ to be the permutation obtained by inserting the letter i into position a_{ℓ} + 1 of π. Then,

des(π′) = des(π) + 1,
maj(π′) = maj(π) + ℓ.

Proof. (1) The descent set of π′ is

D(π′) = {d_{k−1}, …, d_{ℓ}, d_{ℓ−1} + 1, …, d_{0} + 1}.

(2) Let p be the least number such that d_{p} < a_{ℓ}. Then,

D(π′) = {d_{k−1}, …, d_{p}, a_{ℓ}, d_{p−1} + 1, …, d_{0} + 1},

and a_{ℓ} = (ℓ − k) + (k − p) = ℓ − p. □

The equidistribution on S_{n} of maj and inv follows immediately. (See Figure 2.1.) Corollary 2.3. The permutation statistics inv and maj are equally distributed on S_{n}. That is, for each number k in the set [0, n − 1] we have

#{π ∈ S_{n} | inv(π) = k} = #{π ∈ S_{n} | maj(π) = k}.

Proof. Define the bijection ϕ : S_{n} → S_{n} by ϕ = γ^{−1}μ. Since ϕ satisfies

majtable(π) = code(ϕ(π)),

it also satisfies

maj(π) = inv(ϕ(π)).
□

Surprisingly, the letter order n, n − 1, …, 1 preceding Definition 2.2 is not crucial for the construction of the major index table. In fact any letter order σ_{1}, …, σ_{n} induces a bijection S_{n} → E_{n} as in Theorem 2.1 [23]. Let us reconsider Theorem 2.1, Lemma 2.2, and Corollary 2.3 in terms of a more general major index table.

Fix a permutation σ = σ_{1} ⋯ σ_{n}, in S_{n} and denote by π^{(i)} the restriction of π to the letters σ_{i}, …, σ_{n}. (e.g. if σ = 852739461 and π = 284367951, then π^{(4)} = 436791, the restriction of π to the letters {σ_{4}, …, σ_{9}} = {1, 3, 4, 6, 7, 9}.) We will call the sequence π^{(1)}, …, π^{(n)} defined in this way the sequence of restricted permutations corresponding to σ. Definition 2.4. Fix a permutation σ in S_{n}. For any permutation π in S_{n}, construct the sequence of restricted permutations π^{(1)}, …, π^{(n)} corresponding to σ and define the σ-major index table of π to be the word

σ-majtable(π) = m_{1} ⋯ m_{n},

where

m_{i} = \begin{cases}0, & if i = n, \\ maj(π^{(i)}) − maj(π^{(i+1)}), & otherwise. \end{cases}

Note that if σ is the permutation 1 ⋯ n, then the sequence π^{(1)}, …, π^{(n)} retains its prior meaning (preceding Definition 2.2), and the σ-major index table is just the major index table. Theorem 2.4. Fix a permutation σ in S_{n}. The map μ_{σ} : S_{n} → E_{n} defined by μ_{σ}(π) = σ-majtable(π) is a bijection.

Proof. Similar to the proof of Theorem 2.1. Use the following lemma instead of Lemma 2.2. □

Lemma 2.5. Fix a permutation σ in S_{n}. Let π be a word on the letters {σ_{i+1}, …, σ_{n}}, and suppose that π has k descents. Let d_{k−1} < ⋯ < d_{0} be the positions of these k descents, let d_{k} = 0, and let d_{−1} = n − i. Define the positions d′_{k} < ⋯ < d′_{0} by

d′_{ℓ} = \begin{cases}d_{ℓ}, & if π_{d_{ℓ}+1} > σ_{i}, \\ max\{j ∈ [n − i] | d_{ℓ} < j ≤ d_{ℓ−1}; π_{j} < σ_{i}\}, & otherwise. \end{cases}

Let a′_{k+1} < ⋯ < a′_{n−i} be the positions

{0, 1, …, n − i} ∖ {d′_{0}, …, d′_{k}}.

(1) Let ℓ be an integer satisfying 0 ≤ ℓ ≤ k and define π′ to be the permutation obtained by inserting the letter σ_{i} into position d′_{ℓ} + 1 of π. Then,

des(π′) = des(π),
maj(π′) = maj(π) + ℓ.

(2) Let ℓ be an integer satisfying k < ℓ ≤ n−i and define π′ to be the permutation obtained by inserting the letter σ_{i} into position a_{ℓ} + 1 of π. Then,

des(π′) = des(π) + 1,
maj(π′) = maj(π) + ℓ.

Proof. Identical to the proof of Lemma 2.2. □

As a corollary of Theorem 2.4, we have n! bijections of the form

ϕ_{σ} = γ^{−1}μ_{σ} : S_{n} → S_{n}

which satisfy

maj(π) = inv(ϕ_{σ}(π))

and therefore prove the equidistribution of the statistics maj and inv on S_{n}. It is not difficult to show that if σ = σ_{1} ⋯ σ_{n} and σ′ = σ′_{1} ⋯ σ′_{n} are two different permutations, then the bijections μ_{σ} and μ_{σ′} are identical if and only if σ_{n} = σ′_{n−1} and σ_{n−1} = σ′_{n}. Thus, the cardinality of the set \{ϕ_{σ} | σ ∈ S_{n}\} is really \frac{n!}{2} rather than n!. We shall see that any of these bijections suffices to prove our main theorem.

3. Main Result

We introduce a function st : E_{n} → ℕ which provides a new interpretation of the Eulerian numbers,

(3.1)  A(n, k + 1) = #{v ∈ E_{n} | st(v) = k}.

Using this function, we define a simple Eulerian statistic stc such that the joint distribution on S_{n} of the pair (stc, inv) is equal to that of the pair (des, maj). This equidistribution result, which extends Corollary 2.3, solves the well-known problem of finding an Eulerian “partner” for the statistic inv. Definition 3.1. Define st : E_{n} → ℕ to be the function which maps a sub-stair word v = v_{1} ⋯ v_{n} to the greatest number ℓ such that v contains a subsequence v_{i_{1}}, …, v_{i_{ℓ}} which is (componentwise) strictly greater than the stair word of length ℓ,

v_{i_{1}} ⋯ v_{i_{ℓ}} > (ℓ − 1) · (ℓ − 2) ⋯ 0.

Figure 3.1. A histogram interpretation of st(245223010).

While v may contain several such subsequences of maximum length, identifying one and calculating this maximum length is quite easy. Starting from the rightmost position of v and reading left, we circle the first letter which is at least one, the next which is at least two, etc., until we cannot continue. The number of circled positions of v is then st(v). Example 3.2. Let v = 245223010. Starting from the right, we circle the 1, 3, 5, and 4. Thus, st(v) = 4. Note that v_{2}v_{3}v_{5}v_{8} = 4531 is strictly greater than 3210, the stair word of length 4.

Representing words as histograms, we see that st(v) is the number of nonzero stairs which we can place beneath the histogram of v while preserving the order of these stairs. Figure 3.1 shows four nonzero stairs beneath the histogram of the word 245223010.

It is easy to show that the function st indeed gives an interpretation of the Eulerian numbers as claimed in Formula (3.1). Let α(n, k + 1) be the number of words v in E_{n} which satisfy st(v) = k. For any word v in E_{n} we have

st(v) = st(v_{1} · v_{2} ⋯ v_{n}) = \begin{cases}st(v_{2} ⋯ v_{n}) + 1, & if v_{1} > st(v_{2} ⋯ v_{n}), \\ st(v_{2} ⋯ v_{n}), & if v_{1} ≤ st(v_{2} ⋯ v_{n}). \end{cases}

Thus α satisfies the recurrence

α(n, k + 1) = (k + 1)α(n − 1, k + 1) + (n − k)α(n − 1, k)

subject to the initial conditions

α(1, k + 1) = \begin{cases}1, & for k = 0, \\ 0, & otherwise. \end{cases}

It follows that α(n, k+1) is the Eulerian number A(n, k+1). A second (bijective) proof of formula (3.1) follows from our main theorem. Let us define a family of Eulerian permutation statistics which count the stairs under the code and major index tables of a permutation. Definition 3.3. Define the permutation statistics stc and stm_{σ} by

stc(π) = st(code(π)),
stm_{σ}(π) = st(σ-majtable(π)).

We prove the equidistribution of (stc, inv) and (des, maj) on S_{n} by demonstrating that the bijection ϕ_{σ} : S_{n} → S_{n} from Section 2 satisfies

maj(π) = inv(ϕ_{σ}(π)),
des(π) = stc(ϕ_{σ}(π)).

Theorem 3.1. The pairs of permutation statistics (des, maj) and (stc, inv) are equally distributed on S_{n}. That is, for each pair (k, p) we have

#{π ∈ S_{n} | stc(π) = k; inv(π) = p} = #{π ∈ S_{n} | des(π) = k; maj(π) = p},

Proof. Fix a permutation σ in S_{n} and let ϕ_{σ} : S_{n} → S_{n} be the bijection defined following Lemma 2.5. For every permutation π in S_{n}, the bijection ϕ_{σ} satisfies

σ-majtable(π) = code(ϕ_{σ}(π)),

and therefore also satisfies

maj(π) = inv(ϕ_{σ}(π)),
stm_{σ}(π) = stc(ϕ_{σ}(π)).

We claim that stm_{σ}(π) = des(π).

Let m = m_{1} ⋯ m_{n} be the σ-major index table of π, and let π^{(1)}, …, π^{(n)} be the sequence of restricted permutations corresponding to σ. Fix i < n and assume that st(m_{i+1} ⋯ m_{n}) = des(π^{(i+1)}). By Definition 3.1 we have

st(m_{i} · m_{i+1} ⋯ m_{n}) = \begin{cases}st(m_{i+1} ⋯ m_{n}) + 1, & if m_{i} > st(m_{i+1} ⋯ m_{n}), \\ st(m_{i+1} ⋯ m_{n}), & otherwise. \end{cases}

By Lemma 2.5 we have

des(π^{(i)}) = \begin{cases}des(π^{(i+1)}) + 1, & if m_{i} > des(π^{(i+1)}), \\ des(π^{(i+1)}), & otherwise. \end{cases}

Thus, st(m_{i} ⋯ m_{n}) = des(π^{(i)}). Proceeding by induction, we obtain stm_{σ}(π) = des(π), as desired. □

Note in the above proof that the statistics stm_{σ} and des are identical, regardless of our choice of σ. This fact is somewhat surprising, given that the words σ-majtable(π) and σ′-majtable(π) are not in general equal when σ and σ′ are distinct.

Note also that a slight modification of the proof produces an Eulerian partner for other Mahonian permutation statistics. Let sum : E_{n} → ℕ be the function that gives the component sum of a substair word of length n. Since the pair (st, sum) is distributed on E_{n} just as (des, maj) is distributed on S_{n}, we have the following generalization of Theorem 3.1. Corollary 3.2. If stat is any Mahonian permutation statistic and ψ : S_{n} → E_{n} is a bijective encoding of permutations as sub-stair words that satisfies

sum(ψ(π)) = stat(π)

for all permutations π in S_{n}, then the pair (stψ, stat) is equally distributed on S_{n} with (des, maj).

This method produces a second Eulerian partner for inv if we encode permutations by their inversion tables. (See [30, pp. 20-21]. It provides Eulerian partners for Rawlings’s r-maj statistics [27] if we encode permutations with his r-maj codings. It also produces a second Eulerian partner for den if we encode permutations with Foata and Zeilberger’s “Denert table” [18].

4. The stc-set of a permutation

Theorem 3.1 states an analogy between the statistic pairs (des, maj) and (stc, inv). We will extend this analogy by defining an stc-analog for the descent set of a permutation. Let D : S_{n} → 2^{[n−1]} be the set-valued function which maps a permutation to its descent set. (Here 2^{[n−1]} denotes the set of all subsets of [n − 1].) Recall that D satisfies

|D(π)| = des(π),
∑_{i∈D(π)} i = maj(π).

In Definition 4.3 we will define a second set-valued function ST C : S_{n} → 2^{[n−1]} which satisfies

|ST C(π)| = stc(π),
∑_{i∈ST C(π)} i = inv(π).

We will call ST C(π) the stc-set of π, and we will show that the functions D and ST C are equally distributed on S_{n}.

Our strategy in defining ST C(π) for each permutation π in S_{n} is to transform the word code(π), whose components sum to inv(π), into another word in which all nonzero letters are distinct and sum to inv(π). We then define ST C(π) to be this set of nonzero letters.

Let us begin by defining a set of n − 2 operators on E_{n}. Definition 4.1. Let v = v_{1} ⋯ v_{n} be a word in E_{n}. For i = 1, …, n − 2, define the operator η_{i} : E_{n} → E_{n} by

η_{i}(v) = v_{1} ⋯ v_{i−1} · ℓ · ℓ′ · v_{i+2} ⋯ v_{n},

where

(ℓ, ℓ′) = \begin{cases}(v_{i}, v_{i+1}) & if v_{i} > v_{i+1} or v_{i} = v_{i+1} = 0, \\ (v_{i+1} + 1, v_{i} − 1) & if 0 < v_{i} ≤ v_{i+1}, \\ (v_{i+1}, v_{i}) & if 0 = v_{i} < v_{i+1}. \end{cases}

Unless v_{i} is greater than v_{i+1} (or both are zero), the operator η_{i} replaces this nondecreasing pair of letters with a strictly decreasing pair. The sum of the new pair is the same as that of the old.

It may be interesting to note that the operators η_{1}, …, η_{n−2} satisfy the relations

η_{i}^{2} = η_{i}, for all i,
η_{i}η_{i+1}η_{i} = η_{i+1}η_{i}η_{i+1}, for i < n − 2,
η_{i}η_{j} = η_{j}η_{i}, for |i − j| ≥ 2.

It follows that these operators generate H_{n−2}, the 0-Hecke monoid on n−2 generators. (See [21].)

Composing η_{1}, …, η_{n−2}, we define a map ω : E_{n} → E_{n} which applies a modified “bubble sort” algorithm to a sub-stair word v. Each time it exchanges two nonzero letters, it increments the letter moving left and decrements the letter moving right. Definition 4.2. For i = 1, …, n − 2, define the operators ω_{i} : E_{n} → E_{n} by

ω_{i} = η_{n−2} ⋯ η_{i},

and define ω : E_{n} → E_{n} to be the product

ω = ω_{1} ⋯ ω_{n−2}.

Figure 4.1 shows the computation of ωv for v = 332110. Each line in the table represents a single step of the algorithm, the action of η_{j} for some j. Positions j and j + 1 are marked below by × if the corresponding letters are altered, and by )( otherwise.

Figure 4.1. Computation of ω(332110).

Using Definition 4.2, one easily verifies that for any word v in E_{n} with stc(v) = k, the word v′ = ωv also belongs to E_{n} and satisfies

v′_{1} > ⋯ > v′_{k} > 0,
v′_{k+1} = ⋯ = v′_{n} = 0,
v′_{1} + ⋯ + v′_{k} = sum(v).

The map ω therefore naturally associates a subset of [n − 1] to each sub-stair word v in E_{n}: the set of nonzero letters of ωv. Definition 4.3. Define the st-set of a sub-stair word v to be the set

ST (v) = {ℓ > 0 | ℓ appears in ωv}.

Applying this definition to the code and major index tables of a permutation π, define the stc-set and σ-stm-set of π to be the sets

ST C(π) = ST (code(π)),
σ-ST M(π) = ST (σ-majtable(π)).

We claim that for every subset T of [n − 1], the number of permutations in S_{n} with stc-set T equals the number of permutations in S_{n} with descent set T. We prove this equidistribution result by demonstrating that the bijection ϕ_{σ} : S_{n} → S_{n} from Section 2 satisfies

D(π) = ST C(ϕ_{σ}(π)).

Theorem 4.1. For every subset T of [n − 1], we have

#{π ∈ S_{n} | D(π) = T } = #{π ∈ S_{n} | ST C(π) = T }.

Proof. Fix a permutation σ in S_{n}, and let ϕ_{σ} : S_{n} → S_{n} be the bijection defined following Lemma 2.5. For every permutation π in S_{n}, the bijection ϕ_{σ} satisfies

σ-majtable(π) = code(ϕ_{σ}(π)),

and therefore also satisfies

σ-ST M(π) = ST C(ϕ_{σ}(π)).

We claim that σ-ST M(π) = D(π).

Let m = m_{1} ⋯ m_{n} be the σ-major index table of π, and let π^{(1)}, …, π^{(n)} be the sequence of restricted permutations corresponding to σ. Fix i < n and let d_{0} > ⋯ > d_{k−1} be the descents of π^{(i+1)}. Assume that

ω(m_{i+1} ⋯ m_{n}) = d_{0} ⋯ d_{k−1} · 0 ⋯ 0

so that we have

ST (m_{i+1} ⋯ m_{n}) = D(π^{(i+1)}).

It is easy to see from Definition 4.2 that the map ω satisfies

ω(m_{i} ⋯ m_{n}) = ω(m_{i} · ω(m_{i+1} ⋯ m_{n})).

Thus, we have

ω(m_{i} ⋯ m_{n}) = ω(m_{i} · d_{0} ⋯ d_{k−1} · 0 ⋯ 0)

= \begin{cases}m_{i} · d_{0} ⋯ d_{k−1} · 0 ⋯ 0, & if m_{i} > d_{0}, \\ (d_{0} + 1) ⋯ (d_{m_{i}−1} + 1) · d_{m_{i}} ⋯ d_{k−1} · 0 ⋯ 0, & if m_{i} ≤ k, \\ (d_{0} + 1) ⋯ (d_{j−1} + 1) · (m_{i} − j) · d_{j} ⋯ d_{k−1} · 0 ⋯ 0, & otherwise, \end{cases}

where j is the least integer satisfying m_{i} − j > d_{j}.

Comparing the expressions above to those in the proof of Lemma 2.2, we see that the nonzero letters in ω(m_{i} ⋯ m_{n}) are precisely the descent set of π^{(i)}. (Equivalently, the nonzero letters in the last n − i + 1 positions of ω_{i} ⋯ ω_{n−2}m are the descent set of π^{(i)}. See Figure 4.2.) Thus, we have ST (m_{i} ⋯ m_{n}) = des(π^{(i)}). Proceeding by induction, we obtain σ-ST M(π) = D(π), as desired. □

Corollary 4.2. Let π be a permutation in S_{n} with stc(π) = k and inv(π) = p. Then the ST C(π) is a k-subset of [n − 1] whose elements sum to p.

By the discussion following Corollary 3.2, one can use the map ω to define analogs of the descent set for several other Eulerian permutation statistics.

Figure 4.2. Comparison of ω_{i} ⋯ ω_{n−2}(majtable(π)) and D(π^{(i)}), for
π = 413265

5. Open problems

Several important results in the area of permutation statistics involve generalization to word statistics, joint distributions, and the f-vectors of simplicial complexes. These results suggest interesting open problems regarding the statistic stc.

Question 5.1. Is there an Eulerian word statistic which naturally generalizes the permutation statistic stc?

While there is an obvious generalization of the permutation statistic stc to arbitrary words, this generalized statistic unfortunately is not Eulerian. (See [10], [25, Ch. 10], [28] for more information on Eulerian word statistics.) Perhaps a clever adjustment of the definition of the word statistic stc would rectify this situation. It may be interesting to note that the proof of Theorem 3.1 fails to generalize to the rearrangement class R(w) of an arbitrary word w because the sets {code(u) | u ∈ R(w)} and {majtable(u) | u ∈ R(w)} are not in general equal. In fact, even the sets {σ-majtable(u) | u ∈ R(w)} and {σ′-majtable(u) | u ∈ R(w)} are not in general equal when σ and σ′ are distinct.

More open problems concern the joint distributions on S_{n} of the permutation statistic stc with other permutation statistics. In particular, the joint distribution of (des, stc) seems to be symmetric, and the joint distribution of (stc, maj) seems to be equal to that of (des, inv). Further, there seems to be a single bijection that proves these statements while simultaneously demonstrating the symmetry of the joint distribution of (maj, inv). The following conjecture is true for n less than or equal to 10. Conjecture 5.1. The quadruples (des, maj, inv, stc) and (des, maj, imaj, ides) are equally distributed on S_{n}.

We define ides and imaj to be the statistics which give the number of descents and the major index of the inverse of a permutation,

ides(π) = des(π^{−1}),
imaj(π) = maj(π^{−1}).

Thus the joint distributions of (des, ides) and (maj, imaj) are obviously symmetric. (See [17] for more results regarding these permutation statistics.)

One last problem concerning the permutation statistic stc is to use it as other permutation statistics have been used to demonstrate relationships between f-vectors of simplicial complexes and linear extensions of partially ordered sets. (See [2], [3], [12], [28], [29], [31], [32], [33].) One such result uses descents to construct, for any poset P, a balanced simplicial complex whose f-vector counts linear extensions of P [12], [29]. Another result uses Dumont’s statistic dmc to construct, for any disjoint sum of chains P = a_{1}+⋯+a_{d}, another poset whose f-vector counts linear extensions of P [28]. Perhaps the statistic stc can be used to obtain a similar result. Question 5.2. Let P be any finite poset. Can the statistic stc be used to construct a second poset whose f-vector counts linear extensions of P?

An affirmative answer to this question would strengthen a special case of a result of Stanley [29, Cor. 4.5], [31, Thm. 4.6] and would prove the conjecture stated in [28, Conj. 6.1].

6. Acknowledgments

I would like to thank Richard Stanley, Dominique Foata, Tricia Hersh, Ira Gessel, Einar Steingrímsson, and Jennifer Galovich for inspiration and for many helpful suggestions. I would also like to thank my referees for more helpful suggestions.

References

[1] E. Babson and E. Steingrímsson, Generalized permutation patterns and a classification of the Mahonian statistics, Sém. Lothar. Combin., 44 (2000), Art. B44b, 18 pp.

[2] A. Björner, A. Garsia, and R. Stanley, An introduction to the theory of Cohen-Macaulay posets, in Ordered Sets, I. Rival, ed., Reidel, Dordrecht/Boston/London, 1982, pp. 583–615.

[3] A. Björner and M. Wachs, Permutation Statistics and Linear Extensions of Posets, J. Combin. Theory Ser. A, 58 (1991), pp. 85–114.

[4] L. Carlitz, q-Bernoulli and Eulerian numbers, Trans. of the AMS, 76 (1954), pp. 332–350.

[5] , A combinatorial property of q-Eulerian numbers, American Math. Monthly, 82 (1975), pp. 51–54.

[6] R. J. Clarke and D. Foata, Eulerian calculus I: univariable statistics, Europ. J. Combin., 15 (1994), pp. 345–362.

[7] , Eulerian calculus IV: specializations, Sém. Lothar. Combin., 32 (1994), Art. B32b, 12 pp.

[8] , Eulerian calculus II: an extension of Han’s fundamental transformation, Europ. J. Combin., 16 (1995), pp. 221–252.

[9] , Eulerian calculus III: the ubiquitous Cauchy formula, Europ. J. Combin., 16 (1995), pp. 329–355.

[10] R. J. Clarke, E. Steingrímsson, and J. Zeng, New Euler-Mahonian statistics on permutations and words, Adv. Appl. Math., 18 (1997), pp. 237–270.

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

[12] P. Edelman and V. Reiner, H-shellings and h-complexes, Adv. Math., 106 (1994), pp. 36–64.

[13] D. Foata, On the Netto inversion number of a sequence, Proc. Amer. Math. Soc., 19 (1968), pp. 236–240.

[14] , Distributions Eulériennes et Mahoniennes sur le groupe des permutations, in Higher Combinatorics, M. Aigner, ed., vol. 19, D. Reidel Publishing Company, Dordrecht-Holland, 1977, pp. 27–49.

[15] D. Foata, 1999. Personal communication.

[16] D. Foata and C. Krattenthaler, Graphical major indices, II, Sém. Lothar. Combin., 34 (1995), Art. B34k, 16 pp.

[17] D. Foata and M. P. Schützenberger, Major index and inversion number of permutations, Math. Nach., 83 (1978), pp. 143–159.

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

[19] , Graphical major indices, J. Comput. Applied Math, 68 (1996), pp. 79–101.

[20] , Babson-Steingrímsson statistics are indeed Mahonian (and sometimes even Euler-Mahonian), Adv. Appl. Math., (to appear).

[21] S. Fomin and C. Greene, Noncommutative Schur functions and their applications, Disc. Math., (1998), pp. 179–200.

[22] A. M. Garsia and I. Gessel, Permutation statistics and partitions, Adv. Math., 31 (1979), pp. 288–305.

[23] I. Gessel, 1999. Personal communication.

[24] G. N. Han, Une transformation fondamentale sur les réarrangements de mots, Adv. Math., 105 (1994), pp. 26–41.

[25] M. Lothaire, Combinatorics on words, vol. 17 of Encyclopedia of Math. and its Appl., Addison-Wesley, Reading, 1983.

[26] P. MacMahon, Combinatory Analysis, vol. 1 and 2, Cambridge Univ. Press, Cambridge, 1915.

[27] D. Rawlings, The r-major index, J. Combin. Theory Ser. A, 31 (1981), pp. 175–183.

[28] M. Skandera, Dumont’s statistic on words, Elec. J. Combin., 8 (2001), Art. #R11, 19 pp.

[29] R. Stanley, Balanced Cohen-Macaulay complexes, Trans. of the AMS, 241 (1979), pp. 139–157.

[30] , Enumerative Combinatorics, vol. 1, Wadsworth & Brooks/Cole, Belmont, CA, 1986.

[31] , Combinatorics and Commutative Algebra, Birkhäuser, Boston, MA, 1996.

[32] , Positivity problems and conjectures, in Mathematics: Frontiers and Perspectives, V. Arnold, M. Atiyah, P. Lax, and B. Mazur, eds., American Mathematical Society, Providence, RI, 2000, pp. 295–319.

[33] D. Wagner, Enumeration of functions from posets to chains, Europ. J. Combin., 13 (1992), pp. 313–324.

Author’s address: University of Michigan, Dept. of Mathematics, 2074 East Hall, 525 East University, Ann Arbor, MI 48109-1109

  E-mail address: mskan@umich.edu