Binomial Coefficient

The binomial coefficient, also known as "n choose k", calculates the number of ways to choose items from a set of items without regard to the order of selection. It is often denoted as or .

Formula

The closed form solution to calculate the binomial coefficient given and is:

However, this formula is inefficient for large values of and .

Implementation

A better implementation is to use dynamic programming to calculate the binomial coefficient. This is more efficient because it avoids calculating factorials and only calculates the necessary values.

code.ts
1/**
2 * Calculate the binomial coefficient (n choose k)
3 *
4 * @param {Number} available choices
5 * @param {Number} number chosen
6 * @return {Number} number of possible choices
7 */
8function binomialCoefficient(n: number, k: number) {
9  const arr:number[][] = [];
10
11  function binomial(n: number, k: number) {
12    if (n >= 0 && k === 0) return 1;
13    if (n === 0 && k > 0) return 0;
14    if (arr[n] && arr[n][k] > 0) return arr[n][k];
15    if (!arr[n]) arr[n] = [];
16
17    arr[n][k] = binomial(n - 1, k - 1) + binomial(n - 1, k);
18    return arr[n][k];
19  }
20
21  return binomial(n, k);
22};