Python - nth Catalan Number

Python – nth Catalan Number

The nth Catalan number is an important sequence in combinatorial mathematics that appears in various counting problems. It is defined recursively by:

C(0) = 1

C(n) = Σ (C(i) * C(n-1-i)) for 0 ≤ i ≤ n-1

This tutorial demonstrates how to compute the nth Catalan number using Dynamic Programming in Python. We will discuss the problem, provide sample inputs and outputs, and present two dynamic programming approaches with detailed explanations.

Problem Statement

Given a non-negative integer n, compute the nth Catalan number using the recurrence relation:

C(n) = Σ (C(i) * C(n-1-i)) for 0 ≤ i ≤ n-1, with C(0) = 1

This value counts the number of ways to correctly match parentheses, form binary search trees, and solve many other combinatorial problems.

Sample Input and Output

Example 1:

</>

Copy

# Input:
n = 4

# Calculation:
# C(4) = C(0)*C(3) + C(1)*C(2) + C(2)*C(1) + C(3)*C(0)
# Using known values: C(0)=1, C(1)=1, C(2)=2, C(3)=5
# C(4) = 1*5 + 1*2 + 2*1 + 5*1 = 5 + 2 + 2 + 5 = 14

# Output:
14

Explanation: For n = 4, the computation involves summing up the products of pairs of Catalan numbers that partition the problem. This results in C(4) = 14, indicating there are 14 ways to arrange the structure defined by the problem.

Example 2:

</>

Copy

# Input:
n = 6

# Calculation:
# C(6) = C(0)*C(5) + C(1)*C(4) + C(2)*C(3) + C(3)*C(2) + C(4)*C(1) + C(5)*C(0)
# Using known values: C(0)=1, C(1)=1, C(2)=2, C(3)=5, C(4)=14, C(5)=42
# C(6) = 1*42 + 1*14 + 2*5 + 5*2 + 14*1 + 42*1 
#      = 42 + 14 + 10 + 10 + 14 + 42 = 132

# Output:
132

Explanation: For n = 6, we break down the problem into subproblems by summing the products of Catalan numbers computed for smaller indices. This process results in C(6) = 132, which represents the number of valid configurations for the problem.

Solution Approach

To solve for the nth Catalan number efficiently, we can use dynamic programming to store and reuse previously computed values. We will explore two approaches:

Recursive Approach with Memoization: Recursively compute the Catalan numbers and cache results to avoid redundant calculations.
Iterative Dynamic Programming: Build a DP table in a bottom-up manner to compute the Catalan number.

Python Program

Method 1: Recursive Approach with Memoization

</>

Copy

def catalan_recursive(n, memo=None):
    """
    Compute the nth Catalan number using recursion with memoization.
    
    Parameters:
    n (int): The Catalan number to compute.
    memo (dict): Cache for storing computed Catalan numbers.
    
    Returns:
    int: The nth Catalan number.
    """
    if memo is None:
        memo = {}
        
    # Base case: C(0) and C(1) are 1
    if n <= 1:
        return 1
    
    # Return cached value if available
    if n in memo:
        return memo[n]
    
    catalan = 0
    # Recurrence: C(n) = Σ (C(i) * C(n-1-i)) for 0 ≤ i < n
    for i in range(n):
        catalan += catalan_recursive(i, memo) * catalan_recursive(n - 1 - i, memo)
    
    memo[n] = catalan
    return catalan

# Test examples
print("Method 1 - Recursive with Memoization")
print("Catalan(4):", catalan_recursive(4))   # Expected output: 14
print("Catalan(6):", catalan_recursive(6))   # Expected output: 132

Explanation: This method leverages recursion to break the problem into smaller subproblems, using a dictionary to store intermediate results. By caching the values, we avoid recalculating the same Catalan numbers multiple times, improving performance significantly.

Method 2: Iterative Dynamic Programming

</>

Copy

def catalan_iterative(n):
    """
    Compute the nth Catalan number using an iterative dynamic programming approach.
    
    Parameters:
    n (int): The Catalan number to compute.
    
    Returns:
    int: The nth Catalan number.
    """
    # Create a DP array to store Catalan numbers from 0 to n
    dp = [0] * (n + 1)
    dp[0] = 1  # Base case: C(0) = 1
    
    # Compute Catalan numbers from 1 to n using the recurrence relation
    for i in range(1, n + 1):
        dp[i] = 0
        for j in range(i):
            dp[i] += dp[j] * dp[i - 1 - j]
    
    return dp[n]

# Test examples
print("\nMethod 2 - Iterative Dynamic Programming")
print("Catalan(4):", catalan_iterative(4))   # Expected output: 14
print("Catalan(6):", catalan_iterative(6))   # Expected output: 132

Explanation: This iterative method initializes a list dp where each element dp[i] represents the ith Catalan number. We fill the array in a bottom-up manner using the recurrence relation. This approach is efficient and easy to understand, making it ideal for dynamic programming problems in interviews.

Conclusion

In this tutorial, we explored two dynamic programming approaches to compute the nth Catalan number:

Recursive with Memoization: Uses recursion and caching to efficiently compute Catalan numbers.
Iterative Dynamic Programming: Builds a DP table in a bottom-up fashion, providing a clear and efficient solution.

Both methods are effective for solving the problem and can be used based on the constraints of your DSA interview or application requirements.

TutorialKart

Python – nth Catalan Number