Pattern avoidance in coloured permutations (Q5948366)

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. This 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.