# In how many ways can this be done if each pair of shelves together contains more books than the other shelf?

Question:

There are $2n+1$ identical books to be put in a bookcase with three shelves. In how many ways can this be done if each pair of shelves together contains more books than the other shelf?

My Approach:

Let $x_1$ = number of books on shelf $1$,

$\quad$ $x_2$ = number of books on shelf $2$

$\quad$ $x_3$ = number of books on shelf $3$

We are given that $x_1+x_2>x_3$, $x_2+x_3>x_1$, $x_1+x_3>x_2$ and $x_1+x_2+x_3=2n+1$

Substitute $a=x_1+x_2-x_3$, $b=x_2+x_3-x_1$ and $c=x_1+x_3-x_2$, to get

$a,b,c>0$ and $a+b+c=2n+1$

This is just the strong composition

So, the answer is $\binom{2n+1-1}{3-1}=\binom{2n}{2}$

But the answer at the back of my book is $\binom{n+1}{2}$. Where did I go wrong?

Note: This is not a duplicate question as it explicitly asks for verification of proof.

Notice that when you say that you are looking for any $a,b,c>0$ with $a+b+c =2n+1$, we know that something must have gone wrong, since we know that every shelf must contain at least one book (otherwise we immediately violate the constraint) and hence we know that $x_1,x_2,x_3>0$ with $x_1+x_2+x_3=2n+1$ ... which is just like the $a,b,c$, ... except that obviously the constraint will constrain $x_1,x_2,x_3$ much more than just them being greater than 0.

OK, but where did you go wrong? Well, you consider $a=2$ and $b=1$ to be part of a possible solution, but then:

$x_1 + x_2 -x_3 = a = 2$

$x_2 + x_3 - x_1 = b = 1$

And so (subtract):

$2x_1 - 2x_3 = 1$

And thus:

$x_1 - x_3 = \frac{1}{2}$

... I think you can see the problem now ...

• So if there are 5 books, $(a,b,c)=(2,1,2)$, how does your example relate to this? – Joffan Feb 14 '17 at 3:15
• @Joffan The $(a,b,c) = (2,1,2)$ triple would represent the 'solution' $(x_1,x_2,x_3)=(2,1.5,1.5)$ ... which is not a solution ... – Bram28 Feb 14 '17 at 3:21
• Right, so in effect you are saying that since $a=(2n+1)-2x_1$, $a$ (and $b$ and $c$) must be odd. – Joffan Feb 14 '17 at 3:33