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!

  • 1
    $\begingroup$ possible duplicate of math.stackexchange.com/questions/930588/… $\endgroup$ – almagest May 19 '16 at 13:17
  • $\begingroup$ @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. $\endgroup$ – Semiclassical May 19 '16 at 13:56
  • $\begingroup$ @Semiclassical Are you concerned that this question is only about odd $n$, or that the boxes might be distinguishable? $\endgroup$ – almagest May 19 '16 at 14:00
  • 4
    $\begingroup$ @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. $\endgroup$ – 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


and that


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


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.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.