PYTHON

Catalan number

"""
This implementation demonstrates how
to efficiently calculate the nth
Catalan number. For instance, 
the nth catalan number gives the 
number of unique binary search trees 
which has exactly n nodes of unique values
between 1 and n.

Let us denote it by Cn:
C0 = 1 and Cn+1 = 2(2n+1)Cn/(n+2)

More info at:
https://en.wikipedia.org/wiki/Catalan_number

Time complexity: O(n)
Space complexity: O(1)
"""


def C_n(n):
    C = 1
    for i in range(0, n):
        C = C * 2*(2*i+1)/(i+2)
    return int(C)


print("C1 =", C_n(1))  # C1 = 1
print("C3 =", C_n(3))  # C3 = 5