# Choosing books on a bookshelf where no two are consecutive

I'm going through Cohen's Basic Techniques of Combinatorial Theory and I am stuck on this problem:

There are 24 volumes of an Encyclopedia on a bookshelf. In how many ways can 5 of these books be selected if no 2 consecutive volumes are to be chosen?

Any help would be much appreciated! Thanks

-

You have to count the number of binary strings with $24$ bits and $5$ non-consecutive ones. This can be done by taking $19$ consecutive zeroes and by choosing which "gaps" between the zeroes (including the gap preceding the first zero, and the gap following the last one) have to be filled by ones. Since there are $20$ gaps and you have to fill $5$ gaps, the answer is just $\binom{20}{5}$.

-

We start choosing by the lowest number, and will not choose any number before that number and I proceed by choosing only in increasing order.

So, when we choose the lowest number, we eliminate the number next to the chosen number. We continue this process and on the final selection of number, We have chosen all $5$ numbers so we do not have to eliminate any number anymore.

If one thinks carefully, then one will observe that we have eliminated $4$ numbers and we can choose any $5$ numbers from the remaining $20$ numbers as $20\choose 5$

-
I liked this way of thinking, can you please elaborate more? My problem is that, we can eliminate any 4 numbers, there are $\binom{24}{4}$ ways to eliminate 4 numbers, please explain a bit more, I would be graceful. – abstractnature Feb 15 '14 at 16:24
@abstractnature We start choosing with the lowest number,so when we choose the first number,we are not choosing any number less than that number.Now,we eliminate the next number to the chosen number.Now,we choose every number in the increasing order.So, when we choose the next number,we do not choose any number before the second chosen number,and we eliminate the next number to the chosen number.Continuing this way,when we choose the fifth number,we do not choose any number before the fifth chosen number but we do not have to choose any number after this choice,so we eliminate no more number. – Hawk Feb 15 '14 at 16:33
After eliminating $4$ numbers, there are $20$ numbers left, so we can choose these numbers as $20 \choose 5$. – Hawk Feb 15 '14 at 16:36
Thanks alot, I have another way of doing this problem, let me give it as an alternate answer too – abstractnature Feb 15 '14 at 16:37

Hint: try to find the equivalence to the following question: "There are 20 volumes of an Encyclopedia on a bookshelf. In how many ways can 5 of these volumes be selected? (with no special restriction)"

-
That will simply be 20C5 – Hummus Feb 15 '14 at 14:39
My hint was not: "solve the following alternative question", but "find the equivalence to the following question"... – Bach Feb 15 '14 at 14:42
Oh, I see now, Thank you for the hint! – Hummus Feb 15 '14 at 14:45
I don't quite see a correspondence between the two problems. Could you please elaborate further? – 1110101001 Oct 11 '14 at 19:30

As the numbers are non-consecutive, so if we select 1 number, we can skip any amount of numbers (atleast 1 should be skipped) after that number, and before choosing the first number we may or may not skip the numbers. Continuing this way until the 5th number, after that we may be having any amount of non-choosen numbers, which accounts to total 19 non-chosen numbers,

So, this now becomes same as

$\text{coefficient of$x^{19}$in the expansion of}$ $$(1+x^2+x^3+\cdots)^2\cdot (x +x^2+x^3+\cdots)^4$$ $$=x^4(1-x)^{-6}$$

$\text{= coefficient of$x^{15}$in$(1-x)^{-6}$}$

$$=\binom{6+15-1}{15} = \binom{20}{15} = \binom{20}{5}$$

-
This one goes above my head, could you please explain it? – Hawk Feb 16 '14 at 4:35
The first bracket $(1+x^2+x^3+\cdots)^2$ is for the first set of zeroes and the last set ( after the last 1), we can pick, no zero, 1, 2 and so on..., and last bracket is for 4 spaces between 1's, we can put atleast 1 zero (x), 2 zeroes (x^2) and so on.... – abstractnature Feb 16 '14 at 10:42