Enumeration by weight |

In the preceding chapter group actions
were introduced, the
Cauchy-Frobenius Lemma was proved, and
we studied certain actions of groups on sets of the
form *Y ^{X}* in some detail. We saw that various structures like graphs and
partitions can be defined as orbits on such sets in a natural way so that
we already have a method at hand to evaluate the

The Cauchy-Frobenius Lemma, weighted formLetdenote a finite action and_{G}Xw:X -> Ra map fromXinto a commutative ringRcontainingas a subring. IfQwis constant on the orbits ofGonX, then we have, for any transversalTof the orbits:å_{tÎT}w(t)=(1)/(| G |)å_{gÎG}å_{xÎXg}w(x)=(1)/(| bar (G) |)å_{bar (g)Îbar (G)}å_{xÎXbar (g)}w(x).

Proof: The following equations are clear from the foregoing, except maybe the
last one which uses the assumption that *w* is constant on the orbits:

å_{gÎG}å_{xÎXg}w(x)=å_{x}å_{gÎGx}w(x)

=å_{x}| G_{x}| w(x) = | G | å_{x}| G(x) |^{-1}w(x)= | G | å_{tÎT}w(t).

This proves the first of the stated equations, the second follows by an application of the homomorphism theorem.

This result implies the Cauchy-Frobenius Lemma
(put *w:x -> 1*), which
we shall sometimes
call the *constant form* of the Cauchy-Frobenius Lemma. In order to
apply the weighted form of the Cauchy-Frobenius Lemma
to the enumeration of symmetry classes of mappings
*f* in *Y ^{X}* we introduce, for a given mapping

w(f):=Õ_{xÎX}W(f(x)),

and notice that for any finite actions * _{G}X* and

Corollary:IfWis constant on the orbits ofHonY, thenwis constant on the orbits ofH wrand_{X}G , H´G, HGonY. Moreover, for any^{X}W, the corresponding multiplicative weight functionwis constant on the orbits ofGonY.^{X}

Thus the weighted form of the Cauchy-Frobenius Lemma
can be applied as soon as we have
evaluated the sum of the weights
of those *f* which are fixed under *(y,g)ÎH wr _{X} G *. But this sum of
weights follows directly from the characterization of the fixed points of

Corollary:Using the same notation as in the lemma describing cycles in wreath products, for(y, g)inH wr, a function_{X}GW:Y -> Rconstant on the orbits ofH, and the corresponding multiplicative weightw:Y, we obtain the equation^{X}-> Rå_{fÎYX(y,g)}w(f)=Õ_{n}å_{yÎYhn (y,g)}W(y)^{ln}.

Now an application of the weighted form of the Cauchy-Frobenius Lemma to the corollary above yields the desired generating function for the enumeration of symmetry classes by weight:

Theorem:Letand_{G}Xbe finite actions,_{H}YW:Y -> Ra mapping into a commutative ring containingas a subring, and denote byQwthe corresponding multiplicative weight function onY.^{X}

- If
Wis constant on the orbits ofHonY, thenwis constant on the orbits ofH wron_{X}GY, and, for each transversal^{X}Tof these orbits, we haveMoreoverå_{tÎT}w(t)=(1)/(| H |^{ | X | }| G |)å_{(y,g)ÎH wr X G }Õ_{n=1}^{c(bar (g))}å_{yÎYhn (y,g)}W(y)^{ln}.wis also constant on the orbits ofH´GandH, so that, by restriction, we obtain for the sum of the weights of the elements in a transversal the expressionsand(1)/(| H | | G |)å_{(h,g)ÎH´G}Õ_{i=1}^{ | X | }(å_{yÎYhi}W(y)^{i})^{ai(bar (g))},(1)/(| H |)å_{hÎH}(å_{yÎYh}W(y))^{ | X | }.- For any
W:Y -> Rthe corresponding multiplicative weight functionw:Yis constant on the orbits of^{X}-> RGonY, and the sum of its values on a transversal of the orbits is equal to^{X}(1)/(| G |)å_{gÎG}Õ_{i=1}^{ | X | }(å_{yÎY}W(y)^{i})^{ai(bar (g))}.

The most general weight function is obtained when we take for *W* a mapping
which sends each *yÎY* to a separate indeterminate of a polynomial ring.
For the sake of notational simplicity we can do this by taking the elements
*yÎY* themselves as indeterminates and putting *W:Y -> Q[Y]
:y -> y*, where

c(f,-):Y ->N:y -> | f^{-1}[{y}] | ,

i.e. *c(f,y)* is the multiplicity with which *f* takes the value *y*, then
we get

Corollary:The number ofG-classes onY, the elements of which have the same content as^{X}fÎY, is equal to the coefficient of the monomial^{X}Pin the polynomial_{y}y^{c(f,y)}(1)/(| G |)å_{gÎG}Õ_{i=1}^{ | X | }(å_{yÎY}y^{i})^{ai(bar (g))}.

A nice example is the solution of the
so-called *necklace problem*:

Example:We ask for the different necklaces withnbeads in up tomcolours and given content. In order to bring this problem within reach of unromantic mathematics, we consider such a necklace a colouring of the vertices of a regularn-gon, i.e. as anfÎ. Two such necklaces or colourings are different if and only if none of them can be obtained from the other one by a rotation. Hence we are faced with an action of the formm^{n}, namely the natural action of the cyclic group_{G}Y^{X}G:=Con the set_{n}Y. (In case we want to allow reflections, we have to consider^{X}:=m^{n}G:=D, the dihedral group.) A particular case was already discussed in the example, where we obtained the total number of orbits in the special case when_{n}nis prime. Now we are in a position to count these orbits by content. In order to do this for generalmandnwe take from exercise the cycle structure of the elements ofCand obtain, by an application of Pólya's theorem, the desired solution of the necklace problem:_{n}For a numerical example we takeCorollary:The number of different necklaces containingbbeads of the i-th colour,_{i}iÎ, is the coefficient ofmyin the polynomial_{1}^{b1}...y_{m}^{bm}where(1)/(n)å_{d | n}f(d)(y_{1}^{d}+...+y_{m}^{d})^{n/d},fdenotes the Euler function (see exercise).m:=2andn:=5and obtain the generating functionRecall that the monomial summand(1)/(5)((y_{1}+y_{2})^{5}+4(y_{1}^{5}+y_{2}^{5}))=y_{1}^{5}+y_{1}^{4}y_{2}+2y_{1}^{3}y_{2}^{2}+2y_{1}^{2}y_{2}^{3}+y_{1}y_{2}^{4}+y_{2}^{5}.2ymeans that there are exactly two different necklaces consisting of 5 beads three of which are of the first colour and two of which are of the second colour. Figure shows four of the eight different necklaces, the remaining ones are obtained by simply exchanging the two colours._{1}^{3}y_{2}^{2}One half of the different necklaces

The result Pólya's theorem has an important consequence which can be used for a systematic study of certain congruences:

Corollary:For each finite actionand any_{G}XmÎeach coefficient of a monomial summand in the generating function is divisible byN| G |, or, in formal terms:å_{gÎG}Õ_{i=1}^{ | X | }(å_{n=1}^{m}y_{n}^{i})^{ai (bar (g))}º0 ( | G | ).

Besides the Cauchy-Frobenius Lemma also the Involution Principle admits a generalization to a weighted form:

The Involution Principle, weighted formAssume thattis a sign-reversing involution acting on the finite setX=Xand that^{+}DOTCUP X^{-}w:X -> Ris a weight function which is constant on the orbits oft. Thenå_{xÎX}sign (x)w(x)=å_{xÎXt}sign (x)w(x).

The proof is trivial but the applications are not as is shown by

Example:We would like to prove the so-calledq-binomial theorem. It says that, for anyqÎandRnÎ, the following polynomial identity holds:N^{*}where, for(x-1)(x-q)...(x-q^{n-1})=å_{k=0}^{n}[n k]_{q}q^{(n-k 2)}(-1)^{n-k}x^{k},n,kÎ, the rational functionN[n k]is defined by[n k]=[n]![k]!^{-1}[n-k]!^{-1}if 0 <= k <= nand[n k]=0 otherwise.while, for[0]!:=1, [n]!:=[n][n-1]...[1], for n >= 1.n >= 1:and finally the[n]:=1+x+...+x^{n-1},q-binomial numberis defined to be the value of thebinomial function[n k]atq:We consider the identity we want to prove as an identity of polynomials in[n k]_{q}:=[n k](q), in particular [n k]_{1}=[n k](1)=[n choose k].xover. This single identity is equivalent to the following system of identities:RWe prove this system by an application of the weighted form of the Involution Principle. The set on which we shall define an involution is" n>l³0: å_{k=0}^{n}[n k]_{q}q^{[n-k choose 2]}(-1)^{n-k}(q^{l})^{k}=0.which we decompose intoX:={(I,J) |n=I DOTCUP J},The involution which we use is defined, for a fixedX^{+}:={(I,J)ÎX | | J | even}, X^{-}:=X\X^{+}.lÎn, byt(I,J) :=(I\{n-l},JÈ{n-l}) if n-lÎIA weight function is introduced byt(I,J) :=(IÈ{n-l},J\{n-l}) if n-l not ÎI.wherew(I,J):=q^{( | J | 2)+i(I,J)+l· | I | },i(I,J)means the number ofinversions between I and J, i.e. the number of pairs(i,j)ÎI´Jsuch thati>j. It is clear thattis a sign-reversing involution onX, andXIt remains to check that_{t}=Æ.wis constant on the orbits oft. Clearlyi(I\{n-l},JÈ{n-l})is equal toThis givesi(I,J) - i({n-l},J) + i(I\{n-l},{n-l}) =i(I,J) + l - | J | .We are now in a position to apply the weighted form of the Involution Principle which yields, asw(I\{n-l},JÈ{n-l}) =q^{[ | J | +1 choose 2]+i(I,J)+l· | I | - | J | }=w(I,J).X, that_{t}=Æ0is equal toso that it remains to proveå_{(I,J)}(-1)^{ | J | }q^{[ | J | choose 2]+i(I,J) +l· | I | }=å_{k=0}^{n}(-1)^{n-k}q^{[n-k choose 2]+k·l}å_{(I,J) | J | =n-k}q^{i(I,J)},an identity that follows from exercise.[n k]_{q}=å_{(I,J) | J | =n-k}q^{i(I,J)},

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 |

Enumeration by weight |