# 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)

## Leave a Reply

You must be logged in to post a comment.