# Labeled/unlabeled balls in unlabeled boxes

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?

-
I think I saw a very similar question very recently, just with "ordered" instead of "labeled", but I can't find it now. Was that yours? – joriki Dec 18 '12 at 23:50
@joriki: You did $-$ this one $-$ and it was. – Brian M. Scott Dec 19 '12 at 2:14

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.

-