# Combinatorial restriction on choosing adjacent objects

I am having trouble understanding an approach to the following problem. Suppose 14 books are aligned in a bookcase. How many ways can we choose 5 books so that no adjacent books are chosen? I think my Labeling method is the best, please show me how to proceed to a solution from the best method.

Approaches:

Brute Force Method: Choose a book (not the first or the last) this can happen in 14 different ways, choose the second book (not the first or last) this can happen in 8 ways. And this is where I stopped because I realized I am not accounting for the first and last books, as well as the fact that I am introducing order.

Inclusion-Exclusion: Count the total number of ways to choose $5$ books. This is $14\choose 5$. Subtract the number of ways of choosing all non-adjacent books. This means that we always choose an adjacent book. This again leads to the complication of choosing or not choosing the first or last books in the alignment.

Labeling: My idea here is to label 5 books by bars and then 9 x's denoting books that were not chosen. The problem then reduces to finding the number of sequences of x's and bars such that no two bars are adjacent. If no two bars are adjacent, this means that there is an x between each bar, and there may be x's at both ends of the alignment. But, how do I count this?

-

Your labeling approach is indeed best. There are $4$ spaces between bars, each of which must contain a book, and a space at each end, each of which may contain no books. If $x_k$ is the number of books in space $k$ for $k=0,1,\dots,5$ (with the spaces numbered from left to right), you want the number of solutions in non-negative integers to the equation

$$x_0+x_1+x_2+x_3+x_4+x_5=9$$

subject to the condition that $x_1,x_2,x_3,x_4\ge 1$. This is essentially the same as counting the solutions in non-negative integers to

$$x_0+x_1+x_2+x_3+x_4+x_5=5\;:$$

we just pretend that we’ve already placed one book in each internal space, thereby accounting for $4$ of the $9$ extra books, and allocate the remaining $5$ arbitrarily. The answer is therefore

$$\binom{5+6-1}{6-1}=\binom{10}5\;.$$

(See this article if you’ve not seen that before at all, though I suspect that you have.)

-

We describe your labelling method in another way. Imagine taking out $5$ books. But now we space out the unchosen books, so that no one will know where the $5$ books came from. There are then $10$ "gaps" that our $5$ books could have come from (this includes the "endgaps"),

The actual books taken came from $5$ of these gaps, which can be chosen in $\dbinom{10}{5}$ ways.

-