Created
November 3, 2022 03:35
-
-
Save Per48edjes/45e3ae1bba003895cf95d52ce986730b to your computer and use it in GitHub Desktop.
Exploring recursive + closed form solutions to generating Catalan numbers
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
""" | |
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) |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment
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