Cycle indicator polynomials |

This polynomial can be obtained from the polynomial(1)/(| G |)å_{gÎG}Õ_{i=1}^{ | X | }( å_{yÎY}y^{i})^{ai(bar (g))}.

by simply replacing the indeterminateC(G,X):=(1)/(| G |)å_{gÎG}Õ_{i=1}^{ | X | }z_{i}^{ai(bar (g))}ÎQ[z_{1},...,z_{ | X | }]

In order to generalize the substitution process mentioned above which yields the generating function fromCorollary:The number ofG-classes onYis equal to^{X}C(G,X; | Y | ,..., | Y | ).

and call this processC(G,X | p(u_{1},...,u_{m}))=(1)/(| G |)å_{gÎG}Õ_{i=1}^{ | X | }p(u_{1}^{i},...,u_{m}^{i})^{ai(bar (g))}ÎQ[u_{1}, ...],

In order to countPólya's TheoremThe generating function for the enumeration ofG-classes onYby content can be obtained from the cycle indicator of^{X}by Pólya-substituting_{G}Xåinto the cycle indicator polynomial_{yÎY}yC(G,X). Hence this generating function is equal toC(G,X | å_{yÎY}y).

Examples:of cycle indicator polynomials

- The cycle indicator of the identity subgroup of
Sand its natural action on_{n}isnC({1},n)=z_{1}^{n}.- The cycle indicator of the natural action of the cyclic group
Con_{n}is (recall the corollary on the number of different necklaces)nC(C_{n},n)=(1)/(n)å_{d | n}f(d)z_{d}^{n/d}.- The cycle indicator of the natural action of the dihedral group
Dof order_{n}2non the set(which can be considered as being the set of vertices of the regularnn-gon, of whichDis the symmetry group) satisfies_{n}C(D_{n},n)=(1)/(2)C(C_{n},n)+(1)/(2)z_{1}z_{2}^{(n-1)/2}if n is odd,This follows from the fact that the rotations form a cyclic subgroup of orderC(D_{n},n)=(1)/(2)C(C_{n},n)+(1)/(4)(z_{2}^{n/2}+z_{1}^{2}z_{2}^{(n-2)/2}) if n is even.n, while the remaining reflections either leave exactly one vertex fixed (in the case whennis odd) or two vertices or none (in the case whennis even), and group the remaining vertices into pairs of vertices that are mapped onto each other.- Furthermore we have the following cycle indicators of the natural actions of
Sand_{n}A(cf. the descripton of the conjugacy classes of_{n}Sand exercise):_{n}C(S_{n},n)=å_{a|¾| n}Õ_{k}(1)/(a_{k}!)((z_{k})/(k))^{ak},C(A_{n},n) = å_{a|¾| n}(1+(-1)^{a2+a4+...}) Õ_{k}(1)/(a_{k}!)((z_{k})/(k))^{ak}.

For the graphs on 4 vertices we use the cycle index (exercise)

which is obtained from the corollary on the induced action on the set of 2-sets. It yields the generating functionC(S_{4},[4choose 2])=(1)/(24)(z_{1}^{6}+9z_{1}^{2}z_{2}^{2}+8z_{3}^{2}+ 6z_{2}z_{4}),

in accordance with figure.C(S_{4},[4choose 2] | y_{0}+y_{1})= y_{0}^{6}+y_{0}^{5}y_{1}+2y_{0}^{4}y_{1}^{2}+ 3y_{0}^{3}y_{1}^{3}+2y_{0}^{2}y_{1}^{4}+y_{0}y_{1}^{5}+y_{1}^{6},

The graphs on 4 points

In order to make life easier we can replace
*y _{0}+...+y_{m-1}* by

Here the coefficient ofC(S_{4},[4choose 2] | 1+y)= 1+y+2y^{2}+3y^{3}+2y^{4}+y^{5}+y^{6}.

These examples have shown that the evaluation of the cycle indicator polynomial is an important step towards the solution of various enumeration problems, so that a few remarks concerning this are well in order. The cycle indicators of the natural actions ofCorollary:The total number of graphs onvvertices is equal towhile the number of selfcomplementary graphs onC(S_{v},[vchoose 2];2,...,2),vvertices is equal toThe number of graphs onC(S_{v},[vchoose 2];0,2,0,2,...).vvertices which containeedges is the coefficient ofyin the polynomial^{e}C(S_{v},[vchoose 2] | 1+y).

Further important constructions are the plethysmLemma:Letand_{G}Xdenote finite actions. We have_{H}YandC(G´H,X DOTCUP Y)=C(G,X)·C(H,Y),C(G´H,X´Y)=(1)/(| G | | H |)å_{(g,h)}Õ_{i,k=1}^{ | X | | Y | }z_{lcm(i,k)}^{gcd(i,k)ai(bar (g) )ak(bar (h))}.

From the description of the conjugacy classes of elements of complete monomial groups we obtain forC(G[H],Y´X)=C(H G,| Y | | X |).

Finally we show how the cycle indicator polynomialC(H,Y) C(G,X):=(1)/(| G |)å_{g}Õ_{k=1}^{ | X | }((1)/(| H |)å_{h}Õ_{i=1}^{ | Y | }z_{i·k}^{ai(bar (h))})^{ak(bar (g))}.

(cf. the lemma describing the powers of a cycle for the last equation). The inversion procedure uses the number theoretic Moebius function and the corresponding inversion theorem, but as we are going to use also other Moebius functions later on we shall describe this inversion method in a slightly more general context than is actually needed here.c(g^{k})=a_{1}(bar (g^{k}))=a_{1}(bar (g)^{k})=å_{d | k}d·a_{d}(bar (g))

We start doing so by introducing the notion of *incidence algebra*.
Let
*(P, <= )* denote a *poset*
(partially ordered set). Its partial order * <= *
allows us to introduce *intervals*
*[p,q]:={rÎP | p <= r <= q}.* If
all these intervals are finite, then *(P, <= )* is called a *locally finite*
poset.
Assuming this and denoting by * F* a field, we can turn the set

of all theI_{F}(P):={j:P^{2}->F| j(p,q)=0 unless p <= q}

while the local finiteness allows to define the(j+y)(p,q):=j(p,q)+y(p,q) , (rj)(p,q):= r·j(p,q), rÎF,

This makes(j y)(p,q):=å_{rÎ[p,q]}j(p,r)y(r,q).

d(p,q):=1 if p=q

As scalar mutiplication and convolution satisfyd(p,q):=0 otherwise.

this ring is even anr(j y)=(rj) y=j (ry),

and soj -> F:=(j(p_{i},p_{k})),

A specific invertible incidence function is theLemma:For each locally finite partial order(P,£)and anyjÎIthe following is true:_{F}(P)

jis invertible if and only if, for eachpÎP, we havej(p,p) not = 0.- If
jis invertible, thenjsatisfies^{-1}j, and^{-1}(p,p)=j(p,p)^{-1}j^{-1}(p,q) =-j(q,q)^{-1}å_{rÎ[p,q)}j^{-1}(p,r)j(r,q)where as usual=-j(p,p)^{-1}å_{rÎ(p,q]}j(p,r)j^{-1}(r,q),[p,q)and(p,q]denote half open intervals.

z(p,q):=1 if p <= q,

Its inverse is called thez(p,q):=0 otherwise.

This close connection between the zeta and the Moebius function provides a very useful inversion theorem which we introduce next. In a posetm(p,q)=-å_{rÎ[p,q)}m(p,r)=-å_{rÎ(p,q]}m(r,q).

Proof: We prove the first statement, the second one follows analogously. We add toThe Moebius InversionLet(P, <= )denote a locally finite poset and letFandGdenote mappings fromPinto the field. ThenF

- if all the principal ideals of P are finite, we have the following equivalence of systems of equations:
" p: G(p)=å_{q <= p}F(q) iff " p: F(p)=å_{q <= p}G(q)m(q,p).- If all the principal filters of
Pare finite, we have the following equivalence of systems of equations:" p: G(p)=å_{q >= p}F(q) iff " p: F(p)=å_{q >= p}m(p,q)G(q).

j(p,q):=F(q) if p=0 and q>0,

j(p,q):=0 otherwise,

y(p,q):=G(q) if p=0 and q>0,

The system of equationsy(p,q):=0 otherwise.

A particular locally finite poset is *( N^{*}, | )*, the set
of positive natural numbers
together with divisibility as its partial order. The corresponding

In order to apply this result, we need to know the values of the number theoretic Moebius function. AsCorollary:For each finite actionthe following equivalent systems of equations hold:_{G}Xwhere" k: a_{1}(bar (g)^{k})=å_{d | k}d·a_{d}(bar (g)) and " k: a_{k}(bar (g))=(1)/(k)å_{d | k}m(k/d)a_{1}(bar (g)^{d}),mdenotes the number theoretic Moebius function. In particular we obtain the following expression of the cycle indicator ofin terms of the character_{G}Xcof:_{G}XC(G,X)=(1)/(| G |)å_{g}Õ_{i}z_{i}^{i-1Sd | i m(i/d)c(gd)}.

if[1,p_{1}^{k1}]´...´[1,p_{r}^{kr}],

But from the recursion for the Moebius function we can deduce thatm(n/d):=m(d,n)=m(1,n/d)=Õ_{i=1}^{r}m(1,p_{i}^{ki}).

m(n)=1 if n=1

m(n)=(-1)^{r}if n is a product of r different primes,

m(n)=0 otherwise.

Examples:

- The
exterior cycle indexofbar (G) <= Sis defined to be the cycle indicator of the natural action of_{X}Son the set of left cosets_{X}S. The permutation character of this action is (exercise)_{X}/bar (G)This together with an application of the formula for computing the cycle type yields the exterior cycle indexc(p)=(| X | ! | C^{S}(p)Çbar (G) |)/(| bar (G) | | C^{S}(p) |).ofC(S_{X},S_{X}/bar (G))bar (G).- The character of
Son the set_{X}[X choose k]of all thek-subsets ofXissince ac(p)=å_{b|¾| k}Õ_{i=1}^{k}[a_{i}(p) choose b_{i}] ,k-subset is fixed underpif and only if it is the union of cyclically permuted points. Hence we can apply the formula for computing the cycle type in order to evaluateC(G,[X choose k])= C(bar (G),[X choose k]). A particular case isC(Swhich we need for the enumeration of graphs on_{v},i [vchoose 2])vvertices, and which is obtained from the corollary on the induced action on the set of 2-sets:c(bar (p))=[a_{1}(p) choose 2]+a_{2}(p).

harald.fripertinger@kfunigraz.ac.at,

last changed: August 28, 2001

Cycle indicator polynomials |