Examples

Examples

A numerical example is provided by S ₃ wr S ₂. The set of proper partitions characterizing the conjugacy classes of S ₂ is

{ a | a|¾2 }= {(2),(1²) },

the set of corresponding cycle types is

{a | a |¾| 2 }= {(0,1),(2,0) }.

Thus the types of S ₃ wr S ₂ 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 _GY^X.

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

Y^X:=2 ^m´n= {(a_ij) | a_ij Î{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),(a_ij)) -> (a _{y^-1(j)i, p^-1 j}).

Since ( y, p)=( y,1)( i, p), we can do this in two steps:

(a_ij) -> (a_{i, p^-1j}) -> (a _{y^-1(j)i, p^-1j}).

Hence we can first of all permute the columns of (a_ij) in such a way that the numbers of 1's in the columns of the resulting matrix is nonincreasing from left to right: å_i a_{i, p^-11} ³å_i a_{i, 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 (a_ij) 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,ja_ij. Hence the orbits of S _m wr S _n on 2 ^m´n are characterized by the proper partitions a, where each part a_i £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, a₁ <= 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!ⁿn!)^-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.

Examples