How would you use Stirling numbers to partition a n unique objects, into m unique subsets, with minimum cardinality of 2 for each subset?

Question

For example, how would one go about partitioning 10 numbered balls into 4 numbered boxes, such that each box contains at least 2 balls?

Answer 1

We have using combinatorial classes as in Analytic Combinatorics by Flajolet and Sedgewick the following class

$$\def\textsc#1{\dosc#1\csod} \def\dosc#1#2\csod{{\rm #1{\small #2}}} \textsc{SEQ}_{=m}(\textsc{SET}_{\ge 2}(\mathcal{Z})).$$

This gives the exponential generating function

$$F(z) = (\exp(z)-z-1)^m.$$

To relate this to Stirling numbers we write

$$n! [z^n] (\exp(z)-z-1)^m = n! [z^n] \sum_{r=0}^m {m\choose r} (\exp(z)-1)^{m-r} (-1)^r z^r \\ = n! \sum_{r=0}^{\min(n,m)} {m\choose r} (-1)^r [z^{n-r}] (m-r)! \frac{(\exp(z)-1)^{m-r}}{(m-r)!} \\ = n! \sum_{r=0}^{\min(n,m)} {m\choose r} (-1)^r \frac{(m-r)!}{(n-r)!} {n-r\brace m-r} \\ = m! \sum_{r=0}^{\min(n,m)} {n\choose r} (-1)^r {n-r\brace m-r}.$$

If we look this up in the OEIS we find OEIS A200091 which says "The number of ways of putting $n$ labeled items into $k$ labeled boxes so that each box receives at least 2 objects" so we have the right answer.

Note that the closely related class (boxes are not labeled i.e. indistinguishable)

$$\textsc{SET}_{=m}(\textsc{SET}_{\ge 2}(\mathcal{Z}))$$

has EGF by the same computation

$$G(z) = \frac{1}{m!} (\exp(z)-z-1)^m$$

which yields for the coefficients

$$\sum_{r=0}^{\min(n,m)} {n\choose r} (-1)^r {n-r\brace m-r}$$

which is OEIS A009299 "associated Stirling numbers of the second kind."

What we have here is an inclusion-exclusion (PIE) argument where $r$ gives the number of singletons (single element in a box). The nodes $Q$ of the underlying poset represent distributions that have the elements of $Q$ as singletons plus possibly more. So the Hasse diagram of the poset has as nodes the subsets of $[n]$ of cardinality at most $m$ and is ordered by set inclusion. The weight on a node $Q$ is $(-1)^{|Q|}.$ A distribution that has set of singletons $P$ exactly is thus included in all nodes $Q\subseteq P$ for a total weight of

$$\sum_{Q\subseteq P} (-1)^{|Q|} = \sum_{r=0}^{|P|} {|P|\choose r} (-1)^r = 0.$$

This is zero because $|P|\ge 1.$ On the other hand a distribution that has no singletons which is what we seek is only included in $Q=\emptyset$ for a weight of $(-1)^{|\emptyset|} = 1$, precisely as required. The total count of all weights is

$$\sum_{Q\subseteq [n], |Q|\le m} (-1)^{|Q|} {n-|Q|\brace m-|Q|} = \sum_{r=0}^{\min(n,m)} {n\choose r} (-1)^r {n-r\brace m-r}$$

which concludes the argument. Here we have counted any possible distribution of the remaining $n-|Q|$ balls into the remaining $m-|Q|$ boxes at a node, with no box empty (Stirling numbers of the second kind). We can get the count for the first class from the count for the second by multiplying by $m!.$