Associated Topics || Dr. Math Home || Search Dr. Math

### Polya-Burnside Lemma

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

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/
```
Associated Topics:
College Discrete Math
College Number Theory

Search the Dr. Math Library:

 Find items containing (put spaces between keywords):   Click only once for faster results: [ Choose "whole words" when searching for a word like age.] all keywords, in any order at least one, that exact phrase parts of words whole words

Submit your own question to Dr. Math
Math Forum Home || Math Library || Quick Reference || Math Forum Search