Tutorialspoint.dev

Binomial Coefficient | DP-9

Following are common definition of Binomial Coefficients.

  1. A binomial coefficient C(n, k) can be defined as the coefficient of X^k in the expansion of (1 + X)^n.
  2. A binomial coefficient C(n, k) also gives the number of ways, disregarding order, that k objects can be chosen from among n objects; more formally, the number of k-element subsets (or k-combinations) of an n-element set.

The Problem
Write a function that takes two parameters n and k and returns the value of Binomial Coefficient C(n, k). For example, your function should return 6 for n = 4 and k = 2, and it should return 10 for n = 5 and k = 2.



1) Optimal Substructure
The value of C(n, k) can be recursively calculated using following standard formula for Binomial Coefficients.

   C(n, k) = C(n-1, k-1) + C(n-1, k)
   C(n, 0) = C(n, n) = 1

Following is a simple recursive implementation that simply follows the recursive structure mentioned above.

C++

// A naive recursive C++ implementation
#include <bits/stdc++.h>
using namespace std; 
  
// Returns value of Binomial Coefficient C(n, k) 
int binomialCoeff(int n, int k) 
{ 
    // Base Cases 
    if (k == 0 || k == n) 
        return 1; 
  
    // Recur 
    return binomialCoeff(n - 1, k - 1) + 
                binomialCoeff(n - 1, k); 
} 
  
/* Driver code*/
int main() 
{ 
    int n = 5, k = 2; 
    cout << "Value of C("<<n<<", "<<k<<") is " << binomialCoeff(n, k); 
    return 0; 
} 
  
// This is code is contributed by rathbhupendra

C

// A Naive Recursive Implementation
#include<stdio.h>
  
// Returns value of Binomial Coefficient C(n, k)
int binomialCoeff(int n, int k)
{
  // Base Cases
  if (k==0 || k==n)
    return 1;
  
  // Recur
  return  binomialCoeff(n-1, k-1) + binomialCoeff(n-1, k);
}
  
/* Driver program to test above function*/
int main()
{
    int n = 5, k = 2;
    printf("Value of C(%d, %d) is %d ", n, k, binomialCoeff(n, k));
    return 0;
}

Java

// JAVA Code for Dynamic Programming |
// Set 9 (Binomial Coefficient)
import java.util.*;
  
class GFG {
      
    // Returns value of Binomial 
    // Coefficient C(n, k)
    static int binomialCoeff(int n, int k) 
    {
      
        // Base Cases
        if (k == 0 || k == n)
            return 1;
          
        // Recur
        return binomialCoeff(n - 1, k - 1) + 
                    binomialCoeff(n - 1, k);
    }
      
    /* Driver program to test above function */
    public static void main(String[] args) 
   {
        int n = 5, k = 2;
        System.out.printf("Value of C(%d, %d) is %d ",
                        n, k, binomialCoeff(n, k));
    }
}
  
// This code is contributed by Arnav Kr. Mandal.

Python

# A naive recursive Python implementation
  
def binomialCoeff(n , k):
  
    if k==0 or k ==n :
        return 1
  
    # Recursive Call
    return binomialCoeff(n-1 , k-1) + binomialCoeff(n-1 , k)
  
# Driver Program to test ht above function
n = 5
k = 2
print "Value of C(%d,%d) is (%d)" %(n , k , binomialCoeff(n , k))
  
# This code is contributed by Nikhil Kumar Singh (nickzuck_007)

C#

// C# Code for Dynamic Programming |
// Set 9 (Binomial Coefficient)
using System;
  
class GFG {
      
    // Returns value of Binomial 
    // Coefficient C(n, k)
    static int binomialCoeff(int n, int k) 
    {
          
        // Base Cases
        if (k == 0 || k == n)
            return 1;
          
        // Recur
        return binomialCoeff(n - 1, k - 1) + 
                    binomialCoeff(n - 1, k);
    }
      
    /* Driver program to test above function */
    public static void Main() 
    {
        int n = 5, k = 2;
        Console.Write("Value of C(" + n + "," 
                            + k + ") is " +
                        binomialCoeff(n, k));
    }
}
  
// This code is contributed by Sam007.

PHP

<?php
// PHP Code for Dynamic Programming |
// Set 9 (Binomial Coefficient)
  
// Returns value of 
// Binomial Coefficient C(n, k)
function binomialCoeff($n, $k)
{
    // Base Cases
    if ($k==0 || $k==$n)
        return 1;
      
    // Recur
    return binomialCoeff($n - 1, $k - 1) + 
               binomialCoeff($n - 1, $k);
}
  
    // Driver Code
    $n = 5; 
    $k = 2;
    echo "Value of C","(",$n ,$k,") is "
               , binomialCoeff($n, $k);
  
// This code is contributed by aj_36
?>


Output:

Value of C(52) is 10

2) Overlapping Subproblems
It should be noted that the above function computes the same subproblems again and again. See the following recursion tree for n = 5 an k = 2. The function C(3, 1) is called two times. For large values of n, there will be many common subproblems.

                             C(5, 2)
                    /                      
           C(4, 1)                           C(4, 2)
            /                             /           
       C(3, 0)   C(3, 1)             C(3, 1)               C(3, 2)
                /                   /                    /     
         C(2, 0)    C(2, 1)      C(2, 0) C(2, 1)          C(2, 1)  C(2, 2)
                   /                      /               /    
               C(1, 0)  C(1, 1)      C(1, 0)  C(1, 1)   C(1, 0)  C(1, 1)

Since same suproblems are called again, this problem has Overlapping Subproblems property. So the Binomial Coefficient problem has both properties (see this and this) of a dynamic programming problem. Like other typical Dynamic Programming(DP) problems, re-computations of same subproblems can be avoided by constructing a temporary array C[][] in bottom up manner. Following is Dynamic Programming based implementation.

C++

// A Dynamic Programming based solution that uses 
// table C[][] to calculate the Binomial Coefficient
#include<bits/stdc++.h>
using namespace std;
  
// Prototype of a utility function that
// returns minimum of two integers
int min(int a, int b);
  
// Returns value of Binomial Coefficient C(n, k)
int binomialCoeff(int n, int k)
{
    int C[n + 1][k + 1];
    int i, j;
  
    // Caculate value of Binomial Coefficient
    // in bottom up manner
    for (i = 0; i <= n; i++)
    {
        for (j = 0; j <= min(i, k); j++)
        {
            // Base Cases
            if (j == 0 || j == i)
                C[i][j] = 1;
  
            // Calculate value using previosly
            // stored values
            else
                C[i][j] = C[i - 1][j - 1] +
                          C[i - 1][j];
        }
    }
  
    return C[n][k];
}
  
// A utility function to return 
// minimum of two integers
int min(int a, int b)
{
    return (a < b) ? a : b;
}
  
// Driver Code
int main()
{
    int n = 5, k = 2;
    cout << "Value of C[" << n << "][" 
         << k << "] is " << binomialCoeff(n, k);
}
  
// This code is contributed by Shivi_Aggarwal 

C

// A Dynamic Programming based solution that uses table C[][] to
// calculate the Binomial Coefficient
#include<stdio.h>
  
// Prototype of a utility function that returns minimum of two integers
int min(int a, int b);
  
// Returns value of Binomial Coefficient C(n, k)
int binomialCoeff(int n, int k)
{
    int C[n+1][k+1];
    int i, j;
  
    // Caculate value of Binomial Coefficient in bottom up manner
    for (i = 0; i <= n; i++)
    {
        for (j = 0; j <= min(i, k); j++)
        {
            // Base Cases
            if (j == 0 || j == i)
                C[i][j] = 1;
  
            // Calculate value using previosly stored values
            else
                C[i][j] = C[i-1][j-1] + C[i-1][j];
        }
    }
  
    return C[n][k];
}
  
// A utility function to return minimum of two integers
int min(int a, int b)
{
    return (a<b)? a: b;
}
  
/* Drier program to test above function*/
int main()
{
    int n = 5, k = 2;
    printf ("Value of C(%d, %d) is %d ", n, k, binomialCoeff(n, k) );
    return 0;
}

Java

// A Dynamic Programming based solution that uses table C[][] to 
// calculate the Binomial Coefficient 
  
class BinomialCoefficient
{
    // Returns value of Binomial Coefficient C(n, k)
    static int binomialCoeff(int n, int k)
    {
    int C[][] = new int[n+1][k+1];
    int i, j;
      
        // Calculate  value of Binomial Coefficient in bottom up manner
    for (i = 0; i <= n; i++)
    {
        for (j = 0; j <= min(i, k); j++)
        {
            // Base Cases
            if (j == 0 || j == i)
                C[i][j] = 1;
       
            // Calculate value using previosly stored values
            else
                C[i][j] = C[i-1][j-1] + C[i-1][j];
          }
     }
       
    return C[n][k];
    }
  
    // A utility function to return minimum of two integers
    static int min(int a, int b)
    {
    return (a<b)? a: b; 
    }
  
    /* Driver program to test above function*/
    public static void main(String args[])
    {
    int n = 5, k = 2;
    System.out.println("Value of C("+n+","+k+") is "+binomialCoeff(n, k));
    }
}
/*This code is contributed by Rajat Mishra*/

Python

# A Dynamic Programming based Python Program that uses table C[][]
# to calculate the Binomial Coefficient
  
# Returns value of Binomial Coefficient C(n, k)
def binomialCoef(n, k):
    C = [[0 for x in range(k+1)] for x in range(n+1)]
  
    # Calculate value of Binomial Coefficient in bottom up manner
    for i in range(n+1):
        for j in range(min(i, k)+1):
            # Base Cases
            if j == 0 or j == i:
                C[i][j] = 1
  
            # Calculate value using previosly stored values
            else:
                C[i][j] = C[i-1][j-1] + C[i-1][j]
  
    return C[n][k]
  
# Driver program to test above function
n = 5
k = 2
print("Value of C[" + str(n) + "][" + str(k) + "] is "
      + str(binomialCoef(n,k)))
  
# This code is contributed by Bhavya Jain

C#

// A Dynamic Programming based solution that
// uses table C[][] to calculate the Binomial
// Coefficient 
using System;
  
class GFG {
      
    // Returns value of Binomial Coefficient
    // C(n, k)
    static int binomialCoeff(int n, int k)
    {
        int [,]C = new int[n+1,k+1];
        int i, j;
          
        // Calculate value of Binomial 
        // Coefficient in bottom up manner
        for (i = 0; i <= n; i++)
        {
            for (j = 0; j <= Math.Min(i, k); j++)
            {
                // Base Cases
                if (j == 0 || j == i)
                    C[i,j] = 1;
          
                // Calculate value using previosly
                // stored values
                else
                    C[i,j] = C[i-1,j-1] + C[i-1,j];
            }
        }
          
        return C[n,k];
    }
  
    // A utility function to return minimum
    // of two integers
    static int min(int a, int b)
    {
        return (a < b) ? a : b; 
    }
  
    /* Driver program to test above function*/
    public static void Main()
    {
        int n = 5, k = 2;
        Console.WriteLine("Value of C(" + n
                        + "," + k + ") is "
                    + binomialCoeff(n, k));
    }
}
  
// This code is contributed by anuj_67.

PHP

<?php
// A Dynamic Programming based 
// solution that uses table C[][] to
// calculate the Binomial Coefficient
  
// Returns value of Binomial 
// Coefficient C(n, k)
function binomialCoeff( $n, $k)
{
    $C = array(array());
    $i; $j;
  
    // Caculate value of Binomial
    // Coefficient in bottom up manner
    for ($i = 0; $i <= $n; $i++)
    {
        for ($j = 0; $j <= min($i, $k); $j++)
        {
              
            // Base Cases
            if ($j == 0 || $j == $i)
                $C[$i][$j] = 1;
  
            // Calculate value using 
            // previosly stored values
            else
                $C[$i][$j] = $C[$i - 1][$j - 1] + 
                                 $C[$i - 1][$j];
        }
    }
  
    return $C[$n][$k];
}
  
    // Driver Code
    $n = 5; 
    $k = 2;
    echo "Value of C(" ,$n," ",$k, ") is"," "
                 , binomialCoeff($n, $k) ;
  
// This code is contributed by anuj_67.
?>


Output:

Value of C[5][2] is 10

Time Complexity: O(n*k)
Auxiliary Space: O(n*k)

Following is a space optimized version of the above code. The following code only uses O(k). Thanks to AK for suggesting this method.

C/C++

// C++ program for space optimized Dynamic Programming
// Solution of Binomial Coefficient
#include<bits/stdc++.h>
using namespace std;
  
int binomialCoeff(int n, int k)
{
    int C[k+1];
    memset(C, 0, sizeof(C));
  
    C[0] = 1;  // nC0 is 1
  
    for (int i = 1; i <= n; i++)
    {
        // Compute next row of pascal triangle using
        // the previous row
        for (int j = min(i, k); j > 0; j--)
            C[j] = C[j] + C[j-1];
    }
    return C[k];
}
  
/* Drier program to test above function*/
int main()
{
    int n = 5, k = 2;
    printf ("Value of C(%d, %d) is %d ",
            n, k, binomialCoeff(n, k) );
    return 0;
}

Java

// JAVA Code for Dynamic Programming | 
// Set 9 (Binomial Coefficient)
import java.util.*;
  
class GFG {
      
    static int binomialCoeff(int n, int k)
    {
        int C[] = new int[k + 1];
         
        // nC0 is 1
        C[0] = 1;  
       
        for (int i = 1; i <= n; i++)
        {
            // Compute next row of pascal 
            // triangle using the previous row
            for (int j = Math.min(i, k); j > 0; j--)
                C[j] = C[j] + C[j-1];
        }
        return C[k];
    }
      
    /* Driver program  */
    public static void main(String[] args) 
    {
         int n = 5, k = 2;
            System.out.printf("Value of C(%d, %d) is %d "
                                , n, k, binomialCoeff(n, k));
    }
}

Python

# Python program for Optimized Dynamic Programming solution to
# Binomail Coefficient. This one uses the concept of pascal
# Triangle and less memory
  
def binomialCoeff(n , k):
  
    # Declaring an empty array
    C = [0 for i in xrange(k+1)]
    C[0] = 1 #since nC0 is 1
  
    for i in range(1,n+1):
  
        # Compute next row of pascal triangle using
        # the previous row
        j = min(i ,k)
        while (j>0):
            C[j] = C[j] + C[j-1]
            j -= 1
  
    return C[k]
  
# Driver Program to test the above function
n = 5
k = 2
print "Value of C(%d,%d) is %d" %(n,k,binomialCoeff(n,k))
  
# This code is contribtued by Nikhil Kumar Singh(nickzuck_007)

C#

// C# Code for Dynamic Programming | 
// Set 9 (Binomial Coefficient)
using System;
  
class GFG {
      
    static int binomialCoeff(int n, int k)
    {
        int[] C = new int[k + 1];
          
        // nC0 is 1
        C[0] = 1; 
      
        for (int i = 1; i <= n; i++)
        {
            // Compute next row of pascal 
            // triangle using the previous
            // row
            for (int j = Math.Min(i, k);
                              j > 0; j--)
                C[j] = C[j] + C[j-1];
        }
        return C[k];
    }
      
    /* Driver program */
    public static void Main() 
    {
        int n = 5, k = 2;
        Console.WriteLine("Value of C(" 
                + n + " " + k + ") is " 
                + binomialCoeff(n, k));
    }
}
  
// This code is contribtued by anuj_67.

PHP

<?php
// PHP program for space optimized 
// Dynamic Programming Solution of 
// Binomial Coefficient
function binomialCoeff($n, $k)
{
    $C = array_fill(0, $k + 1, 0);
  
    $C[0] = 1; // nC0 is 1
  
    for ($i = 1; $i <= $n; $i++)
    {
        // Compute next row of pascal 
        // triangle using the previous row
        for ($j = min($i, $k); $j > 0; $j--)
            $C[$j] = $C[$j] + $C[$j - 1];
    }
    return $C[$k];
}
  
// Driver Code
$n = 5; $k = 2;
echo "Value of C[$n, $k] is ". 
        binomialCoeff($n, $k);
      
// This code is contributed by mits.
?>


Output:

Value of C[5][2] is 10

Time Complexity: O(n*k)
Auxiliary Space: O(k)

Explanation:
1==========>> n = 0, C(0,0) = 1
1–1========>> n = 1, C(1,0) = 1, C(1,1) = 1
1–2–1======>> n = 2, C(2,0) = 1, C(2,1) = 2, C(2,2) = 1
1–3–3–1====>> n = 3, C(3,0) = 1, C(3,1) = 3, C(3,2) = 3, C(3,3)=1
1–4–6–4–1==>> n = 4, C(4,0) = 1, C(4,1) = 4, C(4,2) = 6, C(4,3)=4, C(4,4)=1
So here every loop on i, builds i’th row of pascal triangle, using (i-1)th row

At any time, every element of array C will have some value (ZERO or more) and in next iteration, value for those elements comes from previous iteration.
In statement,
C[j] = C[j] + C[j-1]
Right hand side represents the value coming from previous iteration (A row of Pascal’s triangle depends on previous row). Left Hand side represents the value of current iteration which will be obtained by this statement.

Let's say we want to calculate C(4, 3), 
i.e. n=4, k=3:

All elements of array C of size 4 (k+1) are
initialized to ZERO.

i.e. C[0] = C[1] = C[2] = C[3] = C[4] = 0;
Then C[0] is set to 1

For i = 1:
C[1] = C[1] + C[0] = 0 + 1 = 1 ==>> C(1,1) = 1

For i = 2:
C[2] = C[2] + C[1] = 0 + 1 = 1 ==>> C(2,2) = 1
C[1] = C[1] + C[0] = 1 + 1 = 2 ==>> C(2,2) = 2

For i=3:
C[3] = C[3] + C[2] = 0 + 1 = 1 ==>> C(3,3) = 1
C[2] = C[2] + C[1] = 1 + 2 = 3 ==>> C(3,2) = 3
C[1] = C[1] + C[0] = 2 + 1 = 3 ==>> C(3,1) = 3

For i=4:
C[4] = C[4] + C[3] = 0 + 1 = 1 ==>> C(4,4) = 1
C[3] = C[3] + C[2] = 1 + 3 = 4 ==>> C(4,3) = 4
C[2] = C[2] + C[1] = 3 + 3 = 6 ==>> C(4,2) = 6
C[1] = C[1] + C[0] = 3 + 1 = 4 ==>> C(4,1) = 4

C(4,3) = 4 is would be the answer in our example.

See this for Space and time efficient Binomial Coefficient

References:
http://www.csl.mtu.edu/cs4321/www/Lectures/Lecture%2015%20-%20Dynamic%20Programming%20Binomial%20Coefficients.htm

Please write comments if you find anything incorrect, or you want to share more information about the topic discussed above.



This article is attributed to GeeksforGeeks.org

tags:

Dynamic Programming Mathematical binomial coefficient Dynamic Programming Mathematical
Prev Next
More topics on Mathematical Algorithms

leave a comment

code

0 Comments

load comments

Subscribe to Our Newsletter

Top Followed books

Mathematical Algor... Sum of all proper divisors of ...
Mathematical Algor... Recursive program for prime nu...
Mathematical Algor... Check if a number is a Krishna...
Mathematical Algor... Program for Fibonacci numbers
Mathematical Algor... Sum of Fibonacci Numbers
Mathematical Algor... LCM of given array elements