Skip to content
Tutorials Center
My learning

Topics

Lesson 26 of 36 ยท Partitions and Catalan Numbers

Catalan Structures

See the Catalan numbers in lattice paths, polygon triangulations, binary trees, stack-sortable permutations and the ballot problem, with the reflection principle and code.

One of the pleasures of combinatorics is finding the same numbers in unrelated problems. The Catalan numbers 1, 1, 2, 5, 14, 42, ... (previous lesson) count many families. Each one fits the recurrence C_n = sum C_i C_{n-1-i} because each has a "first piece plus two smaller pieces" structure. This lesson tours the most important ones and shows the reflection principle, the method behind the closed formula.

Lattice paths below the diagonal

Walk from (0,0) to (n,n) using right and up steps, never going above the line y = x. Each such path is a Dyck path in disguise (right = (, up = )). The total number of paths is binom(2n,n). To count the bad paths (those that touch y = x + 1), reflect the part of the path before its first touching point across that line. This pairs every bad path with a path from (0,0) to (n-1, n+1), and there are binom(2n, n+1) of those. So

good = binom(2n,n) - binom(2n,n+1) = C_n.

Python Brute-force lattice paths and the reflection formula

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

All three lines are 1, 2, 5, 14, 42, 132, 429.

The ballot problem

In an election, candidate A receives a votes and B receives b < a. If the votes are counted in random order, the probability that A is strictly ahead throughout is (a - b)/(a + b). For a = 6, b = 4 this is 0.2. The same reflection argument proves it, and Catalan numbers are the special case where ties are allowed and a = b.

Triangulations of a polygon

How many ways can a convex polygon with n + 2 sides be cut into triangles by non-crossing diagonals? Fix one side. It belongs to exactly one triangle, whose third vertex splits the rest into two smaller polygons. The count is C_n: a triangle (3 sides) has 1, a square 2, a pentagon 5, a hexagon 14.

Binary trees and bracketings

  • The number of binary trees with n nodes (each node has a possibly empty left and right subtree) is C_n. The root splits the other n - 1 nodes into a left and right part: that is the recurrence word for word.
  • The number of full binary trees (every node has 0 or 2 children) with n leaves is C_{n-1}; equivalently the number of ways to fully parenthesize a product of n factors, such as ((ab)c)d versus (ab)(cd).

Stack-sortable permutations

A permutation can be sorted by passing it once through a stack exactly when it avoids the pattern 231 (three entries i < j < k positions with values p_k < p_i < p_j). The number of such permutations of n is C_n.

Python Triangulations, 231-avoiding permutations, full binary trees

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

The triangulation counts start at the triangle: 1, 2, 5, 14, 42, 132, 429, 1430. The 231-avoiders of sizes 1 to 7 are 1, 2, 5, 14, 42, 132, 429, and full binary trees with 1 to 8 leaves give 1, 1, 2, 5, 14, 42, 132, 429.

flowchart TD
    C["Catalan C(n)"] --> P["Dyck paths / balanced parentheses"]
    C --> T["Triangulations of an (n+2)-gon"]
    C --> B["Binary trees with n nodes"]
    C --> F["Full binary trees with n+1 leaves"]
    C --> S["231-avoiding permutations"]
    C --> M["Monotone paths below the diagonal"]

Different objects, one sequence.

How to prove a new family is Catalan

  1. Define a_n clearly and compute the first values by hand or by brute force: 1, 1, 2, 5, 14?
  2. Show the recurrence by splitting on a "first" element into two independent smaller instances; or
  3. Give a bijection to a known family (for example, map a tree to its parenthesization).

Matching the first five terms 1, 2, 5, 14, 42 is evidence, not proof. Always find the decomposition or the bijection.

Check your understanding

Quick check ยท 4 questions

of 4 answered You scored / 4 ยท perfect!

  1. 1. How many ways can a convex hexagon be triangulated?

    A polygon with n + 2 sides has C(n) triangulations; the hexagon has n = 4 and C(4) = 14.
  2. 2. In the reflection principle, bad paths from (0,0) to (n,n) that touch y = x + 1 are counted by...

    Reflecting the initial segment gives a bijection with paths to (n-1, n+1), and there are binom(2n, n+1) of them.
  3. 3. Which permutations of {1..n} are sortable with a single stack?

    A permutation is stack-sortable exactly when it avoids the pattern 231; there are C(n) of them.
  4. 4. In an election A gets 6 votes, B gets 4. What is the chance A is strictly ahead during the entire count?

    The ballot theorem gives (a - b)/(a + b) = 2/10.

Summary

  • Dyck paths, below-diagonal lattice paths, triangulations, binary trees and bracketings, 231-avoiding permutations are all counted by Catalan numbers.
  • The reflection principle gives C_n = binom(2n,n) - binom(2n,n+1); the ballot theorem says A leads throughout with probability (a-b)/(a+b).
  • To recognize a new Catalan family, find the first-piece decomposition or a bijection.

Next: The Pigeonhole Principle