2023-11-06

## Permutation matrices

For permutations $\pi,\sigma \in \symS_n,$ we think of multiplication as composition of functions, so that

\[ (\pi \circ \sigma)(k) = \pi(\sigma(k)) \text{ for $k \in [n].$} \]Given $\pi,$ we associate its permutation matrix,

\[ P_\pi = \left( \delta_{i, \pi(j)} \right)_{1 \leq i, j \leq n}. \]The permutation matrix of the composition $\pi \circ \sigma$ is $P_{\pi} P_{\sigma}.$
We follow the convention in [Kit11]
and illustrate permutation matrices by letting row indices start at the *bottom*,
as in the figure below.
From now on, this is the picture we have in mind when referring to permutation matrices.

**Example.**

The permutation matrix $P_\pi$ associated with $\pi = [1, 8, 5, 3, 7, 4, 6, 2]$ using conventional row/column coordinates, and the convention we use. The rightmost figure is simply the graph of the function $i \mapsto \pi(i)$ (using Cartesian coordinates).

$ 8$ | $\,$ | $\bullet$ | $\,$ | $\,$ | $\,$ | $\,$ | $\,$ | $\,$ |

$ 7$ | $\,$ | $\,$ | $\,$ | $\,$ | $\bullet$ | $\,$ | $\,$ | $\,$ |

$ 6$ | $\,$ | $\,$ | $\,$ | $\,$ | $\,$ | $\,$ | $\bullet$ | $\,$ |

$ 5$ | $\,$ | $\,$ | $\bullet$ | $\,$ | $\,$ | $\,$ | $\,$ | $\,$ |

$ 4$ | $\,$ | $\,$ | $\,$ | $\,$ | $\,$ | $\bullet$ | $\,$ | $\,$ |

$ 3$ | $\,$ | $\,$ | $\,$ | $\bullet$ | $\,$ | $\,$ | $\,$ | $\,$ |

$ 2$ | $\,$ | $\,$ | $\,$ | $\,$ | $\,$ | $\,$ | $\,$ | $\bullet$ |

$ 1$ | $\bullet$ | $\,$ | $\,$ | $\,$ | $\,$ | $\,$ | $\,$ | $\,$ |

$ 1$ | $ 2$ | $ 3$ | $ 4$ | $ 5$ | $ 6$ | $ 7$ | $ 8$ |

### Permutation patterns

A permutation $\pi \in \symS_n$ is said to contain the pattern $\sigma \in \symS_k,$ if there is a subsequence of $\pi$ which is order-isomorphic to $\sigma.$ For example, $\pi = [1, 8, 5, 3, 7, 4, 6, 2]$ contains the pattern $[2,3,1]$ as the subsequence $3, 6, 2$ in $\pi$ have its elements in the same relative order.

**Example.**

The permutation matrices associated with $\pi = [1, 8, 5, 3, 7, 4, 6, 2]$ and $\sigma = [2,3,1].$ Here we see that $\pi$ contains the pattern $\sigma$ (there are other instances of this pattern in $\pi$).

$\,$ | $\bullet$ | $\,$ | $\,$ | $\,$ | $\,$ | $\,$ | $\,$ |

$\,$ | $\,$ | $\,$ | $\,$ | $\bullet$ | $\,$ | $\,$ | $\,$ |

$\,$ | $\,$ | $\,$ | $\,$ | $\,$ | $\,$ | $\odot$ | $\,$ |

$\,$ | $\,$ | $\bullet$ | $\,$ | $\,$ | $\,$ | $\,$ | $\,$ |

$\,$ | $\,$ | $\,$ | $\,$ | $\,$ | $\bullet$ | $\,$ | $\,$ |

$\,$ | $\,$ | $\,$ | $\odot$ | $\,$ | $\,$ | $\,$ | $\,$ |

$\,$ | $\,$ | $\,$ | $\,$ | $\,$ | $\,$ | $\,$ | $\odot$ |

$\bullet$ | $\,$ | $\,$ | $\,$ | $\,$ | $\,$ | $\,$ | $\,$ |

$\,$ | $\bullet$ | $\,$ |

$\bullet$ | $\,$ | $\,$ |

$\,$ | $\,$ | $\bullet$ |

The structure of a permutation matrix avoiding the pattern $132.$ The larger regions on the left and right are also $132$-avoiding.

In [Vat19], the author studies possible growth rates for pattern-avoiding permutations.

### Direct sums and skew sums of permutations

Given $\pi \in \symS_m$ and $\sigma \in \symS_n,$ we define the direct sum and the skew sum of $\pi$ and $\sigma$ as

\begin{align} \pi \ast \sigma \coloneqq & [pi_1,\dotsc,\pi_m,\sigma_1+m,\dotsc,\sigma_n+m] \in \symS_{m+n} \\ \pi \times \sigma \coloneqq & [pi_1+n,\dotsc,\pi_m+n,\sigma_1,\dotsc,\sigma_n] \in \symS_{m+n} \end{align}Note that these operations are not commutative, but they are associative.

## Named sets of permutation

- Up-down — in one-line notation, we have $\pi_1 \lt \pi_2 \gt \pi_3 \lt \pi_4 \dotsb.$ Down-up permutations are of the form $\pi_1 \gt \pi_2 \lt \pi_3 \gt \pi_4 \dotsb.$ Enumerated by the Euler numbers A000111.
- André — Either up-down or down-up, A001250.
- Derangements — permutations with no fixed point, A000166.
- Dominant — 132-avoiding. Enumerated by the Catalan numbers, A000108.
- Baxter — avoids $2-14-3$ and $3-14-2,$ see https://doi.org/10.1016/S0012-365X(97)00112-X.
- Boolean — 123-avoiding and 3412-avoiding, see [Ten07GPRT22]. A permutation is boolean iff the order ideal it defines in the Bruhat order, is a Boolean lattice, see [Thm. 4.3, Ten07]. Enumerated by odd-indexed Fibonacci numbers, A001519.
- Fully commutative — 123-avoiding, see [BJS93GPRT22]. Enumerated by the Catalan numbers, A000108.
- A simsun permutation is a permutation such that restricting to entries $1,2,\dotsc,k,$ it does not have a double descent, i.e., $\pi(i)\gt \pi(i+1) \gt \pi(i+2),$ see [MY16]. The number of simsun permutations in $\symS_n$ is given by the Euler number $E_{n+1},$ see A000111.
- A permutation is vexillary if it avoids the pattern 2143, see A005802.
- A permutation is Grassmann if it has at most one descent. These are special cases of vexillary permutations. There are $2^n-n$ Grassman permutations in $\symS_n,$ see A000325.
- A permutation $\pi$ is bi-Grassmann if both $\pi$ and $\pi^{-1}$ are Grassman. Equivalent with avoiding 2413. This set has size $1+\binom{n+1}{3}.$
- Flattened permutations, where runs are in lex order. Enumerated by Bell numbers A000110, see [Prop. 16, NRB20].
- Parity-alternating permutations are permutations which sends odd numbers to odd numbers, and even numbers to even, see [KR21a]. This can be generalized to mod-k-alternating permutations, where we demand that $\pi(i) \equiv i \mod k.$ For pattern-avoidance in mod-k-alternating permutations, see [AFGQ22].
- The Richardson permutation with parameters $(k_1,k_2,\dotsc,k_m)$
is given by the following in two-line notation.
\[
\begin{pmatrix}
1 & 2 & \dotsc & k_1 & k_1+1 & k_1+2 & \dotsc & k_1 + k2 & k_1+k_2+1 & \dotsc \\
k_1 & k_1-1 & \dotsc, 1 & k_1+k_2 & k_1+k_2-1 & \dotsc & k_1+1 & k_1+k_2+k_3 & \dotsc \\
\end{pmatrix}
\]
Basically, we take the unique longest permutation in each of the sets $\symS_{k_1},\dotsc,\symS_{k_m},$
and produce the
*direct sum*of these. - Wachs permutations — A359039. These are the permutations in $\symS_n$ defined as \[ W_n \coloneqq \{ \sigma \in \symS_n : |\sigma^{-1}(i)-\sigma^{-1}(i^*)|\leq 1 \text{ for all } i \in [n-1] \}, \] where $i^*$ is defined as \[ i^* \coloneqq \begin{cases} i-1 &\text{if $i$ is even} \\ i+1 &\text{if $i$ is odd and $i+1 \leq n$} \\ n & \text{otherwise.} \end{cases} \] These permutations are studied in [BS22], and there are generalizations to other types.

## Permutations of type B

The set of permutations of type $B,$ is defined as the permutations on $B_n \coloneqq \{\pm 1, \pm 2,\dotsc, \pm n\}$ with the property that $\pi(-i)=-\pi(i).$ This is also known as the hyperoctahedral group.

## Stirling permutations

In [GS78], Gessel and Stanley introduced the set of Stirling permutations, $Q_n$. These are permutations of the multiset $\{1,1,2,2,3,3,\dotsc,n,n\}$ with the additional property that for between the two entries equal to $i \in [n],$ only entries larger than $i$ may appear. For example, $12234431$ is an element in $Q_n.$

We have that $|Q_n| = (2n-1)!!.$

## References

- [AFGQ22] Per Alexandersson, Samuel Asefa Fufa, Frether Getachew and Dun Qiu. Pattern-avoidance and Fuss–Catalan numbers. arXiv e-prints, 2022.
- [BJS93] Sara C. Billey, William Jockusch and Richard P. Stanley. Some combinatorial properties of Schubert polynomials. Journal of Algebraic Combinatorics, 2(4):345–374, 1993.
- [BS22] Francesco Brenti and Paolo Sentinelli. Wachs permutations, Bruhat order and weak order. arXiv e-prints, 2022.
- [GPRT22] Emily Gunawan, Jianping Pan, Heather M. Russell and Bridget Eileen Tenner. Rsk tableaux and the weak order on fully commutative permutations. arXiv e-prints, 2022.
- [GS78] Ira Gessel and Richard P Stanley. Stirling polynomials. Journal of Combinatorial Theory, Series A, 24(1):24–33, January 1978.
- [Kit11] Sergey Kitaev. Patterns in permutations and words. Springer Berlin Heidelberg, 2011.
- [KR21a] Frether Getachew Kebede and Fanja Rakotondrajao. Parity alternating permutations starting with an odd integer. Enumerative Combinatorics and Applications, 2021(2):Article {\#}S2R16, March 2021.
- [MY16] Shi-Mei Ma and Yeong-Nan Yeh. The peak statistics on simsun permutations. The Electronic Journal of Combinatorics, 23(2), April 2016.
- [NRB20] Olivia Nabawanda, Fanja Rakotondrajao and Alex Samuel Bamunoba. Run distribution over flattened partitions. Journal of Integer Sequences, 23, 2020.
- [Ten07] Bridget Eileen Tenner. Pattern avoidance and the Bruhat order. Journal of Combinatorial Theory, Series A, 114(5):888–905, July 2007.
- [Vat19] Vincent Vatter. Growth rates of permutation classes: from countable to uncountable. Proceedings of the London Mathematical Society, 119(4):960–997, May 2019.