search

stacs-cp / permutation-classes-cp

0 stars 2 forks source link

Permutation/Sequence Types to implement #2

Open ruthhoffmann opened 2 years ago

ruthhoffmann commented 2 years ago

Permutation/Sequence Types that were mentioned at Permutation Patterns 2022

ruthhoffmann commented 1 year ago

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 commented 1 year ago

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 commented 1 year ago

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 commented 1 year ago

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.