Algorithm For Finding Binomial Coefficents

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 : O ( n * k ), where ’n’ indicates the available options and ‘k’ indicates the items to choose.

Program for finding the binomial coefficients 

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

#include<iostream>
using namespace std;

// Finding binomial coefficients using recursion.
int Rec_Binomial_Coefficient (int n, int 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);
}

// Finding binomial coefficients using dynamic programming.
int DP_Binomial_Coefficient (int n, int k) {

    int C[n+1][k+1];

    for (int i=0; i<=n; i++) {
        for (int j=0; j<=k; j++) {
            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];
}

int main() 
{
   int n=5;
   int k=3;
   cout << "Using Recursion : " << n << " choose " << k << " = " << Rec_Binomial_Coefficient(n, k) << endl;
   cout << "Using Dynamic Programming : " << n << " choose " << k << " = " << DP_Binomial_Coefficient(n, k) << endl;

   n=4;
   k=1;
   cout << "Using Recursion : " << n << " choose " << k << " = " << Rec_Binomial_Coefficient(n, k) << endl;
   cout << "Using Dynamic Programming : " << n << " choose " << k << " = " << DP_Binomial_Coefficient(n, k) << endl;

   return 0;
}

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

import java.util.*;

class Binomial {

    public static int Rec_Binomial_Coefficient ( int n , int 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 );
    }

    public static int DP_Binomial_Coefficient ( int n , int k ) {

        int[][] C = new int[n+1][];

        for (int r = 0; r <= n ; r++ ) {
            C[r] = new int[k+1];
        }


        for ( int i = 0; i <= n; i++ ) {
            for (int j = 0 ; j <= k; j++ ) {
                if ( i >= j ) {
                    if ( j == 0 || i == j )
                        C[i][j] = 1;
                    else
                        C[i][j] = C[i-1][j] + C[i-1][j-1];
                }
            }
        }
        return C[n][k];
    }

    public static void main(String[] args) {

        int n,k;
        n = 5;
        k = 3;

        System.out.println("Using Recursion : " + n + " choose " + k + " = " + Rec_Binomial_Coefficient ( n , k) );
        System.out.println("Using Dynamic Programming : " + n + " choose " + k + " = " + DP_Binomial_Coefficient ( n , k) );

        n = 4;
        k = 1;

        System.out.println("Using Recursion : " + n + " choose " + k + " = " + Rec_Binomial_Coefficient ( n , k) );
        System.out.println("Using Dynamic Programming : " + n + " choose " + k + " = " + 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

Copyright (c) 2019-2024, Algotree.org.
All rights reserved.