["# Computing $ S(6,3) $ Using Recurrence: A Step-by-Step Guide", "In combinatorics, computing $ S(n,k) $ — the Stirling number of the second kind — is essential for counting the number of ways to partition a set of $ n $ elements into $ k $ non-empty, unlabeled subsets. Here, we explore how to compute $ S(6,3) $ using a recurrence relation, a powerful technique valued by statisticians and computer scientists alike.", "## What Is $ S(n,k) $?", "The Stirling number of the second kind, denoted $ S(n,k) $, represents the number of ways to partition a set of $ n $ labeled objects (say, 6 distinct items) into $ k $ non-empty, unlabeled subsets. For instance, $ S(6,3) $ answers: how many ways can 6 distinct objects be grouped into 3 non-empty groups where order of the groups doesn’t matter?", "## Recursive Definition of $ S(n,k) $", "Stirling numbers satisfy the recurrence:", "$$
\nS(n,k) = S(n-1,k-1) + k \cdot S(n-1,k)
\n$$", "with these base cases:", "- $ S(0,0) = 1 $: One way to partition zero elements into zero subsets.
\n- $ S(n,0) = 0 $ for $ n > 0 $: Cannot partition positive elements into zero subsets.
\n- $ S(0,k) = 0 $ for $ k > 0 $: No way to partition zero elements into positive subsets.", "This recurrence arises naturally: the $ n $-th element can either:", "- Be in a subset by itself, preceded by $ S(n-1,k-1) $ partitions, or
\n- Join one of the $ k $ existing subsets in a partition of $ n-1 $ elements, giving $ k \cdot S(n-1,k) $.", "## Computing $ S(6,3) Step-by-Step", "We build a table to compute $ S(n,k) $ for $ 1 \leq k \leq 3 $ and $ 1 \leq n \leq 6 $ using the recurrence.", "| $ n \backslash k $ | 0 | 1 | 2 | 3 | 4 | 5 | 6 |
\n|----------------------|----|----|----|----|----|----|----|
\n| 0 | 1 | 0 | 0 | 0 | 0 | 0 | 0 |
\n| 1 | 0 | 1 | 0 | 0 | 0 | 0 | 0 |
\n| 2 | 0 | 1 | 1 | 0 | 0 | 0 | 0 |
\n| 3 | 0 | 1 | 3 | 1 | 0 | 0 | 0 |
\n| 4 | 0 | 1 | 7 | 6 | 1 | 0 | 0 |
\n| 5 | 0 | 1 | 15 | 25 | 10 | 1 | 0 |
\n| 6 | 0 | 1 | 31 | 90 | 65 | 15 |", "Let’s compute $ S(6,3) $ step-by-step:", "1. Base row $ n=2 $:
\n $ S(2,3) = 0 $ (can’t split 2 items into 3 non-empty subsets)", "2. $ n=3 $:
\n $ S(3,3) = S(2,2) + 3 \cdot S(2,3) = 1 + 3 \cdot 0 = 1 $
\n (Only one way: each element in its own subset.)", "3. $ n=4 $:
\n $ S(4,3) = S(3,2) + 3 \cdot S(3,3) = 3 + 3 \cdot 1 = 6 $", "4. $ n=5 $:
\n $ S(5,3) = S(4,2) + 3 \cdot S(4,3) $
\n Need $ S(4,2) = S(3,1) + 2 \cdot S(3,2) = 1 + 2 \cdot 3 = 7 $
\n So, $ S(5,3) = 7 + 3 \cdot 6 = 7 + 18 = 25 $", "5. $ n=6 $:
\n $ S(6,3) = S(5,2) + 3 \cdot S(5,3) $
\n Compute $ S(5,2) = S(4,1) + 2 \cdot S(4,2) = 1 + 2 \cdot 7 = 15 $
\n Then,
\n $$
\n S(6,3) = 15 + 3 \cdot 25 = 15 + 75 = 90
\n $$", "Thus,
\n$$
\nS(6,3) = 90
\n$$", "## Why Use Recurrence for This?", "- Efficiency: For large $ n $, dynamic programming optimized using recurrence saves exponential time over direct enumeration.
\n- Foundational: Recursive definitions connect Stirling numbers to other combinatorial theories, algorithms, and generating functions.
\n- Accurate: The recurrence guarantees correctness when base cases are handled properly.", "## Conclusion", "Using the recurrence relation $ S(n,k) = S(n-1,k-1) + k \cdot S(n-1,k) $, we efficiently compute $ S(6,3) = 90 $. This method exemplifies how recurrence relations form the backbone of combinatorial computation, offering clarity and power in solving partition problems across mathematics, computer science, and statistics.", "---", "Keywords: Stirling number of the second kind, $ S(n,k) $, recurrence relation, combinatorics, set partitioning, dynamic programming, $ S(6,3) computation.
\nMeta Description: Learn how to compute $ S(6,3) using the recurrence relation $ S(n,k) = S(n-1,k-1) + k \cdot S(n-1,k) $. Step-by-step guide with base cases and intermediate values."]
