About the Project
26 Combinatorial AnalysisProperties

§26.14 Permutations: Order Notation

Contents
  1. §26.14(i) Definitions
  2. §26.14(ii) Generating Functions
  3. §26.14(iii) Identities
  4. §26.14(iv) Special Values

§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=1n1qj1q.
26.14.4 n,k=0nkxktnn!=1xexp((x1)t)x,
|x|<1,|t|<1.
26.14.5 k=0n1nk(x+kn)=xn.

§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+1j)n,
n1,
26.14.8 nk=(k+1)n1k+(nk)n1k1,
n2,
26.14.9 nk=nn1k,
n1,
26.14.10 k=0n1nk=n!,
n1.
26.14.11 Bm=m2m(2m1)k=0m2(1)km1k,
m2.

§26.14(iv) Special Values

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