Stirling Numbers: First and Second Kind Explained with

Stirling numbers count two ways of organizing n labeled objects. The second kind S(n, k) counts splits of n distinct objects into k nonempty unlabeled groups. The first kind c(n, k) counts arrangements of n distinct objects into k cycles. Summing S(n, k) over k gives the Bell numbers; summing c(n, k) gives n!.

These patterns appear in clustering, occupancy problems, and the algebra of powers and factorials. Both kinds satisfy elegant recurrences computing them from smaller values.

Key Concepts

• S(n, k) (second kind): partitions of n labeled objects into k nonempty unlabeled subsets.
• c(n, k) (first kind): permutations of n elements with exactly k disjoint cycles.
• Boundary values: S(n, 1) = 1, S(n, n) = 1, S(n, 0) = 0 for n > 0; same boundaries hold for c(n, k).
• Bell numbers: Bₙ = S(n, 1) + S(n, 2) + … + S(n, n), the total number of partitions of an n-element set.
• Unsigned first kind: c(n, k) counts cycle decompositions; the signed version multiplies by (−1)ⁿ⁻ᵏ.

Formulas

• Second-kind recurrence: S(n, k) = k·S(n−1, k) + S(n−1, k−1). The nth object either joins one of the k existing groups (k choices) or starts a new group alone.
• First-kind recurrence: c(n, k) = (n−1)·c(n−1, k) + c(n−1, k−1). The nth element either joins one of n−1 cycle positions or forms its own 1-cycle.
• Powers via Stirling numbers: xⁿ = Σₖ S(n, k)·x·(x−1)⋯(x−k+1), converting ordinary powers to falling factorials.
• Explicit formula: S(n, k) = (1/k!)·Σⱼ₌₀ᵏ (−1)ʲ·C(k, j)·(k−j)ⁿ, from inclusion-exclusion on onto functions.

Worked Example

Compute S(4, 2) using the recurrence, then verify by listing:

• Needed values: S(3, 2) = 3 and S(3, 1) = 1.
• Recurrence: S(4, 2) = 2·S(3, 2) + S(3, 1) = 2·3 + 1 = 7.
• Verify by listing: the splits of {1,2,3,4} are four of type 1+3 and three of type 2+2, totaling 7. Confirmed.
• Bell check: 1 + 7 + 6 + 1 = B₄ = 15, the known 4th Bell number.
• First-kind sample: c(4, 2) = 3·c(3, 2) + c(3, 1) = 3·3 + 2 = 11 permutations of 4 elements with exactly 2 cycles.

Common Misconceptions

• "The groups in S(n, k) are labeled." They are not: {1,2}|{3,4} and {3,4}|{1,2} are the same grouping. Labeled groups would multiply the count by k!.
• "First and second kind are basically the same." They count genuinely different structures (cycles versus subsets) with different recurrences; only the boundary values coincide.
• "S(n, k) is zero when k > n." That part is true: you cannot make more nonempty groups than objects.

Real-World Applications

• Clustering: the number of ways to cluster n distinct data points into k unlabeled clusters is S(n, k).
• Occupancy: distributing n distinct balls into k identical boxes with none empty is counted by S(n, k).
• Polynomial algebra: the power-to-falling-factorial identity makes Stirling numbers of the second kind the bridge between xⁿ and binomial bases.

Stirling numbers of the second kind S(n, k) split n labeled objects into k unlabeled groups via S(n, k) = k·S(n−1, k) + S(n−1, k−1); the first kind c(n, k) counts permutations with k cycles via a twin recurrence. Keep the groups unlabeled and the two kinds distinct.