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: