In how many ways can $4$ books be removed from a bookshelf with $15$ books such that no two adjacent books are chosen?

Question

A bookshelf has $15$ books. in how many ways can $4$ books be removed such that no two adjacent books are chosen?

I started to solve the question by saying that the first book can be selected in $15$ ways, the second one can be selected in $13$ ways,the third one in 11 ways and the fourth one in $9$ ways. Total number of ways:$15\times13\times11\times9=19305$. However the correct answer must be $495$. Can you explain why my counting technique is false and provide me with hints about the correct one? Thanks you for your help

Answer 1

This solution uses the stars and bars method of counting.

Consider the 4 books you select as bars and the 11 remaining books as stars. That is, we have need to arrange 4 bars and 11 stars, under the constraint that between any two bars there is at least one star.

There are $3$ spaces between the bars, so there must be 3 stars between them.

That now simply requires us to fix the remaining 12 objects (8 stars and 4 bars).

We can do this in $\binom{12}{4}=495$ ways.

The obviously generalises to the following:

For $n\ge2m-1$, there are $\dbinom{n-m+1}{m}$ ways to select $m$ non-consecutive items from a set of $n$ items.

Answer 2

The remaining $11$ books create $12$ slots where the four chosen books could have been. There are ${12\choose4}=495$ ways to choose $4$ slots.