Digital Library of Mathematical Functions
About the Project
NIST
26 Combinatorial AnalysisProperties

§26.14 Permutations: Order Notation

Contents

§26.14(i) Definitions

The set 𝔖n26.13) can be viewed as the collection of all ordered lists of elements of {1,2,,n}: {σ(1)σ(2)σ(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:

26.14.1 inv(σ)=1j<knσ(j)>σ(k)1.

Equivalently, this is the sum over 1j<n of the number of integers less than σ(j) that lie in positions to the right of the jth 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:

26.14.2 maj(σ)=1j<nσ(j)>σ(j+1)j.

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

The Eulerian number, denoted nk, is the number of permutations in 𝔖n with exactly k descents. An excedance in σ𝔖n is a position j for which σ(j)>j. A weak excedance is a position j for which σ(j)j. The Eulerian number nk 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.

Table 26.14.1: Eulerian numbers nk.
n k
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

§26.14(ii) Generating Functions

26.14.3 σ𝔖nqinv(σ)=σ𝔖nqmaj(σ)=j=1n1-qj1-q.
26.14.4 n,k=0nkxktnn!=1-xexp((x-1)t)-x,
|x|<1,|t|<1.

§26.14(iii) Identities

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

26.14.6 nk=j=0k(-1)j(n+1j)(k+1-j)n,
n1,
26.14.8 nk=(k+1)n-1k+(n-k)n-1k-1,
n2,
26.14.9 nk=nn-1-k,
n1,
26.14.10 k=0n-1nk=n!,
n1.
26.14.11 Bm=m2m(2m-1)k=0m-2(-1)km-1k,
m2.

§26.14(iv) Special Values

26.14.13 0k =δ0,k,
26.14.14 n0 =1,
26.14.15 n1 =2n-n-1,
n1,
26.14.16 n2=3n-(n+1)2n+(n+12),
n1.