Published: Sep 9, 2019
What is Catalan number ?
The Catalan number belongs to the domain of combinatorial mathematics.
It is a sequence of natural numbers such that:
1, 1, 2, 5, 14, 42, 132, 429, 1430, 4862, 16796, 58786, 208012, 742900, 2674440, 9694845, 35357670, 129644790, 477638700, 1767263190, ...
The sequence appears in counting problems.
Wikipedia has the details about the sequence: Catalan Number.
The algorithm of the Catalan number calculation is not difficult. Once the problem is identified as the Catalan number, the solution will come up relatively easy. However, something not easy is to identify it is the Catalan number problem.
Various types of counting problems
The Wikipedia article mentions various types of counting problems which are solved by the Catalan number. One more great resource is “Catalan Numbers” (http://www.geometer.org/mathcircles/catalan.pdf). The document refers to multiple counting problems as well as how to solve those. For a reference, it’s worth writing a memo what kind of problems are out there.
-
Balanced parentheses
Problem: Given
n
pairs of parentheses, how many patterns exist to create valid (balanced) combinations of parentheses.Example:
n counts patterns 0 1 * 1 1 () 2 2 (()) ()() 3 5 ((())) ()(()) ()()() (())() (()())
Note: This is a basic pattern of the Catalan number.
-
Dyck words
Problem: Given
n
, how many patterns exist to create words of n Xs and n Ys such that in every prefix of the word frequency(‘X’) ≥ frequency(‘Y’)Example:
n counts patterns 0 1 * 1 1 XY 2 2 XXYY XYXY 3 5 XXXYYY XYXXYY XYXYXY XXYYXY XXYXYY
Note: If X and Y are mapped ( and ) respectively, the problem is the same as the balanced parentheses.
-
Mountain Ranges
Problem: Given
n
pairs of sticks, how many patterns exist to create mountains.n counts patterns 0 1 * 1 1 /\ 2 2 /\ / \ /\/\ 3 5 /\ / \ /\ /\ /\/\ / \ /\/ \ /\/\/\ / \/\ / \
Note: If / and \ are mapped to ( and ) respectively, the problem is the same as the balanced parentheses.
-
Binary Search Trees
Problem: Given
n
, how many unique binary search tress exist to create node value1 to n
.Example:
n counts patterns 0 1 * 1 1 1 2 2 2 1 / \ 1 2 3 5 3 3 2 1 1 / / / \ \ \ 2 1 1 3 3 2 / \ / \ 1 2 2 3
-
Diagonal Paths
Problem: Given
n x n
grid, how many paths of length2n
exist from bottom left to upper right corner.Example:
n counts patterns 0 1 * 1 1 ↑ → 2 2 ↑ ↑ ↑ ↑ → → → → 3 5 ↑ ↑ ↑ ↑ ↑ ↑ ↑ ↑ → ↑ → ↑ ↑ ↑ → → ↑ → ↑ ↑ → → → → → → → → → →
Note: If → and ↑ are mapped to ( and ), the problem is the same as the balanced parentheses.
-
Multiplication orderings
Problem: Given
n+1
numbers to multiply together, how many patterns exist to make multiplication precedences without changing the order of numbers.Example:
n counts patterns 0 1 (a) 1 1 (ab) 2 2 ((ab)c) (a(bc)) 3 5 (((ab)c)d) ((ab)(cd)) ((a(bc))d) (a((bc)d)) (a(b(cd)))
-
Polygon Triangulation
Problem: Given
n+2
sides of convex polygon, how many patterns exist to cut into triangles of non-crossing line segments. -
Handshaking
Problem: Given
2n
people seated around the round table, how many patterns exists to shake hands without crossing arms.
Code Example
For all problems above, the number of patterns can be found the code below:
The first numPatterns
method runs faster if the problem asks only one number such as:
- leetcode: Unique Binary Search Trees
- topcoder: Hands Shaking
However, when problem asks accumulation of patterns such as:
- HackerRank: Popsicle Stick Mountains
the second DP solution works to avoid repetition.
Resources
- Wikipedia: Catalan number
- Tom Davis: Catalan Numbers
- GeeksforGeeks: Program for nth Catalan Number