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

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

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

Properties

Remarks

References

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