Stirling Numbers

Why This Matters

Stirling numbers are the workhorses of combinatorial enumeration—they answer two fundamental questions that appear throughout algebraic combinatorics: How many ways can we arrange elements into cycles? and How many ways can we partition a set into groups? These questions connect directly to permutation groups, symmetric functions, and generating function techniques that form the backbone of the course. When you encounter problems about distributing objects, counting permutations by structure, or expanding polynomials in different bases, Stirling numbers are almost certainly lurking beneath the surface.

You're being tested on your ability to recognize which type of Stirling number applies to a given problem, derive values using recurrence relations, and connect these numbers to broader structures like Bell numbers and generating functions. Don't just memorize the formulas—understand what each Stirling number counts and why the recurrences make combinatorial sense. If you can explain why adding an element either creates a new cycle/subset or joins an existing one, you've mastered the conceptual core.

---

Stirling Numbers of the First Kind: Counting Cycles

The first kind counts permutations by their cycle structure. Every permutation can be uniquely decomposed into disjoint cycles, and $c(n,k)$ tells you exactly how many permutations of $n$ elements have exactly $k$ cycles.

Unsigned Stirling Numbers of the First Kind

• Denoted $c(n,k)$ or $\begin{bmatrix} n \\ k \end{bmatrix}$—counts permutations of $n$ elements with exactly $k$ disjoint cycles
• Recurrence relation: $c(n,k) = c(n-1,k-1) + (n-1) \cdot c(n-1,k)$—the new element either forms its own 1-cycle or inserts into one of $(n-1)$ positions in existing cycles
• Boundary conditions: $c(n,0) = 0$ for $n > 0$, $c(0,0) = 1$, and $c(n,n) = 1$ since the identity permutation has $n$ fixed points

Signed Stirling Numbers of the First Kind

• Denoted $s(n,k)$ with lowercase—these incorporate the sign $(-1)^{n-k}$ based on permutation parity
• Relationship to unsigned version: $s(n,k) = (-1)^{n-k} c(n,k)$, connecting cycle count to even/odd permutation classification
• Appears in polynomial expansions: the falling factorial $x^{\underline{n}} = x(x-1)(x-2)\cdots(x-n+1)$ expands as $\sum_{k=0}^{n} s(n,k) x^k$

---

Stirling Numbers of the Second Kind: Counting Partitions

The second kind counts set partitions. A partition divides elements into non-empty, non-overlapping groups where order within groups doesn't matter, and $S(n,k)$ counts partitions of $n$ elements into exactly $k$ such subsets.

Definition and Recurrence

• Denoted $S(n,k)$ or $\begin{Bmatrix} n \\ k \end{Bmatrix}$—counts ways to partition an $n$-element set into exactly $k$ non-empty subsets
• Recurrence relation: $S(n,k) = k \cdot S(n-1,k) + S(n-1,k-1)$—the new element either joins one of $k$ existing subsets or forms a new singleton subset
• Always non-negative integers with boundaries $S(n,0) = 0$ for $n > 0$, $S(0,0) = 1$, and $S(n,1) = S(n,n) = 1$

Combinatorial Interpretation

• Models "balls into boxes" problems—specifically, $n$ distinguishable objects into $k$ indistinguishable non-empty groups
• Multiply by $k!$ for distinguishable boxes—the number of surjective functions from an $n$-set to a $k$-set is $k! \cdot S(n,k)$
• Connects to equivalence relations: each partition corresponds to an equivalence relation on the set, making $S(n,k)$ fundamental to abstract algebra

---

Generating Functions and Analytic Tools

Generating functions transform Stirling number sequences into algebraic objects, enabling powerful techniques for deriving identities and asymptotic behavior.

Generating Function for First Kind

• Exponential generating function: $\sum_{n=k}^{\infty} c(n,k) \frac{x^n}{n!} = \frac{(-\ln(1-x))^k}{k!}$
• Ordinary generating function form: connects to rising/falling factorial expansions in polynomial bases
• Useful for extracting coefficients and proving identities involving factorials and cycle counts

Generating Function for Second Kind

• Exponential generating function: $\sum_{n=k}^{\infty} S(n,k) \frac{x^n}{n!} = \frac{(e^x - 1)^k}{k!}$
• The factor $(e^x - 1)$ represents "at least one element"—raising it to the $k$th power captures $k$ non-empty subsets
• Derives the explicit formula: $S(n,k) = \frac{1}{k!} \sum_{j=0}^{k} (-1)^{k-j} \binom{k}{j} j^n$ via inclusion-exclusion

---

Connections to Other Combinatorial Objects

Stirling numbers don't exist in isolation—they're nodes in a network of combinatorial relationships that frequently appear on exams.

Bell Numbers

• Definition: $B_n = \sum_{k=0}^{n} S(n,k)$ counts all partitions of an $n$-element set, regardless of number of parts
• Exponential generating function: $\sum_{n=0}^{\infty} B_n \frac{x^n}{n!} = e^{e^x - 1}$, derived directly from the second kind's generating function
• Bell triangle construction provides efficient computation similar to Pascal's triangle for binomial coefficients

Relationship to Binomial Coefficients

• Conversion formulas exist between Stirling numbers and binomial coefficients via combinatorial identities
• Powers to falling factorials: $x^n = \sum_{k=0}^{n} S(n,k) x^{\underline{k}}$ uses second kind to convert between polynomial bases
• Falling factorials to powers: $x^{\underline{n}} = \sum_{k=0}^{n} s(n,k) x^k$ uses signed first kind for the inverse conversion

---

Asymptotic Analysis and Applications

Stirling's Approximation

• The famous formula: $n! \sim \sqrt{2\pi n} \left(\frac{n}{e}\right)^n$ provides asymptotic estimates for factorials
• Named connection but distinct concept—Stirling's approximation relates to Stirling the mathematician, not directly to Stirling numbers
• Useful for analyzing growth rates of expressions involving Stirling numbers when $n$ becomes large

Applications in Partition Theory

• Algorithm analysis: counting ways to distribute tasks among processors or hash table collision analysis
• Statistical mechanics: partition functions and state counting in physical systems
• Symmetric function theory: Stirling numbers appear as coefficients when changing between polynomial bases in the ring of symmetric functions

---

Quick Reference Table

---

Self-Check Questions

1. A permutation of 5 elements has exactly 2 cycles. Which Stirling number counts how many such permutations exist, and what recurrence would you use to compute it?

2. Compare and contrast: Why does the recurrence for $c(n,k)$ have a factor of $(n-1)$ while the recurrence for $S(n,k)$ has a factor of $k$? What combinatorial action does each factor represent?

3. If you need to count the number of ways to assign 6 distinct tasks to 3 distinct teams (each team must have at least one task), which expression gives the answer: $S(6,3)$, $3! \cdot S(6,3)$, or $c(6,3)$?

4. The generating function $\frac{(e^x-1)^4}{4!}$ is the EGF for which sequence? How would you extract the coefficient of $\frac{x^7}{7!}$?

5. Explain why $B_n > S(n,k)$ for any fixed $k < n$, and describe a problem where you'd need $B_n$ instead of individual Stirling numbers of the second kind.