edit this page

Possible database queries for permutations: search your data / browse all statistics / browse all maps

1. Definition & Example

There are two standard ways to denote $\pi \in \mathfrak{S}_n$.

$$\pi(1)=5,\pi(2)=4,\pi(3)=2,\pi(4)=3,\pi(5)=1.$$

The six permutations of size 3

 [1,2,3] 

 [1,3,2] 

 [2,1,3] 

 [2,3,1] 

 [3,1,2] 

 [3,2,1] 

2. Additional information

2.1. The Rothe diagram of a permutation

2.2. Euler-Mahonian statistics

L. Carlitz proved in [Car54] that the generating function for the bistatistic $(\operatorname{des},\operatorname{maj})$ satisfies a nice recurrence: let $$B_n(q,t) = \sum_{\sigma \in \mathbf{S}_n} t^{\operatorname{des}(\sigma)} q^{\operatorname{maj}(\sigma)} = \sum_{k=0}^n B_{n,k}(q) t^k.$$ Then the coefficient $B_{n,k}(q)$ satisfy the recurrence $$B_{n,k}(q) = [k+1]_q B_{n-1,k}(q) + q^k[n-k]_q B_{n-1,k-1}(q), \qquad B_{0,k}(q) = \delta_{0,k}.$$

A permutation statistic is called

Two additional examples of Euler-Mahonian statistics are

2.3. The Lehmer code and the major code of a permutation

$$m_i = \operatorname{maj}(\operatorname{del}_i(\sigma)) - \operatorname{maj}(\operatorname{del}_{i-1}(\sigma)).$$ For example, the permutation $[9,3,5,7,2,1,4,6,8]$ has major code $[5, 0, 1, 0, 1, 2, 0, 1, 0]$ since $$\operatorname{maj}([8,2,4,6,1,3,5,7]) = 5, \quad \operatorname{maj}([7,1,3,5,2,4,6]) = 5, \quad \operatorname{maj}([6,2,4,1,3,5]) = 4,$$ $$\operatorname{maj}([5,1,3,2,4]) = 4, \quad \operatorname{maj}([4,2,1,3]) = 3, \quad \operatorname{maj}([3,1,2]) = 1, \quad \operatorname{maj}([2,1]) = 1.$$ Observe that the sum of the major code of $\sigma$ equals the major index of $\sigma$.

2.4. Special classes of permutations

2.4.1. Pattern-avoiding permutations

$$ \#\big\{ \sigma \in \mathfrak{S}_n : \sigma \text{ avoids } \tau \big\} = \frac{1}{n+1}\binom{2n}{n}, $$

where we set $t_0=0$ and $t_k=n+1$.

2.5. Classes of permutations in Schubert calculus

The following classes of permutations play important roles in the theory of Schubert polynomials, see e.g. [Man01, Section 2.2]. A permutation $\sigma \in \mathfrak{S}_n$ is called

3. Properties

4. Remarks

5. References

6. Sage examples

7. Technical information for database usage