Combinatorics-how many ways to sort books on a shelf 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).
 A: "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}$.
A: A more natural and shorter approach that uses only the lower bounds for the equation 
$$a+b+c = 2n+1$$
is next:
You can count all of the solutions to the equation when there is no restriction and then, using the subtraction principle, remove those solutions when there's a shelf with more than $n$ books on it(this would mean that the other two shelves have $\leq n$ books on them).
The equation when there are more than $n$ books on shelf $a$ is
$$a + b + c = 2n + 1, \\a \geq n + 1,\: b \geq 0,\: c \geq 0\: .$$
The number of solutions to this equation is $\dbinom{n + 2}{2}$.
But, one must notice that this number only counts the situation when there are more books on shelf $a$, in order to account for the other shelves the number should be multiplied by 3.
The final solution is 
$$\dbinom{2n+3}{2} - 3\dbinom{n + 2}{2} = \dbinom{n + 1}{2}$$
A: a+b+c>2c comes from multiplying the previous inequality by 2.
There are (n+1)choose(2) combinations of a,b because 0<=a,b<=n. For each of these possibilities there is exactly one 0<=c<=n such that a+b+c=2n+1.  
