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
• C++
• Java
• C#
• Python
• Ruby
• Scala
• Swift 4
• Php
• Node Js

//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;
}

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;
}

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);
  }
}

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);
    }
}

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()

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()

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);
    }
}

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();

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();

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();

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.