Catalan number series
The Catalan numbers are a sequence of natural numbers that have significant applications in various mathematical problems. They are named after the French-Belgian mathematician Eugène Charles Catalan. The Catalan number sequence can be defined using a recursive formula and has connections to many combinatorial problems, including parentheses expressions, binary trees, and triangulations of polygons.
Problem Statement
The task in this code is to generate and print the first 'size' Catalan numbers using a C program. The Catalan number at index 'n' in the sequence is denoted by C(n) and is defined as follows:
C(n) = C(0)*C(n-1) + C(1)*C(n-2) + ... + C(n-1)*C(0)
where C(0) = 1 is the base case for the recursion.
Explanation with Suitable Example
Let's take an example to understand how the Catalan numbers are generated and what they represent. Consider the case when 'size' is 3.
-
For n = 0: C(0) = 1
-
For n = 1: C(1) = C(0)*C(0) = 1
-
For n = 2: C(2) = C(0)*C(1) + C(1)*C(0) = 1 + 1 = 2
-
For n = 3: C(3) = C(0)C(2) + C(1)C(1) + C(2)C(0) = 12 + 11 + 21 = 5
So, the first 3 Catalan numbers are 1, 1, and 2, respectively.
Standard Pseudocode
Below is the pseudocode to calculate the Catalan number for a given index 'number':
function catalan(number):
if number <= 1:
return 1
result = 0
for i from 0 to number:
result += catalan(i) * catalan(number-i-1)
return result
Algorithm Explanation:
-
The function
catalan(number)
takes an index 'number' as input and calculates the corresponding Catalan number using recursion. -
In the base case, if 'number' is less than or equal to 1, the function returns 1 because C(0) and C(1) are both 1.
-
Otherwise, it initializes a variable 'result' to 0.
-
It then iterates through all possible values of 'i' from 0 to 'number' (inclusive) using a loop.
-
Inside the loop, it recursively calculates the Catalan numbers for 'i' and 'number-i-1', multiplies them, and adds the result to the 'result' variable.
-
After the loop, the function returns the final 'result' which represents the Catalan number for the given 'number'.
Code Solution
Here given code implementation process.
//C Program
//Print catalan number
#include <stdio.h>
//Returns a given catalan number
unsigned long int catalan( unsigned long int number) {
if (number <= 1){
// Base to control recursion process
// Here are ending of execution recursion
return 1;
}
unsigned long int result = 0;
for (unsigned long i=0; i<number; i++){
// Recursively calculating of catalan number
result += catalan(i)*catalan((number-i)-1);
}
return result;
}
//Function which is handling the request of printing catalan number
void catalan_number(int size)
{
printf("\nInitial %d catalan numbers is : \n", size);
for (unsigned long i = 0; i < size; i++)
{
// Display number
printf("%ld ", catalan(i));
}
}
int main() {
// Test Case
catalan_number(10);
catalan_number(15);
return 0;
}
Output
Initial 10 catalan numbers is :
1 1 2 5 14 42 132 429 1430 4862
Initial 15 catalan numbers is :
1 1 2 5 14 42 132 429 1430 4862 16796 58786 208012 742900 2674440
/*
C++ Program
Print catalan number
*/
#include<iostream>
using namespace std;
class MyNumber {
public:
//Returns a given catalan number
unsigned long catalan(unsigned long number) {
if (number <= 1) {
return 1;
}
int result = 0;
for (unsigned long i = 0; i < number; i++) {
// Recursively calculating of catalan number
result += this->catalan(i) *this->catalan((number - i) - 1);
}
return result;
}
//Function which is handling the request of printing catalan number
void catalan_number(int size) {
cout << "\nInitial " << size << " catalan numbers is : \n";
for (unsigned long i = 0; i < size; i++) {
// Display number
cout << " " << this->catalan(i);
}
}
};
int main() {
MyNumber obj ;
// Test Case
obj.catalan_number(10);
obj.catalan_number(15);
return 0;
}
Output
Initial 10 catalan numbers is :
1 1 2 5 14 42 132 429 1430 4862
Initial 15 catalan numbers is :
1 1 2 5 14 42 132 429 1430 4862 16796 58786 208012 742900 2674440
/*
Java Program
Print catalan number
*/
public class MyNumber {
//Returns a given catalan number
public int catalan(int number) {
if (number <= 1){
// Base to control recursion process
// Here are ending of execution recursion
return 1;
}
int result = 0;
for (int i = 0; i < number; i++){
// Recursively calculating of catalan number
result += catalan(i)*catalan((number-i)-1);
}
return result;
}
//Function which is handling the request of printing catalan number
public void catalan_number(int size)
{
System.out.print("\nInitial "+size+" catalan numbers is : \n");
for (int i = 0; i < size; i++)
{
// Display number
System.out.print(" "+catalan(i));
}
}
public static void main(String[] args) {
MyNumber obj = new MyNumber();
// Test Case
obj.catalan_number(10);
obj.catalan_number(15);
}
}
Output
Initial 10 catalan numbers is :
1 1 2 5 14 42 132 429 1430 4862
Initial 15 catalan numbers is :
1 1 2 5 14 42 132 429 1430 4862 16796 58786 208012 742900 2674440
/*
C# Program
Print catalan number
*/
using System;
public class MyNumber {
//Returns a given catalan number
public int catalan(int number) {
if (number <= 1) {
// Base to control recursion process
// Here are ending of execution recursion
return 1;
}
int result = 0;
for (int i = 0; i < number; i++) {
// Recursively calculating of catalan number
result += catalan(i) * catalan((number - i) - 1);
}
return result;
}
//Function which is handling the request of printing catalan number
public void catalan_number(int size) {
Console.Write("\nInitial " + size + " catalan numbers is : \n");
for (int i = 0; i < size; i++) {
// Display number
Console.Write(" " + catalan(i));
}
}
public static void Main(String[] args) {
MyNumber obj = new MyNumber();
// Test Case
obj.catalan_number(10);
obj.catalan_number(15);
}
}
Output
Initial 10 catalan numbers is :
1 1 2 5 14 42 132 429 1430 4862
Initial 15 catalan numbers is :
1 1 2 5 14 42 132 429 1430 4862 16796 58786 208012 742900 2674440
# Python 3 Program
# Print catalan number
class MyNumber :
#Returns a given catalan number
def catalan(self, number) :
if (number <= 1) :
return 1
result = 0
i = 0
while (i < number) :
# Recursively calculating of catalan number
result += self.catalan(i) * self.catalan((number - i) - 1)
i += 1
return result
#Function which is handling the request of printing catalan number
def catalan_number(self, size) :
print("\nInitial ", size ," catalan numbers is : ")
i = 0
while (i < size) :
print(" ", self.catalan(i),end="")
i += 1
def main() :
obj = MyNumber()
obj.catalan_number(10)
obj.catalan_number(15)
if __name__ == "__main__":
main()
Output
Initial 10 catalan numbers is :
1 1 2 5 14 42 132 429 1430 4862
Initial 15 catalan numbers is :
1 1 2 5 14 42 132 429 1430 4862 16796 58786 208012 742900 2674440
# Ruby Program
# Print catalan number
class MyNumber
#Returns a given catalan number
def catalan(number)
if (number <= 1)
return 1
end
result = 0
i = 0
while (i < number)
# Recursively calculating of catalan number
result += self.catalan(i) * self.catalan((number - i) - 1)
i += 1
end
return result
end
#Function which is handling the request of printing catalan number
def catalan_number(size)
print("\nInitial ", size ," catalan numbers is :\n")
i = 0
while (i < size)
print(" ", self.catalan(i))
i += 1
end
end
end
def main()
obj = MyNumber.new()
obj.catalan_number(10)
obj.catalan_number(15)
end
main()
Output
Initial 10 catalan numbers is :
1 1 2 5 14 42 132 429 1430 4862
Initial 15 catalan numbers is :
1 1 2 5 14 42 132 429 1430 4862 16796 58786 208012 742900 2674440
/*
Scala Program
Print catalan number
*/
class MyNumber {
//Returns a given catalan number
def catalan(number: Int): Int = {
if (number <= 1) {
return 1;
}
var result: Int = 0;
var i: Int = 0;
while (i < number) {
// Recursively calculating of catalan number
result += this.catalan(i) * this.catalan((number - i) - 1);
i += 1;
}
return result;
}
//Function which is handling the request of printing catalan number
def catalan_number(size: Int): Unit = {
print(s"\nInitial $size catalan numbers is : \n");
var i: Int = 0;
while (i < size) {
print(s" ${this.catalan(i)}");
i += 1;
}
}
}
object Main {
def main(args: Array[String]): Unit = {
var obj: MyNumber = new MyNumber();
//Test Case
obj.catalan_number(10)
obj.catalan_number(15);
}
}
Output
Initial 10 catalan numbers is :
1 1 2 5 14 42 132 429 1430 4862
Initial 15 catalan numbers is :
1 1 2 5 14 42 132 429 1430 4862 16796 58786 208012 742900 2674440
/*
Swift 4 Program
Print catalan number
*/
class MyNumber {
//Returns a given catalan number
func catalan(_ number: Int) -> Int {
if (number <= 1) {
return 1;
}
var result: Int = 0;
var i: Int = 0;
while (i < number) {
// Recursively calculating of catalan number
result += self.catalan(i) * self.catalan((number - i) - 1);
i += 1;
}
return result;
}
//Function which is handling the request of printing catalan number
func catalan_number(_ size: Int) {
print("\nInitial ", size ," catalan numbers is : ");
var i: Int = 0;
while (i < size) {
print(" ", self.catalan(i),terminator:"");
i += 1;
}
}
}
func main() {
let obj: MyNumber = MyNumber();
//Test Case
obj.catalan_number(10);
obj.catalan_number(15);
}
main();
Output
Initial 10 catalan numbers is :
1 1 2 5 14 42 132 429 1430 4862
Initial 15 catalan numbers is :
1 1 2 5 14 42 132 429 1430 4862 16796 58786 208012 742900 2674440
<?php
/*
Php Program
Print catalan number
*/
class MyNumber {
//Returns a given catalan number
public function catalan($number) {
if ($number <= 1) {
return 1;
}
$result = 0;
for ($i = 0; $i < $number; $i++) {
// Recursively calculating of catalan number
$result += $this->catalan($i) *$this->catalan(($number - $i) - 1);
}
return $result;
}
//Function which is handling the request of printing catalan number
public function catalan_number($size) {
echo("\nInitial ". $size ." catalan numbers is : \n");
for ($i = 0; $i < $size; $i++) {
// Display number
echo(" ". $this->catalan($i));
}
}
};
function main() {
$obj = new MyNumber();
// Test Case
$obj->catalan_number(10);
$obj->catalan_number(15);
}
main();
Output
Initial 10 catalan numbers is :
1 1 2 5 14 42 132 429 1430 4862
Initial 15 catalan numbers is :
1 1 2 5 14 42 132 429 1430 4862 16796 58786 208012 742900 2674440
/*
Node Js Program
Print catalan number
*/
class MyNumber {
//Returns a given catalan number
catalan(number) {
if (number <= 1) {
return 1;
}
var result = 0;
for (var i = 0; i < number; i++) {
// Recursively calculating of catalan number
result += this.catalan(i) *this.catalan((number - i) - 1);
}
return result;
}
//Function which is handling the request of printing catalan number
catalan_number(size) {
process.stdout.write("\nInitial " + size + " catalan numbers is : \n");
for (var i = 0; i < size; i++) {
// Display number
process.stdout.write(" " + this.catalan(i));
}
}
}
function main(args) {
var obj = new MyNumber();
// Test Case
obj.catalan_number(10);
obj.catalan_number(15)
}
main();
Output
Initial 10 catalan numbers is :
1 1 2 5 14 42 132 429 1430 4862
Initial 15 catalan numbers is :
1 1 2 5 14 42 132 429 1430 4862 16796 58786 208012 742900 2674440
Resultant Output Explanation
The main
function in the provided code calls the catalan_number
function with two different
inputs: 10 and 15. The catalan_number
function, in turn, prints the first 10 and 15 Catalan numbers,
respectively.
Output for catalan_number(10)
:
Initial 10 Catalan numbers are:
1 1 2 5 14 42 132 429 1430 4862
Output for catalan_number(15)
:
Initial 15 Catalan numbers are:
1 1 2 5 14 42 132 429 1430 4862 16796 58786 208012 742900 2674440
Time Complexity of the Code
To analyze the time complexity of the code, we need to understand the recursive nature of the Catalan number
calculation. The function catalan(number)
calls itself twice within the loop with 'number' iterations.
Each recursive call leads to two more recursive calls, and so on.
Let T(n) represent the time complexity for calculating the Catalan number C(n). Then, the recursive relationship is given by:
T(n) = T(0) + T(1) + T(2) + ... + T(n-1)
Since each term on the right side of the equation represents the time taken to compute C(i) for i < n, and we know that T(0) and T(1) are constant time operations (the base cases), we can approximate the time complexity as O(2^n).
However, it's important to note that there are overlapping subproblems in this recursive approach. The same Catalan numbers are recalculated multiple times. This inefficiency can be improved using dynamic programming techniques like memoization or using an iterative approach.
In conclusion, while the provided code effectively calculates the Catalan numbers, it is not an optimized solution in terms of time complexity. For larger values of 'number', the recursive approach may take a considerable amount of time. For better performance, consider using a dynamic programming approach.
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