Cycle indicator polynomials |

We have seen in Pólya's Theorem that the generating
function for the enumeration of
the *G*-classes on *Y ^{X}* by weight is equal to

(1)/(| G |)å_{gÎG}Õ_{i=1}^{ | X | }( å_{yÎY}y^{i})^{ai(bar (g))}.

This polynomial can be obtained from the polynomial

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

by simply replacing the indeterminate *z _{i}* by the polynomial

Corollary:The number ofG-classes onYis equal to^{X}C(G,X; | Y | ,..., | Y | ).

In order to generalize the substitution process
mentioned above which yields
the generating function from *C(G,X)*, we put, for any polynomial
*p* in
* Q[u_{1},...,u_{m}]*,

C(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}, ...],

and call this process *Pólya-substitution*.
Using this notation we
can rephrase corollary as follows:

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

In order to count *G*-classes by content it therefore remains to evaluate
the cycle indicator of * _{G}X*. A few examples should be welcome:

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)

C(S_{4},[4choose 2])=(1)/(24)(z_{1}^{6}+9z_{1}^{2}z_{2}^{2}+8z_{3}^{2}+ 6z_{2}z_{4}),

which is obtained from the corollary on the induced action on the set of 2-sets. It yields the generating function

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},

in accordance with figure.

The graphs on 4 points

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

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

Here the coefficient of *y ^{e}* is equal to the number of graphs on 4 vertices
which possess exactly

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

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 of *S _{n} *,

Lemma: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))}.

Further important constructions are the plethysm
*H G*, and the composition.
They are defined as permutation
groups induced by *similar actions* of *H wr _{X} G *, and so the
corresponding cycle indicator polynomials are the same:

C(G[H],Y´X)=C(H G,| Y | | X |).

From the description of the conjugacy classes
of elements of complete monomial groups we obtain for
*C(H G, | Y | | X | )* the following

C(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))}.

Finally we show how the cycle indicator polynomial *C(G,X)*
can be obtained from the character
*c:g -> | X _{g} | *
of the action

c(g^{k})=a_{1}(bar (g^{k}))=a_{1}(bar (g)^{k})=å_{d | k}d·a_{d}(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.

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

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

of all the *incidence functions*
into an * F*-algebra. The following
addition and scalar multiplication define a vector space structure:

(j+y)(p,q):=j(p,q)+y(p,q) , (rj)(p,q):= r·j(p,q), rÎF,

while the local finiteness allows to define the *convolution*
product by

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

This makes *I _{F}(P)* into a ring (exercise). The
identity element is the Kronecker

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

d(p,q):=0 otherwise.

As scalar mutiplication and convolution satisfy

r(j y)=(rj) y=j (ry),

this ring is even an * F*-

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

and so *j* is invertible if and only if the values *j(p,p)*
are nonzero. But this is true also in the more general case when we only
assume *(P,£)* to be locally finite, since then we can easily show
that the incidence function recursively defined
in the second item of the following
lemma is in fact an inverse with respect to the convolution product:

Lemma: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.

A specific invertible incidence function is the *zeta function*
which describes the partial order in question:

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

z(p,q):=0 otherwise.

Its inverse is called the *Moebius function* of *(P, <= )*:
*m:=z ^{-1}*,
for which we obtain from the preceeding lemma the following recursions:

m(p,q)=-å_{rÎ[p,q)}m(p,r)=-å_{rÎ(p,q]}m(r,q).

This close connection between the zeta and the Moebius function
provides a very useful inversion theorem which we
introduce next. In a poset *(P, <= )* the sets *{qÎP | q <= p}*
are called the *principal (order-)ideals*

of *P*, while the sets
*{qÎP | q >= p}* are called the *principal filters*
. The
inversion theorem now reads as follows:

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

Proof: We prove the first statement, the second one follows analogously.
We add to *P* an element 0 such that *0<p*, for
each *pÎP*, obtaining
a new poset *(bar (P)=PÈ{0}, <= )*. As all the principal ideals of
*(P, <= )* are supposed to be finite, *(bar (P), <= )* is a locally finite
poset. Now we associate to *F* and *G* the incidence functions *jyÎI _{F}(bar (P))* defined by

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,

y(p,q):=0 otherwise.

The system of equations *G(p)=å _{q <= p}F(q)* is equivalent to the identity

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

Corollary: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)}.

In order to apply this result, we need to know the values
of the number theoretic Moebius function. As *z* is defined by the partial
order, the same holds for the Moebius function, and hence the Moebius function
is the same for order isomorphic posets. Thus the values of the Moebius
function on *( N^{*}, | )* can be evaluated by noting that the
Moebius function is multiplicative and that an
interval

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

if *n/d* has the prime number decomposition *n/d=p _{1}^{k1}·...·p_{r}^{kr}*, where the

m(n/d):=m(d,n)=m(1,n/d)=Õ_{i=1}^{r}m(1,p_{i}^{ki}).

But from the recursion for the Moebius function
we can deduce that *m(1)=1,m(p)=-1*, if *p* is
prime, and *m(p ^{r})=0*, if

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

UNI-Graz | Institut für Mathematik |

UNI-Bayreuth | Lehrstuhl II für Mathematik |

Cycle indicator polynomials |