Stirling Numbers of the Second Kind: Set Partitions

Welcome back. In our last lesson, we derived a powerful formula using the Principle of Inclusion-Exclusion (PIE) to count the number of surjective functions from a set of size $m$ to a set of size $n$ . This corresponds to distributing $m$ distinct items into $n$ distinct boxes, ensuring no box is empty.

Today, we'll explore a closely related, and equally fundamental, combinatorial object: Stirling numbers of the second kind. These numbers answer a similar question but with a crucial twist: what if the boxes are indistinguishable? This seemingly small change leads to the concept of set partitions, a cornerstone of enumerative combinatorics. Our goal is to define these numbers, learn how to compute them using both a recurrence relation and an explicit formula derived from our work with surjections, and apply them to solve partitioning problems.

What is a Set Partition?

Imagine you have a set of $n$ distinct objects, and you want to divide them into $k$ non-empty groups. The order of groups doesn't matter, and the order of elements within a group doesn't matter. This is called a partition of the set.

The number of ways to partition a set of $n$ elements into exactly $k$ non-empty subsets is given by the Stirling number of the second kind, denoted as $S (n, k)$ or ${k n}$ .

From a "balls and boxes" perspective:

We have $n$ distinct balls (the elements of the set).
We have $k$ identical boxes (the subsets are indistinguishable).
Each box must contain at least one ball (the subsets must be non-empty).

The following video provides an excellent introduction to this concept.

Meet the Stirling Numbers! (of the 2nd kind)

The video "Meet the Stirling Numbers! (of the 2nd kind)" from the Wrath of Math channel introduces the core idea using the intuitive 'balls and boxes' analogy.

Watch the first few minutes, from the beginning, to see how a simple problem of partitioning 3 balls into 2 boxes leads to the formal definition of S(n, k). Pay attention to the distinction between distinct balls and indistinguishable boxes.

For example, let's find $S (4, 2)$ , the number of ways to partition the set ${1, 2, 3, 4}$ into 2 non-empty subsets.
The possible partitions are:

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

So, $S (4, 2) = 7$ . Note that the partition ${{3, 4}, {1, 2}}$ is identical to ${{1, 2}, {3, 4}}$ because the "boxes" (the subsets) are indistinguishable.

Computing Stirling Numbers: The Recurrence Relation

Calculating $S (n, k)$ by listing all partitions becomes impractical very quickly. A more efficient method is to use a recurrence relation, similar to the one that generates Pascal's triangle for binomial coefficients.

To find $S (n, k)$ , we can single out one specific element from our set of $n$ elements, let's call it element $n$ . When we partition the $n$ elements into $k$ subsets, there are two possibilities for element $n$ :

Element $n$ is in a subset by itself. If ${n}$ is one of the $k$ subsets, then the remaining $n - 1$ elements must be partitioned into the remaining $k - 1$ subsets. The number of ways to do this is $S (n - 1, k - 1)$ .
Element $n$ is in a subset with other elements. If $n$ is not alone, we can first partition the other $n - 1$ elements into $k$ non-empty subsets. There are $S (n - 1, k)$ ways to do this. Then, we must place element $n$ into one of these $k$ existing subsets. Since the subsets are formed, they are now distinguishable by their contents, giving us $k$ choices for where to place element $n$ . This gives $k \cdot S (n - 1, k)$ ways.

By the sum rule, we get the recurrence relation:
$S (n, k) = S (n - 1, k - 1) + k \cdot S (n - 1, k)$
The boundary conditions are $S (n, 1) = 1$ , $S (n, n) = 1$ , and $S (n, k) = 0$ for $k > n$ .

The following resource provides a formal combinatorial argument for this recurrence and other basic identities.

[PDF] Stirling Numbers of the Second Kind - MIT Mathematics

This document provides clear proofs for the fundamental properties of Stirling numbers.

Read the section "Stirling Number Identities". Focus on the combinatorial proofs for the special cases S(n, 1), S(n, n-1), and the proof for the recurrence relation, which uses the "kids and committees" analogy.

This recurrence allows us to build a triangle for Stirling numbers, much like Pascal's triangle.

A table of Stirling numbers of the second kind, $S(n,k)$. Each entry is calculated using the recurrence relation from the two entries above it: the one to the left, and the one directly above multiplied by its column index $k$.

Let's use the recurrence to verify the value of $S (4, 3)$ from the table.
$S (4, 3) = S (3, 2) + 3 \cdot S (3, 3)$
From the table, $S (3, 2) = 3$ and $S (3, 3) = 1$ .
So, $S (4, 3) = 3 + 3 \cdot 1 = 6$ , which matches the table.

The Explicit Formula via Surjective Functions

We can also find an explicit formula for $S (n, k)$ by connecting it to our previous lesson on surjective functions.

Surjective functions: Counting ways to put $n$ distinct balls into $k$ distinct boxes (no empty boxes).
Stirling numbers $S (n, k)$ : Counting ways to put $n$ distinct balls into $k$ indistinguishable boxes (no empty boxes).

The only difference is whether the boxes are distinct or not. We can count the number of surjections in two steps:

First, partition the $n$ balls into $k$ non-empty piles. This is exactly what $S (n, k)$ counts.
Then, assign the $k$ distinct labels of the boxes to these $k$ piles. There are $k!$ ways to do this.

This gives us a fundamental relationship:
$Number of surjections from an n -set to a k -set = k! \cdot S (n, k)$
In the last lesson, we used PIE to find the formula for the number of surjections:
$\sum_{i = 0}^{k} (- 1)^{i} (i k) (k - i)^{n}$
By rearranging the relationship above, we get our explicit formula for the Stirling numbers of the second kind:
$S (n, k) = \frac{1}{k !} \sum_{i = 0}^{k} (- 1)^{i} (i k) (k - i)^{n}$
The following "active learning" worksheet guides you through this derivation, forcing you to reconstruct the PIE argument. This is excellent practice for your goal of mastering proofs.

[PDF] Active learning exercise on Stirling numbers of the second kind

This worksheet guides you to derive the explicit formula for S(n,k) by first considering partitions into labeled blocks.

Start reading from the heading that introduces a "closely related number S-hat(n, k)" at the bottom of page 2. This \hat{S}(n,k) is precisely the number of surjective functions. Now, work through the questions: Exercise 6: This question asks you to formalize the relationship we just discussed. Exercise 7: These questions rebuild the PIE argument. Answer parts (a) through (d) by thinking about the total number of functions (k^n) and the number of functions that miss 1, 2, or more specified codomain elements. Exercise 8: This exercise puts it all together. Use your answers from Exercise 7 and the logic of PIE to prove formula (1), and then use your result from Exercise 6 to get the final formula for S(n, k).

An Extension: Bell Numbers

A natural question arises: how many ways are there to partition a set of $n$ elements if we don't specify the number of subsets? This total number of partitions is the $n$ -th Bell Number, denoted $B_{n}$ .

Since we can partition a set of $n$ elements into 1 subset, or 2 subsets, ..., or $n$ subsets, the Bell number is simply the sum of the Stirling numbers over all possible values of $k$ :
$B_{n} = \sum_{k = 0}^{n} S (n, k)$
If you look back at the image Stirling Numbers of the Second Kind, the Bell numbers are conveniently listed as the row sums. For example, $B_{4} = S (4, 0) + S (4, 1) + S (4, 2) + S (4, 3) + S (4, 4) = 0 + 1 + 7 + 6 + 1 = 15$ .

Practice Problems

Now, let's apply these concepts. As per your preference, here are a few problems to solidify your understanding.

Using the Recurrence: Calculate $S (6, 3)$ using the recurrence relation $S (n, k) = S (n - 1, k - 1) + k \cdot S (n - 1, k)$ and the values from the provided table.
Using the Formula: Calculate $S (4, 3)$ using the explicit PIE formula. Verify that your answer matches the value in the table ( $6$ ).
Word Problem: In how many ways can 8 distinct toys be distributed among 3 identical boxes if no box is to be empty?
Equivalence Relations: An equivalence relation on a set is a way of partitioning it into non-empty subsets called equivalence classes. How many distinct equivalence relations can be defined on the set ${a, b, c, d, e}$ ?

Conclusion

In this lesson, we have formally defined Stirling numbers of the second kind, $S (n, k)$ , as the number of ways to partition an $n$ -element set into $k$ non-empty subsets. This is a fundamental concept in combinatorics that models any problem involving grouping distinct items into identical containers.

Key Takeaways:

Definition: $S (n, k)$ counts the partitions of an $n$ -set into $k$ non-empty blocks.
Recurrence Relation: $S (n, k) = S (n - 1, k - 1) + k \cdot S (n - 1, k)$ . This provides a simple way to compute values recursively.
Connection to Surjections: The number of surjections from an $n$ -set to a $k$ -set is $k! \cdot S (n, k)$ .
Explicit Formula (via PIE): $S (n, k) = \frac{1}{k !} \sum_{i = 0}^{k} (- 1)^{i} (i k) (k - i)^{n}$ . This formula directly links set partitions to the Principle of Inclusion-Exclusion.
Bell Numbers: The total number of partitions of an $n$ -set, $B_{n}$ , is the sum of $S (n, k)$ for $k = 0, \dots, n$ .

This lesson concludes our module on the Principle of Inclusion-Exclusion. We have seen how this single principle can be used to solve seemingly disparate problems like counting derangements, surjective functions, and now set partitions.

In our next lesson, we will begin a new module and introduce a different, yet equally elegant, proof technique: double counting. We will see how counting the size of a set in two different ways can lead to surprisingly powerful combinatorial identities.

Recommended resources