A shelf contains $30 $ books in a row, how many ways there are to choose $4 $ books so between each pair of chosen books there are at least $2$ non chosen ones.

Tried to transform the question to stars and bars . But still have no clues. Any hints would be helpful .

  • 1
    $\begingroup$ Say $a<b<c<d$ are the four chosen positions. Then $1\le a < b-1 < c-2 < d-3 \le 30-3$, and now we reduce the problem to choose four different numbers ($a,b-1,c-2,d-3$) in the interval... $\endgroup$ – dan_fulea Nov 8 '18 at 18:01
  • $\begingroup$ I think it should be $1\le a\lt b-2 \lt c-4 \lt d-6 \le 30-6$. Since there are at least 2 non-chosen books. Right? $\endgroup$ – Jaqen Chou Nov 9 '18 at 14:10
  • $\begingroup$ Yes, sure, thanks! (I was programming to many python loops that were starting from zero that bad day...) $\endgroup$ – dan_fulea Nov 9 '18 at 20:07

Each admissible choice can be encoded as a binary word of length $30$ containing exactly $4$ ones, whereby the first three ones have at least two zeros immediately following. Deleting these zeros gives a binary word of length $24$ with $4$ ones and no extra conditions. Conversely: Given any binary word of length $24$ containing $4$ ones insert two zeros after the first three ones, and you obtain an admissible selection of $4$ books from the shelf. The number $N$ you are looking for therefore is $$N={24\choose4}=10\,626\ .$$


Hint: Consider the alternate problem Arrange 26 balls(books) and 4 sticks(these are the books you are choosing. Slightly modify it since you need 2 books between all 4 chosen ones, so set 6 balls aside and put them in between the 3 slots between the 4 sticks in the beginning and now arrange the remaining 20 balls in 5 possible slots. This is the hint, to see the answer just move your cursor over the yellow space below.


Spoiler textThis is the same as the problem- non-negative integral solutions of the equation $x_1+x_2+x_3+x_4+x_5=20$ which is just$\binom{24}{4}=21.22.23=10,626$


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.