CASE STUDY

Catalan Numbers
Counting Structures via Dynamic Programming

Algorithm Design & Analysis

Paradigm: Dynamic Programming / Combinatorics
2025 – 2026 Academic Year

Naveed Shaikh
Class D6ADA
Roll No. 54
1. Algorithm Selection

1.1 Algorithm Name

Catalan Numbers — a sequence of natural numbers arising from a recursive combinatorial formula, named
after the Belgian mathematician Eugène Charles Catalan (1814–1894). The sequence begins: 1, 1, 2, 5, 14, 42,
132, 429, …

1.2 Algorithmic Paradigm

Paradigm Classification
Catalan Numbers are computed using Dynamic Programming — the nth Catalan number is built from
previously computed values C(0) through C(n-1), avoiding redundant sub-problem recomputation. The
combinatorial formula also places it in the Divide and Conquer family when expressed recursively.

1.3 The Formula

Recursive: C(0) = 1
C(n) = SUM of C(i) * C(n-1-i) for i = 0 to n-1

Closed-form: C(n) = (2n)! / ((n+1)! * n!)

Recurrence: C(n) = C(n-1) * 2*(2n-1) / (n+1)

1.4 Problem Statement

Given a non-negative integer n, compute the nth Catalan number C(n), which counts the number of distinct
ways a combinatorial structure of size n can be arranged — such as valid bracket sequences, binary search
trees, triangulated polygons, and mountain ranges.
2. Algorithm Mechanics

2.1 Core Concepts

Concept Definition

C(n) The nth Catalan number — count of valid structures of size n

Sub-problem C(i) for each i < n, stored in a DP table
Overlapping Sub-problems C(n) reuses C(0)…C(n-1), the core reason DP is used
Optimal Substructure C(n) is exactly defined by a sum of products of smaller Cn values
Memoisation Bottom-up DP table prevents recomputing the same C(i) twice

2.2 Dynamic Programming Steps

The bottom-up DP approach to computing the nth Catalan number:
• Create a DP array of size n+1 and initialise dp[0] = 1, dp[1] = 1.
• For each i from 2 to n, compute dp[i] by summing dp[j] * dp[i-1-j] for all j from 0 to i-1.
• Each dp[i] is computed exactly once and stored for reuse.
• Return dp[n] as the final answer.

2.3 Pseudocode

CATALAN-DP(n):
dp[0] = 1
dp[1] = 1

for i = 2 to n:
dp[i] = 0
for j = 0 to i-1:
dp[i] += dp[j] * dp[i-1-j]

return dp[n]

// Closed-form alternative:
CATALAN-FORMULA(n):
return (2n)! / ((n+1)! * n!)
2.4 Step-by-Step Numerical Example — Compute C(4) = 14
We build the DP table from C(0) up to C(4):
Building the DP Table

Step Computing Calculation dp[i]

Init dp[0] Base case 1

Init dp[1] Base case 1
i=2 dp[2] dp[0]*dp[1] + dp[1]*dp[0] = 1+1 2
i=3 dp[3] dp[0]*dp[2] + dp[1]*dp[1] + dp[2]*dp[0] = 2+1+2 5
i=4 dp[4] dp[0]*dp[3]+dp[1]*dp[2]+dp[2]*dp[1]+dp[3]*dp[0] = 14
5+2+2+5

Verification — C(4) counts valid bracket sequences of length 8

All 14 valid bracket sequences with 4 pairs:

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

(()())() (())(()) (())()() ()((())) ()(()())
()(())() ()()(()) ()()()() (()()(()) ...

Count = 14 ✓ matches dp[4]

2.5 Catalan Numbers — Quick Reference Table

n C(n) Example Structure Counted

0 1 Empty structure
1 1 Single element
2 2 2 valid bracket pairs: ()() and (())
3 5 5 BSTs with 3 nodes; 5 bracket sequences
4 14 14 triangulations of a hexagon
5 42 42 ways to parenthesise 6 factors
6 132 132 monotonic lattice paths
10 16796 16796 full binary trees with 11 leaves

2.6 Time & Space Complexity

 Method Time Complexity Space Complexity Notes

Naive Recursion O(3ⁿ) exponential O(n) stack Re-computes sub-problems;

impractical
DP (Bottom-Up) O(n²) O(n) Optimal for general computation
Closed-Form Formula O(n) O(1) Fastest; requires big-integer
arithmetic for large n
Recurrence Formula O(n) O(n) or O(1) Simple loop; preferred in
competitive programming

The Dynamic Programming approach at O(n²) time and O(n) space is the standard recommended method for
general-purpose computation of Catalan numbers, balancing clarity, correctness, and efficiency.
3. Real-Time Application

3.1 Chosen Scenario: SQL Query Optimisation in Database Engines

Real-World Context
Modern relational database engines (MySQL, PostgreSQL, Oracle, SQL Server) must decide the optimal
ORDER in which to JOIN multiple tables. For a query joining n tables, there are C(n-1) distinct binary tree
structures for the join order — and the database query optimiser uses Catalan number-driven DP to
enumerate and evaluate all of them.

3.2 The Problem: Join Order Enumeration

When a SQL query joins n tables, the database must determine which two tables to join first, then which
result to join next, and so on. Each different ordering produces a different execution plan with drastically
different performance characteristics.
The number of distinct left-deep binary trees for n tables equals C(n-1) — the (n-1)th Catalan number. For just
5 tables, that is C(4) = 14 possible join orderings to evaluate.

3.3 Concept Mapping

Database Concept Catalan / DP Mapping

Database table Leaf node in a binary join tree

JOIN operation Internal node combining two sub-results
Join order / plan A specific binary tree structure
Number of possible plans C(n-1) — the (n-1)th Catalan number
Cost of a join plan Estimated rows processed (selectivity × cardinality)
DP sub-problem Optimal join cost for a subset S of tables
Optimal overall plan Minimum-cost binary tree — found bottom-up via DP

3.4 Step-by-Step — Query Optimiser with 4 Tables

Consider the query: SELECT * FROM A JOIN B JOIN C JOIN D
Number of join orderings = C(3) = 5. The optimiser evaluates all 5 binary tree shapes:

((A⋈B)⋈C)⋈D (A⋈(B⋈C))⋈D (A⋈B)⋈(C⋈D)

A⋈((B⋈C)⋈D) A⋈(B⋈(C⋈D))
Plan 1: Plan 2: Plan 3:
Plan 4: Plan 5:
 DP builds optimal cost bottom-up:
dp[{A,B}] = cost of best way to join A and B
dp[{B,C}] = cost of best way to join B and C ...etc.
dp[{A,B,C}] = min( dp[{A,B}]+join(C), dp[{B,C}]+join(A), dp[{A,C}]
+join(B) )
dp[{A,B,C,D}] = best plan across all 14 sub-combinations

Join Subset Plans Considered DP Sub-problem Solved

Size 2 pairs C(1)=1 each × 6 pairs = 6 dp[{A,B}], dp[{A,C}], dp[{A,D}], dp[{B,C}], dp[{B,D}],
dp[{C,D}]
Size 3 triples C(2)=2 each × 4 triples = 8 dp[{A,B,C}], dp[{A,B,D}], dp[{A,C,D}], dp[{B,C,D}]
Full query C(3)=5 × 1 = 5 dp[{A,B,C,D}] — final optimal plan

3.5 Why Catalan DP Over Alternatives?

Approach Strategy Limitation Catalan DP Advantage

Greedy (left-deep Always join smallest Misses globally optimal Evaluates ALL C(n-1)
always) tables first plans structures; finds true
optimum
Exhaustive brute force Try all n! orderings n! grows far faster than C(n-1) ≪ n!; DP avoids re-
C(n) evaluating shared sub-plans
Heuristic / genetic Randomised search No optimality guarantee DP guarantees the minimum-
cost plan
Rule-based Fixed join templates Inflexible to data DP adapts to actual table
distributions statistics at runtime

3.6 Other Industry Applications of Catalan Numbers

• Compiler Design: Counting the number of distinct parse trees for an ambiguous grammar (Dyck
paths).
• Computer Graphics: Triangulating convex polygons for mesh generation — C(n-2) ways for an n-gon.
• AI / Game Trees: Counting full binary game trees for minimax search space analysis.
• Stock Market Analysis: Counting monotonic paths that never cross a diagonal — models restricted
price sequences.
• RNA Secondary Structure Prediction: Counting non-crossing base-pair matchings in a nucleotide
sequence.
• Network Design: Counting hierarchical branching topologies in tree-structured networks.
4. Summary & Conclusion

Attribute Detail

Algorithm Name Catalan Numbers (Dynamic Programming computation)

Paradigm Dynamic Programming + Combinatorics
Core Formula C(n) = Σ C(i)·C(n-1-i) for i=0..n-1; Closed: (2n)!/((n+1)!·n!)
DP Time Complexity O(n²) — bottom-up table
DP Space Complexity O(n)
Closed-form Complexity O(n) time, O(1) space
Sequence 1, 1, 2, 5, 14, 42, 132, 429, 1430, 4862 …
Primary Application SQL Query Optimiser — optimal join-order planning
Other Applications Compiler parsing, polygon triangulation, RNA folding, game trees

Catalan numbers are one of the most frequently appearing sequences in combinatorics and computer
science. Their elegant recursive structure makes them a perfect candidate for Dynamic Programming — each
value is built cheaply from previously solved sub-problems, achieving polynomial time where naive recursion
would be exponential.
In the real world, the impact of Catalan numbers is most visible in database query optimisers, where
computing the optimal join order among n tables — a problem with C(n-1) possible structures — is solved
efficiently using the same DP recurrence taught in algorithm courses. Systems like PostgreSQL's planner and
Oracle's Cost-Based Optimiser owe their performance to this elegant mathematical foundation.
Understanding Catalan numbers builds deep intuition for recursion, memoisation, and combinatorial counting
— skills that underpin a wide range of problems in algorithms, programming language theory, and systems
design.

References
Catalan, E. C. (1838). Note sur une équation aux différences finies. Journal de Mathématiques Pures et Appliquées, 3, 508–516.
Cormen, T. H. et al. (2009). Introduction to Algorithms (3rd ed.). MIT Press. Chapter 15 — Dynamic Programming.
Selinger, P. G. et al. (1979). Access Path Selection in a Relational Database Management System. ACM SIGMOD.
Stanley, R. P. (2015). Catalan Numbers. Cambridge University Press.