Notation

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): G_x:={ 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:

G(x) -> G/G_x, gx -> gG_x.

The cycle index of G is the following polynomial Z(G) in the indeterminates x₁,x₂,...,x_{| X |} over Q, defined by

Z(G):=(1)/(|G|)å_gÎGÕ_i=1^|X|x_i^a_i(g),

where (a₁(g),...,a_|X| (g)) is the cycle type of the permutation gÎG. This means, g decomposes into a_i(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| Õ_i=1^|X|x_i^a_i(g_C),

where C is the system of conjugacy classes of G and where g_C is a representative of the conjugacy class C.

Let G and H denote permutation groups on X and Y, respectively. The wreath product H wr _XG is a permutation group on the set Y^X:={f:X -> Y}, defined by

H wr _XG:=H^X´G={(y,g) | yÎH^X, gÎG}

with multiplication (y,g)(y', g')=(yy'_g, gg'), where yy'_g(x):=y(x)y'_g (x) and y'_g(x):=y'(g^-1x). In the case when G£S_n and X=n:={0,1,...,n-1} we write H wr G instead of H wr _nG.

The wreath product H wr _XG acts in a natural way on Y^X. The effect of the permutation (y,g)ÎH wr _XG on fÎY^X is

(y,g)(f)=: [~f] , where [~f] (x)=y(g)f(g^-1x).

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:
g(f):= f o g^-1.
Moreover, the mapping
F:H wr _XG\\Y^X -> G\\(H\\Y)^X,(H wr _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 Y^X induced by permutation groups on the domain X and on the range Y. For example, S_n´H acts upon Yⁿ by

(p,h)(f):= h o f o p^-1.

The corresponding generating function for the numbers of S_n´H-orbits on Yⁿ is given by (see [1]):

å_n=0^¥|(S_n´H)\\Yⁿ|xⁿ=Z(H) | _{x_i=å_j=0^¥x^ij} =Z(H) | _{x_i=(1)/(1-xⁱ)}.

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^¥|(S_n´H)\\Yⁿ_inj|xⁿ= Z(H) | _{x_i=1+xⁱ}.

harald.fripertinger@kfunigraz.ac.at,
last changed: January 23, 2001

Notation