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

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.

Proof:

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:

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

This cycle is of length *i*, and the cycles of this form arising from
different *k <= (i-1)/2* are pairwise disjoint. Furthermore these are all
the cycles arising from *(1, ...,i)* since, for each such *k*, we have,
as *i* is odd:

( {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

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

together with the *(i/2)*-cycle

( {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:

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

The length of each of these cyclic factors is * lcm (i,j)*, and their number
is therefore equal to * gcd (i,j)*.

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

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).

A table giving the first of these numbers looks as follows:

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 "at" uni-graz.at | http://www-ang.kfunigraz.ac.at/~fripert/ |

UNI-Graz | Institut für Mathematik |

UNI-Bayreuth | Lehrstuhl II für Mathematik |

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