Exploring recursive + closed form solutions to generating Catalan numbers

catalan_numbers.py

"""
Inspired by Problem 3, Lab 09 from Berkeley's CS 61A course to investigate and 
implement the closed form solution via `catalan_nums` function
"""

from math import comb


def num_trees(n):
    """Returns the number of unique full binary trees with exactly n leaves. E.g.,

    1   2        3       3    ...
    *   *        *       *
       / \      / \     / \
      *   *    *   *   *   *
              / \         / \
             *   *       *   *

    >>> num_trees(1)
    1
    >>> num_trees(2)
    1
    >>> num_trees(3)
    2
    >>> num_trees(8)
    429
    """
    if n == 1:
        return 1
    result = 0
    for k in range(1, n):
        result += num_trees(n - k) * num_trees(k)
    return result


def catalan_nums(n: int) -> int:
    """
    Closed-form alternative to the problem presented in `num_trees`

    Helpful bijective proof: https://en.wikipedia.org/wiki/Catalan_number#Second_proof

    >>> num_trees(1)
    1
    >>> num_trees(2)
    1
    >>> num_trees(3)
    2
    >>> num_trees(4)
    5
    >>> num_trees(5)
    14
    >>> num_trees(6)
    42
    >>> num_trees(7)
    132
    >>> num_trees(8)
    429
    """
    # Count all monotonically increasing Manhattan paths on n x n grid
    # and subtract out "bad" paths that cross the diagonal; bijection exists
    # between "bad" paths and monotonically increasing Manhattan paths on
    # (n - 1) x (n + 1) grid!
    return comb(2 * n, n) - comb(2 * n, n - 1)

Note that subtracting out the "bad paths" (after reflection across the "higher diagonal") yields:

$$ \binom{(n + 1) + (n - 1)}{n-1} = \binom{2n}{n-1} = \binom{2n}{n+1} $$

Interestingly, the length of the returned list of numbers of the solution (see example below) to Leetcode 241. Different Ways to Add Parentheses:

Different Ways to Add Parentheses | Python

from functools import cache
from operator import add, sub, mul
import itertools as it


class Solution:

    OPERATORS = {"+": add, "-": sub, "*": mul}

    @cache
    def diffWaysToCompute(self, expression: str) -> List[int]:
        operator_indices = [i for i, c in enumerate(expression) if c in self.OPERATORS]
        if not operator_indices:
            return [int(expression)]
        result = []
        for i in operator_indices:
            f = self.OPERATORS[expression[i]]
            left_results, right_results = self.diffWaysToCompute(expression[:i]), self.diffWaysToCompute(expression[i+1:])
            result.extend([f(*operands) for operands in it.product(left_results, right_results)])
        return result