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.
