A circular necklace contains n beads. Each bead is black or white. How many different necklaces can be made with n beads?

There is no clasp to identify a specific point on the chain, and a flipped over necklace is still the same necklace.
_____________________________

To get you started:

With 1 bead, the necklace can be either 1 black or 1 white bead.

With 2 beads, the necklace can be either 2 black, 2 white, or 1 black-1 white

With 3 beads, the necklace can be either 3 black, 3 white, 2 black-1 white, 2 white-1 black, etc...

# Beads  Number of Necklaces
   1          2
   2          3
   3          4
   4          6
   5          8
   6         13

Thanks to a comment of Richards somewhere else in Perplexus, I learned how to use Polya's counting theory on problems like these (but I only partially understand how it works).  Unfortunately, "FIGURE it out (2)" seemed too easy using this method, but this problem is still a challenge.
________________________________________

To VERY concisely summarize the method:
Take all the cycle notation of all the unique transformations (such as rotations and reflections) of combination problem.  An example of cycle notation is the following:

1 2 3 4 5 6  If this changes to
1 5 2 6 3 4  this, the cycle notation is
(1)(253)(46) this.

Take the number of cycles (pairs of parentheses) in each transformation, and raise c (c being the number of colors) to this number.  Average the result for each unique transformation, and voila!  The number of combinations mysteriously appears.
___________________________________

The problem with using this method in this puzzle is that it is difficult to generalize what all the cycle notations are for n beads.  I will solve this problem, but chances are that the function won't be very simple or straightforward.

Each necklace has 2n (n=number of beads) unique transformations.  There are n rotations, one of those rotations being 0 degrees.  Then, you can flip the necklace and get n more rotations of the reflection.  The exception is the 1 and 2 bead case, where rotation is the same as reflection.
________________________________________

First, I will consider the rotations of the reflection.  Instead of thinking of rotating the reflection, I want the reader to think of simply reflecting around different points in the necklace.  Consider the 5 bead case.  The cycle notations of only the reflections are the following:

(1)(25)(34) flipping around bead 1
(13)(2)(45) flipping around bead 2
(15)(24)(3) flipping around bead 3
(12)(35)(4) flipping around bead 4
(14)(23)(5) flipping around bead 5

Notice that each has three cycles, and 3 just so happens to be (5+1)/2.  Amazing, I'm sure.

In the 4-bead case, there are still 4 reflections, but 2 are around single beads, and 2 are around the space between beads.  This is because there are 8 beads/spaces, and each reflection flips around two of them.  While in the 5-bead case, each reflection flipped around one space and one bead, all the reflections of even-beaded necklaces flip around either two beads or two spaces.  Observe the cycle notations for the 4 bead reflections.

(1)(24)(3) flip around 1 and 3
(12)(34)   ...around spaces between 1 and 2, 3 and 4
(13)(2)(4) ...around 2 and 4
(14)(23)   ...around spaces between 2 and 3, 1 and 4

Notice that half have 2 cycles and the other half have 3.  Notice that 2 is floor((4+1) / 2) and 3 is ciel((4+1) / 2).

In case you didn't see what I was getting at, I say that the even and odd beaded cases can be in one equation.  Going back to the polya's method, the sum of the results of all the reflections should be the following:

n/2 * 2^( floor( (n+1) / 2) ) + n/2 * 2^( ceil( (n+1) / 2) )
which simplifies to...
n * 2^( floor( (n-1) / 2) ) + n * 2^( ceil( (n-1) / 2) )
________________________________________

For the rotations, I took the cycle notation of all the rotations of several numbers of beads.  In fact, I skipped the cycle notation straight to the number of cycles.  The following chart shows the number of cycles of each of the cycle notations for several n.

n  cycle numbers
2  1 2
3  1 1 3
4  1 2 1 4
6  1 2 3 2 1 6
7  1 1 1 1 1 1 7
8  1 2 1 4 1 2 1 8
10 1 2 1 2 5 2 1 2 1 10
12 1 2 3 4 1 6 1 4 3 2 1 12

After a bit of this, it occurred to me that each number was the GCF of n and the number of beads it was shifted clockwise.  This is relatively easy to prove, but rather uninteresting, so I'm going to call it an "exercise to the reader."  heh heh...

Anyway, the sum of the results for all the rotations should be this:

2^GCF(1,n) + 2^GCF(2,n) + 2^GCF(3,n)...+ 2^GCF(n,n)
______________________________________________

The number of combinations is therefore the sum of all the results of rotations and reflections divided by 2n.

[2^GCF(1,n) + 2^GCF(2,n) + 2^GCF(3,n)...+ 2^GCF(n,n)
+ n * 2^( floor( (n-1) / 2) ) + n * 2^( ceil( (n-1) / 2) )]
/ 2n

I told you it would be messy.  I'm not sure you can simplify the above significantly, and I sure don't know how to graph it on my calculator.

Posted by Tristan on 2004-09-30 18:44:14