Permutation Statistics, Inversions and Eulerian Numbers

For $\sigma \in S_n$, the component ${\mathrm{\ell }}_i(\sigma )$ counts entries to the right of position $n-i$, and there are exactly $i-1$ such positions, so $0\le {\mathrm{\ell }}_i(\sigma )\le i-1$. Thus $L(\sigma )$ lies in the stated codomain.

Conversely, let $(c_1,\dots ,c_n)$ lie in the codomain. Begin with the increasing list $R=[0,1,\dots ,n-1]$ of unused values. For $i=n,n-1,\dots ,1$, put in position $n-i$ the value of $R$ having exactly $c_i$ smaller elements in $R$, and delete that value from $R$. This choice exists and is unique because $R$ has $i$ elements and $0\le c_i<i$. Call the resulting permutation ${\sigma }_c$.

The permutation ${\sigma }_c$ has Lehmer code $(c_1,\dots ,c_n)$. At the stage for $i$, all values then left in $R$ will occupy the $i-1$ positions to the right of position $n-i$. The chosen value has exactly $c_i$ smaller values in $R$, so exactly $c_i$ later entries of ${\sigma }_c$ are smaller than it. This is the defining equality ${\mathrm{\ell }}_i({\sigma }_c)=c_i$.

The construction is unique. At position $0$, all $n$ values are unused and the code coordinate $c_n$ requires the entry with exactly $c_n$ smaller unused values. After deleting it, coordinate $c_{n-1}$ uniquely determines the next entry among the remaining values, and so on. Thus any permutation with code $c$ is exactly ${\sigma }_c$. Step 2.1 gives surjectivity and this uniqueness gives injectivity.

Therefore $L$ is a bijection. The case $n=0$ is included: both sides are the singleton empty object.

By [L1], $\mathrm{\mid }{S}_n\mathrm{\mid }$ equals the cardinality of ${\prod }_{i=1}^n\{0,\dots ,i-1\}$. The $i$-th factor has cardinality $i$, so repeated use of [L2] shows that the whole product has cardinality $1\cdot 2\cdots n=n!$.

Therefore $\mathrm{\mid }{S}_n\mathrm{\mid }=n!$. For $n=0$, both sides equal $1$ because the codomain is the empty product.

For $\sigma \in S_n$ with Lehmer code $L(\sigma )=({\mathrm{\ell }}_1,\dots ,{\mathrm{\ell }}_n)$, the inversion number is $\mathrm{inv}(\sigma )={\mathrm{\ell }}_1+\cdots +{\mathrm{\ell }}_n$: the component ${\mathrm{\ell }}_i$ counts exactly the inversions whose left entry is the position $n-i$.

By [L1] and step 1.1, ${\sum }_{\sigma \in S_n}{q}^{\mathrm{inv}(\sigma )}={\sum }_{({\mathrm{\ell }}_1,\dots ,{\mathrm{\ell }}_n)}{q}^{{\mathrm{\ell }}_1+\cdots +{\mathrm{\ell }}_n}={\prod }_{i=1}^n{\sum }_{j=0}^{i-1}{q}^j={\prod }_{i=1}^n[i{]}_q=[n{]}_q!$.

This is the claimed generating function identity. At $n=0$, both sides are $1$.

For a word $v$ and a letter $x$, define ${\delta }_x(v)$ by the inverse block rule: if the first letter of $v$ is $\le x$, cut $v$ immediately before each later letter $\le x$; if the first letter is $>x$, cut immediately before each later letter $>x$; in each block move the first letter to the end. This undoes ${\gamma }_x$, because ${\gamma }_x$ and ${\delta }_x$ use the same distinguished letters to recover the same blocks and then reverse the same cyclic move within each block.

Define a recursive map $\mathrm{\Psi }$ by $\mathrm{\Psi }(ϵ)=ϵ$ and $\mathrm{\Psi }(vx)=\mathrm{\Psi }({\delta }_x(v))x$, where $x$ is the last letter. Induction on word length, using step 1.1 at the last recursive step, gives $\mathrm{\Psi }(\mathrm{\Phi }(w))=w=\mathrm{\Phi }(\mathrm{\Psi }(w))$ for every permutation word $w$. Hence $\mathrm{\Psi }$ is a two-sided inverse to $\mathrm{\Phi }$.

A map with a two-sided inverse is bijective by [L1], so $\mathrm{\Phi }$ is a bijection on $S_n$ for every $n$.

For the empty word and for a one-letter word, both the major index and the inversion number are $0$. Assume inductively that $\mathrm{inv}(\mathrm{\Phi }(w))=\mathrm{maj}(w)$ for a word $w$ of length $m$, and write $r:=\mathrm{\Phi }(w)$. By definition, $\mathrm{\Phi }(wx)={\gamma }_x(r)x$.

Suppose the last letter of $w$ is $\le x$; equivalently, the last letter of $r$ is $\le x$. Then the blocks of ${\gamma }_x(r)$ have the form $U_j{y}_j$ with every letter of $U_j$ strictly greater than $x$ and $y_j\le x$. Moving $y_j$ to the front removes exactly $\mathrm{\mid }{U}_j\mathrm{\mid }$ inversions inside that block, while appending $x$ at the end creates exactly $\mathrm{\mid }{U}_j\mathrm{\mid }$ inversions with those same letters and no others. So $\mathrm{inv}(\mathrm{\Phi }(wx))=\mathrm{inv}(r)$. In this case no new descent is created at the end of $w$, so $\mathrm{maj}(wx)=\mathrm{maj}(w)$.

Suppose instead that the last letter of $w$ is $>x$. Then the blocks of ${\gamma }_x(r)$ have the form $U_j{y}_j$ with every letter of $U_j$ at most $x$ and $y_j>x$. Moving $y_j$ to the front creates exactly $\mathrm{\mid }{U}_j\mathrm{\mid }$ new inversions inside that block, and appending $x$ at the end creates one more inversion with each terminal letter $y_j$. Summing over all blocks gives $\mathrm{inv}(\mathrm{\Phi }(wx))=\mathrm{inv}(r)+m$, because the block lengths add up to $m$. In this case appending $x$ creates a new descent at the last position of $w$, so $\mathrm{maj}(wx)=\mathrm{maj}(w)+m$.

The two cases of steps 2.1 and 2.2 are exhaustive, and in each one the change in inversion number equals the change in major index. The inductive hypothesis from step 1.1 therefore gives $\mathrm{inv}(\mathrm{\Phi }(wx))=\mathrm{maj}(wx)$.

By induction on word length, $\mathrm{inv}(\mathrm{\Phi }(\sigma ))=\mathrm{maj}(\sigma )$ for every permutation $\sigma$.

By [L0], Foata's transformation is a bijection of $S_n$, so reindexing the sum over $S_n$ by $\mathrm{\Phi }$ and using [L1] gives ${\sum }_{\sigma \in S_n}{q}^{\mathrm{maj}(\sigma )}={\sum }_{\sigma \in S_n}{q}^{\mathrm{inv}(\sigma )}$.

Apply [L2] to the right-hand side.

For every cycle and every $0\le j<r_t-1$, the cycle notation means $\sigma (a_{t,j})=a_{t,j+1}$. Therefore $a_{t,j}$ is an anti-excedance of $\sigma$ exactly when $a_{t,j+1}<a_{t,j}$, which is exactly the condition that the adjacent pair $(a_{t,j},a_{t,j+1})$ contributes a descent in the stripped word $w$.

Across cycle boundaries, the stripped word has no descent: the last entry of cycle $t$ is followed by the first entry $a_{t+1,0}$ of cycle $t+1$, and the standard cycle form orders these first entries increasingly, so $a_{t,r_t-1}<a_{t+1,0}$.

The last entry $a_{t,r_t-1}$ of a cycle is never an anti-excedance, because $\sigma (a_{t,r_t-1})=a_{t,0}$ and $a_{t,0}$ is the largest element of the cycle.

By steps 1.1, 2.1 and 1.2, the descents of $w$ occur exactly at the entries of $w$ that are anti-excedances of $\sigma$. Counting them gives $\mathrm{des}(w)=\mathrm{\mid }\mathrm{AExc}(\sigma )\mathrm{\mid }$.

Define $\tau :=c\circ \sigma \circ c$. Then, for every $i\in n$, $\tau (i)<i$ if and only if $c(\sigma (c(i)))<i$, which is equivalent to $\sigma (c(i))>c(i)$. Thus $i$ is an anti-excedance of $\tau$ exactly when $c(i)$ is an excedance of $\sigma$, so $\mathrm{\mid }\mathrm{AExc}(\tau )\mathrm{\mid }=\mathrm{exc}(\sigma )$.

The map $\sigma \mapsto \tau =c\circ \sigma \circ c$ is a bijection of $S_n$, because conjugation by a permutation has inverse itself. Also $\mathcal{F}$ is a bijection: from a one-line word, insert a left parenthesis before each left-to-right maximum and a closing parenthesis just before the next such maximum, or at the end, to recover the standard cycle form.

By [L1], $\mathrm{des}(\mathcal{F}(\tau ))=\mathrm{\mid }\mathrm{AExc}(\tau )\mathrm{\mid }$, which equals $\mathrm{exc}(\sigma )$ by step 1.1. Since step 1.2 makes $\sigma \mapsto \mathcal{F}(c\sigma c)$ a bijection of $S_n$, the statistics $\mathrm{des}$ and $\mathrm{exc}$ are equidistributed.

For every $0\le i\le n-2$, one has $R(\sigma )(i)>R(\sigma )(i+1)$ exactly when $\sigma (i)<\sigma (i+1)$. Thus the descent set of $R(\sigma )$ is the complement of the descent set of $\sigma$ in $\{0,\dots ,n-2\}$, and $\mathrm{des}(R(\sigma ))=n-1-\mathrm{des}(\sigma )$.

The map $R$ is a bijection of $S_n$, since applying it twice returns the original permutation. Therefore the number of permutations with $k$ descents equals the number with $n-1-k$ descents, which is exactly the displayed symmetry of the Eulerian numbers.

Take a permutation $\pi \in S_{n-1}$ and insert the new largest letter $n-1$ into one of the $n$ slots of its one-line notation. If a slot lies after a descent of $\pi$, or is the final slot, then the insertion preserves the number of descents: one old descent is replaced by one new descent, or no descent is created at the end. Every other slot creates one new descent.

If $\pi$ has exactly $k$ descents, step 1.1 gives exactly $k+1$ insertion slots producing a permutation of $S_n$ with $k$ descents. If $\pi$ has exactly $k-1$ descents, the remaining $n-k$ slots produce a permutation with $k$ descents. These two cases are disjoint and exhaust the permutations of $S_n$ with $k$ descents.

Counting the two cases of step 2.1 gives $A(n,k)=(k+1)A(n-1,k)+(n-k)A(n-1,k-1)$. The out-of-range convention makes the same formula correct at the boundary values of $k$.

For $n=1$, [L3] makes the right-hand side $\left(\genfrac{}{}{0px}{}{m}{1}\right)=m=m^1$.

Assume the identity at $n-1$, where $n\ge 2$, and write $W_n(m):={\sum }_{k=0}^{n-1}A(n,k)\left(\genfrac{}{}{0px}{}{m+k}{n}\right)$.

Using [L1] and shifting the second sum, $W_n(m)={\sum }_{k=0}^{n-2}A(n-1,k)((k+1)\left(\genfrac{}{}{0px}{}{m+k}{n}\right)+(n-k-1)\left(\genfrac{}{}{0px}{}{m+k+1}{n}\right))$.

Fix $k$ from step 2.1 and put $M:=m+k$. If $n>M+1$, then [L2] gives $\left(\genfrac{}{}{0px}{}{M}{n}\right)=\left(\genfrac{}{}{0px}{}{M+1}{n}\right)=\left(\genfrac{}{}{0px}{}{M}{n-1}\right)=0$, so the bracket in step 2.1 is $0=m\left(\genfrac{}{}{0px}{}{M}{n-1}\right)$. If $n=M+1$, then $\left(\genfrac{}{}{0px}{}{M}{n}\right)=0$, $\left(\genfrac{}{}{0px}{}{M+1}{n}\right)=1$, and $\left(\genfrac{}{}{0px}{}{M}{n-1}\right)=1$, so the same bracket is $(n-k-1)=m=m\left(\genfrac{}{}{0px}{}{M}{n-1}\right)$. Finally, if $n\le M$, then Pascal's rule from [L2] gives $(n-k-1)\left(\genfrac{}{}{0px}{}{M+1}{n}\right)=(n-k-1)\left(\genfrac{}{}{0px}{}{M}{n}\right)+(n-k-1)\left(\genfrac{}{}{0px}{}{M}{n-1}\right)$, and the closed-form identity from [L2] gives $n\left(\genfrac{}{}{0px}{}{M}{n}\right)=(M+1-n)\left(\genfrac{}{}{0px}{}{M}{n-1}\right)=(m+k+1-n)\left(\genfrac{}{}{0px}{}{M}{n-1}\right)$. Substituting into the bracket of step 2.1 yields $m\left(\genfrac{}{}{0px}{}{M}{n-1}\right)$. So in every case that bracket simplifies to $m\left(\genfrac{}{}{0px}{}{m+k}{n-1}\right)$.

Steps 2.1 and 3.1 give $W_n(m)=m{\sum }_{k=0}^{n-2}A(n-1,k)\left(\genfrac{}{}{0px}{}{m+k}{n-1}\right)$, and the inductive hypothesis of step 1.2 makes this $m\cdot m^{n-1}=m^n$.

This is the required identity.

Summing [L1] against $t^k$ gives the polynomial recurrence $A_n(t)=(1+(n-1)t)A_{n-1}(t)+t(1-t)A_{n-1}^{\mathrm{\prime }}(t)$.

Let $F(x,t):={\sum }_{n\ge 0}{A}_n(t)x^n\mathrm{/}n!\in \mathbb{Q}(t)\mathrm{⟦}x\mathrm{⟧}$. Differentiating termwise in $x$ and using step 1.1 yields $(1-tx){\mathrm{\partial }}_{x}F=F+t(1-t){\mathrm{\partial }}_{t}F$, with initial condition $F(0,t)=1$.

Put $G(x,t):=(t-1)\mathrm{/}(t-e^{(t-1)x})\in \mathbb{Q}(t)\mathrm{⟦}x\mathrm{⟧}$; this is well defined because the denominator has nonzero constant term $t-1$ in the coefficient field $\mathbb{Q}(t)$. Direct formal differentiation shows that $G$ satisfies the same differential equation and the same initial condition as $F$. Since the recurrence of step 1.1 determines the coefficient of $x^n$ from lower degrees uniquely, the formal solution is unique, so $F=G$.

Therefore ${\sum }_{n\ge 0}{A}_n(t)x^n\mathrm{/}n!=(t-1)\mathrm{/}(t-e^{(t-1)x})$.

The table is an exhaustive enumeration of the $24$ one-line permutations of $S_4$, with each statistic computed directly from its definition.

Reading off the distributions from the table gives $1+3q+5q^2+6q^3+5q^4+3q^5+q^6$ for inversions, the same polynomial for the major index, and $(1,11,11,1)$ for both descents and excedances. This matches the three cited theorems.

Every code vector has the form $(0,a,b,c)$ with $a\in \{0,1\}$, $b\in \{0,1,2\}$, and $c\in \{0,1,2,3\}$, so there are $24$ of them. Counting by the sum $a+b+c$ gives the coefficient sequence $1,3,5,6,5,3,1$.

Therefore ${\sum }_{\sigma \in S_4}{q}^{\mathrm{inv}(\sigma )}=1+3q+5q^2+6q^3+5q^4+3q^5+q^6$, which matches [L1].