nCr - Binomial Coefficient

Introduction

Prerequisites: Permutations & Combinations

Consider the following problem - Find the number of ways to pick ‘K’ unordered items from a total of ‘N’ distinct items. For simplicity let us assume that K = 3 and N = 5. So, we can pick 3 items in the following ways:

1, 2, 3;  1, 2, 4;  1, 2, 5;  1, 3, 4;  1, 3, 5;  1, 4, 5;

2, 3, 4;  2, 3, 5;  2, 4, 5; 

3, 4, 5;

Therefore, the total number of ways is 10. But how will we solve this problem for large values of K and N?

Let us try to break the problem into smaller subproblems. We have to calculate the number of ways to choose ‘K’ items from ‘N’ distinct items. We can break the problem into two parts - 

1. The number of ways to choose ‘K’ items from the given set, such that we do not pick the last item.
2. The number of ways to choose ‘K’ items from the given set, such that we always choose the last item.

We can easily show that the answer of the 1st part + 2nd part will be the answer to the given problem since the last item will either be chosen or not chosen.

If we look more closely, the first part is the same as choosing K items from N-1 items since the last item is never chosen and the second part is the same as choosing K-1 items from N-1 items since the last element is always chosen.

Let us call the answer to the problem of choosing K items from N given items as F(N, K). Thus, using the above result, we can write:

F(N,K) = F(N-1, K) + F(N-1, K-1)

Now we have derived the formula to solve the given problem. We can easily write a recursive function that will compute the answer.

Base Case: F(N, 0) = 1, F(N, N) = 1.  There is only one way to choose 0 or N items from N given item.

Dynamic Programming

The recursive code will have exponential time complexity. We can improve this by using dynamic programming. The idea is to store the values of F(N-1, K) and F(N-1, K-1) so that we can compute F(N, K) in constant time. DP[i][j] will store the answer of the number of ways of choosing j items from i items. 

First, initialize a DP matrix of size N * K. Set dp[1][0] = 1 and dp[i][1] = 1. Then for all (2 <=i <= N) and (1 <= j <= K):

1. If j is not equal to 0, set dp[i][j] = dp[i-1][j] + dp[i-1][j-1].
2. Else set dp[i][j] = 0

In the end, dp[N][K] will store the value of F(N, K). This approach will have O(N * K) time complexity.

Multiplicative Formula

F(N, K) = N * (N - 1) * (N - 2)...(N - K + 1) / K * (K - 1) * (K - 2)...* 1

This can also be written as -

Factorial(N) / (Factorial(N - K) * Factorial(K))

Binomial Coefficient

Let us look at one another problem:

Consider the expansion of the equation - (1 + X) ^ N. What is the coefficient of X ^ K in the expansion?

In the problem have N terms of (1 + X) multiplied together, i.e, -

(1 + X) * (1 + X) * (1 + X) * ….. N times

We have to find the coefficient of X ^ K in the expansion of the above equation. Each (1 + X) term adds 1 to the power of X. Therefore, X ^ K will occur when we pick exactly K terms from the N terms of (1 + X). This is the same as the above problem and the answer will be F(N, K).

The expansion of (1 + X)^N can be written as:

(1 + X) ^ N = F(N, 0) + F(N, 1) * X + F(N, 2) * X ^ 2 + ….  F(N, N) * X ^ N

The number F(N, K) is also called the Binomial Coefficient since it occurs as a coefficient in the expansion of binomial expressions. These are also called nCr representing that we have to choose r items from n distinct items.

Also see, Euclid GCD Algorithm

Calculating Binomial Coefficients

Recursive Method

(Exponential Time Complexity)

Function NCR( N, K)
    If K = N or K = 0
        Return 0
    Else
        Return NCR(N - 1, K) + NCR(N - 1 + K - 1)

Factorial Method

( O(N) time complexity )

Function Factorial(N)
    Ans = 1
    For i from 1 to N
        Ans = Ans * i
        Return Ans

Function NCR(N, K)
    Return Factorial(N) / (Factorial(K)*(Factorial(N-K))

Multiplicative Method

O(N) time complexity

(here Num represents Numenator and Den represents Denominator)

Function NCR(N, K)
    Num = 1
    Den = 1
    For i from 1 to K
        Num = Num * (N - i + 1)
        Den = Den * i
        Return Num / Den

Dynamic Programming

O(N * K) time complexity

Function NCR(N, K)
    Dp[N + 1][K + 1]
    Dp[1][0] = 1, Dp[1][1] = 1
    For i from 2 to N:
    Dp[i][0] = 1
    For j from 1 to K:
        Dp[i][j] = Dp[i-1][j] + Dp[i-1][j-1]
    Return Dp[N][K]