# Number of ways to distribute balls in boxes

This question appeared as an unsolved exercise in an introductory combinatorics textbook:

We have a bag with as many identical balls as necessary. We take out i balls and put them in 10 numbered boxes, such that the number of balls in box 1 $\leq$ the balls in box 2 $\leq$ ... $\leq$ the number of balls in box 10 $\leq$ 20. How many ways are there to do this?

A hint is provided (sorry for the shoddy translation): "Think of the sum of the series of differences of the amount of balls in adjacent boxes. The first difference equals the amount of balls in box 1".

Background: Earlier today I asked this question: Number of integer solutions if $x_1\leq x_2\leq x_3\leq ...\leq x_r\leq k$. The question itself was based on this exercise, so I was quite baffled to receive relatively complex answers. I figured I'll ask the question as it appeared, to see if maybe my 'generalisation' made this more complex than it should've been by omitting details.

Thank you for your help as always.

-
Just to make sure, in this problem the total number of balls $i$ may vary, but there are always $10$ boxes and the maximum number of balls in the last box is fixed at $20$. Correct? –  AMPerrine Oct 28 '11 at 17:26
As in the hint, consider such a sequence $x_1,\dots,x_{10}$. Look at the sequence of differences $d_i$, where $d_1=x_1$, and note that $\sum d_i=x_{10}$. Counting the number of sequences $(d_k)$ is a "stars and bars" (or sum) problem. Very doable. Counting "compositions" (order matters) tends to be not hard. Counting partitions (order irrelevant) is generally hard to very hard. –  André Nicolas Oct 28 '11 at 17:38
Compositions and partitions are often difficult, but this case (weak composition with fixed size) is one of the simplest: goo.gl/YYiee –  leonbloy Oct 28 '11 at 17:38

You didn't make this more complex by omitting details, but by adding them. In that other question, you had a fixed sum $k$. The present question doesn't place any requirements on the sum, and that makes it a lot easier. As the hint provided indicates, there's a bijection between the configurations to be counted and the ways of distributing $20$ balls into $11$ boxes: If we denote the number of balls in box $j$ by $n_j$ and add two extra numbers $n_0=0$ and $n_{11}=20$, the $11$ differences between these numbers add up to $20$, and each such sequence of differences determines one of the desired configurations and vice versa. So the desired number is
$$\binom{20+11-1}{11-1}=\binom{30}{10}=30045015\;.$$
But it says, "we take out i balls and put them in 10 numbered boxes," so don't we need an answer that depends on $i$? –  AMPerrine Oct 28 '11 at 17:38
@AMPerrine: Hmm, I guess you're right, in a sense. There seems to be a contradiction between that and "with as many identical balls as necessary". That doesn't really make any sense in your interpretation, whereas the $i$ doesn't make sense in mine. Hmm... –  joriki Oct 28 '11 at 17:43