# 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?

## 4 Answers

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

Let me generalize (your question is obtained for $$n = 14$$ and $$k = 5$$):

Let $$n$$ and $$k$$ be nonnegative integers. Let $$\left[n\right] = \left\{1,2,\ldots,n\right\}$$. A set $$S$$ of integers is called lacunar if it contains no two consecutive integers (i.e., there exists no $$s \in S$$ satisfying $$s+1 \in S$$).

Find the number of all $$k$$-element lacunar subsets of $$\left[n\right]$$.

The answer is $$\dbinom{n-k+1}{k}$$ when $$k \leq n+1$$ (and obviously $$0$$ in all other cases). For a proof, see the solutions to Exercise 3 (a) on UMN Fall 2017 Math 4707 homework set #2. The first solution is the bijective argument some are alluding to in this thread. The second is a straightforward but annoying ("thanks" to the $$k \leq n+1$$ condition) induction on $$n$$.

Your $$n = 14$$ books correspond to the $$n$$ elements of $$\left[n\right]$$, in the order in which they appear on the shelf.

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.

If you are looking for an even easier way to come up with the answer, a formula for choosing k out of n without any two of the k adjacent to one another is $$\binom{n-k+1}{k}$$. It is easy to come up with this expression by observing the properties of the problem and then coming up with a recurrence relation that satisfies the restriction of "no adjacent choices". There is a much more detailed description here.