# §26.14 Permutations: Order Notation

## §26.14(i) Definitions

The set $\mathfrak{S}_{n}$26.13) can be viewed as the collection of all ordered lists of elements of $\{1,2,\ldots,n\}$: $\{\sigma(1)\sigma(2)\cdots\sigma(n)\}$. As an example, $35247816$ is an element of $\mathfrak{S}_{8}.$ The inversion number is the number of pairs of elements for which the larger element precedes the smaller:

 26.14.1 $\mathop{\mathrm{inv}}(\sigma)=\sum_{\begin{subarray}{c}1\leq j\sigma(k)\end{subarray}}1.$ ⓘ Symbols: $j$: nonnegative integer, $k$: nonnegative integer, $n$: nonnegative integer and $\sigma$: permutation Permalink: http://dlmf.nist.gov/26.14.E1 Encodings: TeX, pMML, png See also: Annotations for 26.14(i), 26.14 and 26

Equivalently, this is the sum over $1\leq j of the number of integers less than $\sigma(j)$ that lie in positions to the right of the $j$th position: $\mathop{\mathrm{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:

 26.14.2 $\mathop{\mathrm{maj}}(\sigma)=\sum_{\begin{subarray}{c}1\leq j\sigma(j+1)\end{subarray}}j.$ ⓘ Symbols: $j$: nonnegative integer, $n$: nonnegative integer, $\sigma$: permutation and $\mathop{\mathrm{maj}}(\sigma)$: major index Permalink: http://dlmf.nist.gov/26.14.E2 Encodings: TeX, pMML, png See also: Annotations for 26.14(i), 26.14 and 26

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

The Eulerian number, denoted $\genfrac{<}{>}{0.0pt}{}{n}{k}$, is the number of permutations in $\mathfrak{S}_{n}$ with exactly $k$ descents. An excedance in $\sigma\in\mathfrak{S}_{n}$ is a position $j$ for which $\sigma(j)>j$. A weak excedance is a position $j$ for which $\sigma(j)\geq j$. The Eulerian number $\genfrac{<}{>}{0.0pt}{}{n}{k}$ is equal to the number of permutations in $\mathfrak{S}_{n}$ with exactly $k$ excedances. It is also equal to the number of permutations in $\mathfrak{S}_{n}$ with exactly $k+1$ weak excedances. See Table 26.14.1.

## §26.14(ii) Generating Functions

 26.14.3 $\sum_{\sigma\in\mathfrak{S}_{n}}q^{\mathop{\mathrm{inv}}(\sigma)}=\sum_{\sigma% \in\mathfrak{S}_{n}}q^{\mathop{\mathrm{maj}}(\sigma)}=\prod_{j=1}^{n}\frac{1-q% ^{j}}{1-q}.$
 26.14.4 $\sum_{n,k=0}^{\infty}\genfrac{<}{>}{0.0pt}{}{n}{k}x^{k}\,\frac{t^{n}}{n!}=% \frac{1-x}{\exp((x-1)t)-x},$ $|x|<1,|t|<1$.
 26.14.5 $\sum_{k=0}^{n-1}\genfrac{<}{>}{0.0pt}{}{n}{k}\genfrac{(}{)}{0.0pt}{}{x+k}{n}=x% ^{n}.$

## §26.14(iii) Identities

In this subsection $S\left(n,k\right)$ is again the Stirling number of the second kind (§26.8), and $B_{m}$ is the $m$th Bernoulli number (§24.2(i)).

 26.14.6 $\genfrac{<}{>}{0.0pt}{}{n}{k}=\sum_{j=0}^{k}(-1)^{j}\genfrac{(}{)}{0.0pt}{}{n+% 1}{j}(k+1-j)^{n},$ $n\geq 1$,
 26.14.7 $\genfrac{<}{>}{0.0pt}{}{n}{k}=\sum_{j=0}^{n-k}(-1)^{n-k-j}j!\genfrac{(}{)}{0.0% pt}{}{n-j}{k}S\left(n,j\right),$
 26.14.8 $\genfrac{<}{>}{0.0pt}{}{n}{k}=(k+1)\genfrac{<}{>}{0.0pt}{}{n-1}{k}+(n-k)% \genfrac{<}{>}{0.0pt}{}{n-1}{k-1},$ $n\geq 2$, ⓘ Symbols: $\genfrac{<}{>}{0.0pt}{}{\NVar{n}}{\NVar{k}}$: Eulerian number, $k$: nonnegative integer and $n$: nonnegative integer Permalink: http://dlmf.nist.gov/26.14.E8 Encodings: TeX, pMML, png See also: Annotations for 26.14(iii), 26.14 and 26
 26.14.9 $\genfrac{<}{>}{0.0pt}{}{n}{k}=\genfrac{<}{>}{0.0pt}{}{n}{n-1-k},$ $n\geq 1$, ⓘ Symbols: $\genfrac{<}{>}{0.0pt}{}{\NVar{n}}{\NVar{k}}$: Eulerian number, $k$: nonnegative integer and $n$: nonnegative integer Permalink: http://dlmf.nist.gov/26.14.E9 Encodings: TeX, pMML, png See also: Annotations for 26.14(iii), 26.14 and 26
 26.14.10 $\sum_{k=0}^{n-1}\genfrac{<}{>}{0.0pt}{}{n}{k}=n!,$ $n\geq 1$. ⓘ Symbols: $\genfrac{<}{>}{0.0pt}{}{\NVar{n}}{\NVar{k}}$: Eulerian number, $!$: factorial (as in $n!$), $k$: nonnegative integer and $n$: nonnegative integer Referenced by: §26.14(iii) Permalink: http://dlmf.nist.gov/26.14.E10 Encodings: TeX, pMML, png See also: Annotations for 26.14(iii), 26.14 and 26
 26.14.11 $B_{m}=\frac{m}{2^{m}(2^{m}-1)}\sum_{k=0}^{m-2}(-1)^{k}\genfrac{<}{>}{0.0pt}{}{% m-1}{k},$ $m\geq 2$. ⓘ Symbols: $B_{\NVar{n}}$: Bernoulli numbers, $\genfrac{<}{>}{0.0pt}{}{\NVar{n}}{\NVar{k}}$: Eulerian number, $k$: nonnegative integer and $m$: nonnegative integer Referenced by: §24.4(ix), §26.14(iii) Permalink: http://dlmf.nist.gov/26.14.E11 Encodings: TeX, pMML, png See also: Annotations for 26.14(iii), 26.14 and 26
 26.14.12 $S\left(n,m\right)=\frac{1}{m!}\sum_{k=0}^{n-1}\genfrac{<}{>}{0.0pt}{}{n}{k}% \genfrac{(}{)}{0.0pt}{}{k}{n-m},$ $n\geq m$, $n\geq 1$.

## §26.14(iv) Special Values

 26.14.13 $\displaystyle\genfrac{<}{>}{0.0pt}{}{0}{k}$ $\displaystyle=\delta_{0,k},$ ⓘ Symbols: $\genfrac{<}{>}{0.0pt}{}{\NVar{n}}{\NVar{k}}$: Eulerian number, $\delta_{\NVar{j},\NVar{k}}$: Kronecker delta and $k$: nonnegative integer Permalink: http://dlmf.nist.gov/26.14.E13 Encodings: TeX, pMML, png See also: Annotations for 26.14(iv), 26.14 and 26 26.14.14 $\displaystyle\genfrac{<}{>}{0.0pt}{}{n}{0}$ $\displaystyle=1,$ ⓘ Symbols: $\genfrac{<}{>}{0.0pt}{}{\NVar{n}}{\NVar{k}}$: Eulerian number and $n$: nonnegative integer Permalink: http://dlmf.nist.gov/26.14.E14 Encodings: TeX, pMML, png See also: Annotations for 26.14(iv), 26.14 and 26 26.14.15 $\displaystyle\genfrac{<}{>}{0.0pt}{}{n}{1}$ $\displaystyle=2^{n}-n-1,$ $n\geq 1$, ⓘ Symbols: $\genfrac{<}{>}{0.0pt}{}{\NVar{n}}{\NVar{k}}$: Eulerian number and $n$: nonnegative integer Permalink: http://dlmf.nist.gov/26.14.E15 Encodings: TeX, pMML, png See also: Annotations for 26.14(iv), 26.14 and 26
 26.14.16 $\genfrac{<}{>}{0.0pt}{}{n}{2}=3^{n}-(n+1)2^{n}+\genfrac{(}{)}{0.0pt}{}{n+1}{2},$ $n\geq 1$. ⓘ Symbols: $\genfrac{<}{>}{0.0pt}{}{\NVar{n}}{\NVar{k}}$: Eulerian number, $\genfrac{(}{)}{0.0pt}{}{\NVar{m}}{\NVar{n}}$: binomial coefficient and $n$: nonnegative integer Permalink: http://dlmf.nist.gov/26.14.E16 Encodings: TeX, pMML, png See also: Annotations for 26.14(iv), 26.14 and 26