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

(In reply to re: There is an error is this puzzle by SilverKnight)

Unless I'm missing something (wouldn't be the first time), I don't see how those two are equivalent:

white black black white white black
white black black white black white

If you begin to rotate the second one, one bead at a time, you get:

white black black white white black
black black white black white white

white black black white white black
black white black white white black

white black black white white black
white black white white black black

white black black white white black
black white white black black white

white black black white white black
white white black black white black

white black black white white black
white black black white black white

And we're back to the beginning. 

 

 

Posted by Penny on 2004-08-19 12:14:56