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)
	{
		CatalanNumber task = 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 
		task.nthCatalanNumber(10);
		task.nthCatalanNumber(7);
		task.nthCatalanNumber(12);
	}
}

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()
{
	CatalanNumber *task = 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 
	task->nthCatalanNumber(10);
	task->nthCatalanNumber(7);
	task->nthCatalanNumber(12);
	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)
	{
		CatalanNumber task = 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 
		task.nthCatalanNumber(10);
		task.nthCatalanNumber(7);
		task.nthCatalanNumber(12);
	}
}

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()
{
	$task = 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 
	$task->nthCatalanNumber(10);
	$task->nthCatalanNumber(7);
	$task->nthCatalanNumber(12);
}
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()
{
	var task = 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 
	task.nthCatalanNumber(10);
	task.nthCatalanNumber(7);
	task.nthCatalanNumber(12);
}
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() :
	task = 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 
	task.nthCatalanNumber(10)
	task.nthCatalanNumber(7)
	task.nthCatalanNumber(12)

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() 
	task = CatalanNumber.new()
	#   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 
	task.nthCatalanNumber(10)
	task.nthCatalanNumber(7)
	task.nthCatalanNumber(12)
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 
		task.nthCatalanNumber(10);
		task.nthCatalanNumber(7);
		task.nthCatalanNumber(12);
	}
}

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()
{
	let task: CatalanNumber = 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 
	task.nthCatalanNumber(10);
	task.nthCatalanNumber(7);
	task.nthCatalanNumber(12);
}
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
{
	val task: CatalanNumber = 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 
	task.nthCatalanNumber(10);
	task.nthCatalanNumber(7);
	task.nthCatalanNumber(12);
}

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.

New Comment





Categories
Relative Post