Abstract Combinatorics In a library there is a sequence of $n$ books.
There is someone that never wants to take books that are neighborhoods of each other. How many possibilities are there, for him, to take $k\le n$ books?
For example if there are 3 books and he wanted to take out 2, he would have 1 possibility.
I tried to think how to solve this problem but I didn't manage to get the solution. 
 A: Write down $n-k$ "stars" to represent, in the abstract, books not taken. Then there are $n-k+1$ "gaps" between these stars, including the two endgaps. We must choose $k$ of these gaps to slip the $k$ books back into. 
The number of ways to do this is $\dbinom{n-k+1}{k}$.
Remark: A nice recursion has been given by lulu. Alternately, one can verify that the above expression satisfies the recursion, and initial conditions. The calculation is straightforward, it comes down to the Pascal Identity.
A: Note:  there is a simple recursion.  If $F(k,n)$ is the answer you want, then we split the selections according to whether or not the first book in line is chosen.  This immediately tells us that $$F(k,n)=F(k-1,n-2)+F(k,n-1)$$  Of course we also know that $F(k,n)=0$ if $k>\lceil \frac n2\rceil$, not to mention $F(0,n)=1$ and $F(1,n)=n$.  
Perhaps this can be simplified or even solved in closed form, but I haven't tried to do so.
A: $k$ should be less than or equal to $\lceil n/2 \rceil$.
with the above condition, the answer would be
$\binom nk - (n-1)\binom {n-2}{k-2} + (n-2)\binom {n-3}{k-3}-...=\binom nk-\sum_{i=1}(-1)^i(n-i)\binom {n-i-1}{k-i-1}$
which is achieved using inclusion-exclusion principal. The first term is the number of ways of choosing k books out of n books (with no restriction). The second term is the number of ways, from the first term, that have at least two adjacent books (it has been deducted from the first term). The second term is the number of ways that have at least 3 adjacent books chosen in a row and so on.
