# 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

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