Enumeration by weight

Enumeration by weight

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

å_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 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)),

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.

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.

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

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

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

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

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

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

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.

Enumeration by weight