Program for nth Catalan Number using Binomial Coefficient
We can also use the below formula to find nth Catalan number in O(n) time.
Here is the proof for the Expression:–
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
Below are the steps for calculating nCr.
- 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 nCr.
Below are steps to calculate Catalan numbers using the formula: 2nCn/(n+1)
- Calculate 2nCn using the similar steps that we use to calculate nCr
- Return the value 2nCn/ (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;">
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 Cn, 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: 132Input: n = 8
Output: 1430