Stirling numbers of the second kind
Numbers counting partitions of a set into nonempty subsets.
Stirling numbers of the second kind, often written with brace notation or as S(n,k), count the number of distinct ways to divide a set of n labeled items into k nonempty, unlabeled subsets. They are also equivalent to the number of different equivalence relations that can be defined on an n-element set which have exactly k equivalence classes. For any n greater than or equal to 1, S(n,1) equals 1, as the only partition of a nonempty set into one part is to place all elements together. Similarly, S(n,n) equals 1, since the only way to partition an n-element set into n parts is to put each element into its own part. S(n,0) is 0 for n greater than 0, because a nonempty set cannot be partitioned into zero subsets. These numbers are named after the mathematician James Stirling. The brace notation {n k} was used by Imanuel Marx and Antonio Salmeri in 1962, and later popularized by Donald Knuth in *The Art of Computer Programming*; it was also used earlier by Jovan Karamata in 1935. The notation S(n,k) was employed by Richard Stanley in *Enumerative Combinatorics* and by many earlier writers. Summing S(n,k) over all k from 0 to n gives the nth Bell number, which is the total number of partitions of an n-element set. The numbers obey a recurrence relation, first discovered by Masanobu Saka in 1782, where S(n,k) equals S(n-1,k-1) plus k times S(n-1,k). This recurrence can be proved by considering whether the nth object forms its own singleton subset or joins an existing subset. An explicit formula for S(n,k) involves a sum using inclusion-exclusion, counting surjections from an n-element set to a k-element set. The numbers also appear as the evaluation of incomplete exponential Bell polynomials when all arguments are set to 1.
- 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) for Stirling numbers of the second kind was employed by Richard Stanley in his work *Enumerative Combinatorics* and, earlier, by numerous other writers. These numbers, also known as Stirling partition numbers, count the ways to partition a set of n labeled objects into k nonempty, unlabeled subsets. They are named for the mathematician James Stirling. The numbers can be arranged in a triangular array, where values for a given n and k are found using a recurrence relation first discovered by Masanobu Saka. This relation states that S(n,k) = S(n-1,k-1) + k * S(n-1,k), with initial conditions such that S(n,1) = 1, S(n,n) = 1, and S(n,0) = 0 for n ≥ 1. The recurrence is proven by considering whether the nth object forms its own subset or joins an existing one. An explicit formula for these numbers involves a sum using binomial coefficients and powers, derived through inclusion-exclusion. The sum of all S(n,k) for a fixed n yields the nth Bell number, which is the total number of partitions of an n-element set. The numbers also appear in the evaluation of incomplete exponential Bell polynomials when the sequence of arguments is all ones.
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
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