# Problem C.1

## Balls and bins

In this problem, we investigate the effect of various assumptions on the
number of ways of placing $n$ balls into $b$ distinct bins.

- Suppose that the $n$ balls are distinct and their order within a bin does
not matter. Argue that the number of ways of placing the balls in the bins
is $b^n$.
- Suppose that the balls are distinct and that the balls in each bin are
ordered. Prove that there are exactly $(b + n - 1)!/(b - 1)!$ ways to
place the balls in the bins. (Hint: Consider the number of ways of
arranging $n$ distinct balls and $b-1$ indistinguishable stricks in a
row).
- Suppose that the balls are identical, and hence their order within a bin
does not matter. Show that the number of ways of placing the balls in the
bins is $\binom{b+n-1}{n}$. (Hint: Of the arrangements in part (b), how
many are repeated if the balls are made identical?)
- Suppose that the balls are identical and that no bin may contain more than
one balls, so that $n \le b$. Show that the number of ways of placing the
balls is $\binom{b}{n}$.
- Suppose that the balls are identical and that no bin may be left empty.
Assuming that $n \ge b$, show that the number of ways of placing the balls
is $\binom{n-1}{b-1}$.

### Distinct balls, unordered

There are $b$ ways to place the first ball, then $b$ ways to place the second
and so on. There are $n$ balls, so the total number of ways is $b^n$.

### Distinct balls, ordered

As the hint indicates, this is isomporhic to arranging $n + b - 1$ items, out
of which $b - 1$ are separators. The balls before the first separator go in the
first bin, those between the first and the second go in the second bin, etc.
There are $(n + b - 1)!$ ways to do that, but since the order of the separators
does not matter, $(b - 1)!$ out of those are duplicated. Thus the answer is
$(b + n - 1)!/(b - 1)!$.

### Identical balls, unordered

There are $(b + n - 1)!/(b - 1)!$ ways if the balls are distinct. If they are
made identical, $n!$ of the arrangements are repeated for each position of the
separators. We get $\frac{(b + n - 1)!}{n!(b - 1)!} = \binom{b + n - 1}{n}$
arrangements.

### Identical balls, max 1 per bin

This is reduced to selecting $n$ of the $b$ bins to put balls in, which is the
definition of binomial coefficients - $\binom{b}{n}$.

### Identical balls, no bin left empty

This is fun. First, we put a ball in each bin and we're left with $n - b$ balls
to put in $b$ bins. Now lets use part (c) - substituting $n - b$ for $n$, we
get:

$$ \binom{b + n - b - 1}{n - b} = \binom{n - 1}{n - b}
= \binom{n - 1}{n - 1 - n + b}
= \binom{n - 1}{b - 1} $$