Stirling Numbers — Mathematics Knowledge System

Overview

Stirling numbers come in two families that count fundamentally different structures. The Stirling numbers of the second kind, S(n,k), count the number of ways to partition an n-element set into k nonempty unlabeled subsets. The (unsigned) Stirling numbers of the first kind, c(n,k), count the number of permutations of n elements that decompose into exactly k disjoint cycles. Both families satisfy Pascal-triangle-like recurrences and appear throughout combinatorics, from counting set partitions to expressing rising and falling factorials in terms of ordinary powers.

Intuition

S(n,k) counts ways to partition n labeled objects into k unlabeled nonempty groups: when adding the n-th object to a partition of the first n-1 objects, it either joins one of the existing k groups (k·S(n-1,k) ways) or starts a brand-new group by itself, splitting off from a (k-1)-partition (S(n-1,k-1) ways) — giving the recurrence directly. The first-kind numbers c(n,k) instead count permutations by their cycle structure: inserting the n-th element into a permutation of n-1 elements either creates a new fixed-point cycle (c(n-1,k-1) ways) or slots into any of the n-1 existing 'gaps' within existing cycles ((n-1)·c(n-1,k) ways).

Formal Definition

Definition

Stirling numbers of the second kind and first kind are defined and computed via these recurrences:

S(n,k) = k\,S(n-1,k) + S(n-1,k-1)

Second kind recurrence

S(n,1) = 1,\quad S(n,n) = 1

Second kind boundary values

c(n,k) = (n-1)\,c(n-1,k) + c(n-1,k-1)

First kind (unsigned) recurrence

x^n = \sum_{k=0}^{n} S(n,k)\, x^{\underline{k}}

Second kind connects powers to falling factorials

Worked Examples

Enumerate by the size split: either 1+3 or 2+2.
$\text{1+3 split: choose the singleton, } \binom{4}{1}=4 \text{ ways}$
2+2 split: choose 2 of 4 for one group, but divide by 2 since the two groups are unlabeled.
$\tfrac{1}{2}\binom{4}{2} = \tfrac{1}{2}(6) = 3$
Total partitions.
$S(4,2) = 4 + 3 = 7$

Answer: S(4,2) = 7.

Practice Problems

Difficulty 4/10

Using the recurrence S(n,k) = k·S(n-1,k) + S(n-1,k-1), find S(5,2) given S(4,2)=7 and S(4,1)=1.

Difficulty 3/10

What is S(4,4) and S(4,1)?

Difficulty 4/10

Find c(4,1), the number of permutations of 4 elements forming a single cycle (a 4-cycle).

Quiz

Summary

Stirling numbers of the second kind S(n,k) count partitions of an n-set into k nonempty unlabeled subsets.
Stirling numbers of the first kind c(n,k) count permutations of n elements with exactly k cycles.
Both families satisfy Pascal's-triangle-style recurrences built from a case split on where the n-th element goes.

References

WebsiteWikipedia — Stirling numbers of the second kind