Labeled/unlabeled balls in unlabeled boxes

Question

I was hoping I could receive some clarification into the the four cases:

1. Placing labeled balls in unlabeled boxes with repetition.

2. Placing labeled balls in unlabeled boxes without repetition.

3. Placing unlabeled balls in unlabeled boxes with repetition.

4. Placing unlabeled balls in unlabeled boxes without repetition.

I just want an intuitive understanding of the four cases. How many ways are there to arrange, say, 4 balls into 9 boxes or 9 balls into 4 boxes in each case above, and why?

Answer 1

The number of ways of placing $n$ labelled balls in $k$ unlabelled boxes with repetition allowed is $\left\{n\atop k\right\}$, a Stirling number of the second kind. There is a rather ugly explicit formula for them:

$$\left\{n\atop k\right\}=\frac1{k!}\sum_i(-1)^{k-i}\binom{k}ii^n\;.$$

They also satisfy a rather nice Pascal-like recurrence:

$$\left\{n\atop k\right\}=k\left\{n-1\atop k\right\}+\left\{n-1\atop{k-1}\right\}\;,$$

with initial condition $$\left\{n\atop 0\right\}=\left\{0\atop n\right\}=[n=0]\;,$$

where $[n=0]$ is an Iverson bracket. The explanation here of the recurrence is concise but reasonably clear.

If the balls are also unlabelled, you are in effect looking at partitions of $n$ into $k$ parts. The number of such partitions is sometimes denoted by $P(n,k)$ and satisfies the recurrence

$$P(n,k)=P(n-1,k-1)+P(n-k,k)$$

with initial conditions $P(n,k)=0$ for $k>n$, $P(n,n)=1$, and $P(n,0)=[n=0]$. The triangle of these numbers is OEIS A008284, and you’ll find more information and references there.

If you don’t allow repetition, clearly you must have $n\le k$, and since you can’t tell one box from another, there is only one way to distribute the balls, whether they’re labelled or not: $n$ boxes each containing a ball, and $n-k$ empty boxes.

Answer 2

Just to give more explanation to @Brian M. Scott's answer for dummies like me. There are two complementary cases for $P(n,k)$: (i) at least 1 bucket has only 1 ball, (ii) every bucket has at least 2 balls. For (i), we set aside 1 bucket and 1 ball, so there are $P(n-1,k-1)$ ways for arranging the rest; for (ii), we first bed 1 ball for every bucket, leaving us $n-k$ balls to put in the $k$ buckets, thus $P(n-k,k)$ ways of doing it.

For the ease of notation, denote the Stirling number of the second kind by $Q(n,k)$, for which again there are two complementary cases: (i) the last ($n$th) ball is put in a bucket with no company, (ii) it is put together with some other balls. For (i), we set aside a bucket and throw in the $n$th ball, leaving us $Q(n-1,k-1)$ ways for arranging the rest. For (ii), we first put the first $n-1$ balls in the $k$ buckets, which has $Q(n-1,k)$ ways of doing it, and then we throw the last ball into one of the bucket, thus $k\cdot Q(n-1,k)$. Notice once we put the $n-1$ balls in all the buckets, the buckets are implicitly labeled, thus the multiplier $k$.