Notation
Suppose we are given a permutation group G on a set X. It induces
interesting structures both on X and on G that are closely related
(for more details cf. [7]). To begin with, there are the
orbits of the elements x∈ X: G(x): ={ gx | g∈ G
}⊆ X, two of which are either identical or disjoint.
Therefore, the set
| G\\X: ={ G(x) | x∈ X
}... |
of all the orbits is a set-partition of X. To the orbits
there correspond the stabilizers (which are in fact
subgroups): Gx := { g∈ G | gx=x}, and the close
relationship between orbits and stabilizers is the existence of the
following natural bijection between an orbit of an element and the
set of left cosets of its stabilizer:
The cycle index of G is the following polynomial Z(G) in
the indeterminates x1,x2,...,x|X|
over Q, defined by
| Z(G) := .. |
1
|G|
|
.. |
∑
g∈ G |
.. |
|X|
∏
i=1 |
xiai(g),.. |
where (a1(g),...,a|X| (g)) is the cycle type
of the permutation g∈ G. This means, g decomposes into
ai(g) disjoint cycles of length i for i=1,...,|X|. All
elements of a conjugacy class have the same cycle type, so the
cycle index can be computed in the following way:
| Z(G)=.. |
1
|G|
|
.. |
∑
C∈ C |
|C| .. |
|X|
∏
i=1 |
xiai(gC), .. |
where C is the system of conjugacy classes of G and where
gC is a representative of the conjugacy class C.
Let G and H denote permutation groups on X and Y, respectively.
The wreath product H≀XG is a permutation group on the set
YX:={f: X→ Y}, defined by
| H≀XG:=HX × G={(ψ,g) |
ψ∈ HX, g∈ G}.. |
with multiplication (ψ,g)(ψ', g')=(ψψ'g,
gg'), where ψψ'g(x) :=
ψ(x)ψ'g (x) and ψ'g(x) :=
ψ'(g-1x). In the case when G≤ Sn and
X=n:={0,1,...,n-1} we write H≀G
instead of H≀nG.
The wreath product H≀XG
acts in a natural way on YX. The effect of the
permutation (ψ,g)∈ H≀XG on f∈ YX is
The following lemma ([10][9]) reduces the action of a wreath product
to the action of the group G on the set of all functions from X
into the set of all orbits of H on Y:
Lehmann's Lemma:
If G and H denote permutation groups on X and Y, respectively,
then G acts on (H\\Y)X in the following way:
Moreover, the mapping
| Φ: H≀XG\\YX→
G\\(H\\Y)X,(H≀XG(f)) ↦ G(F) .. |
is a bijection if F∈ (H\\Y)X is given by
F(x)=H(f(x)).
There are many enumerative and constructive results dealing with
various group actions on the set YX induced by
permutation groups on the domain X and on the range Y. For example,
Sn × H acts upon Yn by
| (π,h)(f):= h o f o
π-1. .. |
The corresponding generating function for the numbers of
Sn × H-orbits on Yn is given by (see [1]):
| .. |
∞
∑
n=0 |
|(Sn ×
H)\\Yn|xn=Z(H)|xi=.. |
∞
∑
j=0 |
xij =Z(H)|
xi=(1)/(1-xi).
.. |
The group action of above can be restricted to the set of all
injective mappings from n to Y, the corresponding generating
function is
| .. |
∞
∑
n=0 |
|(Sn ×
H)\\Yninj|xn= Z(H)|
xi=1+xi. .. |
harald.fripertinger "at" uni-graz.at, May 10,
2016
