Binomial Coefficents

Finding binomial coefficients

Binomial coefficients are the positive coefficients that are present in the polynomial expansion of a binomial (two terms) power.

Examples of binomial coefficient
( a + b )^4 = ( 4 choose 0 ) . ( a^4 . b^0 ) + ( 4 choose 1 ) . ( a^3. b^1 ) + ( 4 choose 2 ) . ( a^2 . b^2 ) + ( 4 choose 3 ) . ( a^1 . b^3 ) + ( 4 choose 4 ) . ( a^0 . b^4 )
( a + b )^4 = ( 1 ) . ( a^4 . b^0 ) + ( 4 ) . ( a^3. b^1 ) + ( 6 ) . ( a^2 . b^2 ) + ( 4 ) . ( a^1 . b^3 ) + ( 1 ) . ( a^0 . b^4 )

If the binomial coefficients are arranged in rows for n = 0, 1, 2, … a triangular structure known as Pascal’s triangle is obtained.
The Pascal’s triangle satishfies the recurrence relation (n choose k) = (n choose k-1) + (n-1 choose k-1)

  • The binomial coefficient is denoted as (n k) or (n choose k) or (nCk). It represents the number of ways of choosing “k” items from “n” available options. The order of the chosen items does not matter; hence it is also referred to as combinations.
  • ( n choose k ) = n! / ((n-k)! . k!)
  • When n is equal to k, (n choose k) equals 1 as there is only one way of choosing all the items from all the available options.
  • When k is equal to 0, (n choose k) equals 1 as there is only one way of choosing zero items from all the available options.

Time complexity of finding the binomial coefficient : O(n*k), where ‘n’ indicates the available options and ‘k’ indicates the items to choose.


Python : Finding Binomial Coefficients implemented in Python3

#!/usr/bin/python3

def Rec_Binomial_Coefficient (n, k) : 
    
    if (n == k) : 
        return 1
    if (k == 0) : 
        return 1
    
    return Rec_Binomial_Coefficient (n-1, k) + Rec_Binomial_Coefficient (n-1, k-1)

def DP_Binomial_Coefficient (n, k) : 

    C = [0] * (n+1)
    for r in range(n+1) : 
        C[r] = [0] * (k+1)

    for i in range(n+1) :
        for j in range(k+1) :
            if (j == 0 or i==j) :
                C[i][j] = 1 
            else:
                C[i][j] = C[i-1][j] + C[i-1][j-1]

    return C[n][k]

n=5
k=3
print("Using Recursion : "+str(n)+" choose "+str(k)+" = "+str(Rec_Binomial_Coefficient(n, k)))
print("Using Dynamic Programming : "+str(n)+" choose "+str(k)+" = "+str(DP_Binomial_Coefficient(n, k)))

n=4
k=1
print("Using Recursion : "+str(n)+" choose "+str(k)+" = "+str(Rec_Binomial_Coefficient(n, k)))
print("Using Dynamic Programming : "+str(n)+" choose "+str(k)+" = "+str(DP_Binomial_Coefficient(n, k)))

Output

Using Recursion : 5 choose 3 = 10
Using Dynamic Programming : 5 choose 3 = 10
Using Recursion : 4 choose 1 = 4
Using Dynamic Programming : 4 choose 1 = 4

C++ : Finding Binomial Coefficients implemented in C++11

Reference:
http://www.csl.mtu.edu/cs4321/www/Lectures/Lecture%2015%20-%20Dynamic%20Programming%20Binomial%20Coefficients.htm
http://mathworld.wolfram.com/BinomialCoefficient.html
https://en.wikipedia.org/wiki/Binomial_coefficient

Copyright © 2019-2020, Algotree.org.
All rights reserved.