Pattern avoidance in coloured permutations
A coloured permutation of \(n\) is a permutation \(\psi = (\psi_1, \ldots, \psi_n)\) such that for each \(k \in [n]\), there is a color \(v_k\) associated with the assignment \(k \mapsto \psi_k\). We can write this as \(\psi = (\psi_1^{(v_1)}, \ldots, \psi_n^{(v_n)})\). If \(k \leq n\) and \(\varphi = (\varphi_1^{(s_1)}, \ldots, \varphi_k^{(s_k)})\), we say that \(\psi\) contains \(\varphi\), if there exist indices \(i_1, \ldots, i_k \in [n]\), \(i_1 < \cdots < i_k\), such that (i) for each \(j, l\), \(\varphi_j < \varphi_l\) iff \(\psi_{i_j} < \psi_{i_l}\), and (ii) for each \(j\), \(s_j = v_{i_j}\). If \(\psi\) does not contain \(\varphi\), we say that \(\psi\) is \(\varphi\)-avoiding. NEWLINENEWLINENEWLINEThis paper presents of a number of formulas of the form: given \(n\), \(r\), the number of \(r\)-colored permutations of \([n]\) that avoid all the colored permutations \(T = \{\varphi_1, \varphi_2, \ldots\}\) of \([2]\) is \(|S_n^{(r)}(T)|= \cdots\). For example, for any one such \(\varphi\), the number of \(\varphi\)-avoiding \(r\)-colored permutations of \([n]\) is \(|S_n^{(r)}(\varphi)|= \sum_{j=0}^n j!(r-1)^j \binom nj^2\). There are a few other results as well. Most of the proofs are elementary, although there is some basic work with a generating function.
- Coloured permutations containing and avoiding certain patterns
- Patterns in colored circular permutations
- Generalized pattern-matching conditions for C_k S_n
- Generalized pattern avoidance condition for the wreath product of cyclic groups with symmetric groups
- A Hamilton cycle in the \(k\)-sided pancake network
- Mixed coloured permutations
- Multicolor chain avoidance in the Boolean lattice
- Hamiltonicity of \(k\)-sided pancake networks with fixed-spin: efficient generation, ranking, and optimality
- Finding Patterns Avoiding Many Monochromatic Constellations
- Enumeration of Wilf classes in S_n o C_r for two patterns of length 3
- Avoiding colored partitions of lengths two and three
- Counting patterns in colored orthogonal arrays
- On the group of alternating colored permutations.
- \(n\)-Rainbow archetypal permutations and strings
- 1-colored archetypal permutations and strings of degree \(n\)
- Labelled well-quasi-order for permutation classes
- Inversion generating functions for signed pattern avoiding permutations
- scientific article; zbMATH DE number 6750761 (Why is no real title available?)
- Avoiding colored partitions of two elements in the pattern sense
- Inversion sequences and signed permutations
- Enumerating polynomial colored permutation classes
- Multicolored permutations, sequences, and tableaux
- Restricted colored permutations and Chebyshev polynomials
This page was built for publication: Pattern avoidance in coloured permutations
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5948366)
