Queries for Permutations: search statistic / browse statistics / browse maps from / browse maps to

Definition & Example

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


the 6 Permutations of size 3
  [1,2,3]   [1,3,2]   [2,1,3]   [2,3,1]   [3,1,2]   [3,2,1]

Additional information

The Rothe diagram of a permutation

The Rothe diagram of $\sigma = [4,3,1,5,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

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$.

Special classes of permutations

Pattern-avoiding permutations

$$ \#\big\{ \sigma \in \mathfrak{S}_n : \sigma \text{ avoids } \tau \big\} = \frac{1}{n+1}\binom{2n}{n}, $$
where $\tau$ is any permutation in $\mathfrak{S}_3$.

Thus, classical patterns are mesh patterns with empty $R$ and vincular patterns are mesh patterns with a shaded column.

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

Bigrassmannian permutations can be used to describe the Bruhat order on permutations: $\sigma \leq \tau$ in Bruhat order if and only if every bigrassmannian permutation dominated by $\sigma$ is also dominated by $\tau$ [LS96].




Sage examples

Technical information for database usage

If you want to edit this wiki page, you can download the raw markdown and send your new version to info@findstat.org