Rabbit row

Here is a puzzle based on a neat graph theory counting problem.

Puzzle

Eleven white rabbits live in eleven white houses, all in a row. One day, the rabbits get together and decide that they should spruce up their rabbit row by painting some or all of their houses. They decide that while they don't necessarily need to paint every single house, they will definitely NOT leave any two adjacent houses white. How many choices do they have for which collection of houses to paint?

Help

Hint

Try solving the pattern for smaller numbers of houses and look for a pattern.

Answer

There are 233 different collections of houses which could be painted.

Solution

Perhaps surprisingly, if you start with <m>n</m> houses, the number of collections of houses which could be painted given this restriction is the <m>n+2</m>nd Fibonacci number. To see this, note that with 1 house, there are 2 collections (either paint or don't paint the one house). With 2 houses, there are 3 collections (paint the first, second, or both houses). Now inductively suppose that you want to paint <m>n</m> houses. You could either paint or not paint the first house. If you paint the first house, the remaining <m>n-1</m> houses need to be painted, and we know how to do that. If you don't paint the first house, then you must paint the second house, and then have your choice of how to paint the remaining <m>n-2</m> houses, which we know how to count.

Variations

Another group of eleven white rabbits also live in eleven white houses, but these are positioned in a large circle. Again, they want to repaint some or all of the houses, leaving no two adjacent houses white. How many ways can they do this?

Of course, we could also ask these questions and include paint color choices. For example, what if every house would be painted red, white or blue, but we don't want any two adjacent houses to be colored identically. How many choices do the rabbits have?

Mathematics

The original puzzle asks for the number of independent sets of the path graph <m>P_{11}</m>. An independent set is a set of vertices in a graph no two of which are adjacent (connected by an edge). The first variation asks for the number of independent sets in a cycle graph. The second variation asks for the number of proper 3-colorings of such graphs.