How many necklaces can you make if you have two different color beads (like purple and gold) at your disposal?

If you put 0 beads on your necklace, there’s only one way to do so and it’s mighty boring.

Suppose you put 1 bead on your necklace. It might be purple or it might be gold, giving you two possible necklaces.

If you want to put 2 beads on your necklace, you can do so in three ways. And if you want to use 3 beads, there are four possibilities.

What about with 4 beads? It looks like the answer should be five, right? Right? You know you want to say that. ALAS, there are actually six different ways to do it.

Once the pattern of consecutive integers is broken, it stays broken. There are eight ways to make a necklace out of 5 beads, and either thirteen or fourteen ways to make it out of 6 beads: thirteen if you allow reflexive symmetry — that is, the necklace is “free” and you can flip it over in addition to rotating it — and fourteen if the necklace is “fixed” so you can rotate it but can’t flip it. And then the numbers start to increase a little faster, into the thousands if you have fifteen beads (and, umm, enough time to make a whole bunch of necklaces).

### Like this:

Like Loading...

*Related*

Tags: combinatorics, necklace

This entry was posted on October 15, 2008 at 6:53 pm and is filed under Patterns that Fail. You can follow any responses to this entry through the RSS 2.0 feed.
You can leave a response, or trackback from your own site.

October 16, 2008 at 12:38 am |

I guess with 2 beads, for example, position on the ring (left or right) is not significant. If it were, you’d have to add at least one more configuration: purple on the right and gold on the left. How come it doesn’t matter?

October 16, 2008 at 5:44 am |

It has to do with what you define to be “the same” or “different”. In this problem the clasp is hidden, so you can take that middle necklace and rotate it 180° and then the purple and gold will be on opposite sides.

Likewise, in the necklace with two purple and one gold bead, you can rotate it around so that the gold bead is in one of the other spots.

(If you didn’t allow the necklaces to rotate, then there would be one way with 0 beads, two ways with 1 bead, four ways with 2 beads [PP, PG, GP, GG], eight ways with 3 beads [PPP, PPG, PGP, GPP, PGG, GPG, GGP, GGG], and sixteen ways with 4 beads).

October 19, 2008 at 7:20 pm |

I’m getting a weird pattern in Pascal’s triangle. I guess I should go play with it more.

October 19, 2008 at 7:49 pm |

What pattern are you getting?

October 19, 2008 at 9:54 pm |

Arches up in the middle, divided by something… Let me verify that it holds for the next few numbers, and then I’ll post…

Jonathan