Permutations

Contents

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

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

# 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

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.

# 7. Remarks

The symmetric group is a Coxeter group and a finite reflection group.

The symmetric group admits a beautiful representation theory.

# 8. Statistics

We have the following **234 statistics** in the database:

# 9. Maps

We have the following **27 maps** in the database:

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

*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