The cycle type of the induced action on 2-subsets |

Proof:Lemma:IfpÎS, then_{ v}

- Each
i-cycle ofp,iodd, contributes tobar ( p)exactly(i-1)/2cyclic factors, each of which is ani-cycle.- Each
i-cycle ofp,ieven, contributes tobar ( p)exactly one cycle of lengthi/2and(i/2)-1further cycles, which are of lengthi.- Each pair of cyclic factors of
p, say ani-cycle and aj-cycle, contributes tobar ( p)exactlygcd (i,j)cyclic factors, each of which has the lengthlcm (i,j).- All the cyclic factors of
bar ( p)arise in this way.

i) First let *i* be odd. Without loss of generality we may
assume that the *i*-cycle in question is
*(1, ...,i)*. Consider a positive *k <= (i-1)/2*. Then
* bar ( p)* contains the following cyclic permutation of *2*-subsets:

This cycle is of length( {1,k+1 }, {2,k+2 }, ..., {i-k,i }, {1,i-k+1 }, ..., {k,i }).

( {1,k+1 }, {2,k+2 }, ...)=( {1,i-k+1 }, {2,i-k+2 }, ...).

ii) If *i* is even, say *i=2j*, we
may assume that the cyclic factor of
* p* is *(1 ...2j)*. It yields, for *2 <= k <= j*, the *(i/2)-1* different
*i*-cycles

together with the( {1,k }, {2,k+1 }, ..., {i-k+1,i }, {1,i-k+2 }, ..., {k-1,i }),

( {1,j+1 }, ..., {j,2j }).

iii) A pair of cyclic factors of * p*, say
the pair *(1...i)(i+1...i+j)*
contributes to * bar ( p)* the following product of disjoint cycles:

The length of each of these cyclic factors is( {1,i+k }, {2,i+k+1 }, ...)( {1,i+k+1 }, {2,i+k+2 }, ...) ...

iv) is clear.

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

Corollary:For eachbar ( p)on[we have:vchoose 2]

- If
iis odd, thena_{i}( bar ( p))=(a_{i}( p))/(2)(i ·a_{i}( p)-1)+a_{2i}( p) + å_{r<s lcm(r,s)=i}a_{r}( p)a_{s}( p) gcd (r,s).- If
iis even, thena_{i}( bar ( p))=(a_{i}( p))/(2)(i ·a_{i}( p)-2)+a_{2i}( p) + å_{r<s lcm(r,s)=i}a_{r}( p)a_{s}( p) gcd (r,s).- The total number of cyclic factors is
c( bar ( p))=(1)/(2)å_{i}i ·a_{i}( p)^{2}-(1)/(2)å_{i odd}a_{i}( p) + å_{r<s}a_{r}( p)a_{s}( p) gcd (r,s).

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 *2*-subsets.

Thus, by an application of the Cauchy-Frobenius Lemma, we obtain

A table giving the first of these numbers looks as follows:Corollary:The number ofk-graphs onvvertices is equal towherev!^{-1}å_{ pÎSv}(k+1)^{c( bar ( p))},c( bar ( p))is as above. More explicitly and in terms of cycle types ofv(see Corollary) this number is equal toå_{a |¾| v}((k+1)^{c bar (a)})/(Õ_{i}i^{ai}a_{i}!), where c_{ bar (a)}:=(1)/(2)å_{i}i ·a_{i}^{2}-(1)/(2)å_{i odd}a_{i}+ å_{r<s}a_{r}a_{s}gcd (r,s).

Check these numbers and compute some more of them.

v \k 0 1 2 3 4 1 1 1 1 1 1 2 1 2 3 4 5 3 1 4 10 20 35 4 1 11 66 276 900 5 1 34 792 10688 90005 6 1 156 25506 1601952 43571400

harald.fripertinger@kfunigraz.ac.at,

last changed: August 28, 2001

The cycle type of the induced action on 2-subsets |