Number of ways of distributing balls into boxes

Question

I know that the formula for counting the number of ways in which $n$ indistinguishable balls can be distributed into $k$ distinguishable boxes is $$\binom{n + k -1}{n}$$

but I am having a hard time understanding why this formula counts that. I mean, suppose we have $4$ boxes and $3$ balls, then the problem is equivalent to count the permutations of 5 vertical lines with 3 circles except that two lines have to be fixed (the first and last lines). I would appreciate if someone could help me to relate and translate this way of thinking the problem to the formula with this. Thanks in advance.

Answer 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} $$

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

Answer 3

An explanatiom with the idea of two fixed lines will be a bit contrived,, but one fixed line gives a very good explanation.

Imagine an open container placed horizontally with open end to the right. It has a fixed bottom plate, and 3 movable plates. When plates get squeezed together, obviously no balls can be placed in between. To illustrate:

$|||ooo = 0-0-0-3$

$|ooo||| = 3-0-0-0$

$|o||oo| = 1-0-2-0$

Of the 6 objects whose position can vary, you have to place 3, so ${6\choose3}$

Draw the container vertically ( I can't, here ) and you can see that a ball can rest only on top of a plate, so you don't need to memorize any convention.

PS

The trouble with two fixed lines is that with 5 vertical lines $| | | | |$, 4 compartments are there which means that you will have to stipulate that at least two of the "plates" must always remain squeezed together.