Enumeration by weight |

Proof: The following equations are clear from the foregoing, except maybe the last one which uses the assumption thatThe 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).

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

This proves the first of the stated equations, the second follows by an application of the homomorphism theorem.=å_{x}| G_{x}| w(x) = | G | å_{x}| G(x) |^{-1}w(x)= | G | å_{tÎT}w(t).

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

and notice that for any finite actionsw(f):=Õ_{xÎX}W(f(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 thoseCorollary: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}

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

The most general weight function is obtained when we take forTheorem: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))}.

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

A nice example is the solution of the so-calledCorollary: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))}.

The result Pólya's theorem has an important consequence which can be used for a systematic study of certain congruences: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

Besides the Cauchy-Frobenius Lemma also the Involution Principle admits a generalization to a weighted form: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 | ).

The proof is trivial but the applications are not as is shown byThe 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).

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@kfunigraz.ac.at,

last changed: August 28, 2001

Enumeration by weight |