There are $n$ books in a line on a shelf and we want to choose $k$ of them in such a way that no two adjacent books are selected. Denote this number by ${n \brack k}$.
Show that ${n \brack k}=\binom{n-k+1}{k}$ for $n \geq 1$ whenever $0 \leq k <\frac{n}{2}+1$.
I want to show this by forming a bijection from the set of selections of $k$ books to the set of compositions of $n-k+2$ of length $k+1$. The reason being that I know that this number is $\binom{n+k-1}{k}$.
Say the books are labeled $b_1, \ldots, b_n$. Whenever I select the $k$ books, say $b_{j_1}, \ldots, b_{j_k}$, I know that $|j_i-j_\ell|\geq 2$ for each $i \neq \ell$. I'm just not sure how to form a composition from this.
**Recall that a composition of $n-k+2$ of length $k+1$ is a finite sequence of positive integers $(a_1, \ldots, a_{k+1})$ such that $\sum_{i=1}^k a_i=n-k+2$.