Catalan number

The Catalan numbers form the sequence 1, 1, 2, 5, 14, …, whose terms count many recursively structured objects, including binary trees and balanced parenthesis strings.

Balanced parentheses: A string of opening and closing parentheses in which every prefix has at least as many openings as closings, with equal totals overall. The nth Catalan number counts valid strings with n pairs of parentheses.
Catalan recurrence: The relation C₀ = 1 and Cₙ₊₁ = ∑ᵢ₌₀ⁿ CᵢCₙ₋ᵢ defining Catalan numbers recursively. Splitting a counted object at its root produces two smaller Catalan objects.
Combinatorics: The branch of mathematics concerned with counting, arranging, and analyzing finite structures. Catalan numbers are a central sequence in enumerative combinatorics.
Leonhard Euler: An eighteenth-century Swiss mathematician whose work shaped analysis, number theory, and combinatorics. Euler encountered the polygon-triangulation counts now identified with Catalan numbers.
Binary tree: A rooted tree in which each node has at most two children, distinguished as left and right when ordered. Catalan numbers count ordered binary tree shapes with a fixed number of internal nodes.
Catalan generating function: The formal power series C(x) = ∑ₙ≥₀ Cₙxⁿ satisfying C(x) = 1 + xC(x)². The quadratic identity encodes the sequence's recursive decomposition.
Recursion: A method of defining or solving a problem in terms of smaller instances of itself. Many Catalan-counted objects decompose into smaller objects of the same kind.
Johann Andreas von Segner: An eighteenth-century mathematician who studied the recurrence for counting polygon triangulations. His recurrence is an early form of the relation defining Catalan numbers.
Dyck path: A lattice path using up-steps and down-steps that never falls below its starting height and ends at that height. Dyck paths of semilength n are counted by the nth Catalan number.
Central binomial coefficient: The binomial coefficient binom(2n,n), the largest coefficient in the expansion of (1+x)²ⁿ. Each Catalan number is the central binomial coefficient divided by n+1.

Linked from 12 pages