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 satisfies 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

© 2019-2026 Algotree.org | All rights reserved.

This content is provided for educational purposes. Feel free to learn, practice, and share knowledge.
For questions or contributions, visit algotree.org

"If debugging is the process of removing bugs, then programming must be the process of putting them in. - Edsger Dijkstra"