How many ways are there to select $k$ out of $n$ books on a shelf so
that there are always at least $3$ unselected books between selected books? (Assume
$n$ is large enough for this to be possible.)
The books are in a row. I tried something with a binary sequence and combinations, unsuccessfully.
Best Answer
You can line up the k selected books in a row, creating $k+1$ gaps to put the remaining books.
If we let $x_i$ be the number of books in gap $i$ for $1\le i\le k+1$, we have $x_1+\cdots+x_{k+1}=n-k$
where $x_1\ge0, x_{k+1}\ge0$, and $x_i\ge3$ for $2\le i\le k$.
If we let $y_1=x_1, y_{k+1}=x_{k+1}$, and $y_i=x_{i}-3$ for $2\le i\le k$, we have
$y_1+\cdots+y_{k+1}=n-4k+3$ with $y_i\ge 0$ for $1\le i\le k+1$.
Since we have $k$ dividers and $n-4k+3$ dots, there are $\dbinom{n-3k+3}{k}$ solutions to this equation.