Algebraic Combinatorics -- Surjective symmetry classes

Surjective symmetry classes

Surjective symmetry classes

In order to derive the number of surjective fixed points of (h,g) we use the preceeding corollaries together with an application of the Principle of Inclusion and Exclusion in order to get rid of the nonsurjective fixed points. We denote by Y_n the set of points y ÎY contained in the n-th cyclic factor of bar (h) and put, for each index set I Íc ( bar (h)):

Y^X_(h,g),I:= {f ÎY^X_(h,g) | " nÎI:f^-1[Y_n] = Æ}.

Then, by the Principle of Inclusion and Exclusion, we obtain for the desired number of surjective fixed points of (h,g) the following expression:

| Y^X_s,(h,g) | = | Y^X*_(h,g) | = å_{I Íc( bar (h))}(-1)^{| I |} | Y^X_(h,g),I |

= å_{I Íc( bar (h))}(-1)^{c
( bar (h))- | I |} | Y^X_{(h,g), c( bar (h)) \I} | .

Now we recall that

Y^X_{(h,g), c( bar (h)) \I}= {f ÎY^X_(h,g) | " n not ÎI:f^-1[Y_n]= Æ}.

This set can be identified with [~Y] ^X_{( [~h] ,g)}, where [~h] denotes the product of the cyclic factors of bar (h) the numbers of which lie in I, and where [~Y] is the set of points contained in these cyclic factors. Thus

| Y^X_{(h,g), c( bar (h)) \I} | = | [~Y] ^X_{( [~h] ,g)} | = Õ_j | [~Y] _{[~h] ^j} | ^{a_j( bar (g))}.

We can make this more explicit by an application of lemma which yields:

| [~Y] _{[~h] ^j} | =a₁( [~h] ^j)= å_{d | j}d ·a_d( [~h] ).

Putting these things together we conclude

Corollary: The number of surjective fixed points of (h,g) is
| Y^X_s,(h,g) | = å^{c( bar (h))}_k=1(-1)^{c( bar (
h))-k} å_a Õ^{| Y |}_i=1[a_i( bar (h)) choose a_i] Õ_j=1^{| X |} ( å_{d | j}d ·a_d )^{a_j( bar (g))},
where the middle sum is taken over all the sequences a=(a₁, ...,a_{| Y |}) of natural numbers a_j such that åa_j =k (they correspond to all possible choices of [~h] out of h, where a_i of the chosen cyclic factors of [~h] are i-cycles). Hence the numbers of surjective fixed points of g and of h amount to:
| Y^X_s,g | = å_k=1^{| Y |}(-1)^{| Y | -k} [ | Y | choose k]k^{c( bar (g))},
and
| Y^X_s,h | = å_k=1^{c( bar (h))}(-1)^{c( bar (h))-k} å_a( Õ_i [a_i( bar (h)) choose a_i])a₁^{| X |},
where the sum is taken over all the sequences (a₁, ...,a_{| Y |}), a_i Î N and åa_i=k.

An application of the Cauchy-Frobenius Lemma finally yields the desired numbers of surjective symmetry classes:

Theorem: The number | (H ´G) \\Y^X_s | of surjective H ´G-classes is
(1)/( | H | | G | ) å_(h,g) å_k=1^{c( bar (h))}(-1)^{c( bar (h))-k} å_a Õ_i=1 ^{| Y |}[a_i( bar (h)) choose a_i] Õ_j=1^{| X |} ( å_{d | j}d ·a_d )^{a_j( bar (g))},
where the inner sum is taken over the sequences a=(a₁, ...a_{| Y |}) described in the corollary above. This implies, by restriction, the equations
| G \\Y^X_s | =(1)/( | G | ) å_g å_k=1^{| Y
|}(-1)^{| Y | -k}[ | Y | choose k]k^{c( bar (g))},
and
| H \\Y^X_s | =(1)/( | H | ) å_h å_k=1^{c( bar (h))}(-1)^{c( bar (h))-k} å_a( Õ_i[a_i( bar (h)) choose a_i])a₁^{| X |},
where the last sum is to be taken over all the sequences a=(a₁, ...,a_{| Y |}) such that a_i Î N and åa_i=k.

Try to compute the number of surjective symmetry classes for various group actions.

harald.fripertinger@kfunigraz.ac.at,
last changed: August 28, 2001

Surjective symmetry classes