# 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+b+c\gt 2c$ comes from adding $c$ to each side of $a+b \gt c$ – Ross Millikan Sep 21 '11 at 19:16

## 3 Answers

"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}$.

• So the answer is not n+1 choose 2? – Gbean Sep 21 '11 at 15:01
• @Gbean $\binom{n+1}{2}$ stands for $n+1$ choose 2. See binomial coefficient wikipedia article. – Sasha Sep 21 '11 at 15:29

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+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.

• Suppose $a=0$ and $b=0$, what would $c$ be? – robjohn Sep 21 '11 at 14:48
• Does that mean that c = 2n+1? – Gbean Sep 21 '11 at 14:52
• @Gbean: it would need to be, but that is too big for $c$. – robjohn Sep 21 '11 at 14:59
• How is it too big for c? – Gbean Sep 21 '11 at 15:20
• @Gbean: "each pair of shelves together contains more books than the other shelf". If $c=2n+1$ and $a=0$ and $b=0$ we have $a+b\le c$ instead of $a+b>c$ as the problem requires. – robjohn Sep 21 '11 at 17:52