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?
x1 = number of books on shelf 1,
x2 = number of books on shelf 2,
x3 = number of books on shelf 3
I have the following inequalities:
a+b > c
a+b+c > 2c (don't understand where this one comes from)
2n+1 > 2c
c < n+ (1/2)
c is an integer, so c =< n. Same for a, and b.
=> a+b+c = 2n+1, where 0 =< a, b, c =< n
At this point, I don't know how to finish the computation of the number of integral solutions. The answer is (n+1) choose (2).
I would have thought that r = 2n+1, and k = 3, so the answer would have been: (2n+3) choose (2).
Best Answer
"each pair of shelves together contains more books than the other shelf" is equivalent to "each shelf holds less than half the books" (at most $n$ books). Let $\{s_i\}_{i=1}^3$ be the number of books on each shelf. For each choice of $s_1$ and $s_2$ so that $s_1+s_2<n+1$, we would need $s_3>n$. For each $s_1+s_2\ge n+1$, we have $s_3=2n+1-(s_1+s_2)\le n$. Thus, we need to count the number of $s_1,s_2\le n$ so that $s_1+s_2\ge n+1$. For $s_1=1$, there is $1$ choice for $s_2$ (i.e. $n$). For $s_1=2$, there are $2$ choices (i.e. $n$ and $n-1$). This continues up to $s_1=n$, where there are $n$ choices for $s_2$. Therefore, the number of arrangements is $1+2+\dots+n=\binom{n+1}{2}$.