How to use Binomial Coefficients In Javascript
Another efficient approach to calculate Catalan numbers is by using the formula involving binomial coefficients: We can also use the below formula to find nth Catalan number in O(n) time.
Example: Implementation for nth Catlan numbers using recursive approach.
function binomialCoeff(n, k) {
let res = 1;
if (k > n - k) k = n - k;
for (let i = 0; i < k; ++i) {
res *= (n - i);
res /= (i + 1);
}
return res;
}
function catalanBinomial(n) {
let x = binomialCoeff(2 * n, n) / (n + 1);
console.log(x);
}
catalanBinomial(5);
Output
42
Time Complexity: O(n)
Space Complexity:O(1)
JavaScript Program for Nth Catlan Numbers
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, …
Below are the approaches forNth Catlan numbers in JavaScript:
Table of Content
- Using Recursive approach
- Using Dynamic programming
- Using Binomial Coefficients
Contact Us