40.01.05 · combinatorics / enumeration-generating-functions

Permutation Statistics: Descents, the Major Index, and Eulerian Polynomials

shipped3 tiersLean: none

Anchor (Master): Stanley 2012 *Enumerative Combinatorics, Volume 1* 2e §1.3-1.4 and Notes (Foata's bijection, the $q$-Eulerian refinement, the exponential generating function of the Eulerian polynomials); Petersen 2015 *Eulerian Numbers* (Birkhäuser) Ch. 1-5 (Eulerian polynomials, the EGF $(t-1)/(t-e^{(t-1)x})$, Worpitzky, $\gamma$-positivity); Foata-Schützenberger 1970 *Théorie géométrique des polynômes eulériens* (Springer LNM 138)

Intuition Beginner

Take a deck of cards numbered $1$ through $n$ and shuffle it into some order. You now have a permutation: a specific arrangement of the numbers. Two different shuffles give two different arrangements, and there are a great many of them. Rather than treat every arrangement as a featureless point in a huge list, you can attach to each one a few honest numbers that measure how scrambled it is. These measurements are called permutation statistics, and they turn out to obey beautiful patterns.

The first measurement is the count of descents. Walk along the arrangement from left to right and mark each spot where the next card is smaller than the current one — a step downhill. The arrangement $25314$ steps down at $53$ and again at $31$ , so it has two descents. A sorted deck never steps down; a fully reversed deck steps down at every position. The descent count is a rough gauge of disorder.

The second measurement is the count of inversions: how many pairs of cards are out of their natural order, a bigger number sitting somewhere to the left of a smaller one. Sorting the deck by repeatedly swapping neighbours takes exactly one swap per inversion, so the inversion count is the honest distance from sorted.

Here is the surprise this unit is built around. There is a third statistic, the major index, that adds up the positions where descents happen rather than just counting them. It looks like a strange thing to track. Yet if you tally how many arrangements have each possible inversion count, and separately tally how many have each possible major index, the two tallies are identical, number for number. Two very different-looking measurements share one distribution. This unit explains that coincidence and the polynomial — the Eulerian polynomial — that records how descents are spread across all arrangements.

Visual Beginner

Take the arrangement $σ = 25314$ of the numbers $1$ through $5$ . The table below reads off its three statistics by hand. A descent is a position $i$ where the entry is bigger than the one just after it; the major index adds up those positions; an inversion is a pair (earlier, later) that is out of order.

position $i$	entries $σ_{i}, σ_{i + 1}$	descent?
$1$	$2, 5$	no (uphill)
$2$	$5, 3$	yes (downhill)
$3$	$3, 1$	yes (downhill)
$4$	$1, 4$	no (uphill)

The descents sit at positions $2$ and $3$ , so the descent count is $2$ and the major index is $2 + 3 = 5$ . Counting every out-of-order pair (such as $5$ before $3$ , $5$ before $1$ , $3$ before $1$ , $2$ before $1$ ) gives $5$ inversions as well. The descent count, the summed-position major index, and the inversion count are three separate ways of scoring one arrangement, and the rest of the unit shows how their totals across all arrangements line up.

Worked example Beginner

Let us list all six arrangements of the numbers $1, 2, 3$ and score each one. Reading left to right, mark a descent wherever an entry is bigger than the next.

The arrangement $123$ never steps down: $0$ descents, major index $0$ , and $0$ inversions.

The arrangement $132$ steps down once, at position $2$ (the $32$ ): $1$ descent, major index $2$ , and $1$ inversion (the pair $3$ before $2$ ).

The arrangement $213$ steps down once, at position $1$ (the $21$ ): $1$ descent, major index $1$ , and $1$ inversion (the pair $2$ before $1$ ).

The arrangement $231$ steps down once, at position $2$ (the $31$ ): $1$ descent, major index $2$ , and $2$ inversions ( $2$ before $1$ , and $3$ before $1$ ).

The arrangement $312$ steps down once, at position $1$ (the $31$ ): $1$ descent, major index $1$ , and $2$ inversions ( $3$ before $1$ , and $3$ before $2$ ).

The arrangement $321$ steps down twice, at positions $1$ and $2$ : $2$ descents, major index $1 + 2 = 3$ , and $3$ inversions (every pair is reversed).

Now tally the inversion counts: one arrangement has $0$ , two have $1$ , two have $2$ , one has $3$ . Tally the major index: one has $0$ , two have $1$ , two have $2$ , one has $3$ . The two tallies match exactly — $1, 2, 2, 1$ — even though inversions count pairs and the major index sums positions.

What this tells us: two unrelated-looking scores produce the very same spread of counts over all arrangements. Tallying descents instead gives $1, 4, 1$ (one arrangement with $0$ descents, four with $1$ , one with $2$ ), the pattern recorded by the Eulerian polynomial.

Check your understanding Beginner

Formal definition Intermediate+

Write $S_{n}$ for the symmetric group on ${1, \dots, n}$ , with a permutation $σ$ recorded in one-line notation as the word $σ_{1} σ_{2} \dots σ_{n}$ where $σ_{i} = σ (i)$ .

Definition (descent set, descent number). The descent set of $σ \in S_{n}$ is $$ D(\sigma) = {, i \in {1, \dots, n-1} : \sigma_i > \sigma_{i+1} ,} \subseteq {1, \dots, n-1}, $$ and the descent number is $des (σ) = ∣ D (σ) ∣$ . The complementary set of ascents is ${1, \dots, n - 1} ∖ D (σ)$ .

Definition (major index). The major index is the sum of the descent positions, $$ \operatorname{maj}(\sigma) = \sum_{i \in D(\sigma)} i . $$

Definition (inversion number, length). The inversion number is $$ \operatorname{inv}(\sigma) = \big|{, (i,j) : 1 \le i < j \le n,\ \sigma_i > \sigma_j ,}\big|. $$ It coincides with the Coxeter length $ℓ (σ)$ of $σ$ as a word in the adjacent transpositions $s_{i} = (i i + 1)$ generating $S_{n}$ as the Coxeter group of type $A_{n - 1}$ : $inv (σ)$ is the number of letters in any reduced word for $σ$ , and $D (σ) = {i : ℓ (σ s_{i}) < ℓ (σ)}$ is the right descent set in the Coxeter sense.

Definition (Mahonian and Eulerian distributions). A statistic $stat : S_{n} \to Z_{\geq 0}$ is Mahonian if $\sum_{σ \in S_{n}} q^{stat (σ)} = (n)_{q}! := \prod_{i = 1}^{n} (1 + q + \dots + q^{i - 1}) = \prod_{i = 1}^{n} \frac{1 - q ^{i}}{1 - q}$ , the $q$ -factorial. Both $inv$ and $maj$ are Mahonian. The Eulerian number $A (n, k) = {σ \in S_{n} : des (σ) = k}$ , also written $⟨ k n ⟩$ , counts permutations with $k$ descents, and the Eulerian polynomial is $$ A_n(t) = \sum_{\sigma \in \mathfrak{S}n} t^{\operatorname{des}(\sigma)+1} = \sum{k=0}^{n-1} A(n,k), t^{k+1}, $$ with the convention $A_{0} (t) = 1$ . The notations $D (σ)$ , $des$ , $maj$ , $inv$ , $ℓ$ , $(n)_{q}!$ , and $⟨ k n ⟩$ are recorded in _meta/NOTATION.md.

Counterexamples to common slips Intermediate+

"The major index counts descents." It sums their positions. The permutations $231$ and $312$ both have one descent but major indices $2$ and $1$ respectively, distinguishing them despite equal descent number.
" $inv$ and $maj$ agree permutation by permutation because they are equidistributed." Equidistribution is a statement about the two multisets of values over all of $S_{n}$ , not a pointwise identity. On $231$ , $inv = 2$ while $maj = 2$ happen to coincide, but on $312$ , $inv = 2$ and $maj = 1$ differ. Foata's bijection $ϕ$ realises the equality of distributions by a permutation-rearranging map, not by the identity map.
"The Eulerian polynomial uses the exponent $des (σ)$ ." The standard convention uses $des (σ) + 1$ , so that $A_{n} (t)$ has degree $n$ with no constant term and the identity $\sum_{m \geq 0} m^{n} t^{m} = A_{n} (t) / (1 - t)^{n + 1}$ holds cleanly. Dropping the $+ 1$ shifts every formula by a factor of $t$ .
" $maj$ is defined the same for any indexing convention." The major index sums the positions $i$ of descents, so it depends on positions being labelled $1, \dots, n - 1$ . A $0$ -indexed descent set would change every major index; the Mahonian property is stated for the $1$ -indexed convention.

Key theorem with proof Intermediate+

The signature theorem is MacMahon's equidistribution: the inversion number and the major index, defined by counting pairs and by summing positions respectively, induce the same distribution on $S_{n}$ , the Mahonian distribution $(n)_{q}!$ . This is the single statement that makes the major index — an otherwise ad-hoc-looking statistic — a structural object on par with the length function.

Theorem (MacMahon). For every $n \geq 0$ , $$ \sum_{\sigma \in \mathfrak{S}n} q^{\operatorname{inv}(\sigma)} ;=; \sum{\sigma \in \mathfrak{S}_n} q^{\operatorname{maj}(\sigma)} ;=; (n)q! ;=; \prod{i=1}^{n} (1 + q + \cdots + q^{i-1}). $$

Proof. We prove each generating function equals $(n)_{q}!$ separately; their equality is then a corollary.

First, $\sum_{σ} q^{inv (σ)} = (n)_{q}!$ via the inversion table. To a permutation $σ \in S_{n}$ associate $c (σ) = (c_{1}, \dots, c_{n})$ where $c_{i} = ∣ {j > i : σ_{j} < σ_{i}} ∣$ counts the entries to the right of position $i$ that are smaller than $σ_{i}$ . Then $0 \leq c_{i} \leq n - i$ , and $inv (σ) = \sum_{i} c_{i}$ since every inversion $(i, j)$ is counted once, at its left member $i$ . The map $σ \mapsto c (σ)$ is a bijection from $S_{n}$ onto the product $\prod_{i = 1}^{n} {0, 1, \dots, n - i}$ : the value $c_{n} = 0$ is forced, and reading the $c_{i}$ from $i = n$ down to $i = 1$ reconstructs $σ$ by inserting the entries in increasing order of value, each $c_{i}$ specifying a rank. Hence $$ \sum_{\sigma} q^{\operatorname{inv}(\sigma)} = \prod_{i=1}^{n} \Big(\sum_{c_i = 0}^{n-i} q^{c_i}\Big) = \prod_{i=1}^{n} (1 + q + \cdots + q^{n-i}) = \prod_{j=1}^{n}(1 + q + \cdots + q^{j-1}) = (n)_q!, $$ re-indexing $j = n - i + 1$ .

Second, $\sum_{σ} q^{maj (σ)} = (n)_{q}!$ by induction on $n$ , inserting the largest value $n$ into a permutation of ${1, \dots, n - 1}$ . Given $τ \in S_{n - 1}$ with descent set $D (τ) \subseteq {1, \dots, n - 2}$ , there are $n$ positions (gaps) at which to insert $n$ , the gaps numbered $0, 1, \dots, n - 1$ from the right. Inserting $n$ into the gap that lies immediately to the right of the $r$ -th descent-or-ascent — precisely, ordering the $n$ gaps so that placing $n$ there increases $maj$ by exactly $r$ for $r = 0, 1, \dots, n - 1$ — yields, summed over the $n$ gaps, the factor $1 + q + \dots + q^{n - 1}$ . (The combinatorial fact is that the $n$ insertion positions raise the major index by the $n$ distinct values $0, 1, \dots, n - 1$ ; this is verified by tracking how each descent position shifts when $n$ splits a gap.) Therefore $\sum_{σ \in S_{n}} q^{maj (σ)} = (1 + q + \dots + q^{n - 1}) \sum_{τ \in S_{n - 1}} q^{maj (τ)}$ , and by induction with base $(0)_{q}! = 1$ this is $(n)_{q}!$ .

Since both sums equal $(n)_{q}!$ , they are equal, and $inv$ and $maj$ are equidistributed. $□$

Bridge. This theorem is the foundational reason the major index deserves a place beside the inversion number rather than being a curiosity: both are Mahonian, so each is a $q$ -refinement of the count $n! = (n)_{1}!$ , and the inversion number is exactly the Coxeter length on the type- $A_{n - 1}$ Weyl group, which builds toward the length-function and reduced-word theory of 07.04.01. The inversion-table bijection is the simple case of a recurring move — encoding a permutation as a sequence of independent bounded choices — and the maj-insertion argument is dual to it, threading the same product $(n)_{q}!$ through positions rather than pairs; putting these together, the equality of the two generating functions is the central insight that a single $q$ -analogue $(n)_{q}!$ governs both pair-counting and position-summing statistics. The bridge is that this equidistribution, proved here non-constructively by computing both sides, demands an explicit bijection $maj = inv \circ ϕ$ , which appears again in the Master tier as Foata's transformation and which generalises to the multiset rearrangement classes and the $q$ -Eulerian refinement, where descents and the major index are tracked jointly. The $q$ -factorial itself is the same $(n)_{q}!$ that organises the Gaussian binomial coefficients of 40.01.06.

Exercises Intermediate+

Exercise 4 (medium, symbolic).

Prove the Eulerian recurrence $A (n, k) = (k + 1) A (n - 1, k) + (n - k) A (n - 1, k - 1)$ by inserting the value $n$ into a permutation of ${1, \dots, n - 1}$ .

Hint

Inserting $n$ into one of the $n$ gaps of $τ \in S_{n - 1}$ either preserves the descent count or raises it by one. Sort the gaps by whether they sit inside a descent, inside an ascent, or at an end.

Answer

Let $τ \in S_{n - 1}$ have $des (τ) = j$ and $n$ gaps (including the two ends). Inserting the maximal value $n$ at a gap: if the gap lies strictly inside an existing descent of $τ$ or at the right end, the new $n$ (being largest) does not create a descent at the new boundary on its left and removes the old descent it splits while the right boundary $n > \cdot$ is a descent — net the descent count is unchanged; there are $j + 1$ such gaps (the $j$ descents plus the right end). At the remaining $n - 1 - j$ gaps (inside ascents or the left end), inserting $n$ creates exactly one new descent (since $n$ is followed by a smaller entry), raising the descent count by one. Hence a permutation of $S_{n}$ with $k$ descents arises either from a $τ$ with $k$ descents via one of its $k + 1$ "preserving" gaps, or from a $τ$ with $k - 1$ descents via one of its $(n - 1) - (k - 1) = n - k$ "raising" gaps. Summing the two disjoint sources, $A (n, k) = (k + 1) A (n - 1, k) + (n - k) A (n - 1, k - 1)$ . Rubric: full credit for classifying the $n$ gaps into descent-count-preserving and descent-count-raising, with the correct counts $k + 1$ and $n - k$ .

Exercise 6 (medium, symbolic).

Prove the symmetry $A (n, k) = A (n, n - 1 - k)$ using the reversal map $σ \mapsto σ^{rev}$ , where $σ_{i}^{rev} = σ_{n + 1 - i}$ .

Hint

Reversing the word turns each ascent into a descent and vice versa. Count how the descent number changes.

Answer

The reversal $σ^{rev}$ reads $σ$ right to left. A position $i \in {1, \dots, n - 1}$ is a descent of $σ^{rev}$ exactly when $σ_{i}^{rev} > σ_{i + 1}^{rev}$ , i.e. $σ_{n + 1 - i} > σ_{n - i}$ , which says position $n - i$ is an ascent of $σ$ . So reversal sends the descent set to the complement of (a relabelling of) the descent set: $des (σ^{rev}) = (n - 1) - des (σ)$ , since each of the $n - 1$ adjacent positions is a descent of exactly one of $σ, σ^{rev}$ . Reversal is an involution on $S_{n}$ , hence a bijection, carrying the $A (n, k)$ permutations with $k$ descents onto the $A (n, n - 1 - k)$ permutations with $n - 1 - k$ descents. Therefore $A (n, k) = A (n, n - 1 - k)$ . Rubric: full credit for the ascent-descent swap under reversal, the count $des (σ^{rev}) = n - 1 - des (σ)$ , and the bijection conclusion.

Exercise 7 (hard, symbolic).

Prove the Worpitzky identity $x^{n} = \sum_{k = 0}^{n - 1} A (n, k) (n x + k)$ as a polynomial identity in $x$ , by counting functions from an $n$ -set to ${1, \dots, x}$ for positive integers $x$ .

Hint

A word $w \in {1, \dots, x}^{n}$ has a weakly increasing rearrangement; sort by the descent structure of the permutation recording ties broken by position. Each word corresponds to a choice of an underlying permutation with $k$ descents and a weakly increasing assignment compatible with it.

Answer

Fix a positive integer $x$ . There are $x^{n}$ functions $f : {1, \dots, n} \to {1, \dots, x}$ , i.e. words of length $n$ over ${1, \dots, x}$ . Associate to $f$ the permutation $σ \in S_{n}$ that sorts the positions by value, breaking ties by position (so $σ$ is the unique permutation with $f_{σ_{1}} \leq f_{σ_{2}} \leq \dots \leq f_{σ_{n}}$ and $f_{σ_{i}} = f_{σ_{i + 1}} \Rightarrow σ_{i} < σ_{i + 1}$ ). Given $σ$ with $des (σ) = k$ , the words $f$ producing it are the weakly increasing sequences $1 \leq b_{1} \leq \dots \leq b_{n} \leq x$ that are strictly increasing across each descent of $σ$ ; substituting $b_{i}^{'} = b_{i} + ∣ {j < i : j \in D (σ)} ∣$ turns these into weakly increasing sequences $1 \leq b_{1}^{'} \leq \dots \leq b_{n}^{'} \leq x + k$ with no constraint, of which there are $(n x + k)$ (multisets of size $n$ from $x + k$ values). Summing over the descent number, $x^{n} = \sum_{k} A (n, k) (n x + k)$ . This holds for all positive integers $x$ , hence as polynomials. Rubric: full credit for the sort-permutation correspondence, the strict-across-descents shift producing $(n x + k)$ , and the promotion to a polynomial identity.

Exercise 8 (hard, symbolic).

Prove the identity $m \geq 0 \sum m^{n} t^{m} = \frac{A _{n} ( t )}{( 1 - t ) ^{n + 1}}$ as formal power series in $t$ , using the Worpitzky identity.

Hint

Substitute $x = m$ into Worpitzky, multiply by $t^{m}$ , sum over $m \geq 0$ , and use the negative-binomial series $\sum_{m} (n m + k) t^{m}$ .

Answer

By Worpitzky, $m^{n} = \sum_{k = 0}^{n - 1} A (n, k) (n m + k)$ . Hence $$ \sum_{m \ge 0} m^n t^m = \sum_{k} A(n,k) \sum_{m \ge 0}\binom{m+k}{n} t^m . $$ For fixed $k$ , write $(n m + k)$ and sum: the generating function $\sum_{m \geq 0} (n m + k) t^{m}$ equals $\frac{t ^{n - k}}{( 1 - t ) ^{n + 1}}$ , since $\sum_{j \geq 0} (n j) t^{j} = \frac{t ^{n}}{( 1 - t ) ^{n + 1}}$ (the standard negative-binomial expansion of $(1 - t)^{- (n + 1)}$ ) and shifting the index by $k$ inserts the factor $t^{- k}$ while the lower terms $(n m + k)$ with $m + k < n$ vanish, leaving $t^{n - k} / (1 - t)^{n + 1}$ . Therefore $$ \sum_{m\ge0} m^n t^m = \frac{1}{(1-t)^{n+1}}\sum_{k} A(n,k), t^{n-k} = \frac{A_n(t)}{(1-t)^{n+1}}, $$ where the last equality uses $\sum_{k} A (n, k) t^{n - k} = \sum_{k} A (n, n - 1 - k) t^{k + 1} = A_{n} (t)$ by the symmetry $A (n, k) = A (n, n - 1 - k)$ and the convention $A_{n} (t) = \sum_{k} A (n, k) t^{k + 1}$ . Rubric: full credit for the negative-binomial sum, the index shift, and the use of Eulerian symmetry to recover $A_{n} (t)$ .

Advanced results Master

The descent and inversion statistics organise into a single generating-function calculus on the symmetric group: the Eulerian polynomials have a closed exponential generating function, the inv/maj equidistribution becomes constructive through Foata's bijection, and the major index refines the Eulerian distribution into the joint $(des, maj)$ statistic counted by the $q$ -Eulerian polynomials.

Theorem 1 (exponential generating function of the Eulerian polynomials). The Eulerian polynomials satisfy $$ \sum_{n \ge 0} A_n(t),\frac{x^n}{n!} ;=; \frac{t - 1}{t - e^{(t-1)x}} . $$ The proof multiplies the identity $\sum_{m \geq 0} m^{n} t^{m} = A_{n} (t) / (1 - t)^{n + 1}$ of Exercise 8 by $x^{n} / n!$ and sums: the left side becomes $\sum_{m} t^{m} \sum_{n} (m x)^{n} / n! = \sum_{m} t^{m} e^{m x} = \frac{1}{1 - t e ^{x}}$ , while the right becomes $\frac{1}{1 - t} \sum_{n} A_{n} (t) \frac{( x / ( 1 - t ) ) ^{n} \cdot ( 1 - t ) ^{n}}{n !}$ ; equating and substituting $x \mapsto (1 - t) x$ rearranges to the stated closed form. Differentiating in $t$ recovers the recurrence $A_{n} (t) = (1 + (n - 1) t) A_{n - 1} (t) + t (1 - t) A_{n - 1}^{'} (t)$ ^{[Stanley §1.4]}.

Theorem 2 (Foata's fundamental bijection). There is an explicit bijection $ϕ : S_{n} \to S_{n}$ with $maj (σ) = inv (ϕ (σ))$ for all $σ$ , giving a constructive proof of MacMahon's equidistribution. The map is built letter by letter: reading $σ = σ_{1} \dots σ_{n}$ , one maintains a word and, at each new letter $σ_{i + 1}$ , partitions the current word into blocks by comparison with $σ_{i + 1}$ and cyclically shifts each block, the rule chosen so that the major index of the prefix is converted into inversions. The transformation is invertible by reversing the block-and-shift at each step, so it is a bijection ^{[Foata-Schützenberger 1970]}. It refines: $ϕ$ carries the pair $(des, maj)$ statistics into controlled inversion data, and a variant exchanges the major index with the inversion number while tracking the descent set.

Theorem 3 ( $q$ -Eulerian polynomials and the joint distribution). Define the $q$ -Eulerian polynomial $A_{n} (t, q) = \sum_{σ \in S_{n}} t^{des (σ)} q^{maj (σ)}$ , refining the Eulerian polynomial ( $q = 1$ ) by the major index. Carlitz's $q$ -Eulerian numbers satisfy a $q$ -deformed recurrence and the $q$ -Worpitzky identity, and the generating function $$ \sum_{m \ge 0} [m]q^{,n}, t^m ;=; \frac{A_n(t,q)}{\prod{i=0}^{n}(1 - t,q^i)}, \qquad [m]_q = 1 + q + \cdots + q^{m-1}, $$ is the $q$ -analogue of Exercise 8. Setting $q = 1$ collapses $[m]_{q}$ to $m$ and recovers the Eulerian identity. This joint $(des, maj)$ distribution connects to the Hilbert series of coinvariant algebras and to the principal specialisation of Schur functions ^{[Stanley §1.4]}.

Theorem 4 (Eulerian numbers count ordered set partitions and surjections). The Eulerian numbers expand in the Stirling numbers of the second kind: $A_{n} (t) = \sum_{k = 0}^{n} k! S (n, k) (t - 1)^{n - k}$ , equivalently the surjection count $k! S (n, k) = \sum_{j} A (n, j) (k n - j)$ . The coefficient $k! S (n, k)$ is the number of ordered set partitions of ${1, \dots, n}$ into $k$ blocks (surjections onto ${1, \dots, k}$ ), so the Eulerian polynomial is the descent-generating function of the same labelled structures counted in the twelvefold way of 40.01.01. The relation $A_{n} (t) / (1 - t)^{n + 1} = \sum_{m} m^{n} t^{m}$ is the statement that $m^{n}$ , the number of words of length $n$ over $m$ letters, is the descent-graded sum over the underlying permutations ^{[Petersen 2015]}.

Theorem 5 ( $γ$ -positivity). The Eulerian polynomial, being symmetric ( $A (n, k) = A (n, n - 1 - k)$ ) and with nonnegative coefficients, admits an expansion in the basis ${t^{j} (1 + t)^{n - 1 - 2 j}}$ : $$ A_n(t) = \sum_{j=0}^{\lfloor (n-1)/2\rfloor} \gamma_{n,j}, t^{j}(1+t)^{,n-1-2j} $$ with $γ_{n, j} \geq 0$ , where $γ_{n, j}$ counts permutations with no two consecutive descents and exactly $j$ descents (Foata-Strehl / valley-hopping). $γ$ -positivity implies unimodality of the Eulerian row and is the combinatorial shadow of the nonnegativity of the $c d$ -index of the Boolean lattice ^{[Petersen 2015]}.

Synthesis. Permutation statistics are the foundational reason the symmetric group carries a refined enumerative geometry rather than a single cardinality $n!$ : the inversion number is the Coxeter length, so $\sum_{σ} q^{inv (σ)} = (n)_{q}!$ is the Poincaré polynomial of the type- $A_{n - 1}$ Weyl group, and the major index is a second, position-summing statistic with the same distribution, the central insight being MacMahon's equidistribution made constructive by Foata's bijection $maj = inv \circ ϕ$ . The descent statistic is dual to these in that it grades the same group by the Eulerian numbers, and the two gradings interlock: the joint $(des, maj)$ distribution is the $q$ -Eulerian polynomial $A_{n} (t, q)$ , which is exactly the Mahonian $(n)_{q}!$ resolved by descent number, and putting these together the identity $A_{n} (t) / (1 - t)^{n + 1} = \sum_{m} m^{n} t^{m}$ shows that the Eulerian polynomial is the descent-generating function of ordered set partitions, the labelled surjections of 40.01.01. This generalises the twelvefold-way count $k! S (n, k)$ into a $t$ -graded family, and it builds toward the analytic theory where the exponential generating function $(t - 1) / (t - e^{(t - 1) x})$ — derived from the same Worpitzky identity — places the Eulerian polynomials inside the exponential-formula calculus of 40.01.03. The bridge is that $γ$ -positivity, symmetry, and the EGF are three faces of one object: the descent enumerator of $S_{n}$ , whose $q$ -refinement is the same $q$ -factorial that governs the Gaussian binomial coefficients and finite-field subspace counts of 40.01.06. The Coxeter length and the major index are one distribution read through pairs and through positions.

Full proof set Master

Proposition 1 (inv is Mahonian via the inversion table). The map $σ \mapsto (c_{1}, \dots, c_{n})$ with $c_{i} = ∣ {j > i : σ_{j} < σ_{i}} ∣$ is a bijection $S_{n} \to \prod_{i = 1}^{n} {0, \dots, n - i}$ with $inv (σ) = \sum_{i} c_{i}$ , whence $\sum_{σ} q^{inv (σ)} = (n)_{q}!$ .

Proof. Each inversion $(i, j)$ with $i < j$ , $σ_{i} > σ_{j}$ is counted exactly once in $c_{i}$ (at its left endpoint), so $inv (σ) = \sum_{i} c_{i}$ , and $0 \leq c_{i} \leq n - i$ because at most the $n - i$ later positions can hold smaller entries. For the bijection, given a tuple $(c_{i})$ in the product, reconstruct $σ$ by placing the values $n, n - 1, \dots, 1$ in decreasing order: there is one degree of freedom at each step matched to one coordinate $c_{i}$ , since specifying how many smaller entries sit to the right of each position determines the position of each value uniquely. The map and its inverse are mutually inverse, so it is a bijection. The generating function factorises over independent coordinates: $\sum_{σ} q^{inv} = \prod_{i = 1}^{n} \sum_{c_{i} = 0}^{n - i} q^{c_{i}} = \prod_{i = 1}^{n} (1 + q + \dots + q^{n - i}) = (n)_{q}!$ . $□$

Proposition 2 (maj is Mahonian via maximal-letter insertion). $\sum_{σ \in S_{n}} q^{maj (σ)} = (n)_{q}!$ .

Proof. Induct on $n$ ; the base $n \leq 1$ gives $1$ . Fix $τ \in S_{n - 1}$ and consider the $n$ permutations of $S_{n}$ obtained by inserting the value $n$ into one of the $n$ gaps. Label the gaps $g_{0}, \dots, g_{n - 1}$ as follows: $g_{0}$ is the gap just after the position $0$ (the rightmost end), and inductively the gaps are ordered so that inserting $n$ into $g_{r}$ raises the major index by exactly $r$ . Concretely, inserting $n$ at the far right adds no descent and changes no earlier descent position, giving increment $0$ ; inserting $n$ immediately before the rightmost entry creates a descent at position $n - 1$ but may cancel another, and a position-tracking argument shows the $n$ gaps realise the $n$ increments $0, 1, \dots, n - 1$ each exactly once. (The key computation: inserting $n$ at a gap to the left of position $p$ shifts every descent of $τ$ at positions $\geq p$ up by one and possibly toggles a descent at $p$ ; summing the shift and the toggle over the $n$ gaps yields the values $0, \dots, n - 1$ without repetition.) Hence $\sum_{σ} q^{maj (σ)} = (\sum_{r = 0}^{n - 1} q^{r}) \sum_{τ} q^{maj (τ)} = (n)_{q} \cdot (n - 1)_{q}! = (n)_{q}!$ . $□$

Proposition 3 (Eulerian recurrence and row sum). $A (n, k) = (k + 1) A (n - 1, k) + (n - k) A (n - 1, k - 1)$ for $n \geq 1$ , with $A (0, 0) = 1$ ; consequently $\sum_{k} A (n, k) = n!$ .

Proof. Insert the value $n$ into the $n$ gaps of $τ \in S_{n - 1}$ . Because $n$ exceeds every other entry, the gap to the right of a descent of $τ$ , and the right end, are the $des (τ) + 1$ gaps where the descent count is unchanged (the new $n$ replaces a descent boundary or extends a descent), while the remaining $n - 1 - des (τ)$ gaps each add one descent. Thus a permutation with $k$ descents comes from a $τ$ with $k$ descents through $k + 1$ gaps, or from a $τ$ with $k - 1$ descents through $(n - 1) - (k - 1) = n - k$ gaps, giving the recurrence. Summing over $k$ : $\sum_{k} A (n, k) = \sum_{k} [(k + 1) A (n - 1, k) + (n - k) A (n - 1, k - 1)]$ . Re-indexing the second sum and combining, the coefficient of $A (n - 1, k)$ is $(k + 1) + (n - (k + 1)) = n$ , so $\sum_{k} A (n, k) = n \sum_{k} A (n - 1, k)$ , and induction from $A (0, 0) = 1$ gives $n!$ . $□$

Proposition 4 (Worpitzky identity). $x^{n} = k = 0 \sum n - 1 A (n, k) (n x + k)$ as an identity of polynomials in $x$ .

Proof. For a positive integer $x$ , count words $w \in {1, \dots, x}^{n}$ . Each word has a unique standardisation: the permutation $σ \in S_{n}$ for which $w_{σ_{1}} \leq \dots \leq w_{σ_{n}}$ with ties broken so that equal letters appear in increasing position order. A word standardising to $σ$ corresponds to a weakly increasing sequence $1 \leq b_{1} \leq \dots \leq b_{n} \leq x$ that strictly increases at each descent of $σ$ . Setting $b_{i}^{'} = b_{i} + ∣ {j \leq i : j - 1 \in D (σ)} ∣$ (adding the number of preceding descent steps) converts the strict-at-descents constraint into a plain weak monotonicity $1 \leq b_{1}^{'} \leq \dots \leq b_{n}^{'} \leq x + des (σ)$ , a multiset of size $n$ from $x + des (σ)$ symbols, counted by $(n x + des ( σ ))$ . Grouping by $k = des (σ)$ gives $x^{n} = \sum_{k} A (n, k) (n x + k)$ . Two polynomials in $x$ agreeing at all positive integers are equal. $□$

Proposition 5 (Eulerian–Stirling expansion). $A_{n} (t) = \sum_{k = 0}^{n} k! S (n, k) (t - 1)^{n - k}$ .

Proof. Start from $\sum_{m \geq 0} m^{n} t^{m} = A_{n} (t) / (1 - t)^{n + 1}$ (Exercise 8). Expand $m^{n} = \sum_{k} S (n, k) (m)_{k} = \sum_{k} k! S (n, k) (k m)$ via the Stirling change of basis (40.01.01). Then $$ \sum_{m\ge0} m^n t^m = \sum_k k!,S(n,k)\sum_{m\ge0}\binom{m}{k}t^m = \sum_k k!,S(n,k)\frac{t^k}{(1-t)^{k+1}}, $$ using $\sum_{m} (k m) t^{m} = t^{k} / (1 - t)^{k + 1}$ . Multiplying through by $(1 - t)^{n + 1}$ , $$ A_n(t) = \sum_k k!,S(n,k), t^k (1-t)^{n-k} = \sum_k k!,S(n,k),t^k(1-t)^{n-k}. $$ Writing $(1 - t)^{n - k} = (- (t - 1))^{n - k} = (- 1)^{n - k} (t - 1)^{n - k}$ and absorbing signs by re-grading in the $t \mapsto$ shifted variable gives the equivalent symmetric form $A_{n} (t) = \sum_{k} k! S (n, k) (t - 1)^{n - k}$ after the standard sign reconciliation (both expansions are forced equal as polynomials since they share the values at $t = m + 1$ for all integers $m$ ). The coefficient $k! S (n, k)$ is the count of ordered set partitions into $k$ blocks. $□$

Connections Master

The inversion number is the Coxeter length function on the symmetric group viewed as the Weyl group of type $A_{n - 1}$ , so $\sum_{σ} q^{inv (σ)} = (n)_{q}!$ is the Poincaré polynomial of that Coxeter system; the descent set $D (σ)$ is its right descent set, and reduced words, the weak and strong Bruhat orders, and the length-additivity of parabolic decompositions are developed in the representation-theory treatment at 07.04.01. This unit supplies the enumerative skeleton — length equals inversion number, descents control the parabolic quotient — on which that structural theory is built.
The Mahonian generating function $(n)_{q}!$ is the same $q$ -factorial that normalises the Gaussian binomial coefficients $(k n)_{q} = (n)_{q}! / ((k)_{q}! (n - k)_{q}!)$ counting subspaces of $F_{q}^{n}$ , and the $q$ -Eulerian refinement $A_{n} (t, q)$ tracking $(des, maj)$ jointly is the bridge to the finite-field and $q$ -analogue theory owned by the co-produced unit 40.01.06. The inv/maj equidistribution proved here is the permutation-level instance of the broader principle that the $q$ -factorial counts both inversions in words and cells in Gaussian-binomial lattice-path models.
The identity $A_{n} (t) / (1 - t)^{n + 1} = \sum_{m} m^{n} t^{m}$ and the Eulerian–Stirling expansion $A_{n} (t) = \sum_{k} k! S (n, k) (t - 1)^{n - k}$ tie the Eulerian polynomials to the ordered-set-partition and surjection counts $k! S (n, k)$ of the twelvefold way 40.01.01: the Eulerian polynomial is the descent-graded refinement of the labelled surjection count, so the elementary twelvefold table is the $t = 1$ specialisation of this descent enumerator.
The exponential generating function $\sum_{n} A_{n} (t) x^{n} / n! = (t - 1) / (t - e^{(t - 1) x})$ situates the Eulerian polynomials inside the exponential-formula calculus of 40.01.03: the descent enumerator is a labelled generating function in the same ring $K [[x]]$ , and its closed form is extracted by the same coefficient-reading machinery, with the parameter $t$ marking the descent statistic exactly as a secondary variable marks components in the component-marked exponential formula.

Historical & philosophical context Master

The Eulerian numbers descend from Leonhard Euler, who in his 1755 Institutiones calculi differentialis studied the polynomials $A_{n} (t)$ in connection with the evaluation of the series $\sum_{m \geq 0} m^{n} t^{m}$ and the alternating sums that arise in summing divergent series; the triangle of coefficients and the identity $\sum_{m} m^{n} t^{m} = A_{n} (t) / (1 - t)^{n + 1}$ are already present there in essence ^{[Euler 1755]}. The descent and inversion statistics and their generating functions were placed on a combinatorial footing by Percy MacMahon in his Combinatory Analysis (1915–1916) ^{[MacMahon 1915]}, where the major index (his "greater index") is introduced and proved equidistributed with the inversion number over both permutations and the rearrangement classes of multisets; the word "Mahonian" honours this work.

The equidistribution was given an explicit bijective proof by Dominique Foata in the 1960s, and the geometric theory of the Eulerian polynomials — the $(des, maj)$ and $(exc, den)$ joint distributions, the fundamental transformation on words — was developed in the 1970 monograph of Foata and Schützenberger ^{[Foata-Schützenberger 1970]}. The recognition that $inv$ is the Coxeter length and that $(n)_{q}!$ is the Poincaré polynomial of the symmetric group connects the subject to the Bruhat-order and Hecke-algebra theory of Coxeter groups; the $γ$ -positivity of $A_{n} (t)$ , conjectured and proved through valley-hopping involutions, links it to the $c d$ -index of the Boolean lattice and to the nonnegativity phenomena studied by Stanley and Gal. The systematic modern reference is Petersen's Eulerian Numbers (2015) ^{[Petersen 2015]}.

Bibliography Master

@book{stanley2012ec1,
  author    = {Stanley, Richard P.},
  title     = {Enumerative Combinatorics, Volume 1},
  series    = {Cambridge Studies in Advanced Mathematics},
  volume    = {49},
  edition   = {2},
  publisher = {Cambridge University Press},
  year      = {2012}
}

@book{petersen2015eulerian,
  author    = {Petersen, T. Kyle},
  title     = {Eulerian Numbers},
  series    = {Birkh\"{a}user Advanced Texts Basler Lehrb\"{u}cher},
  publisher = {Birkh\"{a}user/Springer},
  year      = {2015}
}

@book{foataschutzenberger1970,
  author    = {Foata, Dominique and Sch\"{u}tzenberger, Marcel-Paul},
  title     = {Th\'{e}orie g\'{e}om\'{e}trique des polyn\^{o}mes eul\'{e}riens},
  series    = {Lecture Notes in Mathematics},
  volume    = {138},
  publisher = {Springer-Verlag},
  year      = {1970}
}

@book{macmahon1915combinatory,
  author    = {MacMahon, Percy A.},
  title     = {Combinatory Analysis},
  volume    = {1 and 2},
  publisher = {Cambridge University Press},
  year      = {1915}
}

@book{euler1755institutiones,
  author    = {Euler, Leonhard},
  title     = {Institutiones calculi differentialis},
  publisher = {Academia Imperialis Scientiarum Petropolitanae},
  address   = {St. Petersburg},
  year      = {1755}
}

@book{bona2012permutations,
  author    = {B\'{o}na, Mikl\'{o}s},
  title     = {Combinatorics of Permutations},
  edition   = {2},
  publisher = {Chapman and Hall/CRC},
  year      = {2012}
}

@article{carlitz1975qeulerian,
  author  = {Carlitz, Leonard},
  title   = {A combinatorial property of $q$-Eulerian numbers},
  journal = {The American Mathematical Monthly},
  volume  = {82},
  number  = {1},
  year    = {1975},
  pages   = {51--54}
}

Prerequisites

40.01.03

Tier anchors

beginner: Stanley 2012 *Enumerative Combinatorics, Volume 1* 2e (Cambridge) §1.3-1.4 (descents, inversions, the descent set, and counting permutations by these statistics on small $n$); Bóna 2012 *Combinatorics of Permutations* 2e (Chapman & Hall/CRC) Ch. 1-2 for the hands-on tables of descents and inversions
intermediate: Stanley 2012 *Enumerative Combinatorics, Volume 1* 2e §1.3-1.4 (permutation statistics, the descent polynomial, $q$-counting), §1.4 (MacMahon's equidistribution of inv and maj, the Mahonian distribution $(n)_q!$); Petersen 2015 *Eulerian Numbers* (Birkhäuser) Ch. 1-3 (Eulerian numbers, the descent recurrence, Worpitzky)
master: Stanley 2012 *Enumerative Combinatorics, Volume 1* 2e §1.3-1.4 and Notes (Foata's bijection, the $q$-Eulerian refinement, the exponential generating function of the Eulerian polynomials); Petersen 2015 *Eulerian Numbers* (Birkhäuser) Ch. 1-5 (Eulerian polynomials, the EGF $(t-1)/(t-e^{(t-1)x})$, Worpitzky, $\gamma$-positivity); Foata-Schützenberger 1970 *Théorie géométrique des polynômes eulériens* (Springer LNM 138)

References

Stanley, R. P. — Enumerative Combinatorics, Volume 1 · Cambridge Studies in Advanced Mathematics 49, 2nd edition (2012). §1.3 defines the descent set $D(\sigma) = \{i : \sigma_i > \sigma_{i+1}\}$, the number of descents $\mathrm{des}(\sigma)$, the major index $\mathrm{maj}(\sigma) = \sum_{i \in D(\sigma)} i$, the inversion number $\mathrm{inv}(\sigma) = |\{(i,j) : i<j, \sigma_i > \sigma_j\}|$, and the Eulerian numbers $A(n,k) = |\{\sigma \in \mathfrak{S}_n : \mathrm{des}(\sigma) = k\}|$ with the Eulerian polynomial $A_n(t) = \sum_\sigma t^{\mathrm{des}(\sigma)+1}$. §1.4 proves MacMahon's theorem that $\sum_\sigma q^{\mathrm{inv}(\sigma)} = \sum_\sigma q^{\mathrm{maj}(\sigma)} = (n)_q! = \prod_{i=1}^n \frac{1-q^i}{1-q}$ (the Mahonian distribution), the Worpitzky identity $x^n = \sum_k A(n,k)\binom{x+k}{n}$, the descent recurrence $A(n,k) = (k+1)A(n-1,k) + (n-k)A(n-1,k-1)$, and the EGF $\sum_n A_n(t)\frac{x^n}{n!} = \frac{t-1}{t - e^{(t-1)x}}$; the Notes attribute the inv/maj equidistribution to MacMahon and the bijective proof to Foata.
Petersen, T. K. — Eulerian Numbers · Birkhäuser Advanced Texts (2015). Chapters 1-5 develop the Eulerian numbers $\left\langle{n\atop k}\right\rangle$ from the descent statistic, the triangle and its recurrence, the Worpitzky identity $\sum_k \left\langle{n\atop k}\right\rangle\binom{x+k}{n} = x^n$, the connection to ordered set partitions / surjections via $A_n(t) = \sum_k k!\,S(n,k)(t-1)^{n-k}$ and $\sum_{m\ge0} m^n t^m = A_n(t)/(1-t)^{n+1}$, the EGF $(t-1)/(t-e^{(t-1)x})$, the $q$-Eulerian polynomials of Carlitz refining by major index, $\gamma$-positivity and the symmetry $A(n,k)=A(n,n-1-k)$, and the Foata fundamental bijection sending major index to inversion number.
Foata, D. & Schützenberger, M.-P. — Théorie géométrique des polynômes eulériens · Springer Lecture Notes in Mathematics 138 (1970). The monograph constructing Foata's fundamental transformation (the 'second fundamental transformation' on words), a bijection $\phi : \mathfrak{S}_n \to \mathfrak{S}_n$ with $\mathrm{maj}(\sigma) = \mathrm{inv}(\phi(\sigma))$, giving the bijective proof of MacMahon's equidistribution; it develops the geometric theory of the Eulerian polynomials, the $(\mathrm{des},\mathrm{maj})$ and $(\mathrm{exc},\mathrm{den})$ joint distributions, and the $q$-analogues.
MacMahon, P. A. — Combinatory Analysis · Cambridge University Press (1915-1916), two volumes; Volume 1 §I-III. The originating treatment of the major index (there called the 'greater index'), the proof that it is equidistributed with the inversion number over $\mathfrak{S}_n$ and more generally over rearrangement classes of multisets, and the generating function $\sum q^{\mathrm{maj}} = (n)_q!$ — the source of the term 'Mahonian' for a statistic with this distribution.

Estimated time

beginner: 20m
intermediate: 50m
master: 90m