Stirling numbers of the second kind
Numbers counting partitions of a set into nonempty subsets.
Stirling numbers of the second kind, denoted S(n,k) or {n k}, are a fundamental concept in combinatorics. They count the number of ways to partition a set of n labeled objects into k nonempty unlabeled subsets, and they appear in the study of partitions and equivalence relations. Named after James Stirling, these numbers are the inverses of Stirling numbers of the first kind when viewed as triangular matrices.
- field
- Mathematics, combinatorics
- known_for
- Counting set partitions into nonempty subsets
- notation
- S(n,k) or {n k}
- named_after
- James Stirling
- related_concepts
- Stirling numbers of the first kind, Bell numbers, ordered Bell numbers
Lore & Background
The notation S(n,k) was used by Richard Stanley in Enumerative Combinatorics and by many earlier writers.
Reader's Guide
Stirling numbers of the second kind are central to combinatorics, providing a direct count of set partitions into a given number of nonempty subsets. Their recurrence relation and explicit summation formula allow for straightforward computation. They connect to Bell numbers, which sum over all k to give the total number of partitions of an n-element set, and to ordered Bell numbers via a weighted sum. The numbers appear in various combinatorial identities and are inverses of Stirling numbers of the first kind in triangular matrix form. Their notation varies, with both brace notation and S(n,k) in common use, reflecting their widespread adoption in mathematical literature.
Did You Know?
- The Stirling numbers of the second kind count the number of ways to partition a set of n labeled objects into k nonempty unlabeled subsets.
- The sum over k of {n k} gives the nth Bell number, the total number of partitions of an n-element set.
Frequently Asked Questions
What are Stirling numbers of the second kind?
They are a family of numbers that count how many ways you can split a set of n distinct items into exactly k nonempty groups where the groups themselves carry no labels. Written as S(n,k) or {n k}, they sit at the heart of partition theory in combinatorics.
Who are Stirling numbers of the second kind named after?
They take their name from the 18th-century Scottish mathematician James Stirling, who investigated these quantities in his work on finite differences and series expansions.
How do Stirling numbers of the second kind connect to Bell numbers?
The Bell number B(n) is obtained by summing S(n,k) over every k from 1 up to n, so it tallies all possible partitions of an n-element set no matter how many blocks each partition has. In that sense, the Stirling numbers of the second kind are the finer-grained building blocks behind the Bell numbers.
What's the difference between Stirling numbers of the first and second kind?
The first kind counts permutations of n objects grouped into exactly k cycles, whereas the second kind counts ways to partition n labeled objects into k nonempty unlabeled subsets. When arranged as triangular matrices, the two families are matrix inverses of one another.
What does S(n,k) actually count in combinatorics?
S(n,k) gives the exact number of equivalence relations on an n-element set that have precisely k equivalence classes, which is the same as the number of ways to divide n labeled objects into k nonempty, unlabeled groups.
More in Combinatorics 1-24
Elsewhere in the Combinatorics universe
Spotted an error? Know more?
This is a living reference — every entry is fact-audited, and reader corrections feed straight into our audit queue. Suggest an edit · See this site's audit record