Selecting K books out of N books This question is from Mathematics for Computer Science by Prof. Albert R Mayer under the topic "Counting One Thing By Counting Other":
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? (Assuming n is large enough for this to be possible.)
I am not able to understand the part which says that "there are at least 3 unselected books between selected books" ?
 A: Let $S$ be a selected book but $U$ be unselected. Then he means $SUUUS$ is okay but $SUUS$ is not, when you look at the shelf.
A: The direct answer here is to make sure that any selected book is followed by at least 3 unselected books on the shelf.
In these problems, selected items and unselected items are usually symmetrical and one case can be easier than the other. In this case, options for the unselected items can be fairly simply identified.
We can start by considering a selection mask for the bookshelf, consisting of select markers and leave markers. This avoids thinking about individual books; we're just making a selection pattern. We can make a minimal qualifying mask for selection, consisting of $k$ selects and then $3$ leaves in between each two selects. In total this has $k+3(k-1) = 4k-3$ markers.
Now we can insert our remaining leave markers, which we have $n-(4k-3) = n-4k+3$ of. These go into the $k+1$ distinct spaces before, between and after the select markers. This is a straightforward sticks and stones selection partitioning those leaves into the $k+1$ categories identified above, which gives us $\dbinom{n-4k+3+k}{k}=\dbinom{n-3k+3}{k}$ options.
Finally of course we use the assembled selection mask to pick actual books.
A: Are you looking for the solution to the problem, or just trying to clarify what it's asking?  For the solution, see below (hidden):

 First, think of the "minimal" arrangement of $k$ books: $SUUU SUUU ... S$.  There are $n-(4k-3)$ books left and $k+1$ places to add unselected books to this arrangement. So the question becomes: how many ways can you place $n-(4k-3)$ identical items in $k+1$ bins? This is equivalent to the stars and bars problem, and the answer is $$ \left(\binom{n-4k+3}{k+1}\right) = \binom{n-3k+3}{k+1} $$

