Labeled and Unlabeled Balls in Unlabeled Boxes

balls-in-binscombinatoricsintuitionpermutations

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?

Best Answer

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.

Related Question