C program for the nth Catalan number

Given an integer n; the task is to find the Catalan number at the nth position. Therefore, before executing the program, we must know what Catalan numbers are?

Catalan numbers are a sequence of natural numbers that appear in various forms of counting problems.

Catalan numbers C0, C1, C2,... Cn is driven by the formula-

$$c_ {n} = \frac {1} {n + 1} \binom {2n} {n} = \frac {2n!} { (n + 1）!n!} $$

For n = 0,1,2,3, the Catalan number of ... is1,1,2,5,14,42,132,429,1430,4862 ...

Therefore, if we input n = 3We should get from the program5As output

Some applications of Catalan numbers-

• Calculate the number of possible binary search trees using n keys.

• Find the number of expressions containing n pairs of correctly matched brackets. 3Likewise, possible bracket expressions are ((()))(), ()(()), ()()(), (()()), (()()).

• Find methods to connect points on chords that do not intersect in a circle, etc.

Example

Input: n =　6
Output:　132
Input: n =　8
Output:　1430

The method we will use to solve the given problem-

• Take and input n.

• Check n <= 1Then return1

• Loop from i = 0 to i < n and i ++

• For each i Set result = result+（catalan(i)* catalan(ni-1)）

• Return and print the result.

Algorithm

Start
　　　Step　1　-> In function unsigned long int catalan(unsigned int n)
　　　　　　If n <=　1　then,
　　　　　　　　　Return　1
　　　　　　End if
　　　　　　Declare an unsigned long variable res = 0
　　　　　　Loop For i=0 and i<n and i++
　　　　　　　　　Set res = res　+　(catalan(i)*catalan(n-i-1))
　　　　　　End Loop
　　　　　　Return res
　　　Step　2　-> int main() Declare an input n =　6
　　　Print "catalan is: then call function catalan(n)
Stop

Example

#include <stdio.h>
//Use recursive method to find Catalan number
unsigned long int catalan(unsigned int n) {
　　　//Basic Case
　　　if (n <=　1) return　1;
　　　//Catalan language (n) is Catalan language (i)*Catalan language (ni-1) Sum
　　　unsigned long int res = 0;
　　　for (int i = 0; i < n; i++)
　　　　　　res　+= catalan(i)*catalan(n-i-1);
　　　return res;
}
//Main Function
int main() {
　　　int n =　6;
　　　printf("catalan is :%ld\n", catalan(n));
　　　return 0;
}

Output Result

catalan is :132