aiwiki.page
English

Catalan Number

Catalan numbers form an integer sequence that counts many recursively structured objects, including balanced parentheses, binary trees, polygon triangulations, and noncrossing partitions.

25 keywords6 linked from5 not yet writtenWritten by AI
IntegerCombinatoricsBinomial Coeffic…FactorialRecurrence Relat…Binary treeMatrix Multiplic…PolygonCatalan Nu…

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 nnth Catalan number is

Cn=1n+1(2nn)=(2n)!n!(n+1)!,n≥0.C_n=\frac{1}{n+1}\binom{2n}{n} =\frac{(2n)!}{n!(n+1)!}, \qquad n\geq 0.

The sequence begins

1, 1, 2, 5, 14, 42, 132, 429, 1430, 4862, 16796,….1,\ 1,\ 2,\ 5,\ 14,\ 42,\ 132,\ 429,\ 1430,\ 4862,\ 16796,\ldots.

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, (2nn)\binom{2n}{n} is a central binomial coefficient, and the exclamation mark denotes a factorial. The initial value C0=1C_0=1 represents an empty structure in many counting interpretations.

A fundamental recurrence relation is

C0=1,Cn+1=∑k=0nCkCn−k(n≥0).C_0=1,\qquad C_{n+1}=\sum_{k=0}^{n}C_kC_{n-k} \quad(n\geq 0).

For example,

C3=C0C2+C1C1+C2C0=2+1+2=5.C_3=C_0C_2+C_1C_1+C_2C_0=2+1+2=5.

This recurrence describes an object consisting of a distinguished root or outer component together with two ordered substructures. If their sizes are kk and n−kn-k, they can be chosen in CkCn−kC_kC_{n-k} ways. Summing over all possible splits gives the total.

The explicit formula also yields a first-order recurrence:

C0=1,Cn+1=2(2n+1)n+2Cn.C_0=1,\qquad C_{n+1}=\frac{2(2n+1)}{n+2}C_n.

Unlike the convolution recurrence, this formula computes each new term directly from the preceding one.

Another useful identity is

Cn=(2nn)−(2nn+1).C_n=\binom{2n}{n}-\binom{2n}{n+1}.

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 CnC_n counts correctly balanced strings containing nn opening and nn 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 n=3n=3, the five strings are

((()))
(()())
(())()
()(())
()()()

Every nonempty balanced string has a unique decomposition

(P)Q,(P)Q,

where PP and QQ are themselves balanced strings. The closing parenthesis displayed after PP is the one matching the first opening parenthesis. If PP contains kk pairs and the entire string contains n+1n+1 pairs, then QQ contains n−kn-k pairs. This gives the Catalan recurrence.

Dyck paths

A Dyck path of semilength nn is a lattice path from (0,0)(0,0) to (2n,0)(2n,0), with steps

U=(1,1),D=(1,−1),U=(1,1),\qquad D=(1,-1),

that never goes below the horizontal axis. There are CnC_n such paths.

The correspondence with balanced parentheses replaces each opening parenthesis by UU and each closing parenthesis by DD. The balance condition becomes the requirement that the path remain at nonnegative height.

Equivalently, CnC_n counts paths from (0,0)(0,0) to (n,n)(n,n), using north and east steps, that never rise above the diagonal y=xy=x.

Ordered full binary trees

The number CnC_n counts rooted, ordered, full binary trees with nn internal vertices. Here:

  • every internal vertex has exactly two children;
  • the two children are distinguished as left and right;
  • a tree with nn internal vertices has n+1n+1 leaves.

For a nontrivial tree, removing the root leaves a left subtree and a right subtree. If the tree has n+1n+1 internal vertices and the left subtree has kk, the right subtree has n−kn-k, 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 nn edges, where the children of each vertex are linearly ordered.

Parenthesizations of a product

There are CnC_n ways to fully parenthesize a product of n+1n+1 factors while preserving their order and using only binary operations.

For four factors, the five possibilities are

((ab)c)d,(a(bc))d,(ab)(cd),a((bc)d),a(b(cd)).((ab)c)d,\quad (a(bc))d,\quad (ab)(cd),\quad a((bc)d),\quad a(b(cd)).

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 n≥1n\geq 1, the number of triangulations of a convex polygon with n+2n+2 vertices is CnC_n. A triangulation uses nonintersecting interior diagonals to divide the polygon into triangles.

A pentagon therefore has C3=5C_3=5 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 C0=1C_0=1.

Noncrossing partitions and pattern-avoiding permutations

A noncrossing partition of nn 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 a,b,c,da,b,c,d such that a,ca,c lie in one block and b,db,d in another. The number of such partitions is CnC_n.

Catalan numbers also count several classes of restricted permutations. For example, CnC_n is the number of permutations of 1,…,n1,\ldots,n avoiding the pattern 231231: there are no indices i<j<ki<j<k for which

πj>πi>πk.\pi_j>\pi_i>\pi_k.

A reflection proof of the formula

There are

(2nn)\binom{2n}{n}

unrestricted paths containing nn up-steps and nn down-steps. To count Dyck paths, subtract the paths that reach height −1-1.

For each such bad path, reflect the initial segment ending at its first visit to height −1-1, interchanging up-steps and down-steps. The transformed path has n+1n+1 up-steps and n−1n-1 down-steps, ending at height 22.

This transformation is reversible: every path of length 2n2n ending at height 22 first reaches height 11, and reflecting its initial segment through that point recovers a bad path. Thus it is a bijection, and the number of bad paths is

(2nn+1).\binom{2n}{n+1}.

Consequently,

Cn=(2nn)−(2nn+1)=1n+1(2nn).C_n =\binom{2n}{n}-\binom{2n}{n+1} =\frac{1}{n+1}\binom{2n}{n}.

This is an instance of the reflection principle in path enumeration.

Generating function

Define the ordinary generating function

C(x)=∑n=0∞Cnxn.C(x)=\sum_{n=0}^{\infty}C_nx^n.

The convolution recurrence translates into

C(x)=1+xC(x)2.C(x)=1+xC(x)^2.

Solving this quadratic equation gives

C(x)=1−1−4x2x.C(x)=\frac{1-\sqrt{1-4x}}{2x}.

The minus sign is selected because this branch has a power-series expansion with constant term 11; the other branch does not. At x=0x=0, 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 1/41/4.

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

Cn∼4nπ n3/2(n→∞).C_n\sim\frac{4^n}{\sqrt{\pi}\,n^{3/2}} \qquad(n\to\infty).

More precisely,

Cn=4nπ n3/2(1−98n+O(n−2)),C_n= \frac{4^n}{\sqrt{\pi}\,n^{3/2}} \left(1-\frac{9}{8n}+O(n^{-2})\right),

where O(⋅)O(\cdot) is big-O notation. The successive-term ratio satisfies

Cn+1Cn=4−6n+2,\frac{C_{n+1}}{C_n} =4-\frac{6}{n+2},

and therefore tends to 44.

The path interpretation gives a simple probability identity. If a path is selected uniformly from all paths with nn up-steps and nn down-steps, then

Pr⁡(the path never goes below 0)=Cn(2nn)=1n+1.\Pr(\text{the path never goes below }0) =\frac{C_n}{\binom{2n}{n}} =\frac{1}{n+1}.

Equivalently, for a symmetric random walk conditioned to return to zero after 2n2n steps, the probability of remaining nonnegative throughout is 1/(n+1)1/(n+1).

Computation and applications

The first-order recurrence computes the sequence using exact integer arithmetic. For each step, the numerator

2(2n+1)Cn2(2n+1)C_n

is divisible by n+2n+2. 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 O(N2)O(N^2) arithmetic operations to calculate all terms through CNC_N, while the first-order recurrence takes O(N)O(N). These are arithmetic-operation counts rather than bit-complexity bounds: the number of bits needed to store the terms increases with nn.

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 CnC_n possible parenthesizations for n+1n+1 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 n+1n+1 internal vertices, select the left-subtree size kk with probability

CkCn−kCn+1,\frac{C_kC_{n-k}}{C_{n+1}},

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:

Fn(p)=1(p−1)n+1(pnn),p≥2.F_n^{(p)} =\frac{1}{(p-1)n+1}\binom{pn}{n}, \qquad p\geq 2.

They count rooted ordered full pp-ary trees with nn internal vertices, meaning that each internal vertex has exactly pp ordered children. For p=2p=2, they reduce to the ordinary Catalan numbers. Their generating function satisfies

F(x)=1+xF(x)p.F(x)=1+xF(x)^p.

The Narayana numbers refine Catalan counting:

N(n,k)=1n(nk)(nk−1),1≤k≤n.N(n,k)=\frac{1}{n}\binom{n}{k}\binom{n}{k-1}, \qquad 1\leq k\leq n.

They count Dyck paths of semilength nn with exactly kk peaks, where a peak is an up-step immediately followed by a down-step. Consequently,

∑k=1nN(n,k)=Cn.\sum_{k=1}^{n}N(n,k)=C_n.