Skip to content

Catalan Numbers: Where They Appear and How to Compute Them

The Catalan numbers 1, 1, 2, 5, 14, 42 count balanced brackets, mountain paths, binary trees and triangulations. The formula, the recurrence and why they match.

By Published 4 min read

Reign Creative LLC makes Discrete Math: Study & Quiz, which this article links to, so we have a commercial interest in it. How we write and check articles.

AI-assisted article. Drafted with AI tools from the sources cited below and checked by automated tests and an AI editorial review. No person has reviewed it yet. How we write and check articles.

Key takeaways

  • The Catalan numbers begin 1, 1, 2, 5, 14, 42, 132, 429, 1430 and are given by Cₙ = C(2n, n)/(n + 1).
  • They count balanced strings of n pairs of brackets, mountain paths that never dip below the start, binary trees with n nodes and triangulations of a polygon with n + 2 sides.
  • They satisfy the recurrence Cₙ₊₁ = C₀Cₙ + C₁Cₙ₋₁ + ⋯ + CₙC₀, from splitting a structure at its first point of return.
  • The reflection principle gives the formula: all paths minus bad paths, C(2n, n) − C(2n, n + 1).
  • When a counting problem gives 1, 2, 5, 14 for small cases, suspect Catalan numbers and look for a bijection to brackets.

Some sequences turn up so often that recognising them is a skill in itself. The Catalan numbers are a prime example in combinatorics:

1, 1, 2, 5, 14, 42, 132, 429, 1430, 4862, …

They count brackets, paths, trees and triangulations, problems that look unrelated until you see that each is built the same recursive way. The OEIS lists the sequence as A000108 with the formula Cₙ = C(2n, n)/(n + 1).

Four things they count

Take n = 3, where the answer is C₃ = 5.

Balanced brackets. Strings of 3 opening and 3 closing brackets in which no prefix has more closers than openers:

((())) · (()()) · (())() · ()(()) · ()()()

Mountain paths (Dyck paths). Paths of 3 up-steps and 3 down-steps that never go below the starting level. Replace "(" with up and ")" with down and the five bracket strings become the five paths. This is the same structure, which is the point.

Binary trees. Binary trees with 3 nodes, where each node has an optional left child and an optional right child: there are 5 shapes.

Triangulations. A convex pentagon (3 + 2 = 5 sides) can be cut into triangles by non-crossing diagonals in 5 ways, one for each vertex the two diagonals can share. MathWorld introduces the Catalan numbers with this question, Euler's polygon division problem.

n Cₙ Bracket strings with n pairs Polygon with n + 2 sides
0 1 the empty string a 2-gon, by convention
1 1 () a triangle: already one triangle
2 2 (()), ()() a square: 2 diagonals to choose from
3 5 five strings, above a pentagon: 5
4 14 14 strings a hexagon: 14

MathWorld's entry lists more: ballot sequences in which the first candidate never trails, full binary trees, and the ways to bracket a product of n + 1 factors such as ((ab)c)d.

The formula, from the reflection principle

Count mountain paths with n up-steps and n down-steps.

  1. All paths. Without the "stay above the start" rule, choose which n of the 2n steps go up: C(2n, n). This is the lattice-path count from Levin's Discrete Mathematics: An Open Introduction and from counting lattice paths.
  2. Bad paths. A path that dips below the start touches level −1 somewhere. Reflect the part of the path after its first touch of −1: ups become downs and downs become ups. The reflected path ends at −2 instead of 0, so it has n − 1 ups and n + 1 downs. Every path ending at −2 must touch −1, and reflecting back recovers the original, so bad paths match paths with n + 1 downs one-to-one: C(2n, n + 1) of them.
  3. Good paths. Cₙ = C(2n, n) − C(2n, n + 1).

Simplifying, C(2n, n + 1) = C(2n, n) · n/(n + 1), so

Cₙ = C(2n, n) · 1/(n + 1) = (2n)!/((n + 1)! n!).

Check: n = 4 gives C(8, 4) − C(8, 5) = 70 − 56 = 14, and 70/5 = 14.

The recurrence

Every non-empty balanced string starts with "(" and has a first matching ")". Inside that pair sits a balanced string with some k pairs; after it comes a balanced string with the remaining n − k pairs. Summing over k:

Cₙ₊₁ = C₀Cₙ + C₁Cₙ₋₁ + ⋯ + CₙC₀.

For example, C₄ = C₀C₃ + C₁C₂ + C₂C₁ + C₃C₀ = 5 + 2 + 2 + 5 = 14. MathWorld attributes this recurrence to Segner (1761), in his solution to Euler's problem. It is a convolution, the kind of recurrence that generating functions are designed to solve, and it is not the linear constant-coefficient kind covered in recurrence relations.

The same split works for every Catalan family. A binary tree with n + 1 nodes is a root with a left subtree of k nodes and a right subtree of n − k nodes. A triangulated polygon splits at the triangle containing one fixed edge. Recognising that "first return" decomposition is how you prove a new problem is Catalan.

Growth

The numbers grow roughly like 4ⁿ divided by a power of n: each term is a little under four times the previous one for large n. C₁₀ = 16,796 and C₂₀ = 6,564,120,420. A sequence that more than doubles at each step quickly outpaces brute-force listing, which is why the formula matters.

Recognising a Catalan problem

  1. Compute the first few cases by hand. If you get 1, 2, 5, 14, the Catalan numbers are the prime suspect.
  2. Look for a bijection with bracket strings: what plays the role of "(" and ")"?
  3. Check that your structure splits at a "first return" into two smaller structures of the same kind.

Practice. How many ways can 8 people seated around a round table shake hands in 4 simultaneous pairs with no arms crossing? (C₄ = 14.) How many sequences of 4 pushes and 4 pops on an empty stack never pop from an empty stack? (Also 14.)

Counting problems of this kind belong to the combinatorics unit of Discrete Math: Study & Quiz, and recurrences have a unit of their own. Find it among our education apps, and see the discrete math hub for the counting and graph guides that connect to these structures, including trees.

Good to know

Frequently asked questions

What are the Catalan numbers?
A sequence, 1, 1, 2, 5, 14, 42, 132, 429, …, that counts many recursively built structures: balanced bracket strings, binary trees, polygon triangulations and paths that stay on one side of a diagonal. The nth term is C(2n, n)/(n + 1).
What is the formula for the nth Catalan number?
Cₙ = (1/(n + 1)) · C(2n, n) = (2n)!/((n + 1)! n!). For n = 4: C(8, 4)/5 = 70/5 = 14. An equivalent form is C(2n, n) − C(2n, n + 1), which comes from the reflection principle.
How many ways can a hexagon be divided into triangles?
14. A convex polygon with n + 2 sides can be triangulated by non-crossing diagonals in Cₙ ways, and a hexagon has 6 = 4 + 2 sides, so the answer is C₄ = 14. This is Euler's polygon division problem.
Where do Catalan numbers appear in computer science?
They count the binary trees with n nodes, the ways to fully parenthesise a product of n + 1 factors, the valid sequences of n pushes and n pops on a stack, and the balanced strings of n bracket pairs a parser can accept.

Sources

  1. Catalan Number (opens in a new tab)Wolfram MathWorld — accessed
  2. A000108: Catalan numbers (opens in a new tab)The On-Line Encyclopedia of Integer Sequences (OEIS) — accessed
  3. Binomial Coefficients: Lattice Paths (Discrete Mathematics: An Open Introduction, 3rd edition, Oscar Levin) (opens in a new tab)Open Math Books — accessed

About the author

— The independent app studio that builds the apps covered on this site and publishes every article here. On Google Play it publishes as Reign Collective Apps.

We use AI tools to help research, draft and edit our articles. Each article lists the sources its factual claims rely on, and details about our apps come from their live Google Play listings. No article on this site has been reviewed by an independent expert unless the reviewer is named on it.

No person at Reign Creative LLC has read this article in full. It was published after automated checks and an AI editorial review, which are described in our editorial policy and are not the same as a person reading every sentence.

Spotted an error? Tell us — how corrections are handled is set out in our editorial policy.

Keep reading