The involution principleActionsComplete monomial groupsEnumeration of symmetry classes

Enumeration of symmetry classes

Our paradigmatic examples are the actions of G, H, H ´G and H wr X G on YX, obtained from given actions GX and HY. The orbits of these groups are called symmetry classes of mappings. If we want to be more explicit, we call them G-classes, H-classes, H ´G-classes and H wr X G -classes, respectively. Their total number can be obtained by an application of the Cauchy-Frobenius Lemma as soon as we know the number of fixed points for each element of the respective group. In order to derive these numbers we characterize the fixed points of each ( y,g) ÎH wr X G on YX and then we use the natural embedding of G, H and H ´G in H wr X G as described above. Thus the following lemma will turn out to be crucial:
Lemma: Consider an f ÎYX, an element ( y,g) of H wr X G and assume that
bar (g)= Õ n=1c( bar (g)) (x n gx n ...gl n-1x n)
is the disjoint cycle decomposition of bar (g), the permutation of X which corresponds to g. Then f is a fixed point of ( y,g) if and only if the following two conditions hold:
Proof: The formula says that f is fixed under ( y,g) if and only if its values f(x) satisfy the equations
f(x)= y(x)f(g-1x)= y(x) y(g-1x)f(g-2x) ...
...= y(x) y(g-1x) ...y(g-l+1x)f(x),
where l denotes the length of the cyclic factor of bar (g) containing the point x ÎX. Hence in particular the following must be true:
f(x n)=h n( y,g)f(x n),
which means that f(x n) is a fixed point of h n( y,g), as claimed. Thus any fixed f ÎYX clearly has the stated properties, and vice versa.

This, together with the Cauchy-Frobenius Lemma, yields the number of H wr X G -classes on YX, and the restrictions to the subgroups G, H and H ´G give the numbers of G-, H- and H ´G-classes on YX:

Theorem: If both GX and HY are finite actions, then we obtain the following expression for the total number of orbits of the corresponding action of H wr X G on YX:
| H wr X G \\YX | =(1)/( | H | | X | | G | ) å( y,g) ÎH wr X G Õ n=1c( bar (g)) | Yh n( y,g) | .
The restriction to G, H and H ´G according to the formula yields:
| G \\YX | = (1)/( | G | ) åg ÎG | Y | c( bar (g)), | H \\YX | = (1)/( | H | ) åh ÎH | Yh | | X | ,
and
| (H ´G) \\YX | = (1)/( | H | | G | ) å(h,g) ÎH ´G Õi | Yhi | ai( bar (g)).
In order to apply these results to a specific case it remains to evaluate c( bar (g)), | Yh | , | Yhi | and ai( bar (g)) or | Yh n ( y,g) | which still can be quite cumbersome as the following example shows.

Try to compute the number of symmetry classes of mappings for various group actions. Furthermore you can compute a transversal of G-classes on YX.

  • Graphs
  • The cycle type of the induced action on 2-subsets
  • Some congruences
  • Exercises
    • harald.fripertinger@kfunigraz.ac.at,
    last changed: August 28, 2001

    The involution principleActionsComplete monomial groupsEnumeration of symmetry classes