§26.14 Permutations: Order Notation

The set ${𝔖}_n$ (§26.13) can be viewed as the collection of all ordered lists of elements of $\{1,2,\mathrm{\dots },n\}$: $\{\sigma (1)\sigma (2)\mathrm{\cdots }\sigma (n)\}$. As an example, $35247816$ is an element of ${𝔖}_8.$ The inversion number is the number of pairs of elements for which the larger element precedes the smaller:

Equivalently, this is the sum over of the number of integers less than $\sigma (j)$ that lie in positions to the right of the $j$th position: $inv(35247816)=2+3+1+1+2+2+0=11.$

A descent of a permutation is a pair of adjacent elements for which the first is larger than the second. The permutation $35247816$ has two descents: $52$ and $81$. The major index is the sum of all positions that mark the first element of a descent:

For example, $maj(35247816)=2+6=8$. The major index is also called the greater index of the permutation.

The Eulerian number, denoted , is the number of permutations in ${𝔖}_n$ with exactly $k$ descents. An excedance in $\sigma \in {𝔖}_n$ is a position $j$ for which $\sigma (j)>j$. A weak excedance is a position $j$ for which $\sigma (j)\ge j$. The Eulerian number is equal to the number of permutations in ${𝔖}_n$ with exactly $k$ excedances. It is also equal to the number of permutations in ${𝔖}_n$ with exactly $k+1$ weak excedances. See Table 26.14.1.

In this subsection $S(n,k)$ is again the Stirling number of the second kind (§26.8), and $B_m$ is the $m$th Bernoulli number (§24.2(i)).