| | | **Enumeration of symmetry classes** |

## Enumeration of symmetry classes

Our
paradigmatic examples
are the actions of *G*, *H*, *H ´G*
and * H wr *_{X} G on *Y*^{X}, obtained from given actions _{G}X and _{H}Y. 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 *Y*^{X} 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 ÎY*^{X}, an element
*( y,g)* of * H wr *_{X} G and assume that
* bar (g)= Õ*_{ n=1}^{c( bar (g))}
(x_{ n}
gx_{ n} ...g^{l n-1}x_{ 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:
- Each
*f(x*_{ n}) is a fixed point of the
cycleproduct *h*_{ n}( y,
g):
*f(x*_{ n}) ÎY_{h n
( y,g)}.

- The other values of
*f* arise from the
values *f(x*_{ n}) according to
the following equations:
*f(x*_{ n})= y(x_{ n})f(g^{-1}x_{ n})= y(x_{ n}) y(g^{-1}
x_{ n})f(g^{-2}x_{ n})= ... .

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*^{-1}x)= y(x) y(g^{-1}x)f(g^{-2}x)
...

* ...= y(x) y(g*^{-1}x) ...y(g^{-l+1}x)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 ÎY*^{X} 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 *Y*^{X}, and the restrictions to the subgroups *G*, *H*
and *H ´G*
give the numbers of *G*-, *H*- and *H ´G*-classes
on *Y*^{X}:

**Theorem: **
*
If both *_{G}X and
_{H}Y 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 *Y*^{X}:
* | H wr *_{X} G \\Y^{X} | =**(**1**)/(** | H | ^{ | X | }
| G | **)** å_{( y,g) ÎH wr X G } Õ_{ n=1}^{c( bar (g))}
| Y_{h n( y,g)} | .

The restriction to *G*, *H* and *H ´G* according to
the formula yields:
* | G \\Y*^{X} | = **(**1**)/(** | G | **)**
å_{g ÎG} | Y | ^{c( bar (g))},
| H \\Y^{X} | = **(**1**)/(** | H | **)**
å_{h ÎH} | Y_{h}
| ^{ | X | },

and
* | (H ´G) \\Y*^{X} | =
**(**1**)/(** | H | | G | **)**
å_{(h,g) ÎH ´G} Õ_{i} | Y_{hi} | ^{ai( bar (g))}.

In order to apply these results to a
specific case it remains to evaluate
*c( bar (g)), | Y*_{h} | ,
| Y_{hi} | and *a*_{i}( bar (g)) or * | Y*_{h 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 *Y*^{X}.

last changed: January 19, 2005

| | | **Enumeration of symmetry classes** |