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.

  • 2
    $\begingroup$ they're on a row, I assume? $\endgroup$ – Exodd Oct 18 '14 at 15:35
  • $\begingroup$ Yes, I tried something with a binary sequence. I also tried combinations but probably don't them right $\endgroup$ – Schidu Luca Oct 18 '14 at 15:37
  • $\begingroup$ perhaps consider how many tilings there are with $k$ quadrominos and $n-4k$ monominos. (quadrominos are a 1x4 tile and monominos are 1x1 tiles as compared to the usual dominos which are 1x2). The furthest left of the quadrominos can represent the book selected, and the three unselected books to the right while the monominos represent additional unselected books. $\endgroup$ – JMoravitz Oct 18 '14 at 15:39
  • $\begingroup$ or you can solve the problem with 1 unselected books, and then solve with 2, and finally with 3, all by induction $\endgroup$ – Exodd Oct 18 '14 at 15:48

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.


The way that came into my mind first was as mentioned above to consider tilings using quadrominos and monominos. I realize now that that solution was incomplete as it is not necessary to have unselected books to the right of the rightmost selected book, so you can break this into cases with the final book having zero to the right, one to the right, two to the right, and three or more to the right.

In the case of having three or more to the right, here is an example: enter image description here You should be able to quickly find a general formula for this involving combinations. Now to handle the case of exactly two to the right, treat it the same but decrease $n$ by three and $k$ by one, essentially picking how the furthest right three squares look and leaving no restriction on the rest. Treat the cases with 1 or 0 to the right of the final selected book similarly.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.