The cycle type of the induced action on 2-subsets

. Lemma   If , then

• Each -cycle of , odd, contributes to exactly cyclic factors, each of which is an -cycle.
• Each -cycle of , even, contributes to exactly one cycle of length and further cycles, which are of length .
• Each pair of cyclic factors of , say an -cycle and a -cycle, contributes to exactly cyclic factors, each of which has the length .
• All the cyclic factors of arise in this way.

Proof:

i) First let be odd. Without loss of generality we may assume that the -cycle in question is . Consider a positive . Then contains the following cyclic permutation of -subsets:

This cycle is of length , and the cycles of this form arising from different are pairwise disjoint. Furthermore these are all the cycles arising from since, for each such , we have, as is odd:

ii) If is even, say , we may assume that the cyclic factor of is . It yields, for , the different -cycles

together with the -cycle

iii) A pair of cyclic factors of , say the pair contributes to the following product of disjoint cycles:

The length of each of these cyclic factors is , and their number is therefore equal to .

iv) is clear.

This lemma yields the cycle structure of and the desired number of cyclic factors which we need in order to evaluate the number of graphs on vertices by an application of the Cauchy-Frobenius Lemma:

. Corollary   For each on we have:

• If is odd, then

  

• If is even, then

  

• The total number of cyclic factors is

  

In the next two programs you can enter a permutation and compute the cycle type and the total number of cyclic factors of the induced permutation on -subsets.