Posted on by Kalkicode
Code Number

# 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.

1. For n = 0: C(0) = 1

2. For n = 1: C(1) = C(0)*C(0) = 1

3. For n = 2: C(2) = C(0)*C(1) + C(1)*C(0) = 1 + 1 = 2

4. 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:

1. The function `catalan(number)` takes an index 'number' as input and calculates the corresponding Catalan number using recursion.

2. 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.

3. Otherwise, it initializes a variable 'result' to 0.

4. It then iterates through all possible values of 'i' from 0 to 'number' (inclusive) using a loop.

5. 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.

6. 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.

## 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