Program for nth Catalan Number using the (n-1)th Catalan Number

Program for nth Catalan Number using Binomial Coefficient:

We already know how to calculate the nth Catalan Number using the below formula,

This formula can be further simplified to express the nth Catalan Number in the terms of (n-1)th Catalan Number,

Below are steps to calculate Catalan numbers using the above formula:

Initialize a variable res = 1
Print 1 as the first Catalan Number
Iterate from i = 1 to i < n
- Update res with res = (res * (4 * i – 2)) / (i + 1)
- print res

Below is the implementation for the above approach:

C++

#include <bits/stdc++.h>
using namespace std;
 
// Function to print first n Catalan numbers
void catalan(int n)
{
    int res = 1;
    cout << res << " ";
    // Iterate till n
    for (int i = 1; i < n; i++) {
        // Calculate the ith Catalan number
        res = (res * (4 * i - 2)) / (i + 1);
           cout << res << " ";
    }
}
 
// Driver code
int main()
{
    int n = 10;
 
    // Function call
    catalan(n);
    return 0;
}

Java

import java.util.*;
class GFG {
 
    // Function to print first n Catalan numbers
    static void catalan(int n)
    {
        int res = 1;
        System.out.print(1 + " ");
        // Iterate till N
        for (int i = 1; i < n; i++) {
            // Calculate the ith Catalan Number
            res = (res * (4 * i - 2)) / (i + 1);
            System.out.print(res + " ");
        }
    }
 
    // Driver code
    public static void main(String args[])
    {
        int n = 10;
 
        // Function call
        catalan(n);
    }
}
 
// This code is contributed by Debojyoti Mandal

Python3

# Function to print first n Catalan numbers
def catalan(n):
 
    res = 1
 
    print(1, end=" ")
    # Iterate till N
    for i in range(1, n):
 
        # Calculate the ith Catalan number
        res = (res * (4 * i - 2)) // (i + 1)
        print(res, end=" ")
 
 
# Driver code
n = 10
 
# Function call
catalan(n)
 
# This code is contributed by rohan07

C#

using System;
 
public class GFG {
 
    // Function to print first n Catalan numbers
    static void catalan(int n)
    {
        int res = 1;
 
        Console.Write(1 + " ");
        // Iterate till N
        for (int i = 1; i < n; i++) {
            // Calculate the ith Catalana Number
            res = (res * (4 * i - 2)) / (i + 1);
            Console.Write(res + " ");
        }
    }
 
    // Driver code
    public static void Main(String[] args)
    {
        int n = 10;
        // Function call
        catalan(n);
    }
}
 
// This code is contributed by Rajput-Ji

Javascript

<script>
    // Function to print first n Catalan numbers
    function catalan(n)
    {
        let res = 1;
        document.write(1 + " ");
         
        // Iterate till N
        for (let i = 1; i < n; i++)
        {
            // Calculate the ith Catalan Number
            res = (res * (4 * i - 2)) / (i + 1);
            document.write(res + " ");
        }
    }
     
    // Driver code
        let n = 10;
     
        // Function call
        catalan(n);
     
    //This code is contributed by Mayank Tyagi
</script>

Output

1 1 2 5 14 42 132 429 1430 4862

Time Complexity: O(n)
Auxiliary Space: O(1), since no extra space has been taken.

Program for nth Catalan Number

Catalan numbers are defined as a mathematical sequence that consists of positive integers, which can be used to find the number of possibilities of various combinations.

The nth term in the sequence denoted C_n, is found in the following formula:

The first few Catalan numbers for n = 0, 1, 2, 3, … are : 1, 1, 2, 5, 14, 42, 132, 429, 1430, 4862, …

Catalan numbers occur in many interesting counting problems like the following.

Count the number of expressions containing n pairs of parentheses that are correctly matched. For n = 3, possible expressions are ((())), ()(()), ()()(), (())(), (()()).
Count the number of possible Binary Search Trees with n keys (See this)
Count the number of full binary trees (A rooted binary tree is full if every vertex has either two children or no children) with n+1 leaves.
Given a number n, return the number of ways you can draw n chords in a circle with 2 x n points such that no 2 chords intersect.

See this for more applications.

Examples:

Input: n = 6
Output: 132

Input: n = 8
Output: 1430

Tags:

#Amazon #catalan #series #DSA #Dynamic Programming #Mathematical #Amazon #Dynamic Programming #Mathematical #series