Séminaire Lotharingien de Combinatoire, B46g (2001), 12 pp.

Toufik Mansour

Pattern Avoidance in Coloured Permutations

Abstract. Let Sn be the symmetric group, Cr the cyclic group of order r, and let Sn(r) be the wreath product of Sn and Cr; 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 S2(r), that the number of \phi-avoiding coloured permutations in Sn(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 S2(r) is one for r=1, is four for r=2, and is six for r>=3.

Received: June 24, 2001; Accepted: Oct. 17, 2001.

The following versions are available: