Finding n-th Catalan number with Python.

Catalan numbers use case.


There are special numbers in combinatorial mathematics named after the French-Belgian mathematician Eugène Charles Catalan who studied the Towers of Hanoi puzzle.

The Catalan numbers are a sequence of natural numbers that usually describe recursively defined objects and calculated by formula:

Cn = ( ( 2n! ) / ( (n+1)! n! ) ) , where n is always non-negative.

Catalan numbers.



An example for the first Catalan numbers for n = 0, 1, 2, 3, 4, 5 are 1, 1, 2, 5, 14, 42.

Today’s practical use cases of the Catalan numbers lay in the fields of computer science, geometry, GIS and geodesy, cryptography, and medicine.


A recursive function to find n-th Catalan number with Python code:




def catalan(n):
   
    if n <= 1:
        return 1
 
    res = 0
    for i in range(n):
        res += catalan(i) * catalan(n-i-1)
 
    return res
 
 
# Check
N=6
for i in range(N):
    print (catalan(i),end=",")

OUT: 1,1,2,5,14,42,





See also related topics: