Binomial Coefficient | DP-9

The following are the common definitions of Binomial Coefficients. 

A binomial coefficient C(n, k) can be defined as the coefficient of x^k in the expansion of (1 + x)^n.

A binomial coefficient C(n, k) also gives the number of ways, disregarding order, that k objects can be chosen from among n objects more formally, the number of k-element subsets (or k-combinations) of a n-element set.

The Problem 
Write a function that takes two parameters n and k and returns the value of Binomial Coefficient C(n, k). For example, your function should return 6 for n = 4 and k = 2, and it should return 10 for n = 5 and k = 2.

1) Optimal Substructure 
The value of C(n, k) can be recursively calculated using the 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

Following is a simple recursive implementation that simply follows the recursive structure mentioned above.  

Value of C(5, 2) is 10

Time Complexity: O(n*max(k,n-k)) 

Auxiliary Space: O(n*max(k,n-k))

2) Overlapping Subproblems 
It should be noted that the above function computes the same subproblems again and again. See the following recursion tree for n = 5 and k = 2. The function C(3, 1) is called two times. For large values of n, there will be many common subproblems. 
 

Binomial Coefficients Recursion tree for C(5,2)

Since the same subproblems are called again, this problem has the Overlapping Subproblems property. So the Binomial Coefficient problem has both properties (see this and this) of a dynamic programming problem. Like other typical Dynamic Programming(DP) problems, re-computations of the same subproblems can be avoided by constructing a temporary 2D-array C[][] in a bottom-up manner. Following is Dynamic Programming-based implementation. 

Value of C[5][2] is 10

Time Complexity: O(n*k) 
Auxiliary Space: O(n*k)

Following is a space-optimized version of the above code. The following code only uses O(k). Thanks to AK for suggesting this method. 

Value of C(5, 2) is 10 

Time Complexity: O(n*k) 
Auxiliary Space: O(k)

Explanation: 
1==========>> n = 0, C(0,0) = 1 
1–1========>> n = 1, C(1,0) = 1, C(1,1) = 1 
1–2–1======>> n = 2, C(2,0) = 1, C(2,1) = 2, C(2,2) = 1 
1–3–3–1====>> n = 3, C(3,0) = 1, C(3,1) = 3, C(3,2) = 3, C(3,3)=1 
1–4–6–4–1==>> n = 4, C(4,0) = 1, C(4,1) = 4, C(4,2) = 6, C(4,3)=4, C(4,4)=1 
So here every loop on i, builds i’th row of pascal triangle, using (i-1)th row
At any time, every element of array C will have some value (ZERO or more) and in the next iteration, the value for those elements comes from the previous iteration. 
In statement, 
C[j] = C[j] + C[j-1] 
The right-hand side represents the value coming from the previous iteration (A row of Pascal’s triangle depends on the previous row). The left-Hand side represents the value of the current iteration which will be obtained by this statement. 

Let's say we want to calculate C(4, 3), 
i.e. n=4, k=3:
All elements of array C of size 4 (k+1) are
initialized to ZERO.
i.e. C[0] = C[1] = C[2] = C[3] = C[4] = 0;
Then C[0] is set to 1
For i = 1:
C[1] = C[1] + C[0] = 0 + 1 = 1 ==>> C(1,1) = 1
For i = 2:
C[2] = C[2] + C[1] = 0 + 1 = 1 ==>> C(2,2) = 1
C[1] = C[1] + C[0] = 1 + 1 = 2 ==>> C(2,1) = 2
For i=3:
C[3] = C[3] + C[2] = 0 + 1 = 1 ==>> C(3,3) = 1
C[2] = C[2] + C[1] = 1 + 2 = 3 ==>> C(3,2) = 3
C[1] = C[1] + C[0] = 2 + 1 = 3 ==>> C(3,1) = 3
For i=4:
C[4] = C[4] + C[3] = 0 + 1 = 1 ==>> C(4,4) = 1
C[3] = C[3] + C[2] = 1 + 3 = 4 ==>> C(4,3) = 4
C[2] = C[2] + C[1] = 3 + 3 = 6 ==>> C(4,2) = 6
C[1] = C[1] + C[0] = 3 + 1 = 4 ==>> C(4,1) = 4
C(4,3) = 4 is would be the answer in our example.

Memoization Approach: The idea is to create a lookup table and follow the recursive top-down approach. Before computing any value, we check if it is already in the lookup table. If yes, we return the value. Else we compute the value and store it in the lookup table. Following is the Top-down approach of dynamic programming to finding the value of the Binomial Coefficient. 

 Time Complexity: O(n*k)

Auxiliary Space: O(n*k)

Value of C(5, 2) is 10

Cancellation of factors between numerator and denominator:

nCr = (n-r+1)*(n-r+2)*….*n / (r!)

Create an array arr of numbers from n-r+1 to n which will be of size r. As nCr is always an integer, all numbers in the denominator should cancel with the product of the numerator (represented by arr).

for i = 1 to i = r,

        search arr, if arr[j] and i have gcd>1, divide both by the gcd and when i becomes 1, stop the search

Now, the answer is just the product of arr, whose value mod 10^9+7 can be found using a single pass and the formula use (a*b)%mod = (a%mod * b%mod)%mod 

Value of C(5, 2) is 10

Time Complexity: O(( min(r, n-r)^2 ) * log(n)),   useful when n >> r  or  n >> (n-r)

Auxiliary Space: O(min(r, n-r))

See this for GCD in logarithmic time

Prime factorization of every number from 1 to n using Sieve of Eratosthenes :

1. Create an array SPF of size n+1 to the smallest prime factor of each number from 1 to n 

Set SPF[i] = i for all i = 1 to i = n

2. Use Sieve of Eratosthenes:

for i = 2 to i = n:
    if i is prime,
       for all multiples j of i, j<=n:
           if SPF[j] equals j, set SPF[j] = i

3. Once, we know the SPF of each number from 1 to n, we can find the prime factorization of any number from 1 to n in O(log(n)) time using recursive division by SPF until the number becomes 1

Now, nCr  =  (n-r+1)*(r+2)* ... *(n) / (r)!

4. Create a dictionary (or hashmap) to store the frequency of each prime in the prime factorization of the actual value of nCr.

5. So, just calculate the frequency of each prime in nCr and multiply them raised to the power of their frequency.

6. For the numerator, iterate through i = n-r+1 to i = n, and for all prime factors of i, store their frequency in a dictionary.

( prime_pow[prime_factor] += freq_in_i ) 

7. For the denominator, iterate through i = 1 to i = r and now subtract the frequency instead of adding.

8. Now, traverse the dictionary and multiply the answer to (prime ^ prime_pow[prime]) % (10^9 + 7)

ans = (ans * pow(prime, prime_pow[prime], mod) ) % mod