26 Combinatorial Analysis Properties 26.13 Permutations: Cycle Notation 26.15 Permutations: Matrix Notation

§26.14 Permutations: Order Notation

Keywords:: permutations
Permalink:: http://dlmf.nist.gov/26.14

§26.14(i) Definitions
§26.14(ii) Generating Functions
§26.14(iii) Identities
§26.14(iv) Special Values

§26.14(i) Definitions

Notes:: See Andrews (1976, pp. 39–42), Graham et al. (1994, pp. 267–272), Stanley (1997, pp. 20–23). Table 26.14.1 was computed by the author.
Defines:: $\mathop{\genfrac{<}{>}{0.0pt}{}{n}{k}\/}\nolimits$ : Eulerian number
Keywords:: Eulerian numbers, permutations
Permalink:: http://dlmf.nist.gov/26.14.i

The set $\mathop{\mathfrak{S}_{{n}}\/}\nolimits$ (§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 $\mathop{\mathfrak{S}_{{8}}\/}\nolimits.$ 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_{{\substack{1\leq j<k\leq n\\ \sigma(j)>\sigma(k)}}}1.$

Symbols:: : nonnegative integer, : nonnegative integer, : nonnegative integer and $\sigma$ : permutation
Permalink:: http://dlmf.nist.gov/26.14.E1
Encodings:: TeX, pMML, png

Equivalently, this is the sum over $1\leq j<n$ of the number of integers less than $\sigma(j)$ that lie in positions to the right of the 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_{{\substack{1\leq j<n\\ \sigma(j)>\sigma(j+1)}}}j.$

Symbols:: : nonnegative integer, : nonnegative integer, $\sigma$ : permutation and $\mathop{\mathrm{maj}}(\sigma)$ : major index
Permalink:: http://dlmf.nist.gov/26.14.E2
Encodings:: TeX, pMML, png

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

Table 26.14.1: Eulerian numbers $\mathop{\genfrac{<}{>}{0.0pt}{}{n}{k}\/}\nolimits$ .


	0	1	2	3	4	5	6	7	8	9
0	1
1	1
2	1	1
3	1	4	1
4	1	11	11	1
5	1	26	66	26	1
6	1	57	302	302	57	1
7	1	120	1191	2416	1191	120	1
8	1	247	4293	15619	15619	4293	247	1
9	1	502	14608	88234	1 56190	88234	14608	502	1
10	1	1013	47840	4 55192	13 10354	13 10354	4 55192	47840	1013	1

Symbols:: $\mathop{\genfrac{<}{>}{0.0pt}{}{n}{k}\/}\nolimits$ : Eulerian number, : nonnegative integer and : nonnegative integer
Keywords:: Eulerian numbers
Referenced by:: §26.14(i), §26.14(i)
Permalink:: http://dlmf.nist.gov/26.14.T1

§26.14(ii) Generating Functions

Notes:: See Andrews (1976, pp. 39–42), Graham et al. (1994, pp. 267–272), Riordan (1958, pp. 38–39), Stanley (1997, pp. 20–21).
Keywords:: Eulerian numbers, permutations
Permalink:: http://dlmf.nist.gov/26.14.ii

26.14.3 $\sum_{{\sigma\in\mathop{\mathfrak{S}_{{n}}\/}\nolimits}}q^{{\mathop{\mathrm{% inv}}(\sigma)}}=\sum_{{\sigma\in\mathop{\mathfrak{S}_{{n}}\/}\nolimits}}q^{{% \mathop{\mathrm{maj}}(\sigma)}}=\prod_{{j=1}}^{n}\frac{1-q^{j}}{1-q}.$

Symbols:: $\in$ : element of, $\mathop{\mathfrak{S}_{{n}}\/}\nolimits$ : set of permutations of $\{1,2,\ldots,n\}$ , : nonnegative integer, : nonnegative integer and : parameter
Permalink:: http://dlmf.nist.gov/26.14.E3
Encodings:: TeX, pMML, png

26.14.4 $\sum_{{n,k=0}}^{{\infty}}\mathop{\genfrac{<}{>}{0.0pt}{}{n}{k}\/}\nolimits x^{% k}\,\frac{t^{n}}{n!}=\frac{1-x}{\mathop{\exp\/}\nolimits((x-1)t)-x},$

Symbols:: $\mathop{\genfrac{<}{>}{0.0pt}{}{n}{k}\/}\nolimits$ : Eulerian number, $\mathop{\exp\/}\nolimits z$ : exponential function, : : factorial, : real variable, : nonnegative integer and : nonnegative integer
Referenced by:: §26.14(iii)
Permalink:: http://dlmf.nist.gov/26.14.E4
Encodings:: TeX, pMML, png

26.14.5 $\sum_{{k=0}}^{{n-1}}\mathop{\genfrac{<}{>}{0.0pt}{}{n}{k}\/}\nolimits\binom{x+% k}{n}=x^{n}.$

Symbols:: $\mathop{\genfrac{<}{>}{0.0pt}{}{n}{k}\/}\nolimits$ : Eulerian number, $\binom{m}{n}$ : binomial coefficient, : real variable, : nonnegative integer and : nonnegative integer
Permalink:: http://dlmf.nist.gov/26.14.E5
Encodings:: TeX, pMML, png

§26.14(iii) Identities

Notes:: See Graham et al. (1994, pp. 268–269). (26.14.10) and (26.14.11) follow from (26.14.4) and (24.2.1).
Keywords:: Eulerian numbers, permutations
Permalink:: http://dlmf.nist.gov/26.14.iii

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

26.14.6 $\mathop{\genfrac{<}{>}{0.0pt}{}{n}{k}\/}\nolimits=\sum_{{j=0}}^{k}(-1)^{j}% \binom{n+1}{j}(k+1-j)^{n},$ $n\geq 1$ ,

Symbols:: $\mathop{\genfrac{<}{>}{0.0pt}{}{n}{k}\/}\nolimits$ : Eulerian number, $\binom{m}{n}$ : binomial coefficient, : nonnegative integer, : nonnegative integer and : nonnegative integer
Permalink:: http://dlmf.nist.gov/26.14.E6
Encodings:: TeX, pMML, png

26.14.7 $\mathop{\genfrac{<}{>}{0.0pt}{}{n}{k}\/}\nolimits=\sum_{{j=0}}^{{n-k}}(-1)^{{n% -k-j}}j!\binom{n-j}{k}\mathop{S\/}\nolimits\!\left(n,j\right),$

Symbols:: $\mathop{\genfrac{<}{>}{0.0pt}{}{n}{k}\/}\nolimits$ : Eulerian number, $\mathop{S\/}\nolimits\!\left(n,k\right)$ : Stirling number of the second kind, $\binom{m}{n}$ : binomial coefficient, : : factorial, : nonnegative integer, : nonnegative integer and : nonnegative integer
Permalink:: http://dlmf.nist.gov/26.14.E7
Encodings:: TeX, pMML, png

26.14.8 $\mathop{\genfrac{<}{>}{0.0pt}{}{n}{k}\/}\nolimits=(k+1)\mathop{\genfrac{<}{>}{% 0.0pt}{}{n-1}{k}\/}\nolimits+(n-k)\mathop{\genfrac{<}{>}{0.0pt}{}{n-1}{k-1}\/}\nolimits,$ $n\geq 2$ ,

Symbols:: $\mathop{\genfrac{<}{>}{0.0pt}{}{n}{k}\/}\nolimits$ : Eulerian number, : nonnegative integer and : nonnegative integer
Permalink:: http://dlmf.nist.gov/26.14.E8
Encodings:: TeX, pMML, png

26.14.9 $\mathop{\genfrac{<}{>}{0.0pt}{}{n}{k}\/}\nolimits=\mathop{\genfrac{<}{>}{0.0pt% }{}{n}{n-1-k}\/}\nolimits,$ $n\geq 1$ ,

Symbols:: $\mathop{\genfrac{<}{>}{0.0pt}{}{n}{k}\/}\nolimits$ : Eulerian number, : nonnegative integer and : nonnegative integer
Permalink:: http://dlmf.nist.gov/26.14.E9
Encodings:: TeX, pMML, png

26.14.10 $\sum_{{k=0}}^{{n-1}}\mathop{\genfrac{<}{>}{0.0pt}{}{n}{k}\/}\nolimits=n!,$ $n\geq 1$ .

Symbols:: $\mathop{\genfrac{<}{>}{0.0pt}{}{n}{k}\/}\nolimits$ : Eulerian number, : : factorial, : nonnegative integer and : nonnegative integer
Referenced by:: §26.14(iii)
Permalink:: http://dlmf.nist.gov/26.14.E10
Encodings:: TeX, pMML, png

26.14.11 $\mathop{B_{{m}}\/}\nolimits=\frac{m}{2^{m}(2^{m}-1)}\sum_{{k=0}}^{{m-2}}(-1)^{% k}\mathop{\genfrac{<}{>}{0.0pt}{}{m-1}{k}\/}\nolimits,$ $m\geq 2$ .

Symbols:: $\mathop{B_{{n}}\/}\nolimits\!\left(x\right)$ : Bernoulli polynomials, $\mathop{\genfrac{<}{>}{0.0pt}{}{n}{k}\/}\nolimits$ : Eulerian number, : nonnegative integer and : nonnegative integer
Referenced by:: §24.4(ix), §26.14(iii)
Permalink:: http://dlmf.nist.gov/26.14.E11
Encodings:: TeX, pMML, png

26.14.12 $\mathop{S\/}\nolimits\!\left(n,m\right)=\frac{1}{m!}\sum_{{k=0}}^{{n-1}}% \mathop{\genfrac{<}{>}{0.0pt}{}{n}{k}\/}\nolimits\binom{k}{n-m},$ $n\geq m$ , $n\geq 1$ .