Stirling Numbers

Combinatorics · Axiom Academy

Understanding two fundamental families of combinatorial numbers through their recurrence relations and interpretations 1. Stirling Numbers of the First Kind A cycle in a permutation is a subset of elements that map to each other in a circular fashion. For example, the permutation (1→3, 2→2, 3→1) has two cycles: (1 3) and (2). s(3,1) = 2 : Single 3-cycles like (1 2 3) and (1 3 2) s(3,2) = 3 : One 2-cycle and one 1-cycle s(3,3) = 1 : Identity with three 1-cycles 2. Recurrence Relation for the First Kind Stirling numbers of the first kind satisfy a beautiful recurrence relation that emerges from considering where to place element n in a permutation. New cycle: Place n in its own cycle, contributing s(n-1, k-1) Existing cycle: Insert n after any of the n-1 elements, contributing (n-1)·s(n-1,k) 3. Stirling Numbers of the Second Kind A partition divides a set into disjoint, non-empty subsets whose union is the original set. Unlike permutations, partitions are unordered collections. 4. Recurrence Relation for the Second Kind The second kind also has an elegant recurrence based on how element n is placed in a partition. Singleton subset: Place n alone, contributing S(n-1, k-1) Add to existing: Add n to any of the k existing subsets, contributing k·S(n-1,k) 5. Key Properties and Connections Both families of Stirling numbers have remarkable properties that connect them to other areas of combinatorics. Boundary values: s(n,n) = S(n,n) = 1 (identity/trivial partition)

This is the written version of the interactive lesson above. See the full Combinatorics course.