Posted on by Kalkicode
Code Number

# Find nth Catalan Number

The Catalan numbers are a sequence of natural numbers that have many applications in combinatorial mathematics. They are named after the French-Belgian mathematician Eugène Charles Catalan. The nth Catalan number, denoted as Cn, represents the number of different ways n + 1 factors can be uniquely parenthesized. Catalan numbers also appear in various other combinatorial problems, such as counting valid expressions with balanced parentheses, triangulating polygons, and counting different types of binary trees.

## Problem Statement

Given an integer n, the task is to find the nth Catalan number Cn.

## Explanation with Suitable Example

Let's take the example of n = 3. We need to find the 3rd Catalan number, which represents the number of ways three factors can be uniquely parenthesized. The factors are (A * B) * C, A * (B * C), and (A * B * C). There are three unique ways to parenthesize the factors, so the 3rd Catalan number (C3) is 5.

## Standard Pseudocode

The algorithm to find the nth Catalan number can be implemented as follows:

``````1. Define a function nthCatalanNumber(n) to calculate the nth Catalan number.
2. If n <= 0, return.
3. Initialize a variable m = (n - 1) * 2.
4. Initialize a variable result = 1.
5. Loop from i = 0 to n - 1:
a. Update result = result * (m - i).
b. Update result = result / (i + 1).
6. Update result = result / n.
7. Display the calculated result.
``````

## Algorithm Explanation

1. The function nthCatalanNumber(n) is defined to calculate the nth Catalan number. If n is less than or equal to 0, there is no valid Catalan number for negative values, and hence, we return without any further computation.
2. We initialize a variable m as (n - 1) * 2. This is because the nth Catalan number can be expressed using the binomial coefficient formula as (2n)! / [(n + 1)! * n!], which simplifies to (2n * (2n - 1) * ... * (n + 1)) / (n!). The variable m helps us calculate the numerator part of the binomial coefficient.
3. We initialize a variable result to store the calculated Catalan number.
4. Using a loop, we calculate the binomial coefficient iteratively. The loop runs from i = 0 to n - 1. In each iteration, we multiply the result by (m - i) and then divide it by (i + 1). This effectively calculates the binomial coefficient.
5. After the loop, we have the binomial coefficient of (2n * (2n - 1) * ... * (n + 1)), so we divide it by n to get the nth Catalan number.
6. Finally, we display the calculated Catalan number for the given value of n.

## Code Solution

Here given code implementation process.

``````// C Program for
// Find nth Catalan Number
#include <stdio.h>

void nthCatalanNumber(int n)
{
if (n <= 0)
{
return;
}
int m = (n - 1) *2;
unsigned long result = 1;
// Binomial coefficient and find catalan number
for (int i = 0; i < n - 1; ++i)
{
result = result *(m - i);
result = result / (i + 1);
}
result = result / n;
// Display calculated result
printf("\n %d-th Catalan Number Is : %ld", n, result);
}
int main()
{
//  Catalan Number
//  --------------
//  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 .....
// Test
nthCatalanNumber(10);
nthCatalanNumber(7);
nthCatalanNumber(12);
return 0;
}``````

#### Output

`````` 10-th Catalan Number Is : 4862
7-th Catalan Number Is : 132
12-th Catalan Number Is : 58786``````
``````// Java program for
// Find nth Catalan Number
public class CatalanNumber
{
public void nthCatalanNumber(int n)
{
if (n <= 0)
{
return;
}
int m = (n - 1) * 2;
long result = 1;
// Binomial coefficient and find catalan number
for (int i = 0; i < n - 1; ++i)
{
result = result * (m - i);
result = result / (i + 1);
}
result = result / n;
// Display calculated result
System.out.print("\n " + n + "-th Catalan Number Is : " + result);
}
public static void main(String[] args)
{
//  Catalan Number
//  --------------
//  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 ..... etc
// Test
}
}``````

#### Output

`````` 10-th Catalan Number Is : 4862
7-th Catalan Number Is : 132
12-th Catalan Number Is : 58786``````
``````// Include header file
#include <iostream>
using namespace std;

// C++ program for
// Find nth Catalan Number

class CatalanNumber
{
public: void nthCatalanNumber(int n)
{
if (n <= 0)
{
return;
}
int m = (n - 1) *2;
long result = 1;
// Binomial coefficient and find catalan number
for (int i = 0; i < n - 1; ++i)
{
result = result *(m - i);
result = result / (i + 1);
}
result = result / n;
// Display calculated result
cout << "\n " << n << "-th Catalan Number Is : " << result;
}
};
int main()
{
//  Catalan Number
//  --------------
//  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 ..... etc
// Test
return 0;
}``````

#### Output

`````` 10-th Catalan Number Is : 4862
7-th Catalan Number Is : 132
12-th Catalan Number Is : 58786``````
``````// Include namespace system
using System;
// Csharp program for
// Find nth Catalan Number
public class CatalanNumber
{
public void nthCatalanNumber(int n)
{
if (n <= 0)
{
return;
}
int m = (n - 1) * 2;
long result = 1;
// Binomial coefficient and find catalan number
for (int i = 0; i < n - 1; ++i)
{
result = result * (m - i);
result = result / (i + 1);
}
result = result / n;
// Display calculated result
Console.Write("\n " + n + "-th Catalan Number Is : " + result);
}
public static void Main(String[] args)
{
//  Catalan Number
//  --------------
//  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 ..... etc
// Test
}
}``````

#### Output

`````` 10-th Catalan Number Is : 4862
7-th Catalan Number Is : 132
12-th Catalan Number Is : 58786``````
``````package main
import "fmt"
// Go program for
// Find nth Catalan Number

func nthCatalanNumber(n int) {
if n <= 0 {
return
}
var m int = (n - 1) * 2
var result int = 1
// Binomial coefficient and find catalan number
for i := 0 ; i < n - 1 ; i++ {
result = result * (m - i)
result = result / (i + 1)
}
result = result / n
// Display calculated result
fmt.Print("\n ", n, "-th Catalan Number Is : ", result)
}
func main() {

//  Catalan Number
//  --------------
//  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 ..... etc
// Test
nthCatalanNumber(10)
nthCatalanNumber(7)
nthCatalanNumber(12)
}``````

#### Output

`````` 10-th Catalan Number Is : 4862
7-th Catalan Number Is : 132
12-th Catalan Number Is : 58786``````
``````<?php
// Php program for
// Find nth Catalan Number
class CatalanNumber
{
public	function nthCatalanNumber(\$n)
{
if (\$n <= 0)
{
return;
}
\$m = (\$n - 1) * 2;
\$result = 1;
// Binomial coefficient and find catalan number
for (\$i = 0; \$i < \$n - 1; ++\$i)
{
\$result = \$result * (\$m - \$i);
\$result = \$result / (\$i + 1);
}
\$result = \$result / \$n;
// Display calculated result
echo("\n ".\$n.
"-th Catalan Number Is : ".\$result);
}
}

function main()
{
//  Catalan Number
//  --------------
//  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 ..... etc
// Test
}
main();``````

#### Output

`````` 10-th Catalan Number Is : 4862
7-th Catalan Number Is : 132
12-th Catalan Number Is : 58786``````
``````// Node JS program for
// Find nth Catalan Number
class CatalanNumber
{
nthCatalanNumber(n)
{
if (n <= 0)
{
return;
}
var m = (n - 1) * 2;
var result = 1;
// Binomial coefficient and find catalan number
for (var i = 0; i < n - 1; ++i)
{
result = result * (m - i);
result = result / (i + 1);
}
result = result / n;
// Display calculated result
process.stdout.write("\n " +
n + "-th Catalan Number Is : " + result);
}
}

function main()
{
//  Catalan Number
//  --------------
//  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 ..... etc
// Test
}
main();``````

#### Output

`````` 10-th Catalan Number Is : 4862
7-th Catalan Number Is : 132
12-th Catalan Number Is : 58786``````
``````#  Python 3 program for
#  Find nth Catalan Number
class CatalanNumber :
def nthCatalanNumber(self, n) :
if (n <= 0) :
return

m = (n - 1) * 2
result = 1
i = 0
#  Binomial coefficient and find catalan number
while (i < n - 1) :
result = result * (m - i)
result = result / (i + 1)
i += 1

result = int(result / n)
#  Display calculated result
print("\n ", n ,"-th Catalan Number Is : ", result, end = "",sep="")

def main() :
#   Catalan Number
#   --------------
#   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 ..... etc
#  Test

if __name__ == "__main__": main()``````

#### Output

`````` 10-th Catalan Number Is : 4862
7-th Catalan Number Is : 132
12-th Catalan Number Is : 58786``````
``````#  Ruby program for
#  Find nth Catalan Number
class CatalanNumber
def nthCatalanNumber(n)
if (n <= 0)
return
end

m = (n - 1) * 2
result = 1
i = 0
#  Binomial coefficient and find catalan number
while (i < n - 1)
result = result * (m - i)
result = result / (i + 1)
i += 1
end

result = result / n
#  Display calculated result
print("\n ", n ,"-th Catalan Number Is : ", result)
end

end

def main()
#   Catalan Number
#   --------------
#   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 ..... etc
#  Test
end

main()``````

#### Output

`````` 10-th Catalan Number Is : 4862
7-th Catalan Number Is : 132
12-th Catalan Number Is : 58786``````
``````// Scala program for
// Find nth Catalan Number
class CatalanNumber()
{
def nthCatalanNumber(n: Int): Unit = {
if (n <= 0)
{
return;
}
var m: Int = (n - 1) * 2;
var result: Long = 1;
var i: Int = 0;
// Binomial coefficient and find catalan number
while (i < n - 1)
{
result = result * (m - i);
result = result / (i + 1);
i += 1;
}
result = result / n;
// Display calculated result
print("\n " + n + "-th Catalan Number Is : " + result);
}
}
object Main
{
def main(args: Array[String]): Unit = {
var task: CatalanNumber = new CatalanNumber();
//  Catalan Number
//  --------------
//  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 ..... etc
// Test
}
}``````

#### Output

`````` 10-th Catalan Number Is : 4862
7-th Catalan Number Is : 132
12-th Catalan Number Is : 58786``````
``````// Swift 4 program for
// Find nth Catalan Number
class CatalanNumber
{
func nthCatalanNumber(_ n: Int)
{
if (n <= 0)
{
return;
}
let m: Int = (n - 1) * 2;
var result: Int = 1;
var i: Int = 0;
// Binomial coefficient and find catalan number
while (i < n - 1)
{
result = result * (m - i);
result = result / (i + 1);
i += 1;
}
result = result / n;
// Display calculated result
print("\n \(n)-th Catalan Number Is : ",
result, terminator: "");
}
}
func main()
{
//  Catalan Number
//  --------------
//  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 ..... etc
// Test
}
main();``````

#### Output

`````` 10-th Catalan Number Is :  4862
7-th Catalan Number Is :  132
12-th Catalan Number Is :  58786``````
``````// Kotlin program for
// Find nth Catalan Number
class CatalanNumber
{
fun nthCatalanNumber(n: Int): Unit
{
if (n <= 0)
{
return;
}
val m: Int = (n - 1) * 2;
var result: Long = 1;
var i: Int = 0;
// Binomial coefficient and find catalan number
while (i < n - 1)
{
result = result * (m - i);
result = result / (i + 1);
i += 1;
}
result = result / n;
// Display calculated result
print("\n " + n + "-th Catalan Number Is : " + result);
}
}
fun main(args: Array < String > ): Unit
{
//  Catalan Number
//  --------------
//  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 ..... etc
// Test
}``````

#### Output

`````` 10-th Catalan Number Is : 4862
7-th Catalan Number Is : 132
12-th Catalan Number Is : 58786``````

## Time Complexity

The time complexity of this algorithm is O(n), where n is the input value for which we want to find the nth Catalan number. The loop runs n - 1 times, and each iteration involves constant-time operations, making the overall time complexity linear with respect to n.

Resultant Output Explanation: After running the provided C program with the values 10, 7, and 12 for n, we get the following output:

``````10-th Catalan Number Is : 4862
7-th Catalan Number Is : 132
12-th Catalan Number Is : 58786``````

This output indicates that the 10th Catalan number is 4862, the 7th Catalan number is 132, and the 12th Catalan number is 58786, which aligns with the sequence of Catalan numbers mentioned in the code comments.

Finally, the algorithm presented in the program efficiently calculates the nth Catalan number and provides the correct output for various values of n. It follows the binomial coefficient approach and has a time complexity of O(n), making it suitable for computing larger Catalan numbers efficiently.

## Comment

Please share your knowledge to improve code and content standard. Also submit your doubts, and test case. We improve by your feedback. We will try to resolve your query as soon as possible.

Categories
Relative Post