Permutations

1. Definition

A permutation of a set $\mathcal{S}$ is a bijection $\psi : \mathcal{S} \tilde\rightarrow \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 such a permutatio $\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 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 252 statistics on Permutations in the database:

The number of ways to write a permutation as a minimal length product of simple t....
The number of occurrences of the pattern 123 in a permutation.
The major index of a permutation.
The number of saliances of the permutation.
The number of inversions of a permutation.
The cardinality of the complement of the connectivity set.
The rank of the permutation.
The number of descents of a permutation.
The number of fixed points of a permutation.
The number of inner peaks of a permutation.
The number of stack-sorts needed to sort a permutation.
The depth of a permutation.
The sum of the descent differences of a permutations.
The number of cycles in the cycle decomposition of a permutation.
The number of permutations greater than or equal to the given permutation in (str....
The maximum defect over any reduced expression for a permutation and any subexpre....
The number of left outer peaks of a permutation.
The evaluation of the Kazhdan-Lusztig polynomial $P(id,w)$ for each permutation $w$ i....
The sign of a permutation.
The number of crossings of a permutation.
The number of regions of inversion arrangement of a permutation.
The first entry of the permutation.
The inversion sum of a permutation.
The decomposition (or block) number of a permutation.
The order of a permutation.
The greater neighbor of the maximum.
The length of the longest increasing subsequence of the permutation.
The number of one-box pattern of a permutation.
The number of alternating sign matrices whose left key is the permutation.
The number of outer peaks of a permutation.
The number of valleys of a permutation, including the boundary.
The number of elements less than or equal to the given element in Bruhat order.
The number of permutations less than or equal to given permutation in left weak o....
The sum of the descent tops (or Genocchi descents) of a permutation.
The number of occurrences of the pattern 321 in a permutation.
The difference in Coxeter length of a permutation and its image under the Simion-....
The cardinality of the preimage of the Simion-Schmidt map.
The "bounce" of a permutation.
The maximum drop size of a permutation.
The number of adjacent cycles of a permutation.
The sum of the descent bottoms of a permutation.
The number of exceedances (also excedences) of a permutation.
The Denert index of a permutation.
The number of nontrivial cycles of a permutation $\pi$ in its cycle decomposition.
Maximum difference of elements in cycles.
Minimum over maximum difference of elements in cycles.
The number of weak exceedances (also weak excedences) of a permutation.
The number of adjacencies (or small descents) of a permutation.
The number of adjacencies of a permutation, 0 appended.
The absolute length of a permutation.
The number of occurrences of the pattern 312 in a permutation.
The number of occurrences of the pattern 213 in a permutation.
The number of occurrences of the pattern 231 in a permutation.
The number of occurrences of the pattern 132 in a permutation.
The number of strong fixed points of a permutation.
The number of alignments of a permutation
The number of nestings of a permutation
The sorting index of a permutation.
The convexity of a permutation.
The number of global ascents of a permutation.
The number of indices $i$ such that $\pi_i \neq i+1$ considered cyclically.
The number of indices $i$ such that $\pi_i \in \{ i,i+1 \}$ considered cyclically.
The number of indices $i$ such that $\pi_i=i+1$.
The number of indices $i$ such that $\pi_i \notin \{i,i+1\}$.
The number of indices $i$ such that $\pi_i \in \{i,i+1\}$.
The number of indices $i$ for which $\pi_i \neq i+1$.
The number of indices $i$ such that $\pi_i = i+1$ considered cyclically.
The number of indices $i$ such that $\pi_i \notin \{ i,i+1 \}$ considered cyclically.....
The number of cyclic valleys and cyclic peaks of a permutation.
The number of ascents of a permutation.
The number of non-inversions of a permutation.
The number of reduced Kogan faces with the permutation as type.
The size of the preimage of the map 'cycle-as-one-line notation' from Permutation....
The size of the preimage of the map 'to labelling permutation' from Parking funct....
The inverse major index of a permutation.
The height of the tree associated to a permutation.
The number of left-to-right-maxima of a permutation.
The number of non-left-to-right-maxima of a permutation.
The cycle descent number of a permutation.
The shape of the tree associated to a permutation.
The width of the tree associated to a permutation.
The dez statistic, the number of descents of a permutation after replacing fixed ....
The maz index, the major index of a permutation after replacing fixed points by z....
The lec statistic, the sum of the inversion numbers of the hook factors of a perm....
The number of pixed points of a permutation.
The maf index of a permutation.
The non-inversion sum of a permutation.
The cosine of a permutation.
The Elizalde-Pak rank of a permutation.
The number of inner valleys of a permutation.
The number of recoils of a permutation.
The number of occurrences of the pattern 21-3.
The number of occurrences of the pattern 13-2.
The number of occurrences of the pattern 12-3.
The number of occurrences of the pattern 31-2.
The number of occurrences of the pattern 23-1.
The number of occurrences of the pattern 32-1.
The number of double ascents of a permutation.
The number of double descents of a permutation.
The number of simsun double descents of a permutation.
The number of positions mid points of decreasing subsequences of length 3 in a pe....
The number of positions of mid points of increasing subsequences of length 3 in a....
The number of weak exceedences of a permutation that are also mid-points of a dec....
The number of non weak exceedences of a permutation that are also not mid-points ....
The number of non weak exceedences of a permutation that are mid-points of a decr....
The size of the symmetry class of a permutation.
Half the size of the symmetry class of a permutation.
The number of occurrences of the pattern 3241 or of the pattern 4231 in a permuta....
The number of occurrences of the pattern 1324 in a permutation.
The number of occurrences of the pattern 3241 in a permutation.
The number of occurrences of the pattern 2143 in a permutation.
The number of occurrences of the pattern 4231 in a permutation.
The number of occurrences of the pattern 123 or of the pattern 132 in a permutati....
The number of occurrences of the pattern 132 or of the pattern 231 in a permutati....
The number of occurrences of the pattern 132 or of the pattern 213 in a permutati....
The number of occurrences of the pattern 132 or of the pattern 312 in a permutati....
The number of occurrences of the pattern 123 or of the pattern 231 in a permutati....
The number of occurrences of the pattern 123 or of the pattern 213 in a permutati....
The number of occurrences of the pattern 123 or of the pattern 321 in a permutati....
The number of occurrences of the pattern 123 or of the pattern 312 in a permutati....
The number of occurrences of the pattern 213 or of the pattern 321 in a permutati....
The number of occurrences of the pattern 231 or of the pattern 312 in a permutati....
The number of occurrences of the pattern 132 or of the pattern 321 in a permutati....
The number of occurrences of the pattern 213 or of the pattern 312 in a permutati....
The number of occurrences of the pattern 213 or of the pattern 231 in a permutati....
The number of occurrences of the pattern 231 or of the pattern 321 in a permutati....
The number of occurrences of the pattern 312 or of the pattern 321 in a permutati....
The number of occurrences of the pattern 4132 or of the pattern 4231 in a permuta....
The number of successions (or small ascents) of a permutation.
The disorder of a permutation.
The length of the longest pattern of the form k 1 2.
The number of occurrences of one of the patterns 132, 213 or 321 in a permutation....
The number of permutations obtained by switching adjacencies or successions.
The rix statistic of a permutation.
The major index minus the number of excedences of a permutation.
The number of admissible inversions of a permutation.
The number of runs in a permutation.
The sum of the ascent tops of a permutation.
The sum of the ascent bottoms of a permutation.
The number of times a permutation switches from increasing to decreasing or decre....
The sum of St000483 over all subsequences of length at least three.
The length of the longest cycle of a permutation.
The number of cycles of length at least 3 of a permutation.
The length of the shortest cycle of a permutation.
The number of cycle of a permutation of length at most 2.
The number of cycle of a permutation of length at most 3.
The number of inversions of distance at most 3 of a permutation.
The number of inversions of distance at most 2 of a permutation.
Eigenvalues of the random-to-random operator acting on the regular representation....
The size of the first part in the decomposition of a permutation.
The number of stretching pairs of a permutation.
The number of subsequences of a permutation which are not order-isomorphic.
The number of permutations with the same descent word as the given permutation.
The number of 2-rises of a permutation.
The number of even inversions of a permutation.
The number of odd inversions of a permutation.
The number of indices greater than or equal to 2 of a permutation such that all s....
The number of left-to-right-minima of a permutation.
The number of parabolic double cosets with minimal element being the given permut....
The number of global descents of a permutation.
The Edelman-Greene number of a permutation.
The inversion index of a permutation.
The number of cyclic descents of a permutation.
The number of occurrences of the patterns 2143 or 4231 in a permutation.
The number of occurrences of the pattern 52341 in a permutation.
The normalized sum of the minimal distances to a greater element.
The sum of the minimal distances to a greater element.
The number of up-down runs of a permutation.
The number of big ascents of a permutation.
The number of big descents of a permutation.
The number of 2-excedences of a permutation.
The number of 3-excedences of a permutation.
The number of 3-rises of a permutation.
The maximal size of a rise in a permutation.
The maximal difference between successive positions of a permutation.
The last descent of a permutation.
The first descent of a permutation.
The staircase size of the code of a permutation.
The number of right floats of a permutation.
The number of right ropes of a permutation.
The number of rafts of a permutation.
The number of right tethers of a permutation.
The number of permutations obtained by switching ascents or descents of size 2.
The reversal length of a permutation.
The number of minimal elements in Bruhat order not less than the permutation.
The size of the support of a permutation.
The standardized bi-alternating inversion number of a permutation.
The size of the conjugacy class of a permutation.
Babson and Steingrímsson's statistic stat of a permutation.
The number of affine bounded permutations that project to a given permutation.
The number of cycles in the breakpoint graph of a permutation.
The number of weak deficiencies of a permutation.
The number of deficiencies of a permutation.
The number of occurrences of 14-2-3 or 14-3-2.
The number of big deficiencies of a permutation.
The number of big exceedences of a permutation.
The label of the leaf of the path following the smaller label in the increasing b....
The smallest label of a leaf of the increasing binary tree associated to a permut....
The normalized sum of the leaf labels of the increasing binary tree associated to....
The largest label of a leaf in the binary search tree associated with the permuta....
The number of double exceedences of a permutation.
The number of double deficiencies of a permutation.
The last entry of a permutation.
The number of big ascents of a permutation after adding the value $\pi(0) = 0$.
The number of occurrences of the pattern 4213 in a permutation.
The number of occurrences of either of the pattern 2143 or 2143 in a permutation.....
The sum of the positions of the left to right maxima of a permutation.
The tier of a permutation.
The mak of a permutation.
The stat' of a permutation.
The stat of a permutation.
The makl of a permutation.
The number of occurrences of the vincular pattern |213 in a permutation.
The number of occurrences of the vincular pattern |231 in a permutation.
The number of occurrences of the vincular pattern |312 in a permutation.
The number of occurrences of the vincular pattern |321 in a permutation.
The number of occurrences of the vincular pattern |132 in a permutation.
The number of occurrences of the vincular pattern |123 in a permutation.
The reduced reflection length of the permutation.
The sum of the number of descents and the number of recoils of a permutation.
The sum of the number of major and the inverse major index of a permutation.
The spearman's rho of a permutation and the identity permutation.
The Ulam distance of a permutation to the identity permutation.
The total displacement of a permutation.
The number of indices that are either descents or recoils.
The number of permutations obtained by reversing blocks of three consecutive numb....
The comajor index of a permutation.
The number of right outer peaks of a permutation.
The number of descents of distance 2 of a permutation.
The number of ascents of distance 2 of a permutation.
The size of the largest block in the direct sum decomposition of a permutation.
The number of parts of the shifted shape of a permutation.
The length of the first row of the shifted shape of a permutation.
The number of circled entries of the shifted recording tableau of a permutation.
The number of admissible inversions of a permutation in the sense of Shareshian-W....
The aid statistic in the sense of Shareshian-Wachs.
The number of very big ascents of a permutation.
The number of very big descents of a permutation.
The aix statistic of a permutation.
The number of long braid edges in the graph of braid moves of a permutation.
The number of connected components of long braid edges in the graph of braid move....
The number of short braid edges in the graph of braid moves of a permutation.
The number of connected components of short braid edges in the graph of braid mov....
The number of longest increasing subsequences of a permutation.
The number of isolated descents of a permutation.
The number of permutations with the same antidiagonal sums.
The maximal number of nonzero entries on a diagonal of a permutation matrix.
The number of distinct diagonal sums of a permutation matrix.
The minimal number with no two order isomorphic substrings of this length in a pe....

9. Maps

We have the following 42 maps in the database:

to left key permutation
to 132-avoiding permutation
to 312-avoiding permutation
to non-crossing permutation
to 321-avoiding permutation
to 132-avoiding permutation
to 312-avoiding permutation
to car permutation
to labelling permutation
to permutation
Robinson-Schensted insertion tableau
Robinson-Schensted tableau shape
to increasing tree
inversion-number to major-index bijection
to alternating sign matrix
reverse
permutation poset
inverse
Foata bijection
Simion-Schmidt map
complement
Robinson-Schensted recording tableau
descent composition
binary search tree: left to right
major-index to inversion-number bijection
to permutation
first fundamental transformation
inverse first fundamental transformation
Kreweras complement
Inverse Kreweras complement
cycle-as-one-line notation
cycle type
descent word
connectivity set
to 321-avoiding permutation (Krattenthaler)
cactus evacuation
left-to-right-maxima to Dyck path
to 321-avoiding permutation (Billey-Jockusch-Stanley)
descent tops
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).