Classical combinatorial numbers · Definition
Stirling number of the second kind
Before you start you need to know
When you partition a set, the groups never come in a meaningful order. Stirling numbers of the second kind count exactly how many such groupings exist.
Definition
The Stirling number of the second kind S(n,k) counts the partitions of a set of n elements into k nonempty, indistinguishable blocks.
Its basic properties are S(n,1)=1, S(n,n)=1, and S(n,k)=0 when k>n. They satisfy the recurrence S(n,k)=kS(n-1,k)+S(n-1,k-1), justified by splitting on whether element n forms its own block or joins an existing one. Moreover, summing S(n,k) over k gives the Bell number.
For n=4 and k=2, the recurrence gives S(4,2)=2S(3,2)+S(3,1)=2·3+1=7. Checking by enumeration, the partitions of {1,2,3,4} into two blocks number 7, which confirms the value.
A typical mistake is confusing S(n,k) with binomial coefficients, or counting ordered partitions as if the order of the blocks mattered. Remember that the blocks are indistinguishable, so S(n,k) is not multiplied by k! unless you want ordered partitions.
Think about it
Why is S(n,k) not multiplied by k! when the blocks have no order, and what would change if they did?
Unlabeled blocks have no inherent order, so each partition is counted once. If the blocks were labeled or ordered, each partition would be counted k! times, giving \(k!\,S(n,k)\).
Exercises 10
- How many partitions of a 3-element set into 2 nonempty blocks exist?
- State the value of S(n,n) for any n≥1.
- State what the Stirling number S(n,k) counts.
- What is the value of \(S(n,1)\) for \(n\ge 1\)?
- What is S(n,k) when k>n?
- Use the recurrence to compute S(4,2).
- Compute S(4,3) using S(n,k)=kS(n-1,k)+S(n-1,k-1) and S(3,3)=1.
- Add the values S(3,k) for k=1,2,3 and state which Bell number this is.
- How many ordered partitions of 3 elements into 2 nonempty blocks exist?
- Prove that \(S(n,2)=2^{n-1}-1\) for \(n\ge 1\) and check with \(n=4\). State the value of \(S(4,2)\).
What comes next
References
- Richard P. Stanley, Enumerative Combinatorics, Volume 1, 2nd edition, Cambridge University Press, 2012.
- Herbert S. Wilf, generatingfunctionology, 3rd edition, A K Peters, 2006.