The Catalan numbers are a sequence of positive integers that occurs throughout combinatorics, especially in problems involving nesting, branching, and noncrossing structures. With indexing beginning at zero, the th Catalan number is
The sequence begins
Although many of the objects counted by these numbers look unrelated, their recursive decompositions often have the same form. Correspondences between these objects explain why the same sequence repeatedly appears.
Definition and recurrence relations
In the defining formula, is a central binomial coefficient, and the exclamation mark denotes a factorial. The initial value represents an empty structure in many counting interpretations.
A fundamental recurrence relation is
For example,
This recurrence describes an object consisting of a distinguished root or outer component together with two ordered substructures. If their sizes are and , they can be chosen in ways. Summing over all possible splits gives the total.
The explicit formula also yields a first-order recurrence:
Unlike the convolution recurrence, this formula computes each new term directly from the preceding one.
Another useful identity is
Besides establishing that the closed form is an integer, this expression arises naturally from a reflection argument for lattice paths.
Principal counting interpretations
Balanced parentheses
The number counts correctly balanced strings containing opening and closing parentheses. A string is balanced when every initial segment contains at least as many opening as closing parentheses, and the total numbers are equal.
For , the five strings are
((()))
(()())
(())()
()(())
()()()
Every nonempty balanced string has a unique decomposition
where and are themselves balanced strings. The closing parenthesis displayed after is the one matching the first opening parenthesis. If contains pairs and the entire string contains pairs, then contains pairs. This gives the Catalan recurrence.
Dyck paths
A Dyck path of semilength is a lattice path from to , with steps
that never goes below the horizontal axis. There are such paths.
The correspondence with balanced parentheses replaces each opening parenthesis by and each closing parenthesis by . The balance condition becomes the requirement that the path remain at nonnegative height.
Equivalently, counts paths from to , using north and east steps, that never rise above the diagonal .
Ordered full binary trees
The number counts rooted, ordered, full binary trees with internal vertices. Here:
- every internal vertex has exactly two children;
- the two children are distinguished as left and right;
- a tree with internal vertices has leaves.
For a nontrivial tree, removing the root leaves a left subtree and a right subtree. If the tree has internal vertices and the left subtree has , the right subtree has , again producing the Catalan recurrence.
The qualifications “ordered” and “full” matter: changing the class of trees changes the counting sequence. Catalan numbers also count rooted plane trees with edges, where the children of each vertex are linearly ordered.
Parenthesizations of a product
There are ways to fully parenthesize a product of factors while preserving their order and using only binary operations.
For four factors, the five possibilities are
These are syntactic arrangements. If the operation is associative, all arrangements have the same value, but they remain distinct parenthesizations. For matrix multiplication, different parenthesizations may require different numbers of arithmetic operations even though the resulting matrix is unchanged.
Polygon triangulations
For , the number of triangulations of a convex polygon with vertices is . A triangulation uses nonintersecting interior diagonals to divide the polygon into triangles.
A pentagon therefore has triangulations. The polygon’s vertices are regarded as fixed and distinguishable; triangulations related by rotation or reflection are not identified.
Fixing one boundary edge and considering the triangle incident to it decomposes the remaining region into two smaller polygonal regions. This yields another version of the Catalan recurrence, with empty regions handled by the convention .
Noncrossing partitions and pattern-avoiding permutations
A noncrossing partition of points placed in order around a circle is a partition whose blocks do not cross. More precisely, there must not be four points in cyclic order such that lie in one block and in another. The number of such partitions is .
Catalan numbers also count several classes of restricted permutations. For example, is the number of permutations of avoiding the pattern : there are no indices for which
A reflection proof of the formula
There are
unrestricted paths containing up-steps and down-steps. To count Dyck paths, subtract the paths that reach height .
For each such bad path, reflect the initial segment ending at its first visit to height , interchanging up-steps and down-steps. The transformed path has up-steps and down-steps, ending at height .
This transformation is reversible: every path of length ending at height first reaches height , and reflecting its initial segment through that point recovers a bad path. Thus it is a bijection, and the number of bad paths is
Consequently,
This is an instance of the reflection principle in path enumeration.
Generating function
Define the ordinary generating function
The convolution recurrence translates into
Solving this quadratic equation gives
The minus sign is selected because this branch has a power-series expansion with constant term ; the other branch does not. At , the expression is interpreted by its removable limit.
As a formal power series, the identity encodes the recurrence without requiring analytic convergence. As a complex power series, it has radius of convergence .
The square-root form is characteristic of many recursively defined tree-like classes. It also provides a route from the recurrence to the explicit coefficient formula.
Growth and probability
Using Stirling’s approximation in the factorial formula gives
More precisely,
where is big-O notation. The successive-term ratio satisfies
and therefore tends to .
The path interpretation gives a simple probability identity. If a path is selected uniformly from all paths with up-steps and down-steps, then
Equivalently, for a symmetric random walk conditioned to return to zero after steps, the probability of remaining nonnegative throughout is .
Computation and applications
The first-order recurrence computes the sequence using exact integer arithmetic. For each step, the numerator
is divisible by . Multiplication before division avoids truncation in integer arithmetic. Direct floating-point evaluation of factorials can overflow even when the final result remains representable.
The convolution recurrence takes arithmetic operations to calculate all terms through , while the first-order recurrence takes . These are arithmetic-operation counts rather than bit-complexity bounds: the number of bits needed to store the terms increases with .
In computer science, Catalan numbers describe the sizes of search spaces involving expression trees, nested syntax, and parenthesizations. They explain why exhaustive enumeration quickly becomes impractical.
Counting and optimization are distinct tasks. A matrix-chain multiplication problem has possible parenthesizations for matrices, yet dynamic programming can find an optimal parenthesization without listing them all.
Catalan decompositions also support uniform random generation. To generate a uniformly chosen ordered full binary tree with internal vertices, select the left-subtree size with probability
then independently generate uniform left and right subtrees of the selected sizes. Choosing the split uniformly would generally not produce a uniform distribution on trees.
History and generalizations
The sequence is named after the Belgian mathematician Eugène Charles Catalan, who studied parenthesization problems in the nineteenth century. Its history predates that work: Leonhard Euler investigated polygon triangulations in the eighteenth century, and Johann Andreas von Segner obtained the associated recurrence. The same numbers also appeared independently in work by the Mongolian mathematician Minggatu.
A standard generalization is given by the Fuss–Catalan numbers:
They count rooted ordered full -ary trees with internal vertices, meaning that each internal vertex has exactly ordered children. For , they reduce to the ordinary Catalan numbers. Their generating function satisfies
The Narayana numbers refine Catalan counting:
They count Dyck paths of semilength with exactly peaks, where a peak is an up-step immediately followed by a down-step. Consequently,