Permutation/Sequence Types to implement

[ruthhoffmann]

Permutation/Sequence Types that were mentioned at Permutation Patterns 2022

• Involutions
• Stirling Permutations
• m-Stirling Permutations
• quasi-Stirling Permutations
• "Toothbrush" permutations (not the actual name (yet), check Troyka's abstract)

[ruthhoffmann]

Definition of a Stirling Permutation (Ira M. Gessel and Richard P. Stanley. Stirling polynomials. J. Combinatorial Theory
Ser. A, 1978.)

Stirling permutations are permutations p_{1}p_{2} ... p_{2n} of the multiset {1,1,2,2,...,n,n} satisfying that, if i < j < k and p_{i} = p_{k}, then p_{j} > p_{i}; in other words, avoiding the pattern 212.

[ruthhoffmann]

Definition of quasi-Stirling Permutation (Kassie Archer, Adam Gregory, Bryan Pennington, and Stephanie Slayden. Pat-
tern restricted quasi-Stirling permutations. Australas. J. Combin., 2019.)

Quasi-Stirling permutations are permutations p_{1}p_{2} ... p_{2n} of the multiset {1,1,2,2,...,n,n} that avoid 1212 and 2121, meaning that there do not exist i < j < l < m such that p_{i} = p_{l} and p{j} = p_{m}.

[ruthhoffmann]

Definition of a r-Stirling Permutation (Justin Troyka, Permutation Patterns, 2022)

An r-Stirling permutation of degree k is a permutation p of the multiset {1^{r} , . . . , k^{r}} such that the values between two t’s are all at least t; that is, if a < b < c and p_{a} = p{c}, then p_{b} ≥ p_{a}.

[ruthhoffmann]

Definition of an involution

An involution p is a permutation such that p=p^{-1} or p^{2} is the identity.
OR
A permutation is an involution if and only if it can be written as a finite product of disjoint transpositions.