Enumeration by weight

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 total number of such structures. The question arises how these methods can be refined in such a way that we can also derive the number of orbits with certain prescribed properties like, for example, the number of graphs on v vertices which have e edges. The answer to many such questions can be given by introducing a weight which mostly will be a mapping from the set on which the group is acting into a polynomial ring over Q. The final result will be a generating function for the enumeration problem in question, i.e. we shall obtain a polynomial which has the desired numbers of orbits as coefficients of its different monomial summands. The basic tool is

The Cauchy-Frobenius Lemma, weighted form Let _GX denote a finite action and w:X -> R a map from X into a commutative ring R containing Q as a subring. If w is constant on the orbits of G on X, then we have, for any transversal T of the orbits:

å_tÎTw(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ÎXgw(x)=å_xå_gÎGxw(x)

=å_x | G_x | w(x) = | G | å_x | G(x) | ^-1w(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:Y -> R, R a commutative ring with Q as a subring, the multiplicative weight   w:Y^X -> R, defined by

  w(f):=Õ_xÎX W(f(x)),

and notice that for any finite actions _GX and _HY the following is true:

Corollary: If W is constant on the orbits of H on Y, then w is constant on the orbits of H wr _X G , H´G, H and G on Y^X. Moreover, for any W, the corresponding multiplicative weight function w is constant on the orbits of G on Y^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 (y,g) given in the lemma describing cycles in wreath products:

Corollary: Using the same notation as in the lemma describing cycles in wreath products, for (y, g) in H wr _X G , a function W:Y -> R constant on the orbits of H, and the corresponding multiplicative weight w:Y^X -> R, we obtain the equation

å_fÎY^X(y,g)w(f)=Õ_nå_{yÎYhn (y,g)} W(y)^l_n.

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: Let _GX and _HY be finite actions, W:Y -> R a mapping into a commutative ring containing Q as a subring, and denote by w the corresponding multiplicative weight function on Y^X.

• If W is constant on the orbits of H on Y, then w is constant on the orbits of H wr _X G on Y^X, and, for each transversal T of these orbits, we have

  å_tÎTw(t)=(1)/( | H | ^{| X |} | G | ) å_{(y,g)ÎH wr X G} Õ_n=1^{c(bar (g))} å_{yÎYhn (y,g)}W(y)^l_n.

  Moreover w is also constant on the orbits of H´G and H, so that, by restriction, we obtain for the sum of the weights of the elements in a transversal the expressions

  (1)/( | H | | G | )å_(h,g)ÎH´G Õ_i=1 ^{| X |} (å_yÎYhⁱW(y)ⁱ)^{a_i(bar (g))},

  and

  (1)/( | H | )å_hÎH(å_yÎYhW(y)) ^{| X |} .

• For any W:Y -> R the corresponding multiplicative weight function w:Y^X -> R is constant on the orbits of G on Y^X, and the sum of its values on a transversal of the orbits is equal to

  (1)/( | G | )å_gÎG Õ_i=1 ^{| X |} (å_yÎYW(y)ⁱ)^{a_i(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 Q[Y] denotes the polynomial ring over Q in the set Y of commuting indeterminates. This yields the multiplicative weight w(f)=P_x f(x), a monomial in Q[Y]. If we define the content of fÎY^X to be the mapping

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 of G-classes on Y^X, the elements of which have the same content as fÎY^X, is equal to the coefficient of the monomial P_yy^c(f,y) in the polynomial

(1)/( | G | ) å_gÎG Õ_i=1 ^{| X |} (å_yÎY yⁱ)^{a_i(bar (g))}.

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

Example: We ask for the different necklaces with n beads in up to m colours 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 regular n-gon, i.e. as an fÎmⁿ . 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 form _GY^X, namely the natural action of the cyclic group G:=C_n on the set Y^X:=mⁿ. (In case we want to allow reflections, we have to consider G:=D_n, 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 is prime. Now we are in a position to count these orbits by content. In order to do this for general m and n we take from exercise the cycle structure of the elements of C_n and obtain, by an application of Pólya's theorem, the desired solution of the necklace problem:

Corollary: The number of different necklaces containing b_i beads of the i-th colour, iÎm, is the coefficient of y₁^b₁...y_m^b_m in the polynomial

(1)/(n)å_{d | n}f(d)(y₁^d+...+y_m^d)^n/d,

where f denotes the Euler function (see exercise).

For a numerical example we take m:=2 and n:=5 and obtain the generating function

(1)/(5)((y₁+y₂)⁵+4(y₁⁵+y₂⁵))=y₁⁵+y₁⁴y₂+2y₁³y₂²+2y₁ ²y₂³+y₁y₂⁴+y₂⁵.

Recall that the monomial summand 2y₁³y₂² means 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.

 

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 action _GX and any mÎN each coefficient of a monomial summand in the generating function is divisible by | G | , or, in formal terms:

å_gÎG Õ_i=1 ^{| X |} (å_n=1^my_n ⁱ )^{a_i (bar (g))} º0 ( | G | ).

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

 The Involution Principle, weighted form Assume that t is a sign-reversing involution acting on the finite set X=X⁺ DOTCUP X^- and that w:X -> R is a weight function which is constant on the orbits of t. 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-called q-binomial theorem. It says that, for any qÎR and nÎN^*, the following polynomial identity holds:

(x-1)(x-q)...(x-q^n-1)=å_k=0ⁿ[n    k]_q q^{(n-k    2)} (-1)^n-kx^k,

where, for n,kÎN, the rational function [n    k] is defined by

[n    k]=[n]![k]!^-1[n-k]!^-1 if 0 <= k <= n

[n    k]=0 otherwise.

and

[0]!:=1, [n]!:=[n][n-1]...[1], for n >= 1.

while, for n >= 1:

[n]:=1+x+...+x^n-1,

and finally the q-binomial number is defined to be the value of the binomial function  [n    k] at q:

[n    k]_q:=[n    k](q), in particular [n    k]₁=[n    k](1)=[n choose k].

We consider the identity we want to prove as an identity of polynomials in x over R. This single identity is equivalent to the following system of identities:

" n>l³0: å_k=0ⁿ[n    k]_q q^{[n-k choose 2]}(-1)^n-k(q^l)^k=0.

We prove this system by an application of the weighted form of the Involution Principle. The set on which we shall define an involution is

X:={(I,J) | n=I DOTCUP J},

which we decompose into

X⁺:={(I,J)ÎX | | J | even}, X^-:=X\X⁺ .

The involution which we use is defined, for a fixed lÎn, by

t(I,J) :=(I\{n-l},JÈ{n-l}) if n-lÎI

t(I,J) :=(IÈ{n-l},J\{n-l}) if n-l not ÎI.

A weight function is introduced by

w(I,J):=q^{( | J |     2)+i(I,J)+l· | I |} ,

where i(I,J) means the number of inversions between I and J, i.e. the number of pairs (i,j)ÎI´J such that i>j. It is clear that t is a sign-reversing involution on X, and X_t=Æ. It remains to check that w is constant on the orbits of t. Clearly i(I\{n-l},JÈ{n-l}) is equal to

i(I,J) - i({n-l},J) + i(I\{n-l},{n-l}) =i(I,J) + l - | J | .

This gives

w(I\{n-l},JÈ{n-l}) =q^{[ | J | +1 choose 2]+i(I,J)+l· | I | - | J |} =w(I,J).

We are now in a position to apply the weighted form of the Involution Principle which yields, as X_t=Æ, that 0 is equal to

å_(I,J)(-1) ^{| J |} q^{[ | J | choose 2]+i(I,J) +l· | I |} =å_k=0ⁿ(-1)^n-kq^{[n-k choose 2]+k·l} å_{(I,J)    | J | =n-k} q^i(I,J),

so that it remains to prove

[n    k]_q=å_{(I,J)    | J | =n-k}q^i(I,J),

an identity that follows from exercise.

• Exercises

Enumeration by weight