🔢Enumerative Combinatorics Unit 8 – Stirling and Bell Numbers in Combinatorics

Key Concepts and Definitions

• Stirling numbers of the first kind $s(n,k)$ count the number of permutations of $n$ elements with $k$ disjoint cycles
• Stirling numbers of the second kind $S(n,k)$ count the number of ways to partition a set of $n$ elements into $k$ non-empty subsets
• Bell numbers $B_n$ represent the total number of partitions of a set with $n$ elements
  • Can be calculated using the sum of Stirling numbers of the second kind: $B_n = \sum_{k=0}^n S(n,k)$
• Recurrence relations provide a way to calculate Stirling and Bell numbers based on previous values
  • For Stirling numbers of the first kind: $s(n+1,k) = s(n,k-1) - n \cdot s(n,k)$
  • For Stirling numbers of the second kind: $S(n+1,k) = k \cdot S(n,k) + S(n,k-1)$
• Generating functions encode sequences of numbers as coefficients of a power series
  • Exponential generating function for Bell numbers: $\sum_{n=0}^{\infty} B_n \frac{x^n}{n!} = e^{e^x-1}$

Historical Background

• James Stirling, a Scottish mathematician, introduced Stirling numbers in the 18th century while studying permutations and partitions
• Stirling numbers of the second kind were discovered first, appearing in Stirling's work on the coefficients of polynomial expansions
• Stirling numbers of the first kind were introduced later by Stirling in the context of permutations with cycles
• Eric Temple Bell, an American mathematician, studied and popularized the numbers that now bear his name in the early 20th century
  • Bell's work focused on the total number of partitions of a set
• The study of Stirling and Bell numbers has since become an important part of enumerative combinatorics
  • Researchers continue to explore their properties, relationships, and applications

Stirling Numbers of the First Kind

• Denoted as $s(n,k)$, where $n$ represents the number of elements and $k$ the number of disjoint cycles
• Can be defined using a recurrence relation: $s(n+1,k) = s(n,k-1) - n \cdot s(n,k)$
  • Base cases: $s(n,0) = 0$ for $n > 0$ and $s(n,n) = 1$ for $n \geq 0$
• Alternate definition using falling factorials: $x^{\underline{n}} = \sum_{k=0}^n s(n,k) x^k$
  • Falling factorial: $x^{\underline{n}} = x(x-1)(x-2) \cdots (x-n+1)$
• Stirling numbers of the first kind can be negative for some values of $n$ and $k$
  • For example, $s(4,2) = -11$
• Unsigned Stirling numbers of the first kind, denoted $|s(n,k)|$, count the number of permutations of $n$ elements with $k$ disjoint cycles, disregarding the sign

Stirling Numbers of the Second Kind

• Denoted as $S(n,k)$, where $n$ represents the number of elements and $k$ the number of non-empty subsets
• Can be defined using a recurrence relation: $S(n+1,k) = k \cdot S(n,k) + S(n,k-1)$
  • Base cases: $S(n,0) = 0$ for $n > 0$ and $S(n,n) = 1$ for $n \geq 0$
• Alternate definition using powers: $x^n = \sum_{k=0}^n S(n,k) x^{\underline{k}}$
  • Rising factorial: $x^{\overline{k}} = x(x+1)(x+2) \cdots (x+k-1)$
• Stirling numbers of the second kind are always non-negative
• Can be used to express the Bell numbers: $B_n = \sum_{k=0}^n S(n,k)$
• Have a combinatorial interpretation related to the number of ways to distribute $n$ distinguishable balls into $k$ indistinguishable boxes

Bell Numbers and Their Properties

• Bell numbers, denoted $B_n$, count the total number of partitions of a set with $n$ elements
  • For example, $B_3 = 5$ because there are 5 ways to partition a set of 3 elements: $\{\{1,2,3\}\}, \{\{1\},\{2,3\}\}, \{\{1,2\},\{3\}\}, \{\{1,3\},\{2\}\}, \{\{1\},\{2\},\{3\}\}$
• Can be calculated using a sum of Stirling numbers of the second kind: $B_n = \sum_{k=0}^n S(n,k)$
• Satisfy the recurrence relation: $B_{n+1} = \sum_{k=0}^n \binom{n}{k} B_k$
  • Represents the number of ways to partition a set of $n+1$ elements by considering the number of elements in the subset containing the $(n+1)$-th element
• Have an exponential generating function: $\sum_{n=0}^{\infty} B_n \frac{x^n}{n!} = e^{e^x-1}$
• Bell numbers grow rapidly, with the first few values being 1, 1, 2, 5, 15, 52, 203, 877, 4140, 21147

Relationships and Connections

• Stirling numbers of the first and second kind are related through the orthogonality property:
  • $\sum_{k=0}^n s(n,k) S(k,m) = \sum_{k=0}^n S(n,k) s(k,m) = \delta_{n,m}$, where $\delta_{n,m}$ is the Kronecker delta
• Bell numbers can be expressed as a sum of Stirling numbers of the second kind: $B_n = \sum_{k=0}^n S(n,k)$
• Stirling numbers of the second kind appear in the expansion of the $n$-th derivative of the exponential function: $\frac{d^n}{dx^n} e^x = \sum_{k=0}^n S(n,k) e^x$
• Stirling numbers have connections to other combinatorial objects, such as the Catalan numbers and the Lah numbers
  • Catalan numbers count the number of ways to parenthesize a product of $n+1$ factors, which can be expressed using Stirling numbers of the first kind
  • Lah numbers, denoted $L(n,k)$, count the number of ways to partition a set of $n$ elements into $k$ non-empty linearly ordered subsets

Applications in Combinatorics

• Stirling numbers of the first kind have applications in the study of permutations and cycles
  • They can be used to count the number of permutations of $n$ elements with a specified number of cycles
• Stirling numbers of the second kind have applications in the study of set partitions
  • They can be used to count the number of ways to partition a set into a specified number of non-empty subsets
• Bell numbers have applications in the study of set partitions and the theory of partitions
  • They provide a way to count the total number of partitions of a set
• Stirling and Bell numbers appear in various combinatorial identities and generating function manipulations
  • For example, the exponential generating function for Bell numbers can be used to derive identities involving Bell numbers and Stirling numbers

Problem-Solving Techniques

• Recognize problems that involve counting permutations with cycles or set partitions, as these may be solvable using Stirling numbers
• Identify problems that ask for the total number of partitions of a set, as these may be solvable using Bell numbers
• Use recurrence relations to calculate Stirling and Bell numbers when needed
  • For Stirling numbers of the first kind: $s(n+1,k) = s(n,k-1) - n \cdot s(n,k)$
  • For Stirling numbers of the second kind: $S(n+1,k) = k \cdot S(n,k) + S(n,k-1)$
  • For Bell numbers: $B_{n+1} = \sum_{k=0}^n \binom{n}{k} B_k$
• Apply the combinatorial interpretations of Stirling numbers when solving counting problems
  • Stirling numbers of the first kind: number of permutations with a specified number of cycles
  • Stirling numbers of the second kind: number of ways to partition a set into a specified number of non-empty subsets
• Utilize generating functions and their properties when manipulating expressions involving Stirling and Bell numbers
  • Exponential generating function for Bell numbers: $\sum_{n=0}^{\infty} B_n \frac{x^n}{n!} = e^{e^x-1}$
• Look for opportunities to apply the orthogonality property or other relationships between Stirling numbers and Bell numbers