Number of ways of distributing balls into boxes

Solution 1:

This is the "Stars and bars" problem, which we may see as follows: Assume stars $*$ represent the balls and $\\|$ represent an end side of a box. $$ \underbrace{*\ *\ *\ \ \ \ \ \ *}_{n\ balls}\ \ \ \underbrace{[ \ \vert \ \vert \ \vert \ \vert \ \ \ \ \vert \ \vert \ ]}_{k \ boxes}^{k-1\ bars} $$ Take two of the bars as special, to represent left and right ends. Then the original problem may be reformulated : How many different combinations of these $n+k-1$ objects there are? This is $$ {(n+k-1)!\over n!\cdot (k-1)!} = \binom{n+k-1}{n} $$

Solution 2:

Let's look at your example $4$ boxes and $3$ balls. Suppose your ball distribution is: $$\text{box}_1 = 2, \text{box}_2 = 0, \text{box}_3 = 1, \text{box}_4 = 0$$ You can encode this configuration in the sequence $110010$ with the $1$'s representing the balls and $0's$ the transition from one box to the other. (you need 3 transitions since you have 4 boxes) Next, you may ask yourself is it true that each binary string with 3 $1$'s and 3 $0$'s represent a valid $3 $ balls distribution over $4$ boxes. The answer is yes. You can see that from having such string you could get the distribution. So have a bijection between the number of the strings with 3 $1$'s and 3 $0$'s and the number of distributing the $3$ balls. You can see that the number of strings is much easier to calculate, it is $\binom{6}{3}$. Generalize this idea and you get $$\binom{n+k-1}{n}$$.