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/
Search the Dr. Math Library:
Ask Dr. MathTM
© 1994- The Math Forum at NCTM. All rights reserved.