Posts Tagged ‘combinatorics’

One, Two, Three, Four, Six(?)

October 15, 2008

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).