Program to find nth Catalan Number in Python

In this tutorial, you will learn about how to find the nth Catalan Number in Python in an easy way. First, we have to know about the Catalan numbers.

Catalan numbers:
The Catalan numbers are the special sequence of positive integers. They appear in various counting problems. The Catalan numbers for n=0, 1, 2, 3, … are 1, 1, 2, 5, 14, 42, 132, 429, …

We can find the nth Catalan number using the Recursive solution and the Binomial coefficient methods.

Method 1: Recursive Solution

Formula:

Catalan Numbers satisfy the following Recursive formula.

The following is the implementation of the above recursive formula.

def catalan(no): 
    if no<= 1 : 
        return 1 
    re=0
    for x in range(no): 
        re += catalan(x) * catalan(no-x-1) 
    return re
no=int(input("Enter the number:"))
an=catalan(no)
print("Catalan number is",an)

Input:

Enter the number:7

Output:

Catalan number is 429

Time Complexity:

• The Time complexity of the above implementation is equivalent to nth Catalan Number. The value of the nth Catalan Number is exponential.
• So, that makes time complexity exponential.

Method 2: Using Binomial Coefficient

We can also use the below formula to find the nth Catalan number.

Formula:

The following is the implementation of the above formula.

def binomialCoeff(no, k): 
    if (k >no - k): 
        k = no - k  
    res = 1
    for x in range(k): 
        res = res * (no - x) 
        res = res / (x + 1) 
    return res 
def catalanNum(no): 
    co = binomialCoeff(2*no, no) 
    return int(co/(no + 1)) 
no=int(input("Enter the number:"))
print("Catalan number:",catalanNum(no))

Input:

Enter the number:7

Output:

Catalan number: 429

Time Complexity:

The Time complexity of the above implementation is O(n).

Also read: Catalan Number in Python – Iterative Approach (Factorial)