Problem

Given two parameters n and k and returns the value of Binomial Coefficient C(n, k).

Definition

Binomial coefficients, denoted by C(n, k), have two common interpretations:

  1. the coefficient of X^k in the expansion of (1 + X)^n. For eg., in (1 + X)^3, C(3, 2) gives you the coefficient of the term X^2. Expanding the expression, we see 3X^2, and indeed, C(3, 2) is equal to 3.
  2. the number of ways to choose k objects from a set of n, regardless of order.

Formula

$$ C(n, k) \text{ OR } \binom{n}{k} = \frac{n!}{k! * (n - k)!} $$

Examples

Example 1:

Input: n = 4, k = 2
Output: 6
Explanation: C(4, 2) = 4 C 2 = 4! / (2! * 2!) = 24 / 2*2 = 6

Example 2:

Input: n = 5 and k = 2
Output: 10
Explanation:  C(5, 2) = 5 C 2 = 5!/(3!*2!) = 10

Solution

Method 1 - Recursion

Optimal Substructure - The value of C(n, k) can be recursively calculated using following standard formula for Binomial Coefficients.

C(n, k) = C(n-1, k-1) + C(n-1, k)
C(n, 0) = C(n, n) = 1

Code

Java
public int binomialCoefficient(int n, int k) {
  if (k > n) {
    return 0; // C(n, k) is 0 when k > n
  } else if (k == 0 || k == n) {
    return 1; // C(n, 0) = C(n, n) = 1
  } else {
    // Recursive case: C(n, k) = C(n-1, k-1) + C(n-1, k)
    return binomialCoefficient(n - 1, k - 1) + binomialCoefficient(n - 1, k);
  }
}

Complexity

  • ⏰ Time complexity: O(2^n)
  • 🧺 Space complexity: O(n)

Method 2 - Top Down DP

As, we can see there exists overlapping problems OR optimal substructure to the problem:

graph TD
A(((5, 3))) --> B(((4, 2)))
A --> C(((4, 3)))
B --> D(((3, 1)))
B --> E(((3, 2)))
C --> D
C --> E
D --> F(((2, 0)))  
E --> F
E --> G(((2, 1)))

Code

Java
public int binomialCoefficientTopDownDP(int n, int k) {
  // Helper function to calculate using memoization
  return helper(n, k, new int[n + 1][k + 1]);
}

private int helper(int n, int k, int[][] memo) {
  // If base case (C(n, 0) or C(n, n)) return 1
  if (k == 0 || k == n) {
    return 1;
  }

  if (memo[n][k] != 0) {
    return memo[n][k];
  }

  return memo[n][k] = helper(n - 1, k - 1, memo) + helper(n - 1, k, memo);
}

Complexity

  • ⏰ Time complexity: O(n*k)
  • 🧺 Space complexity: O(n*k)

Method 3 - Bottom up DP

Code

Java
public int binomialCoefficientDP(int n, int k) {
  int[][] dp = new int[n + 1][k + 1];

  // Initialize base cases (C(n, 0) and C(n, n))
  for (int i = 0; i <= n; i++) {
    dp[i][0] = 1; // C(n, 0) = 1 for all n
    dp[i][i] = 1; // C(n, n) = 1 for all n
  }

  for (int i = 1; i <= n; i++) {
    for (int j = 1; j <= k && j <= i; j++) {
      // Apply the formula: C(n, k) = C(n-1, k-1) + C(n-1, k)
      dp[i][j] = dp[i - 1][j - 1] + dp[i - 1][j];
    }
  }

  return dp[n][k];
}

Complexity

  • ⏰ Time complexity: O(n*k)
  • 🧺 Space complexity: O(n*k)

Method 4 - Mathematics

We can take use of this identity to calculate binomial coefficent:

$$ \binom{n}{k} = \binom{n}{n - k} $$ Why this identity holds? We have seen that the binomial coefficient is: $$ \binom{n}{k} = \frac{n!}{k! * (n - k)!} $$

Then, $$ \binom{n}{n - k} = \frac{n!}{(n - k)! * (n - (n - k))!} = \frac{n!}{(n - k)! * (k)!} = \binom{n}{k} $$ Notice that after simplifying the latter, the factorial terms match with the former. In both expressions, (n-k)! is the number of ways to arrange the not chosen elements, and k! is the number of ways to arrange the chosen elements within the subsets. Since we aren’t interested in how the subsets themselves are ordered - only in their composition - both expressions simplify to the same thing.

Also, lets expand on C(n, k):

$$ \binom{n}{k} = \frac{n!}{k! * (n - k)!} = \frac{n * (n - 1) * … (n - k + 1) * (n - k)!}{k! * (n - k)!} $$ On simplifying we get:

$$ \binom{n}{k} = \frac{n * (n - 1) * … * (n - k + 1)}{ k! } = \frac{n * (n - 1) * … * (n - k + 1)}{k * (k - 1) * … *1} $$

Algorithm

  1. Change k to n - k if k > (n - k)
  2. Run loop k times from 0 ... k - 1 say with iterator i
  3. Calculate each term as as (ans * (n - i)) / (i + 1)

Code

Java
 public int binomialCoefficient(int n, int k) {
	 // Since C(n, k) = C(n, n-k)
	 if (k > n - k) {
		 k = n - k;
	 }

	 int ans = 1;
	 for (int i = 0; i < k; ++i) {
		 ans *= (n - i);
		 ans /= (i + 1);
	 }

	 return ans;
 }

Complexity

  • ⏰ Time complexity: O(k) (as we loop from 0 to k)
  • 🧺 Space complexity: O(1)