2
$\begingroup$

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.

$\endgroup$
4
$\begingroup$

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

$\endgroup$
2
$\begingroup$

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

$\endgroup$
1
$\begingroup$

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.

$\endgroup$

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.