Binomial Coefficents

Algorithm for 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 ) . ( a4 . b0 ) + ( 4 choose 1 ) . ( a3. b1 ) + ( 4 choose 2 ) . ( a2 . b2 ) + ( 4 choose 3 ) . ( a1 . b3 ) + ( 4 choose 4 ) . ( a0 . b4 )
( a + b )4 = ( 1 ) . ( a4 . b0 ) + ( 4 ) . ( a3. b1 ) + ( 6 ) . ( a2 . b2 ) + ( 4 ) . ( a1 . b3 ) + ( 1 ) . ( a0 . b4 )

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 ( nCk ) = ( nCk-1 ) + ( n-1Ck-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.

Pascal Triangle

Pascal Triangle


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



Finding the binomial coefficients in Java.

Finding Binomial Coefficients in C++.

Finding Binomial Coefficients in Python.

#!/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

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 (c) 2019-2021, Algotree.org.
All rights reserved.