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
- 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.
- 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.
- We initialize a variable result to store the calculated Catalan number.
- 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.
- 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.
- 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.
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