# 1. Definition

A permutation of a set $\mathcal{S}$ is a bijection $\psi : \mathcal{S}\ \tilde\longrightarrow\ \mathcal{S}$. $\mathfrak{S}_n$ denotes the collection of all bijections $$\pi : \{1,\ldots,n\}\ \tilde\longrightarrow\ \{1,\ldots,n\}.$$ We call $n$ the size of $\pi$. $\mathfrak{S}_n$ has a group structure given by composition of bijections, and is called symmetric group. There are two standard ways to denote $\pi \in \mathfrak{S}_n$.

• The one-line notation is given by $\pi = [\pi(1),\ldots,\pi(n)]$. E.g., $\pi = [5,4,2,3,1]$ says that

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

• The cycle notation is given by $\pi = (a^{(1)}_1, \ldots, a^{(1)}_{k_1}) \cdots (a^{(m)}_1, \ldots, a^{(m)}_{k_m})$ which means that every integer in a cycle is mapped to the next integer in this cycle, $\pi(a^{(j)}_i) = a^{(j)}_{i+1}$. E.g., $\pi = (1,5)(2,4,3) = [5,4,2,3,1]$. Often, fixed points are suppressed in the cycle notation.

# 2. Examples

• $\mathfrak{S}_1 = \{ [1] \} = \{()\}$

• $\mathfrak{S}_2 = \{ [1,2],[2,1]\} = \{(),(1,2)\}$

• $\mathfrak{S}_3 = \{ [1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]\} = \{ (),(2,3),(1,2),(1,2,3),(1,3,2),(1,3)\}$

# 3. The Rothe diagram of a permutation

Another way to visualize a permutation is by drawing its Rothe diagram introduced by H.A. Rothe in 1800. It is given by the collection of boxes $$R(\sigma) = \{ (\sigma_j,i) : i < j, \sigma_i > \sigma_j \}.$$ Another way to obtain $R(\sigma)$ is by marking all boxes $b_i = (i,\sigma_i)$ and cross out all boxes below and to the right of $b_i$. The Rothe diagram of $\sigma = [4,3,1,5,2]$ is for example given by

The essential set of the Rothe diagram is the collection of boxes $(i,j)$ for which $(i+1,j)$ and $(i,j+1)$ are both not in the Rothe diagram. The Rothe diagram can also be used to understand the Bruhat order on permutations, see [Man01]. It is also closely related to the Lehmer code for a permutation, described below.

# 4. The Lehmer code for a permutation

The Lehmer code encodes the inversions (St000018) of a permutation. It is given by $L(\sigma) = l_1 \ldots l_n$ with $l_i = \# \{ j > i : \sigma_j < \sigma_i \}$. In particular, $l_i$ is the number of boxes in the $i$-th column of the Rothe diagram. The Lehmer code of $\sigma = [4,3,1,5,2]$ is for example given by $32010$. The Lehmer code $L : \mathfrak{S}_n\ \tilde\longrightarrow\ S_n$ is a bijection between permutations of size $n$ and sequences $l_1\ldots l_n \in \mathbf{N}^n$ with $l_i \leq i$.

# 5. Special classes of permutations

## 5.1. Pattern-avoiding permutations

A permutation $\sigma$ avoids a permutation $\tau$ if no subword of $\sigma$ in one-line notation appears in the same relative order as $\tau$. E.g. $[4,2,1,3]$ is not $[3,1,2]$-avoiding since the subword $[4,1,3]$ has the same relative order as $[3,1,2]$. See also the wiki page on permutation pattern and the references therein. Each subword of $\sigma$ having the same relative order as $\tau$ is called occurrence of $\tau$.

Is was proven in [Knu68] that $3$-pattern avoiding permutations are all counted by the famous Catalan numbers, $$\#\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$.

A permutation $\sigma$ avoids a pattern $ab\!\!-\!\!c$ for $\{a,b,c\} = \{1,2,3\}$ if it avoids the permutation $[a,b,c]$ with the additional property that the positions of $a$ and $b$ in $\sigma$ must be consecutive. In other words, a pattern $ab\!\!-\!\!c$ in $\sigma$ is a subword $\sigma_i,\sigma_i+1,\sigma_j$ with $\sigma_i > \sigma_j > \sigma_{i+1}$. In particular, usual three-pattern-avoidance is of the form $a\!\!-\!\!b\!\!-\!\!c$.

Mesh patterns, introduced by [BrCl11], constitute a further generalization. A mesh pattern is a pair $(\tau, R)$, where $\tau\in\mathfrak{S}_k$ and $R$ is a subset of $\{0,\dots,k\}\times\{0,\dots,k\}$. An occurrence of $(\tau, R)$ in a permutation $\pi$ is an occurrence $(t_1,\dots,t_k)$ of $\tau$ in $\pi$, satisfying the following additional requirement: for all $(i,j)\in R$, the permutation $\sigma$ has no values between $t_j$ and $t_{j+1}$ in the positions between the positions of $t_i$ and $t_{i+1}$, where we set $t_0=0$ and $t_k=n+1$.

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

## 5.2. 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

• dominant if the following equivalent conditions hold:

• its Lehmer code is a partition, this is if $l_1 \geq l_2 \geq \ldots \geq l_n$,

• its Rothe diagram is the shape of a partition. In particular, $\sigma$ is dominant if and only if $\sigma^{-1}$ is dominant.

The Schubert polynomial $S_\sigma(x,y)$ for a dominant permutation $\sigma$ is given by $S_\sigma(x,y) = \prod_{(i,j) \in \lambda(\sigma)} (x_i - y_j),$ where $\lambda(\sigma)$ is the shape of the Rothe diagram of $\sigma$ [Man01, Proposition 2.6.7].

• Grassmannian if the following equivalent conditions hold:

• $l_1 \leq l_2 \leq \ldots \leq l_r$ and $l_i = 0$ for for some $r$ and all $i>r$,

• $\sigma$ has a unique descent.

The Schubert polynomial $S_\sigma(x)$ for a Grassmannian permutation $\sigma$ is given by $S_\sigma(x) = s_{\lambda(\sigma)}(x_1,\ldots,x_n)$, where $s_\lambda$ is the Schur function for the shape $\lambda$ [Man01, Proposition 2.6.8].

• bigrassmannian if $\sigma$ and $\sigma^{-1}$ are both Grassmannian.

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

• vexillary if the following equivalent conditions hold:

• its Rothe diagram is, up to a permutation of its rows and columns, the diagram of a partition,
• there is no sequence $i < j < k < l$ with $\sigma_j < \sigma_i < \sigma_l < \sigma_k$,

• its essential set lies on a piecewise linear curve oriented $SW-NE$.

The Schubert polynomials for vexillary permutations are exactly the flagged Schur functions, see [Man01, Section 2.6.5] for a detailed description. The term vexillary comes from the Latin vexillum for a flag-like object used in the Classical Era of the Roman Empire [Man01, p. 65] and is due to A. Lascoux and M.-P. Schützenberger.

# 6. Properties

• $|\mathfrak{S}_n| = n!$

• The cycle type of a permutation $\pi \in \mathfrak{S}_n$ is given by the integer partition of $n$ formed by the lengths of the cycles of $\pi$. E.g., $\pi = (1,4,3,7)(2)(5,6)$ has cycle type $[4,2,1]$. Two permutations $\pi$ and $\tau$ in $\mathfrak{S}_n$ are conjugated (i.e., $\pi = \sigma \tau \sigma^{-1}$ for some $\sigma \in \mathfrak{S}_n$) if and only if their cycle types coincide.

# 8. Statistics

We have the following 284 statistics on Permutations in the database:

St000001 Permutations ⟶ ℤ
The number of ways to write a permutation as a minimal length product of simple t....
St000002 Permutations ⟶ ℤ
The number of occurrences of the pattern 123 in a permutation.
St000004 Permutations ⟶ ℤ
The major index of a permutation.
St000007 Permutations ⟶ ℤ
The number of saliances of the permutation.
St000018 Permutations ⟶ ℤ
The number of inversions of a permutation.
St000019 Permutations ⟶ ℤ
The cardinality of the complement of the connectivity set.
St000020 Permutations ⟶ ℤ
The rank of the permutation.
St000021 Permutations ⟶ ℤ
The number of descents of a permutation.
St000022 Permutations ⟶ ℤ
The number of fixed points of a permutation.
St000023 Permutations ⟶ ℤ
The number of inner peaks of a permutation.
St000028 Permutations ⟶ ℤ
The number of stack-sorts needed to sort a permutation.
St000029 Permutations ⟶ ℤ
The depth of a permutation.
St000030 Permutations ⟶ ℤ
The sum of the descent differences of a permutations.
St000031 Permutations ⟶ ℤ
The number of cycles in the cycle decomposition of a permutation.
St000033 Permutations ⟶ ℤ
The number of permutations greater than or equal to the given permutation in (str....
St000034 Permutations ⟶ ℤ
The maximum defect over any reduced expression for a permutation and any subexpre....
St000035 Permutations ⟶ ℤ
The number of left outer peaks of a permutation.
St000036 Permutations ⟶ ℤ
The evaluation at 1 of the Kazhdan-Lusztig polynomial with parameters given by th....
St000037 Permutations ⟶ ℤ
The sign of a permutation.
St000039 Permutations ⟶ ℤ
The number of crossings of a permutation.
St000040 Permutations ⟶ ℤ
The number of regions of inversion arrangement of a permutation.
St000054 Permutations ⟶ ℤ
The first entry of the permutation.
St000055 Permutations ⟶ ℤ
The inversion sum of a permutation.
St000056 Permutations ⟶ ℤ
The decomposition (or block) number of a permutation.
St000058 Permutations ⟶ ℤ
The order of a permutation.
St000060 Permutations ⟶ ℤ
The greater neighbor of the maximum.
St000062 Permutations ⟶ ℤ
The length of the longest increasing subsequence of the permutation.
St000064 Permutations ⟶ ℤ
The number of one-box pattern of a permutation.
St000078 Permutations ⟶ ℤ
The number of alternating sign matrices whose left key is the permutation.
St000092 Permutations ⟶ ℤ
The number of outer peaks of a permutation.
St000099 Permutations ⟶ ℤ
The number of valleys of a permutation, including the boundary.
St000109 Permutations ⟶ ℤ
The number of elements less than or equal to the given element in Bruhat order.
St000110 Permutations ⟶ ℤ
The number of permutations less than or equal to given permutation in left weak o....
St000111 Permutations ⟶ ℤ
The sum of the descent tops (or Genocchi descents) of a permutation.
St000119 Permutations ⟶ ℤ
The number of occurrences of the pattern 321 in a permutation.
St000123 Permutations ⟶ ℤ
The difference in Coxeter length of a permutation and its image under the Simion-....
St000124 Permutations ⟶ ℤ
The cardinality of the preimage of the Simion-Schmidt map.
St000133 Permutations ⟶ ℤ
The "bounce" of a permutation.
St000141 Permutations ⟶ ℤ
The maximum drop size of a permutation.
St000153 Permutations ⟶ ℤ
The number of adjacent cycles of a permutation.
St000154 Permutations ⟶ ℤ
The sum of the descent bottoms of a permutation.
St000155 Permutations ⟶ ℤ
The number of exceedances (also excedences) of a permutation.
St000156 Permutations ⟶ ℤ
The Denert index of a permutation.
St000162 Permutations ⟶ ℤ
The number of nontrivial cycles of a permutation $\pi$ in its cycle decomposition.
St000209 Permutations ⟶ ℤ
Maximum difference of elements in cycles.
St000210 Permutations ⟶ ℤ
Minimum over maximum difference of elements in cycles.
St000213 Permutations ⟶ ℤ
The number of weak exceedances (also weak excedences) of a permutation.
St000214 Permutations ⟶ ℤ
The number of adjacencies (or small descents) of a permutation.
St000215 Permutations ⟶ ℤ
The number of adjacencies of a permutation, 0 appended.
St000216 Permutations ⟶ ℤ
The absolute length of a permutation.
St000217 Permutations ⟶ ℤ
The number of occurrences of the pattern 312 in a permutation.
St000218 Permutations ⟶ ℤ
The number of occurrences of the pattern 213 in a permutation.
St000219 Permutations ⟶ ℤ
The number of occurrences of the pattern 231 in a permutation.
St000220 Permutations ⟶ ℤ
The number of occurrences of the pattern 132 in a permutation.
St000221 Permutations ⟶ ℤ
The number of strong fixed points of a permutation.
St000222 Permutations ⟶ ℤ
The number of alignments in the permutation.
St000223 Permutations ⟶ ℤ
The number of nestings in the permutation.
St000224 Permutations ⟶ ℤ
The sorting index of a permutation.
St000226 Permutations ⟶ ℤ
The convexity of a permutation.
St000234 Permutations ⟶ ℤ
The number of global ascents of a permutation.
St000235 Permutations ⟶ ℤ
The number of indices $i$ such that $\pi_i \neq i+1$ considered cyclically.
St000236 Permutations ⟶ ℤ
The number of indices $i$ such that $\pi_i \in \{ i,i+1 \}$ considered cyclically.
St000237 Permutations ⟶ ℤ
The number of indices $i$ such that $\pi_i=i+1$.
St000238 Permutations ⟶ ℤ
The number of indices $i$ such that $\pi_i \notin \{i,i+1\}$.
St000239 Permutations ⟶ ℤ
The number of indices $i$ such that $\pi_i \in \{i,i+1\}$.
St000240 Permutations ⟶ ℤ
The number of indices $i$ for which $\pi_i \neq i+1$.
St000241 Permutations ⟶ ℤ
The number of indices $i$ such that $\pi_i = i+1$ considered cyclically.
St000242 Permutations ⟶ ℤ
The number of indices $i$ such that $\pi_i \notin \{ i,i+1 \}$ considered cyclically.....
St000243 Permutations ⟶ ℤ
The number of cyclic valleys and cyclic peaks of a permutation.
St000245 Permutations ⟶ ℤ
The number of ascents of a permutation.
St000246 Permutations ⟶ ℤ
The number of non-inversions of a permutation.
St000255 Permutations ⟶ ℤ
The number of reduced Kogan faces with the permutation as type.
St000279 Permutations ⟶ ℤ
The size of the preimage of the map 'cycle-as-one-line notation' from Permutation....
St000280 Permutations ⟶ ℤ
The size of the preimage of the map 'to labelling permutation' from Parking funct....
St000304 Permutations ⟶ ℤ
St000305 Permutations ⟶ ℤ
The inverse major index of a permutation.
St000308 Permutations ⟶ ℤ
The height of the tree associated to a permutation.
St000314 Permutations ⟶ ℤ
The number of left-to-right-maxima of a permutation.
St000316 Permutations ⟶ ℤ
The number of non-left-to-right-maxima of a permutation.
St000317 Permutations ⟶ ℤ
The cycle descent number of a permutation.
St000324 Permutations ⟶ ℤ
The shape of the tree associated to a permutation.
St000325 Permutations ⟶ ℤ
The width of the tree associated to a permutation.
St000333 Permutations ⟶ ℤ
The dez statistic, the number of descents of a permutation after replacing fixed ....
St000334 Permutations ⟶ ℤ
The maz index, the major index of a permutation after replacing fixed points by z....
St000337 Permutations ⟶ ℤ
The lec statistic, the sum of the inversion numbers of the hook factors of a perm....
St000338 Permutations ⟶ ℤ
The number of pixed points of a permutation.
St000339 Permutations ⟶ ℤ
The maf index of a permutation.
St000341 Permutations ⟶ ℤ
The non-inversion sum of a permutation.
St000342 Permutations ⟶ ℤ
The cosine of a permutation.
St000352 Permutations ⟶ ℤ
The Elizalde-Pak rank of a permutation.
St000353 Permutations ⟶ ℤ
The number of inner valleys of a permutation.
St000354 Permutations ⟶ ℤ
The number of recoils of a permutation.
St000355 Permutations ⟶ ℤ
The number of occurrences of the pattern 21-3.
St000356 Permutations ⟶ ℤ
The number of occurrences of the pattern 13-2.
St000357 Permutations ⟶ ℤ
The number of occurrences of the pattern 12-3.
St000358 Permutations ⟶ ℤ
The number of occurrences of the pattern 31-2.
St000359 Permutations ⟶ ℤ
The number of occurrences of the pattern 23-1.
St000360 Permutations ⟶ ℤ
The number of occurrences of the pattern 32-1.
St000365 Permutations ⟶ ℤ
The number of double ascents of a permutation.
St000366 Permutations ⟶ ℤ
The number of double descents of a permutation.
St000367 Permutations ⟶ ℤ
The number of simsun double descents of a permutation.
St000371 Permutations ⟶ ℤ
The number of mid points of decreasing subsequences of length 3 in a permutation.....
St000372 Permutations ⟶ ℤ
The number of mid points of increasing subsequences of length 3 in a permutation.....
St000373 Permutations ⟶ ℤ
The number of weak exceedences of a permutation that are also mid-points of a dec....
St000374 Permutations ⟶ ℤ
The number of exclusive right-to-left minima of a permutation.
St000375 Permutations ⟶ ℤ
The number of non weak exceedences of a permutation that are mid-points of a decr....
St000401 Permutations ⟶ ℤ
The size of the symmetry class of a permutation.
St000402 Permutations ⟶ ℤ
Half the size of the symmetry class of a permutation.
St000404 Permutations ⟶ ℤ
The number of occurrences of the pattern 3241 or of the pattern 4231 in a permuta....
St000405 Permutations ⟶ ℤ
The number of occurrences of the pattern 1324 in a permutation.
St000406 Permutations ⟶ ℤ
The number of occurrences of the pattern 3241 in a permutation.
St000407 Permutations ⟶ ℤ
The number of occurrences of the pattern 2143 in a permutation.
St000408 Permutations ⟶ ℤ
The number of occurrences of the pattern 4231 in a permutation.
St000423 Permutations ⟶ ℤ
The number of occurrences of the pattern 123 or of the pattern 132 in a permutati....
St000424 Permutations ⟶ ℤ
The number of occurrences of the pattern 132 or of the pattern 231 in a permutati....
St000425 Permutations ⟶ ℤ
The number of occurrences of the pattern 132 or of the pattern 213 in a permutati....
St000426 Permutations ⟶ ℤ
The number of occurrences of the pattern 132 or of the pattern 312 in a permutati....
St000427 Permutations ⟶ ℤ
The number of occurrences of the pattern 123 or of the pattern 231 in a permutati....
St000428 Permutations ⟶ ℤ
The number of occurrences of the pattern 123 or of the pattern 213 in a permutati....
St000429 Permutations ⟶ ℤ
The number of occurrences of the pattern 123 or of the pattern 321 in a permutati....
St000430 Permutations ⟶ ℤ
The number of occurrences of the pattern 123 or of the pattern 312 in a permutati....
St000431 Permutations ⟶ ℤ
The number of occurrences of the pattern 213 or of the pattern 321 in a permutati....
St000432 Permutations ⟶ ℤ
The number of occurrences of the pattern 231 or of the pattern 312 in a permutati....
St000433 Permutations ⟶ ℤ
The number of occurrences of the pattern 132 or of the pattern 321 in a permutati....
St000434 Permutations ⟶ ℤ
The number of occurrences of the pattern 213 or of the pattern 312 in a permutati....
St000435 Permutations ⟶ ℤ
The number of occurrences of the pattern 213 or of the pattern 231 in a permutati....
St000436 Permutations ⟶ ℤ
The number of occurrences of the pattern 231 or of the pattern 321 in a permutati....
St000437 Permutations ⟶ ℤ
The number of occurrences of the pattern 312 or of the pattern 321 in a permutati....
St000440 Permutations ⟶ ℤ
The number of occurrences of the pattern 4132 or of the pattern 4231 in a permuta....
St000441 Permutations ⟶ ℤ
The number of successions (or small ascents) of a permutation.
St000446 Permutations ⟶ ℤ
The disorder of a permutation.
St000451 Permutations ⟶ ℤ
The length of the longest pattern of the form k 1 2.
St000457 Permutations ⟶ ℤ
The number of occurrences of one of the patterns 132, 213 or 321 in a permutation....
St000458 Permutations ⟶ ℤ
The number of permutations obtained by switching adjacencies or successions.
St000461 Permutations ⟶ ℤ
The rix statistic of a permutation.
St000462 Permutations ⟶ ℤ
The major index minus the number of excedences of a permutation.
St000463 Permutations ⟶ ℤ
The number of admissible inversions of a permutation.
St000470 Permutations ⟶ ℤ
The number of runs in a permutation.
St000471 Permutations ⟶ ℤ
The sum of the ascent tops of a permutation.
St000472 Permutations ⟶ ℤ
The sum of the ascent bottoms of a permutation.
St000483 Permutations ⟶ ℤ
The number of times a permutation switches from increasing to decreasing or decre....
St000484 Permutations ⟶ ℤ
The sum of St000483 over all subsequences of length at least three.
St000485 Permutations ⟶ ℤ
The length of the longest cycle of a permutation.
St000486 Permutations ⟶ ℤ
The number of cycles of length at least 3 of a permutation.
St000487 Permutations ⟶ ℤ
The length of the shortest cycle of a permutation.
St000488 Permutations ⟶ ℤ
The number of cycles of a permutation of length at most 2.
St000489 Permutations ⟶ ℤ
The number of cycles of a permutation of length at most 3.
St000494 Permutations ⟶ ℤ
The number of inversions of distance at most 3 of a permutation.
St000495 Permutations ⟶ ℤ
The number of inversions of distance at most 2 of a permutation.
St000500 Permutations ⟶ ℤ
Eigenvalues of the random-to-random operator acting on the regular representation....
St000501 Permutations ⟶ ℤ
The size of the first part in the decomposition of a permutation.
St000516 Permutations ⟶ ℤ
The number of stretching pairs of a permutation.
St000520 Permutations ⟶ ℤ
The number of patterns in a permutation.
St000530 Permutations ⟶ ℤ
The number of permutations with the same descent word as the given permutation.
St000534 Permutations ⟶ ℤ
The number of 2-rises of a permutation.
St000538 Permutations ⟶ ℤ
The number of even inversions of a permutation.
St000539 Permutations ⟶ ℤ
The number of odd inversions of a permutation.
St000541 Permutations ⟶ ℤ
The number of indices greater than or equal to 2 of a permutation such that all s....
St000542 Permutations ⟶ ℤ
The number of left-to-right-minima of a permutation.
St000545 Permutations ⟶ ℤ
The number of parabolic double cosets with minimal element being the given permut....
St000546 Permutations ⟶ ℤ
The number of global descents of a permutation.
St000570 Permutations ⟶ ℤ
The Edelman-Greene number of a permutation.
St000616 Permutations ⟶ ℤ
The inversion index of a permutation.
St000619 Permutations ⟶ ℤ
The number of cyclic descents of a permutation.
St000622 Permutations ⟶ ℤ
The number of occurrences of the patterns 2143 or 4231 in a permutation.
St000623 Permutations ⟶ ℤ
The number of occurrences of the pattern 52341 in a permutation.
St000624 Permutations ⟶ ℤ
The normalized sum of the minimal distances to a greater element.
St000625 Permutations ⟶ ℤ
The sum of the minimal distances to a greater element.
St000638 Permutations ⟶ ℤ
The number of up-down runs of a permutation.
St000646 Permutations ⟶ ℤ
The number of big ascents of a permutation.
St000647 Permutations ⟶ ℤ
The number of big descents of a permutation.
St000648 Permutations ⟶ ℤ
The number of 2-excedences of a permutation.
St000649 Permutations ⟶ ℤ
The number of 3-excedences of a permutation.
St000650 Permutations ⟶ ℤ
The number of 3-rises of a permutation.
St000651 Permutations ⟶ ℤ
The maximal size of a rise in a permutation.
St000652 Permutations ⟶ ℤ
The maximal difference between successive positions of a permutation.
St000653 Permutations ⟶ ℤ
The last descent of a permutation.
St000654 Permutations ⟶ ℤ
The first descent of a permutation.
St000662 Permutations ⟶ ℤ
The staircase size of the code of a permutation.
St000663 Permutations ⟶ ℤ
The number of right floats of a permutation.
St000664 Permutations ⟶ ℤ
The number of right ropes of a permutation.
St000665 Permutations ⟶ ℤ
The number of rafts of a permutation.
St000666 Permutations ⟶ ℤ
The number of right tethers of a permutation.
St000669 Permutations ⟶ ℤ
The number of permutations obtained by switching ascents or descents of size 2.
St000670 Permutations ⟶ ℤ
The reversal length of a permutation.
St000672 Permutations ⟶ ℤ
The number of minimal elements in Bruhat order not less than the permutation.
St000673 Permutations ⟶ ℤ
The size of the support of a permutation.
St000677 Permutations ⟶ ℤ
The standardized bi-alternating inversion number of a permutation.
St000690 Permutations ⟶ ℤ
The size of the conjugacy class of a permutation.
St000692 Permutations ⟶ ℤ
Babson and Steingrímsson's statistic stat of a permutation.
St000694 Permutations ⟶ ℤ
The number of affine bounded permutations that project to a given permutation.
St000696 Permutations ⟶ ℤ
The number of cycles in the breakpoint graph of a permutation.
St000702 Permutations ⟶ ℤ
The number of weak deficiencies of a permutation.
St000703 Permutations ⟶ ℤ
The number of deficiencies of a permutation.
St000709 Permutations ⟶ ℤ
The number of occurrences of 14-2-3 or 14-3-2.
St000710 Permutations ⟶ ℤ
The number of big deficiencies of a permutation.
St000711 Permutations ⟶ ℤ
The number of big exceedences of a permutation.
St000724 Permutations ⟶ ℤ
The label of the leaf of the path following the smaller label in the increasing b....
St000725 Permutations ⟶ ℤ
The smallest label of a leaf of the increasing binary tree associated to a permut....
St000726 Permutations ⟶ ℤ
The normalized sum of the leaf labels of the increasing binary tree associated to....
St000727 Permutations ⟶ ℤ
The largest label of a leaf in the binary search tree associated with the permuta....
St000731 Permutations ⟶ ℤ
The number of double exceedences of a permutation.
St000732 Permutations ⟶ ℤ
The number of double deficiencies of a permutation.
St000740 Permutations ⟶ ℤ
The last entry of a permutation.
St000742 Permutations ⟶ ℤ
The number of big ascents of a permutation after adding the value $\pi(0) = 0$.
St000750 Permutations ⟶ ℤ
The number of occurrences of the pattern 4213 in a permutation.
St000751 Permutations ⟶ ℤ
The number of occurrences of either of the pattern 2143 or 2143 in a permutation.....
St000756 Permutations ⟶ ℤ
The sum of the positions of the left to right maxima of a permutation.
St000779 Permutations ⟶ ℤ
The tier of a permutation.
St000794 Permutations ⟶ ℤ
The mak of a permutation.
St000795 Permutations ⟶ ℤ
St000796 Permutations ⟶ ℤ
The stat' of a permutation.
St000797 Permutations ⟶ ℤ
The stat of a permutation.
St000798 Permutations ⟶ ℤ
The makl of a permutation.
St000799 Permutations ⟶ ℤ
The number of occurrences of the vincular pattern |213 in a permutation.
St000800 Permutations ⟶ ℤ
The number of occurrences of the vincular pattern |231 in a permutation.
St000801 Permutations ⟶ ℤ
The number of occurrences of the vincular pattern |312 in a permutation.
St000802 Permutations ⟶ ℤ
The number of occurrences of the vincular pattern |321 in a permutation.
St000803 Permutations ⟶ ℤ
The number of occurrences of the vincular pattern |132 in a permutation.
St000804 Permutations ⟶ ℤ
The number of occurrences of the vincular pattern |123 in a permutation.
St000809 Permutations ⟶ ℤ
The reduced reflection length of the permutation.
St000824 Permutations ⟶ ℤ
The sum of the number of descents and the number of recoils of a permutation.
St000825 Permutations ⟶ ℤ
The sum of the number of major and the inverse major index of a permutation.
St000828 Permutations ⟶ ℤ
The spearman's rho of a permutation and the identity permutation.
St000829 Permutations ⟶ ℤ
The Ulam distance of a permutation to the identity permutation.
St000830 Permutations ⟶ ℤ
The total displacement of a permutation.
St000831 Permutations ⟶ ℤ
The number of indices that are either descents or recoils.
St000832 Permutations ⟶ ℤ
The number of permutations obtained by reversing blocks of three consecutive numb....
St000833 Permutations ⟶ ℤ
The comajor index of a permutation.
St000834 Permutations ⟶ ℤ
The number of right outer peaks of a permutation.
St000836 Permutations ⟶ ℤ
The number of descents of distance 2 of a permutation.
St000837 Permutations ⟶ ℤ
The number of ascents of distance 2 of a permutation.
St000842 Permutations ⟶ ℤ
St000844 Permutations ⟶ ℤ
The size of the largest block in the direct sum decomposition of a permutation.
St000862 Permutations ⟶ ℤ
The number of parts of the shifted shape of a permutation.
St000863 Permutations ⟶ ℤ
The length of the first row of the shifted shape of a permutation.
St000864 Permutations ⟶ ℤ
The number of circled entries of the shifted recording tableau of a permutation.
St000866 Permutations ⟶ ℤ
The number of admissible inversions of a permutation in the sense of Shareshian-W....
St000868 Permutations ⟶ ℤ
The aid statistic in the sense of Shareshian-Wachs.
St000871 Permutations ⟶ ℤ
The number of very big ascents of a permutation.
St000872 Permutations ⟶ ℤ
The number of very big descents of a permutation.
St000873 Permutations ⟶ ℤ
The aix statistic of a permutation.
St000879 Permutations ⟶ ℤ
The number of long braid edges in the graph of braid moves of a permutation.
St000880 Permutations ⟶ ℤ
The number of connected components of long braid edges in the graph of braid move....
St000881 Permutations ⟶ ℤ
The number of short braid edges in the graph of braid moves of a permutation.
St000882 Permutations ⟶ ℤ
The number of connected components of short braid edges in the graph of braid mov....
St000883 Permutations ⟶ ℤ
The number of longest increasing subsequences of a permutation.
St000884 Permutations ⟶ ℤ
The number of isolated descents of a permutation.
St000886 Permutations ⟶ ℤ
The number of permutations with the same antidiagonal sums.
St000887 Permutations ⟶ ℤ
The maximal number of nonzero entries on a diagonal of a permutation matrix.
St000891 Permutations ⟶ ℤ
The number of distinct diagonal sums of a permutation matrix.
St000923 Permutations ⟶ ℤ
The minimal number with no two order isomorphic substrings of this length in a pe....
St000956 Permutations ⟶ ℤ
The maximal displacement of a permutation.
St000957 Permutations ⟶ ℤ
The number of Bruhat lower covers of a permutation.
St000958 Permutations ⟶ ℤ
The number of Bruhat factorizations of a permutation.
St000959 Permutations ⟶ ℤ
The number of strong Bruhat factorizations of a permutation.
St000961 Permutations ⟶ ℤ
The shifted major index of a permutation.
St000962 Permutations ⟶ ℤ
The 3-shifted major index of a permutation.
St000963 Permutations ⟶ ℤ
The 2-shifted major index of a permutation.
St000988 Permutations ⟶ ℤ
The orbit size of a permutation under Foata's bijection.
St000989 Permutations ⟶ ℤ
The number of final rises of a permutation.
St000990 Permutations ⟶ ℤ
The first ascent of a permutation.
St000991 Permutations ⟶ ℤ
The number of right-to-left minima of a permutation.
St000994 Permutations ⟶ ℤ
The number of cycle peaks and the number of cycle valleys of a permutation.
St000996 Permutations ⟶ ℤ
The number of exclusive left-to-right maxima of a permutation.
St001004 Permutations ⟶ ℤ
The number of indices that are either left-to-right maxima or right-to-left minim....
St001005 Permutations ⟶ ℤ
The number of indices for a permutation that are either left-to-right maxima or r....
St001052 Permutations ⟶ ℤ
The length of the exterior of a permutation.
St001059 Permutations ⟶ ℤ
Number of occurrences of the patterns 41352,42351,51342,52341 in a permutation.
St001061 Permutations ⟶ ℤ
The number of indices that are both descents and recoils of a permutation.
St001074 Permutations ⟶ ℤ
The number of inversions of the cyclic embedding of a permutation.
St001076 Permutations ⟶ ℤ
The minimal length of a factorization of a permutation into transpositions that a....
St001077 Permutations ⟶ ℤ
The minimal length of a factorization of a permutation into star transpositions.
St001078 Permutations ⟶ ℤ
The minimal number of occurrences of (12) in a factorization of a permutation int....
St001079 Permutations ⟶ ℤ
The minimal length of a factorization of a permutation using the permutations (12....
St001080 Permutations ⟶ ℤ
The minimal length of a factorization of a permutation using the transposition (1....
St001081 Permutations ⟶ ℤ
The number of minimal length factorizations of a permutation into star transposit....
St001082 Permutations ⟶ ℤ
The number of boxed occurrences of 123 in a permutation.
St001083 Permutations ⟶ ℤ
The number of boxed occurrences of 132 in a permutation.
St001084 Permutations ⟶ ℤ
The number of occurrences of the vincular pattern |1-23 in a permutation.
St001085 Permutations ⟶ ℤ
The number of occurrences of the vincular pattern |21-3 in a permutation.
St001086 Permutations ⟶ ℤ
The number of occurrences of the consecutive pattern 132 in a permutation.
St001087 Permutations ⟶ ℤ
The number of occurrences of the vincular pattern |12-3 in a permutation.
St001090 Permutations ⟶ ℤ
The number of pop-stack-sorts needed to sort a permutation.

# 9. Maps

We have the following 42 maps from and to Permutations in the database:

Mp00002 Alternating sign matrices ⟶ Permutations
to left key permutation
Mp00014 Binary trees ⟶ Permutations
to 132-avoiding permutation
Mp00017 Binary trees ⟶ Permutations
to 312-avoiding permutation
Mp00023 Dyck paths ⟶ Permutations
to non-crossing permutation
Mp00024 Dyck paths ⟶ Permutations
to 321-avoiding permutation
Mp00025 Dyck paths ⟶ Permutations
to 132-avoiding permutation
Mp00031 Dyck paths ⟶ Permutations
to 312-avoiding permutation
Mp00053 Parking functions ⟶ Permutations
to car permutation
Mp00055 Parking functions ⟶ Permutations
to labelling permutation
Mp00058 Perfect matchings ⟶ Permutations
to permutation
Mp00059 Permutations ⟶ Standard tableaux
Robinson-Schensted insertion tableau
Mp00060 Permutations ⟶ Integer partitions
Robinson-Schensted tableau shape
Mp00061 Permutations ⟶ Binary trees
to increasing tree
Mp00062 Permutations ⟶ Permutations
inversion-number to major-index bijection
Mp00063 Permutations ⟶ Alternating sign matrices
to alternating sign matrix
Mp00064 Permutations ⟶ Permutations
reverse
Mp00065 Permutations ⟶ Posets
permutation poset
Mp00066 Permutations ⟶ Permutations
inverse
Mp00067 Permutations ⟶ Permutations
Foata bijection
Mp00068 Permutations ⟶ Permutations
Simion-Schmidt map
Mp00069 Permutations ⟶ Permutations
complement
Mp00070 Permutations ⟶ Standard tableaux
Robinson-Schensted recording tableau
Mp00071 Permutations ⟶ Integer compositions
descent composition
Mp00072 Permutations ⟶ Binary trees
binary search tree: left to right
Mp00073 Permutations ⟶ Permutations
major-index to inversion-number bijection
Mp00075 Semistandard tableaux ⟶ Permutations
Mp00080 Set partitions ⟶ Permutations
to permutation
Mp00081 Standard tableaux ⟶ Permutations
Mp00086 Permutations ⟶ Permutations
first fundamental transformation
Mp00087 Permutations ⟶ Permutations
inverse first fundamental transformation
Mp00088 Permutations ⟶ Permutations
Kreweras complement
Mp00089 Permutations ⟶ Permutations
Inverse Kreweras complement
Mp00090 Permutations ⟶ Permutations
cycle-as-one-line notation
Mp00108 Permutations ⟶ Integer partitions
cycle type
Mp00109 Permutations ⟶ Binary words
descent word
Mp00114 Permutations ⟶ Binary words
connectivity set
Mp00119 Dyck paths ⟶ Permutations
to 321-avoiding permutation (Krattenthaler)
Mp00126 Permutations ⟶ Permutations
cactus evacuation
Mp00127 Permutations ⟶ Dyck paths
left-to-right-maxima to Dyck path
Mp00129 Dyck paths ⟶ Permutations
to 321-avoiding permutation (Billey-Jockusch-Stanley)
Mp00130 Permutations ⟶ Binary words
descent tops
Mp00131 Permutations ⟶ Binary words
descent bottoms

## 9.1. Other maps

There is also the following map from permutations of $n$ to rooted trees of size $n+1$ described in the OEIS: A greedy decreasing subsequence of a word $w_1,\ldots,w_p$ in a totally ordered alphabet is given by scanning from left to right through the word, picking up a descent whenever possible. For example, the greedy decreasing subsequence of $5,4,4,6,5,2,3,1,1,2$ is given by $5,4,2,1$, picking up positions $1,2,6,8$. Let now be $\pi = [\pi_1,\ldots,\pi_n]$ a permutation of $\{1,\ldots,n\}$ in one-line notation. The associated rooted tree has $n+1$ nodes $\{0,\ldots,n\}$ with root $0$. The children of $0$ are given by the greedy decreasing subsequence of $\pi_1,\ldots,\pi_n$, and the children of a node $i$ are given by the greedy decreasing subsequence of the consecutive subword of $\pi_1,\ldots,\pi_n$ left out after $i$ in the greedy decreasing subsequence containing $i$. For example, the permutation $[2,4,5,3,1]$ has root $0$ with children $2$ and $1$, the node $1$ has children $4$ and $3$, and the node $4$ has child $5$.

# 10. References

[BrCl11]   P. Brändén and A. Claesson, Electron. J. Combin, 2011.

[Knu68]   D. Knuth, The Art Of Computer Programming Vol. 1, Boston: Addison-Wesley (1968).

[LS96]   A. Lascoux, M.-P. Schützenberger, Treillis et bases des groupes de Coxeter, Electron. J. Combin. 3(2) (1996).

[Man01]   L. Manivel, Symmetric functions, Schubert polynomials and degeneracy loci, SMF/AMS Texts and Monographs 6 (2001).