Partitioning Sets with Stirling Numbers of the Second Kind
This article provides a comprehensive overview of how Stirling numbers of the second kind are used in mathematics to count the number of ways to partition a set of distinct objects into non-empty subsets. It covers the fundamental definition of these numbers, walks through a practical example, explains the logic behind their recurrence relation, and presents the explicit formula used for direct calculation.
The Core Definition
In combinatorics, a Stirling number of the second kind, commonly denoted as \(S(n, k)\) or \(\left\{ \begin{matrix} n \\ k \end{matrix} \right\}\), represents the number of ways to divide a set of \(n\) distinct elements into \(k\) non-empty, unlabeled subsets.
To understand how this counting works, two rules must be applied:
- Elements are distinct: Every item in the original set is unique.
- Subsets are unlabeled and non-empty: The order of the subsets does not matter, the order of elements within a subset does not matter, and no subset can be left empty.
A Step-by-Step Example
Suppose you have a set of 3 distinct elements, \(\{A, B, C\}\), and you want to partition them into 2 non-empty subsets. Here, \(n = 3\) and \(k = 2\).
To find \(S(3, 2)\), we list all possible ways to group these three elements into two groups without leaving any group empty:
- \(\{A, B\}\) and \(\{C\}\)
- \(\{A, C\}\) and \(\{B\}\)
- \(\{B, C\}\) and \(\{A\}\)
Because the subsets are unlabeled, the grouping \(\{\{A, B\}, \{C\}\}\) is identical to \(\{\{C\}, \{A, B\}\}\). Therefore, there are exactly 3 ways to do this, meaning \(S(3, 2) = 3\).
Counting via the Recurrence Relation
For larger numbers, listing every possibility is inefficient. Instead, mathematicians count the partitions recursively by focusing on a single, specific element—let's call it the \(n\)-th element—and deciding how to place it.
To partition \(n\) elements into \(k\) subsets, there are only two mutually exclusive possibilities for the \(n\)-th element:
- It forms a subset entirely by itself: If the \(n\)-th element is alone in its own subset, the remaining \(n - 1\) elements must be partitioned into the remaining \(k - 1\) subsets. By definition, there are \(S(n - 1, k - 1)\) ways to do this.
- It joins an already existing subset: If the \(n\)-th element does not form its own group, then the other \(n - 1\) elements must first be partitioned into \(k\) subsets. There are \(S(n - 1, k)\) ways to do this. Once those \(k\) subsets are formed, the \(n\)-th element can be placed into any one of the \(k\) subsets. This gives \(k \times S(n - 1, k)\) possibilities.
Combining these two scenarios gives the recurrence relation for Stirling numbers of the second kind:
\[S(n, k) = k \cdot S(n - 1, k) + S(n - 1, k - 1)\]
Fundamental Base Cases
Using the logic of set partitioning, certain values can be known immediately without complex calculation:
- \(S(n, 1) = 1\): There is only 1 way to put \(n\) elements into a single subset (all elements go together).
- \(S(n, n) = 1\): There is only 1 way to put \(n\) elements into \(n\) subsets (every element gets its own subset).
- \(S(n, k) = 0\) when \(k > n\): It is impossible to partition \(n\) elements into more than \(n\) non-empty subsets.
Counting via the Explicit Formula
You can also calculate \(S(n, k)\) directly without calculating the previous values. This is done by first imagining that the \(k\) subsets are distinct (labeled), and then adjusting the count.
If you distribute \(n\) distinct elements into \(k\) distinct boxes (allowing empty boxes), there are \(k^n\) ways to do this. However, Stirling numbers require non-empty and unlabeled subsets.
- Remove empty subsets: Using the Principle of Inclusion-Exclusion, we subtract the scenarios where one or more subsets are left empty.
- Remove subset labels: Since the order of the \(k\) subsets does not matter, we divide the entire result by \(k!\) (the number of ways to arrange \(k\) items).
This yields the explicit formula:
\[S(n, k) = \frac{1}{k!} \sum_{j=0}^{k} (-1)^{k-j} \binom{k}{j} j^n\]
Where \(\binom{k}{j}\) is the binomial coefficient ("\(k\) choose \(j\)"). By stripping away the empty groups via inclusion-exclusion and eliminating the group order by dividing by \(k!\), this formula precisely isolates the exact number of valid set partitions.