# In how many ways can $2t+1$ identical balls be placed in $3$ boxes so that any two boxes together will contain more balls than the third?

In how many ways can $2t+1$ identical balls be placed in $3$ boxes so that any two boxes together will contain more balls than the third?

I think we have to use multinomial theorem, but I cannot frame the expression!

• possible duplicate of math.stackexchange.com/questions/930588/… – almagest May 19 '16 at 13:17
• @almagest Can you clarify the sense in which that's a duplicate? I can see how the "no one box exceeds the other two" condition corresponds to the numbers being the sides of a triangle, but the rest isn't clear. – Semiclassical May 19 '16 at 13:56
• @Semiclassical Are you concerned that this question is only about odd $n$, or that the boxes might be distinguishable? – almagest May 19 '16 at 14:00
• @almagest: I don’t consider it a duplicate of that question: the setting is different enough to be a problem for a beginner; the boxes are probably intended to be distinguishable; and the restriction to odd $n$ does make a difference. – Brian M. Scott May 19 '16 at 14:15

Notation: A box $X$ has $x$ balls inside.

First of all, note that no box can contain less than $1$ and more than $t$ balls. Also, the sum of two boxes mustn't be lower than $t + 1$.

Let's say box $A$ has $1 \leq a \leq t$ balls. Box $B$ must have then at least $t - a + 1 \leq b \leq t$ balls. This gives you $a$ ways of filling box $B$. The remaining balls go to box $C$.

Therefore, since $a$ ranges from $1$ to $t$, you have $\sum_{a=1}^{t} a = \dfrac{t\cdot\left(t+1\right)}{2}$ ways of filling these boxes that satisfy the condition.

Edit: I am assuming that boxes are distinguishable from eachother, so that the distribution $\{t, t, 1\}$ differs from $\{t, 1, t\}$

There must be at least $1$ ball in the first box; why? On the other hand, there cannot be more than $t$ balls in the first box; why?

Say there are $n$ balls in the first box, where $1\le n\le t$. If there are $m$ balls in the second box, what are the possible values for $m$? We have to be sure that

$$m+n>(2t+1)-(m+n)$$

and that

$$n+\big((2t+1)-(m+n)\big)>m\;.$$

Solving these for $m$, we see that we have to be sure that

$$t-n+\frac12<m<t+\frac12\;.$$

Since $t,n$, and $m$ are integers, this is equivalent to $t-n+1\le m\le t$. Any ordered pair $\langle n,m\rangle$ satisfying the conditions $1\le n\le t$ and $t-n+1\le m\le t$ corresponds to a possible distribution of balls to the first two boxes, with the third box getting the remaining $2t-n-m$ balls, and each possible distribution of balls yields one of these ordered pairs.

You can count these pairs by summing the possibilities for different values of $n$, as in the answer by ddsLeonardo, or you can count them all at once by a more combinatorial argument, as follows.

Line up $t$ of the balls. There are $t-1$ slots between adjacent balls and one slot on each end of the line, for a total of $t+1$ open slots. Insert markers into any two distinct slots; this can be done in $\binom{t+1}2$ ways. Let $m$ be the number of balls to the right of the lefthand marker and $n$ the number of balls to the left of the righthand marker. Clearly $n$ can be any integer from $1$ through $t$, and $m$ can then be any integer from $t-n+1$ through $t$. Thus, each placement of the two markers corresponds to a possible ordered pair $\langle n,m\rangle$ of the numbers of balls in the first and second boxes, and vice versa. Since there are $\binom{t+1}2$ ways to place the markers, there are $\binom{t+1}2$ possible distributions of the balls.