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