Labeled/unlabeled balls in unlabeled boxes I was hoping I could receive some clarification into the the four cases:


*

*Placing labeled balls in unlabeled boxes with repetition.

*Placing labeled balls in unlabeled boxes without repetition.

*Placing unlabeled balls in unlabeled boxes with repetition.

*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?
 A: 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.
A: 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$.
