Pattern Avoidance in Coloured Permutations

Toufik Mansour

Séminaire lotharingien de combinatoire, Tome 46 (2001-2002)

Résumé

Let S_n be the symmetric group, C_r the cyclic group of order r, and let S_n^(r) be the wreath product of S_n and C_r; which is the set of all coloured permutations on the symbols 1,2,...,n with colours 1,2,...,r, which is the analogous of the symmetric group when r=1, and the hyperoctahedral group when r=2. We prove, for every 2-letter coloured pattern \phi in S₂^(r), that the number of \phi-avoiding coloured permutations in S_n^(r) is given by the formula \sum_{j=0}^n j! (r-1)^j {\binom n j}^2. Also we prove that the number of Wilf classes of restricted coloured permutations by two patterns with r colours in S₂^(r) is one for r=1, is four for r=2, and is six for r>=3.