edit this page

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

See also the wikipedia pages on permutations and on the symmetric group.

2. Examples

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

6. Properties

7. Remarks

8. Statistics

We have the following 263 statistics 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 of the Kazhdan-Lusztig polynomial $P(id,w)$ for each permutation $w$ i....
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 of a permutation
St000223
Permutations ⟶ ℤ
The number of nestings of a 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 ⟶ ℤ
The load of a permutation.
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 positions of mid points of increasing subsequences of length 3 in a....
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 cycle of a permutation of length at most 2.
St000489
Permutations ⟶ ℤ
The number of cycle 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 ⟶ ℤ
The mad of a permutation.
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 ⟶ ℤ
The breadth of a permutation.
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.

9. Maps

We have the following 42 maps 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
reading word permutation
Mp00080
Set partitions ⟶ Permutations
to permutation
Mp00081
Standard tableaux ⟶ Permutations
reading word permutation
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).

11. Sage examples