TAOCP 1.2.6 Exercise 64

Let $S(n,m)$ denote the number of partitions of an $n$-element set into $m$ nonempty disjoint subsets.

taocpmathematicsalgorithmsvolume-1math-medium

Section 1.2.6: Binomial Coefficients

Exercise 64. [M20] Show that $\left{{n \atop m}\right}$ is the number of ways to partition a set of $n$ elements into $m$ nonempty disjoint subsets.

Verified: no
Solve time: -

Solution

Let $S(n,m)$ denote the number of partitions of an $n$-element set into $m$ nonempty disjoint subsets. We will prove that

$$ S(n,m)=\left{{n \atop m}\right}, $$

where $\left{{n \atop m}\right}$ denotes the Stirling number of the second kind.

The numbers $\left{{n \atop m}\right}$ satisfy the recurrence

$$ \left{{n \atop m}\right} = m\left{{n-1 \atop m}\right} + \left{{n-1 \atop m-1}\right}, \tag{1} $$

together with the initial conditions

$$ \left{{0 \atop 0}\right}=1, \qquad \left{{n \atop 0}\right}=0 \quad (n>0), \qquad \left{{0 \atop m}\right}=0 \quad (m>0). \tag{2} $$

We show that $S(n,m)$ satisfies the same recurrence and initial conditions.

Fix an $n$-element set, say ${1,2,\ldots,n}$. Consider a partition of this set into $m$ nonempty disjoint subsets. There are two mutually exclusive possibilities for the element $n$.

First, $n$ may form a singleton block ${n}$. The remaining $n-1$ elements must then be partitioned into $m-1$ nonempty disjoint subsets. The number of such partitions is

$$ S(n-1,m-1). $$

Second, $n$ may belong to a block containing other elements. Start with a partition of ${1,\ldots,n-1}$ into $m$ nonempty disjoint subsets. Since there are $m$ blocks, the element $n$ can be inserted into any one of them. Therefore the number of such partitions is

$$ m,S(n-1,m). $$

These two cases exhaust all partitions, hence

$$ S(n,m) = m,S(n-1,m) + S(n-1,m-1). \tag{3} $$

The initial conditions are immediate. There is exactly one partition of the empty set into zero subsets, namely the empty partition, so

$$ S(0,0)=1. $$

If $n>0$, no partition of an $n$-element set into zero nonempty subsets exists, hence

$$ S(n,0)=0. $$

If $m>0$, the empty set cannot be partitioned into $m$ nonempty subsets, hence

$$ S(0,m)=0. $$

Comparing (3) with (1), and the initial conditions with (2), we conclude by induction on $n$ that

$$ S(n,m)=\left{{n \atop m}\right} $$

for all integers $n,m\ge0$.

Therefore $\left{{n \atop m}\right}$ is the number of ways to partition a set of $n$ elements into $m$ nonempty disjoint subsets.

This completes the proof.

∎