Polya-Burnside Lemma

Date: 07/02/99 at 16:51:04
From: Nathan Linger
Subject: Algorithms for Polya theory

I have been thinking about this problem for a year now. If you have 
unlimited amounts of 2 types of beads, how many unique necklaces can 
you make from them using exactly k beads? Two necklaces are considered 
the same if they can be obtained only by shifting the beads (as 
opposed to turning the necklace over). I know this question has 
something to do with Polya Theory, about which I know nothing else.

Actually my problem is more complicated. I not only want to count 
unique necklaces (or bit strings), but generate them.

So far I've tried to treat the necklaces as discrete digital functions 
and put them through a discrete Fourier transform. I hoped unique 
necklaces would produce unique transforms and I could find some 
pattern.  Well, they weren't unique so that didn't work.

Are there any directions you can point me to for answers?

Thanks.

Date: 07/02/99 at 19:12:54
From: Doctor Anthony
Subject: Re: Algorithms for Polya theory

I will work through an example using 30 beads - any combination of 
black or white beads as long as they total 30. I shall be using the 
Polya-Burnside lemma. The justification of the method is somewhat 
lengthy and I will not include it here, but will give it in a second 
post if you require it. You will be able to adapt the method shown 
below to different numbers of beads or more than 2 colours of bead.

Burnside's lemma states in effect that the number of distinct 
configurations is equal to the sum of all the group actions that keep 
the colours fixed divided by the order of the group (30 in this case).

To calculate the number of these group actions we shall be using the 
Euler Totient (phi) function and the Polya method of enumeration. The 
phi function of a number N is the number of positive integers less 
than N and prime to it. To find phi(N) we proceed as follows:

First express the number N in its prime factors in the form:

     N = a^p b^q c^r ...

where a, b, c, ... are different prime numbers and p, q, r, ... are 
positive integers.

Then the number of positive integers less than N and prime to it is:

     phi(N) = N(1 - 1/a)(1 - 1/b)(1 - 1/c)...

The rotational group actions that keep colours fixed are found in the 
table below.

The rotation sum is:

     SUM[2^GCD(j,30);j=0, 1, 2, 3, ... ,29]

2 is the number of available colours, and j is the number of beads we 
can rotate the necklace and keep colours fixed. j must be a factor of 
30 so not all the numbers 0, 1, 2, ......, 29 can be used.

Let us group terms... (as in using the Euler phi function)... the GCD 
is a divisor of 30=2*3*5 and hence must be one of the 8 terms:

                       1, 2, 3, 5, 6, 10, 15, 30

(GCD = 1 corresponds to the rotations through amounts relatively prime 
to 30, GCD = 30 corresponds to the identity j = 0)

There are phi(30/1)  = 30*(1-1/2)*(1-1/3)*(1-1/5)   = 8 terms with
                                                        GCD(j,30) = 1
There are phi(30/2)  = phi(15) = 15*(1-1/3)(1-1/5)  = 8 terms with
                                                        GCD(j,30) = 2
There are phi(30/3)  = phi(10) = 10*(1-1/2)*(1/1-5) = 4 terms with
                                                        GCD(j,30) = 3
There are phi(30/5)  = phi(6)  = 6*(1-1/2)*(1-1/3)  = 2 terms with
                                                        GCD(j,30) = 5
There are phi(30/6)  = phi(5)  = 5*(1-1/5)          = 4 terms with
                                                        GCD(j,30) = 6
There are phi(30/10) = phi(3)  = 3*(1-1/3)          = 2 terms with
                                                        GCD(j,30) = 10
There is  phi(30/15) = phi(2)  = 2*(1-1/2)          = 1 term  with
                                                        GCD(j,30) = 15
There is  phi(30/30) = phi(1)  =                      1 term  with
                                                        GCD(j,30) = 30
                                                     __
                                                     30 terms in all
So we obtain:

     8*2^1 + 8*2^2 + 4*2^3 + 2*2^5 + 4*2^6 + 2*2^10 + 1*2^15 + 1*2^30
   = 16 + 32 + 32 + 64 + 256 + 2,048+32,768 + 1,073,741,824
   = 1,073,777,040

Under rotations only (ignore reflections) there are then

     1,073,777,040/30

   = 35,792,568     different necklaces.

- Doctor Anthony, The Math Forum
  http://mathforum.org/dr.math/