Program for nth Catalan Number using Binomial Coefficient

Program for nth Catalan Number using Dynamic Programming:

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

We can also use the below formula to find nth Catalan number in O(n) time.

Here is the proof for the Expression:–

This is the expression for which we are going to see the proof

In the pascal triangle,

1
1 1
1 2 1
1 3 3 1
1 4 6 4 1
1 5 10 10 5 1

Pascal’s triangle as binomial coefficients

the formula for a cell of Pascal’s triangle

Pascal’s triangle

Below are the steps for calculating nC_r.

Create a variable to store the answer and change r to n – r if r is greater than n – r because we know that C(n, r) = C(n, n-r) if r > n – r
Run a loop from 0 to r-1
- In every iteration update ans as (ans*(n-i))/(i+1), where i is the loop counter.
So the answer will be equal to ((n/1)*((n-1)/2)*…*((n-r+1)/r), which is equal to nC_r.

Below are steps to calculate Catalan numbers using the formula: 2nC_n/(n+1)

Calculate 2nC_n using the similar steps that we use to calculate nC_r
Return the value 2nC_n/ (n + 1)

Below is the implementation of the above approach:

C++

// C++ program for nth Catalan Number
#include <iostream>
using namespace std;
 
// Returns value of Binomial Coefficient C(n, k)
unsigned long int binomialCoeff(unsigned int n,
                                unsigned int k)
{
    unsigned long int res = 1;
 
    // Since C(n, k) = C(n, n-k)
    if (k > n - k)
        k = n - k;
 
    // Calculate value of [n*(n-1)*---*(n-k+1)] /
    // [k*(k-1)*---*1]
    for (int i = 0; i < k; ++i) {
        res *= (n - i);
        res /= (i + 1);
    }
 
    return res;
}
 
// A Binomial coefficient based function to find nth catalan
// number in O(n) time
unsigned long int catalan(unsigned int n)
{
    // Calculate value of 2nCn
    unsigned long int c = binomialCoeff(2 * n, n);
 
    // return 2nCn/(n+1)
    return c / (n + 1);
}
 
// Driver code
int main()
{
    for (int i = 0; i < 10; i++)
        cout << catalan(i) << " ";
    return 0;
}

Java

// Java program for nth Catalan Number
 
class GFG {
 
    // Returns value of Binomial Coefficient C(n, k)
    static long binomialCoeff(int n, int k)
    {
        long res = 1;
 
        // Since C(n, k) = C(n, n-k)
        if (k > n - k) {
            k = n - k;
        }
 
        // Calculate value of [n*(n-1)*---*(n-k+1)] /
        // [k*(k-1)*---*1]
        for (int i = 0; i < k; ++i) {
            res *= (n - i);
            res /= (i + 1);
        }
 
        return res;
    }
 
    // A Binomial coefficient based function
    //  to find nth catalan number in O(n) time
    static long catalan(int n)
    {
        // Calculate value of 2nCn
        long c = binomialCoeff(2 * n, n);
 
        // return 2nCn/(n+1)
        return c / (n + 1);
    }
 
    // Driver code
    public static void main(String[] args)
    {
        for (int i = 0; i < 10; i++) {
            System.out.print(catalan(i) + " ");
        }
    }
}

Python3

# Python program for nth Catalan Number
# Returns value of Binomial Coefficient C(n, k)
 
 
def binomialCoefficient(n, k):
 
    # since C(n, k) = C(n, n - k)
    if (k > n - k):
        k = n - k
 
    # initialize result
    res = 1
 
    # Calculate value of [n * (n-1) *---* (n-k + 1)]
    # / [k * (k-1) *----* 1]
    for i in range(k):
        res = res * (n - i)
        res = res / (i + 1)
    return res
 
# A Binomial coefficient based function to
# find nth catalan number in O(n) time
 
 
def catalan(n):
    c = binomialCoefficient(2*n, n)
    return c/(n + 1)
 
 
# Driver Code
for i in range(10):
    print(catalan(i), end=" ")
 
# This code is contributed by Aditi Sharma

C#

// C# program for nth Catalan Number
using System;
class GFG {
 
    // Returns value of Binomial Coefficient C(n, k)
    static long binomialCoeff(int n, int k)
    {
        long res = 1;
 
        // Since C(n, k) = C(n, n-k)
        if (k > n - k) {
            k = n - k;
        }
 
        // Calculate value of [n*(n-1)*---*(n-k+1)] /
        // [k*(k-1)*---*1]
        for (int i = 0; i < k; ++i) {
            res *= (n - i);
            res /= (i + 1);
        }
 
        return res;
    }
 
    // A Binomial coefficient based function to find nth
    // catalan number in O(n) time
    static long catalan(int n)
    {
        // Calculate value of 2nCn
        long c = binomialCoeff(2 * n, n);
 
        // return 2nCn/(n+1)
        return c / (n + 1);
    }
 
    // Driver code
    public static void Main()
    {
        for (int i = 0; i < 10; i++) {
            Console.Write(catalan(i) + " ");
        }
    }
}
 
// This code is contributed
// by Akanksha Rai

Javascript

<script>
// Javascript program for nth Catalan Number 
 
// Returns value of Binomial 
// Coefficient C(n, k) 
function binomialCoeff(n, k) 
{ 
    let res = 1; 
 
    // Since C(n, k) = C(n, n-k) 
    if (k > n - k) 
        k = n - k; 
 
    // Calculate value of [n*(n-1)*---*(n-k+1)] / 
    //                    [k*(k-1)*---*1] 
    for (let i = 0; i < k; ++i) 
    { 
        res *= (n - i); 
        res = Math.floor(res / (i + 1)); 
    } 
 
    return res; 
} 
 
// A Binomial coefficient based function 
// to find nth catalan number in O(n) time 
function catalan(n) 
{ 
 
    // Calculate value of 2nCn 
    c = binomialCoeff(2 * (n), n); 
 
    // return 2nCn/(n+1) 
    return Math.floor(c / (n + 1)); 
} 
 
// Driver code 
for (let i = 0; i < 10; i++) 
document.write(catalan(i) + " " ); 
 
// This code is contributed by _saurabh_jaiswal
</script>

PHP

<?php
// PHP program for nth Catalan Number 
 
// Returns value of Binomial 
// Coefficient C(n, k) 
function binomialCoeff($n, $k) 
{ 
    $res = 1; 
 
    // Since C(n, k) = C(n, n-k) 
    if ($k > $n - $k) 
        $k = $n - $k; 
 
    // Calculate value of [n*(n-1)*---*(n-k+1)] / 
    //                    [k*(k-1)*---*1] 
    for ($i = 0; $i < $k; ++$i) 
    { 
        $res *= ($n - $i); 
        $res = floor($res / ($i + 1)); 
    } 
 
    return $res; 
} 
 
// A Binomial coefficient based function 
// to find nth catalan number in O(n) time 
function catalan($n) 
{ 
    // Calculate value of 2nCn 
    $c = binomialCoeff(2 * ($n), $n); 
 
    // return 2nCn/(n+1) 
    return floor($c / ($n + 1)); 
} 
 
// Driver code 
for ($i = 0; $i < 10; $i++) 
echo catalan($i), " " ; 
 
// This code is contributed by Ryuga
?>

Output

1 1 2 5 14 42 132 429 1430 4862

Time Complexity: O(n).
Auxiliary Space: O(1)

We can also use the below formulas to find nth Catalan number in O(n) time.

0} " title="Rendered by QuickLaTeX.com" height="39" width="346" style="vertical-align: 22px;">