Examples
A numerical example is provided by S 3
wr S 2. The set of proper
partitions characterizing the conjugacy classes of S 2 is
{ a | a|¾2 }= {(2),(12) },
the set of corresponding cycle types is
{a | a |¾| 2 }= {(0,1),(2,0) }.
Thus the types of S 3 wr S 2
turn out to be
The orders of the conjugacy classes are 6,18,12,1,9,4,6,4,12.
We now describe an interesting action of S m wr S n which
is in fact an action of the form GYX.
Example:
The action of S m wr S n on mn is obviously
similar to the following
action of
S m wr S n on the set m´n:
S m wr S n ´( m´n) -> m´n:(( y, p),(i,j)) -> ( y( pj)i, pj).
The corresponding permutation group on m´n will be denoted by
S n [ S m ]
and called the composition
of S n and S m , while
G[H]
will be used for the permutation group on Y ´X, induced by the
natural action of H wr X G on Y ´X.
The action of the wreath product S m wr S n on m´n
induces a natural action of S m wr S n on the set
YX:=2 m´n= {(aij) | aij Î{0,1 },i Î m,j Î n },
i.e. on the set of 0-1-matrices consisting of m rows and n columns:
S m wr S n ´2 m´n :(( y, p),(aij)) -> (a y-1(j)i, p-1 j).
Since ( y, p)=( y,1)( i, p),
we can do this in two steps:
(aij) -> (ai, p-1j)
-> (a y-1(j)i, p-1j).
Hence we can first of all permute the columns of (aij) in
such a way that the numbers of 1's in the columns of the resulting matrix
is nonincreasing from left to right:
åi ai, p-11 ³åi ai, p-12 ³...
And after having carried out
this permutation with a suitable p, we can find
a yÎS m * that moves the 1's of each column in flush top
position. This proves that the orbit of (aij)
under S m wr S n is characterized by an element of the form
1 | ... | ... | ... | 1 | | |
. | | | . | | | |
1 | ... | 1 | | | | |
| | | | | | 0
|
(which is an element of
2 m´n),
i.e. by a proper partition of k:= åi,jaij. Hence the orbits of
S m wr S n on 2 m´n are characterized by the
proper partitions a, where each part ai £n and where the total number of parts is £m:
Corollary:
There exists a natural bijection
S m wr S n \\2 m´n -> { a|¾k | k <= mn, a1 <= n, l( a) £m }.
Hence an application of the Cauchy-Frobenius Lemma yields
the following formula for the number of partitions of this form:
| S m wr S n \\2 m´n | =
(m!nn!)-1 å( y, p) ÎS m wr S n 2 S n
c(h n( y, p)),
which can be made more explicit by an application of the Lemma.
last changed: January 19, 2005