Permutation Statistics, Inversions and Eulerian Numbers: Examples and Counterexamples

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].

Applying the recursion step by step gives $\mathrm{\Phi }([2])=[2]$, then $\mathrm{\Phi }([2,0])=[2,0]$, then $\mathrm{\Phi }([2,0,3])=[2,0,3]$, and finally $\mathrm{\Phi }([2,0,3,1])=[2,3,0,1]$.

The original permutation has descents at positions $0$ and $2$, so $\mathrm{maj}([2,0,3,1])=1+3=4$. The image $[2,3,0,1]$ has inversions $(2,0)$, $(2,1)$, $(3,0)$, and $(3,1)$, so $\mathrm{inv}([2,3,0,1])=4$. This matches the theorem.

The recurrence gives $A(4,2)=3A(3,2)+2A(3,1)=3\cdot 1+2\cdot 4=11$.

Worpitzky's identity with $n=4$ and $m=2$ gives $2^4=A(4,2)\left(\genfrac{}{}{0px}{}{4}{4}\right)+A(4,3)\left(\genfrac{}{}{0px}{}{5}{4}\right)$, because the $k=0,1$ terms vanish. Since $A(4,3)=1$, this reads $16=A(4,2)+5$, so again $A(4,2)=11$.

By descents/excedances equidistribution, $A(4,2)$ also counts permutations of $S_4$ with exactly two excedances, and the $S_4$ table on this companion page contains exactly $11$ such permutations.

Computing inversion sets gives the six weak-order covers displayed above. In particular, $021$ and $201$ are incomparable in weak order because their inversion sets are $\{(1,2)\}$ and $\{(0,1),(0,2)\}$ respectively.

Computing the rank inequalities shows that $021<201$ and $102<120$ in Bruhat order, producing the two extra cover relations listed above. Thus Bruhat order is strictly finer than weak order on $S_3$.

For both permutations, the only descent is at position $0$: in each case the first entry exceeds the second, while the second does not exceed the third.

The permutation $[1,0,2]$ has one inversion, namely $(1,0)$, while $[2,0,1]$ has two inversions, namely $(2,0)$ and $(2,1)$. So the inversion numbers differ even though the descent sets agree.

On $S_3$, the excedance counts are distributed as $1,4,1$: there is one permutation with $0$ excedances, four with $1$, and one with $2$.

On $S_3$, the inversion numbers are distributed as $1,2,2,1$ over $0,1,2,3$. Since these two distributions are different, $\mathrm{exc}$ is not Mahonian.

Take $\sigma =[2,0,1]$. Its only descent is at position $0$, so $\mathrm{maj}(\sigma )=1$.

The same permutation has two inversions, namely $(2,0)$ and $(2,1)$, so $\mathrm{inv}(\sigma )=2$. Therefore $\mathrm{maj}(\sigma )\mathrm{\ne }\mathrm{inv}(\sigma )$, and the claim is false.