choosing $5$ non consecutive books from a shelve of $12$

Question

In how many ways can you pick five books from a shelve with twelve books, such that no two books you pick are consecutive?

This is a problem that I have encountered in several different forms ("In how many ways can you paint five steps of a twelve step staircase, without any two consecutive steps being painted?", etc.) but the idea is the same. Here is how I solved it:

Consider a shelve with $13$ books, and then calculate the number of ways you arrange $5$ pairs and $3$ single books on that shelve. The answer to that question is ${8 \choose 5} = 56$. This question is equivalent to the original, because the pairs prevent you from choosing two consecutive books, and a shelve of $13$ books rather than $12$ is considered because otherwise, it would not be possible to choose the last book on the shelve.

This approach has its downside: writing a formal proof of this is not easy, as you can see. I tried to explain this proof to a friend of mine in order to give him the intuition ${8 \choose 5}$ is the right answer (which is usually easier than a formal proof) but I already had a hard time doing that.

My question is: Is there a more rigorous proof this is the right answer? Not only would that help me explain my answer, but it would probably allow me to use that technique to a broader range of problems.

Answer 1

Imagine the books are numbered $1$ to $12$. Let $a_1,a_2,a_3,a_4,a_5$ be the numbers of the chosen books, in increasing order.

Consider the numbers $a_1,a_2-1, a_3-2,a_4-3, a_5-4$. This is an increasing sequence taken from the numbers $1$ to $12-4$.

Conversely, given any increasing sequence $x_1,x_2,\dots,x_5$ taken from the numbers $1$ to $8$, we obtain an allowed book choice by choosing books $x_1, x_2+1, x_3+2, x_4+3, x_5+4$.

Thus there are as many allowed choices as there are ways to choose $5$ numbers from $8$.

One could use more formal language. In effect, we have an explicit bijection between the set of allowed book choices and the collection of $5$-subsets of $\{1,2,\dots,8\}$.

Of course there is nothing special about $12$ and $5$, the same reasoning works in general.

Answer 2

Here are two ways to think of this:

a) Line up 7 sticks in a row, representing the books NOT being selected. Since there are 8 gaps between the sticks (counting the gaps on the outside), the number of ways to choose 5 of these gaps in which to insert balls (representing the books being chosen) is C(8,5).

b) Line up 5 sticks, representing the books being chosen. Since we don't want these to appear consecutively, put aside 4 balls (representing books not chosen) to be inserted as blockers at the end. This leaves 3 balls to be distributed in the gaps between the sticks, and there are C(8,5) ways to do this. (Then at the end insert one blocker between each pair of consecutive sticks.)