2022-12-28
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.
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.
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.
- Dominant — 132-avoiding.
- 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]{Tenner2007}. Enumerated by odd-indexed Fibonacci numbers, A001519.
- Fully commutative — 123-avoiding, see [BJS93GPRT22].
- 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.
- 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.$
- 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, 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 — 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.