Number of ways to put n labeled balls distributed among k unlabeled boxes. All boxes should be non-empty.

Question

There are $n$ labeled balls and $k$ unlabeled boxes. The balls should be distributed among the $k$ boxes. All boxes should contain at least one ball.

Question: In how many different ways the balls can be distributed among the boxes?

Let me give some explicit examples.

Example 1

$n = 3$ balls, $\{1,2,3\}$.

$k = 2$ boxes.

There are 3 different possibilities:

$\{1\},\{2,3\} \\ \{2\},\{1,3\} \\ \{3\},\{2,3\}$

Example 2

$n = 4$ balls,

$k = 2$ boxes.

The cases can be separated into two group. In the first group of cases, there is one box with one ball, and one box with three balls. Here, the cases are

$\{1\},\{2,3,4\} \\ \{2\},\{1,3,4\} \\ \{3\},\{1,2,4\} \\ \{4\},\{1,2,3\}$

In the second group of cases, both boxes have two balls each. Here the cases are

$\{1,2\},\{3,4\} \\ \{1,3\},\{2,4\} \\ \{1,4\},\{2,3\} \\ %\{2,3\},\{1,4\} \\ %\{2,4\},\{1,3\} \\ %\{3,4\},\{1,2\}$

The total number of cases is, therefore, 4 + 3 = 7.

General considerations

I see some resemblance to the first theorem of stars and bars[1] problem, where there are $k$ boxes, all non-empty. However, the problem is different to the one stated here. Here the balls (which are the analogous of the stars) are labeled, while in [1] the stars are not labeled.

The problem may be related to one previously stated here in stack-exchange [2], where $k$ colors should be used to paint a strip of $n$ slots. I am not sure what a strip of slots is but, I think this other problem is also different because the colors corresponds to labeled boxes, while in the problem stated here the boxes are unlabeled.

Answer 1

What you’re looking for is the number of partitions of $[n]$ into $k$ sets; this is a Stirling number of second kind, denoted by ${n\brace k}$ (or $S(n,k)$). These numbers satisfy a nice recurrence relation:

$${{n+1}\brace k}=k{n\brace k}+{n\brace{k-1}}\;,$$

with initial conditions ${0\brace 0}=1$, and ${n\brace 0}={0\brace n}=0$ for $n>0$. There is an explicit formula, but it involves a summation and isn’t terribly nice:

$${n\brace k}=\frac1{k!}\sum_{i=0}^k(-1)^{k-i}\binom{k}ii^n\;.$$

There is much more information in the linked article and in the OEIS entry and its references.