Catalan Numbers

Catalan numbers form a sequence of natural numbers that occur in various counting problems.
Series is
1, 1, 2, 5, 14, 42, 132, 429, 1430, 4862, 16796, 58786, 208012, 742900, 2674440, 9694845, 35357670, 129644790, 477638700, 1767263190, 6564120420, 24466267020, 91482563640, 343059613650, 1289904147324, 4861946401452…. and so on.
Application

This sequence is very popular in many combinatorial problems.  More on application of Catalan Numbers here

Formula

The nth Catalan number is given directly in terms of binomial coefficients by

Cn = 2nCn/(n+1) = 2n!/{(n+1)!n!}

we can also use this formula
C0 = 1
Cn = Cn-1*(4n-2)/(n+1)


cat=[]

#1st term is 1
cat.append(1)

for i in range (1,1001):
    x=cat[i-1]*(4*i-2)/(i+1)
    cat.append(x)


def CatalanNumber(n):
    return cat[n]

Advertisements