Catalan Numbers

Formula

The n-th Catalan number is given by:

Cn = (2n)! / ((n + 1)! * n!)

Applications of Catalan Numbers

• Valid Parentheses
  Number of valid parentheses expressions with n pairs.

• Binary Search Trees
  Number of unique BSTs that can be formed using values 1..n.

• Binary Tree Structures
  Number of different full binary trees with n internal nodes.

• Stack Permutations
  Number of valid pop sequences from a stack with n push operations.

• Polygon Triangulation
  Number of ways to triangulate a convex polygon with (n + 2) sides.

• Matrix Chain Parenthesization
  Number of valid ways to parenthesize matrix multiplication.

• Dyck Paths / Mountain Ranges
  Number of paths from (0,0) to (n,n) that never cross the diagonal.

How to Identify a Catalan Problem

• Problem involves pairs of elements.
• Structure must be balanced or well-formed.
• Order matters, but invalid arrangements are disallowed.
• Early closing or crossing is not allowed.
• Problem can be divided into left and right independent subproblems.

Catalan Recurrence Relation (DP)

Base case:

C₀ = 1

Recurrence:

Cn = Σ (Ci * Cn-1-i) for i = 0 to n-1

Useful when:

• Dynamic programming is required.
• Results must be computed under modulo.
• Actual structures need to be generated.

Choosing the Right Approach

• Use formula: When only the count is required.
• Use DP: When constraints are large or modulo is involved.
• Use backtracking: When generating all valid structures.

Example: Generating Permutations (Backtracking)

GeeksforGeeks: Generate permutations of an array

def permuteDist(self, arr):
    res = []
    def backtrack(path, remaining):
        if not remaining:
            res.append(path)
            return
        for i in range(len(remaining)):
            backtrack(path + [remaining[i]], remaining[:i] + remaining[i+1:])
    backtrack([], arr)
    return res
    # return [list(p) for p in permutations(arr)]