Catalan numbers are a fascinating sequence in combinatorics, popping up in countless counting problems. They're like the Swiss Army knife of number sequences, helping us solve puzzles involving parentheses, trees, and paths.

From binary trees to mountain ranges, Catalan numbers show up everywhere. They're a key player in this chapter on enumerative combinatorics, giving us powerful tools to tackle complex counting problems with elegance and efficiency.

Catalan Numbers and Combinatorial Interpretations

Definition and Notation

• Catalan numbers are a sequence of natural numbers that occur in various counting problems, often involving recursively defined objects
• The n-th Catalan number is denoted as C(n) and counts the number of structurally unique objects of a certain type of size n
• The first few Catalan numbers are 1, 1, 2, 5, 14, 42, 132, 429, 1430, 4862, 16796, 58786, 208012, 742900, 2674440, 9694845, 35357670, 129644790, 477638700, 1767263190

Combinatorial Interpretations

• Catalan numbers have many combinatorial interpretations, including:
  1. The number of valid parentheses expressions with n pairs of parentheses (e.g., for n=3, the valid expressions are ()()(), (())(), ()(()), (()()), (()()))
  2. The number of binary trees with n nodes (e.g., for n=3, there are 5 unique binary trees)
  3. The number of monotonic paths on an n x n grid from the bottom-left corner to the top-right corner, using only up and right steps and staying below the diagonal (e.g., for n=3, there are 5 such paths)
  4. The number of ways to triangulate a convex polygon with n+2 sides (e.g., for n=2, there are 2 ways to triangulate a square)
  5. The number of ways to parenthesize a product of n+1 factors (e.g., for n=2, the valid parenthesizations are (ab)c and a(bc))

Closed-Form Formula and Generating Function for Catalan Numbers

Closed-Form Formula

• The closed-form formula for the n-th Catalan number is:
  • $C(n) = \frac{1}{n+1} \binom{2n}{n}$, where $\binom{2n}{n}$ represents the binomial coefficient
• The closed-form formula can be derived using a recursive definition of Catalan numbers and solving the recurrence relation:
  • $C(0) = 1$
  • $C(n+1) = \sum_{i=0}^{n} C(i) \cdot C(n-i)$ for $n \geq 0$
• The binomial coefficient $\binom{2n}{n}$ counts the number of ways to choose n objects from 2n objects, and dividing by $n+1$ gives the n-th Catalan number

Generating Function

• The generating function for Catalan numbers is:
  • $C(x) = \frac{1 - \sqrt{1 - 4x}}{2x}$, where $C(x) = \sum_{n=0}^{\infty} C(n) \cdot x^n$
• The generating function can be derived using the recursive definition of Catalan numbers and solving the resulting functional equation:
  • $C(x) = 1 + x \cdot C(x)^2$
• The generating function allows for efficient computation of Catalan numbers and provides insights into their asymptotic behavior
• The generating function can be used to prove identities involving Catalan numbers and to analyze the growth rate of the sequence (e.g., using singularity analysis)

Solving Combinatorial Problems with Catalan Numbers

Dyck Paths

• Dyck paths are lattice paths from (0,0) to (2n,0) using only up-steps (1,1) and down-steps (1,-1), never falling below the x-axis
• The number of Dyck paths of length 2n is given by the n-th Catalan number
• Example: For n=3, there are 5 Dyck paths: UUUDDD, UDUUDD, UDUDDD, UUDDUD, UDDUUD
• Dyck paths can be used to model various problems, such as balanced parentheses expressions and mountain ranges

Binary Trees

• Binary trees are rooted trees in which each node has at most two children
• The number of structurally unique binary trees with n nodes is given by the n-th Catalan number
• Example: For n=3, there are 5 unique binary trees
• Binary trees have applications in computer science, such as expression trees and search trees

Other Combinatorial Problems

• Catalan numbers can be used to solve various other combinatorial problems, such as:
  1. The number of ways to triangulate a convex polygon with n+2 sides
  2. The number of ways to parenthesize a product of n+1 factors
  3. The number of non-crossing partitions of a set of size n
  4. The number of ways to divide a polygon into triangles by connecting vertices with non-intersecting line segments
• These problems often involve recursive structures and can be solved using the recursive definition of Catalan numbers or by establishing bijections with known Catalan objects

Connections Between Catalan Numbers and Other Structures

Relationship with Binomial Coefficients

• Catalan numbers are closely related to the binomial coefficients, as evident from the closed-form formula:
  • $C(n) = \frac{1}{n+1} \binom{2n}{n}$
• The binomial coefficient $\binom{2n}{n}$ counts the number of ways to choose n objects from 2n objects, and dividing by $n+1$ gives the n-th Catalan number
• This relationship allows for the efficient computation of Catalan numbers using binomial coefficients

Connection to Narayana Numbers

• Narayana numbers refine the Catalan numbers by counting the number of Dyck paths with a specific number of peaks
• The Narayana number $N(n,k)$ counts the number of Dyck paths of length 2n with exactly k peaks
• The sum of Narayana numbers $N(n,k)$ over all possible values of k (from 1 to n) gives the n-th Catalan number:
  • $C(n) = \sum_{k=1}^{n} N(n,k)$
• Narayana numbers provide a more detailed breakdown of the structure of Dyck paths and have applications in enumerative combinatorics

Möbius Function and Noncrossing Partitions

• The Catalan numbers are the Möbius function of the noncrossing partition lattice
• The noncrossing partition lattice is a partially ordered set (poset) of all noncrossing partitions of a set of size n, ordered by refinement
• The Möbius function is a key concept in combinatorics and poset theory, measuring the "inversions" of the poset
• This connection provides insights into the structure and properties of noncrossing partitions and their relationship with Catalan numbers

Relation to Ballot Numbers

• Catalan numbers are related to the Ballot numbers, which count the number of ways to walk from (0,0) to (n,k) staying above the diagonal line y = x
• The Ballot number $B(n,k)$ is defined as:
  • $B(n,k) = \frac{k+1}{n+1} \binom{n+k}{k}$, where $n \geq k \geq 0$
• When n = k, the Ballot number reduces to the Catalan number:
  • $B(n,n) = \frac{n+1}{2n+1} \binom{2n}{n} = C(n)$
• Ballot numbers have applications in voting theory and the analysis of elections

Appearance in Permutations

• Catalan numbers also appear in the study of certain types of permutations
• The number of 321-avoiding permutations of length n (permutations that do not contain a decreasing subsequence of length 3) is given by the n-th Catalan number
• The number of stack-sortable permutations of length n (permutations that can be sorted using a stack) is also given by the n-th Catalan number
• These connections highlight the importance of Catalan numbers in the study of permutation patterns and sorting algorithms