Posted on by Kalkicode
Code Dynamic Programming

# Binomial coefficient using dynamic programming

The problem at hand revolves around calculating binomial coefficients using dynamic programming. Binomial coefficients are often denoted as "n choose k," representing the number of ways to choose k elements from a set of n distinct elements. This problem has applications in various domains, including combinatorics, probability, and statistics.

## Problem Statement and Description

Given two positive integers, n and k, the goal is to calculate the binomial coefficient C(n, k) using the formula:

``````
n!
C(n,k) =  ––––––––––
k! (n -k)!
``````

The binomial coefficient represents the number of ways to choose k elements from a set of n elements, without considering the order of selection. It is a crucial concept in mathematics with numerous applications, such as in counting combinations and calculating probabilities.

## Example

Let's consider an example to understand the problem better. Suppose you are planning to form a committee from a group of 7 people (n = 7), and you want to select 3 individuals (k = 3) for the committee. The binomial coefficient C(7, 3) will tell you how many ways you can form such a committee.

Imagine you have a group of 7 friends: Alice, Bob, Carol, David, Emma, Frank, and Grace. You want to choose a committee of 3 people from this group. The binomial coefficient C(7, 3) will tell you how many different ways you can form this committee.

Here are all the possible committees you can form:

1. Alice, Bob, Carol
2. Alice, Bob, David
3. Alice, Bob, Emma
4. Alice, Bob, Frank
5. Alice, Bob, Grace
6. Alice, Carol, David
7. Alice, Carol, Emma
8. Alice, Carol, Frank
9. Alice, Carol, Grace
10. Alice, David, Emma
11. Alice, David, Frank
12. Alice, David, Grace
13. Alice, Emma, Frank
14. Alice, Emma, Grace
15. Alice, Frank, Grace
16. Bob, Carol, David
17. Bob, Carol, Emma
18. Bob, Carol, Frank
19. Bob, Carol, Grace
20. Bob, David, Emma
21. Bob, David, Frank
22. Bob, David, Grace
23. Bob, Emma, Frank
24. Bob, Emma, Grace
25. Bob, Frank, Grace
26. Carol, David, Emma
27. Carol, David, Frank
28. Carol, David, Grace
29. Carol, Emma, Frank
30. Carol, Emma, Grace
31. Carol, Frank, Grace
32. David, Emma, Frank
33. David, Emma, Grace
34. David, Frank, Grace
35. Emma, Frank, Grace

## Idea to Solve the Problem

To efficiently calculate binomial coefficients, dynamic programming can be employed. The idea is to build a table of values where each entry corresponds to a specific binomial coefficient. By leveraging the property of binomial coefficients, which states that C(n, k) = C(n-1, k) + C(n-1, k-1), we can recursively fill in the table.

## Standard Pseudocode

``````function calculateBinomialCoefficient(n, k):
create a 2D array dp of size (n+1) x (k+1)

for i from 0 to n:
for j from 0 to min(i, k):
if j = 0 or j = i:
dp[i][j] = 1
else:
dp[i][j] = dp[i-1][j-1] + dp[i-1][j]

return dp[n][k]``````

## Algorithm Explanation

1. Initialize a 2D array `dp` of size (n+1) x (k+1) to store the binomial coefficients.
2. Iterate through i from 0 to n.
• For each i, iterate through j from 0 to min(i, k).
• If j is 0 or j is equal to i, set `dp[i][j]` to 1, as these are the boundary cases where C(n, 0) = 1 and C(n, n) = 1.
• Otherwise, use the recurrence relation: `dp[i][j] = dp[i-1][j-1] + dp[i-1][j]`.
3. The final result will be stored in `dp[n][k]`.

## Resultant Output Explanation

For the provided code and example inputs (7, 3), (6, 4), and (8, 2), the output is as follows:

• For (7, 3):
• The calculated binomial coefficient C(7, 3) is 35, which means there are 35 ways to choose 3 people from a group of 7.
• For (6, 4):
• The calculated binomial coefficient C(6, 4) is 15, indicating 15 possible combinations of selecting 4 items from a set of 6.
• For (8, 2):
• The calculated binomial coefficient C(8, 2) is 28, representing 28 different pairs that can be formed from a collection of 8 items.

## Code Solution

This implementation of binomial coefficient using dynamic programming uses the space optimization technique to reduce the auxiliary space complexity to O(k). The time complexity of this algorithm is O(n*k).

The implementation uses an array c to store the intermediate results of the binomial coefficient calculation. The array is initialized with zeros, and the first element is set to 1 since C(n, 0) = 1 for all n.

The outer loop iterates from i = 1 to n, and for each value of i, the inner loop iterates from j = min(i, k) to 1. This ensures that we only compute the necessary values of C(i, j) based on the recurrence relation:

C(i, j) = C(i-1, j-1) + C(i-1, j)

In the inner loop, we update the values of the array c by adding the value of c[j] to c[j-1], which corresponds to the above recurrence relation. The final result is stored in c[k], which represents the value of C(n, k).

This will compute C(5, 2) = 10 using dynamic programming.

``````// C Program
// Binomial coefficient using dynamic programming
#include <stdio.h>

void biCoefficient(int n, int k)
{
//   Formula nCr
//      n!
//   ––––––––––
//   k! (n -k)!
// auxiliary space
int c[k + 1];
int j = 0;
// Set initial value
for (j = 0; j <= k; ++j)
{
c[j] = 0;
}
// Set first
c[0] = 1;
// iterate the loop through by n
for (int i = 1; i <= n; i++)
{
// Get minimum
if (k > i)
{
j = i;
}
else
{
j = k;
}
while (j > 0)
{
c[j] = c[j] + c[j - 1];
j--;
}
}
// Display given n , k
printf("\n Given  : (%d,%d) ", n, k);
printf("\n Result :  %d\n", c[k]);
}
int main()
{
// Test case
biCoefficient(7, 3);
biCoefficient(6, 4);
biCoefficient(8, 2);
return 0;
}``````

#### Output

`````` Given  : (7,3)
Result :  35

Given  : (6,4)
Result :  15

Given  : (8,2)
Result :  28``````
``````/*
Java Program
Binomial coefficient using dynamic programming
*/
class BinomialCoefficient
{
public void biCoefficient(int n, int k)
{
//   Formula nCr
//      n!
//   ––––––––––
//   k! (n -k)!
// auxiliary space
int[] c = new int[k + 1];
int j = 0;
// Set initial value
for (j = 0; j <= k; ++j)
{
c[j] = 0;
}
// Set first
c[0] = 1;
// iterate the loop through by n
for (int i = 1; i <= n; i++)
{
// Get minimum
if (k > i)
{
j = i;
}
else
{
j = k;
}
while (j > 0)
{
c[j] = c[j] + c[j - 1];
j--;
}
}
// Display given n , k
System.out.print("\n Given : (n = " + n + ",k = " + k + ") ");
System.out.print("\n Result : " + c[k] + "\n");
}
public static void main(String[] args)
{
// Test case
}
}``````

#### Output

`````` Given : (n = 7,k = 3)
Result : 35

Given : (n = 6,k = 4)
Result : 15

Given : (n = 8,k = 2)
Result : 28``````
``````// Include header file
#include <iostream>

using namespace std;
/*
C++ Program
Binomial coefficient using dynamic programming
*/
class BinomialCoefficient
{
public: void biCoefficient(int n, int k)
{
//   Formula nCr
//      n!
//   ––––––––––
//   k! (n -k)!
// auxiliary space
int c[k + 1];
int j = 0;
// Set initial value
for (j = 0; j <= k; ++j)
{
c[j] = 0;
}
// Set first
c[0] = 1;
// iterate the loop through by n
for (int i = 1; i <= n; i++)
{
// Get minimum
if (k > i)
{
j = i;
}
else
{
j = k;
}
while (j > 0)
{
c[j] = c[j] + c[j - 1];
j--;
}
}
// Display given n , k
cout << "\n Given : (n = " << n << ",k = " << k << ") ";
cout << "\n Result : " << c[k] << "\n";
}
};
int main()
{
// Test case
return 0;
}``````

#### Output

`````` Given : (n = 7,k = 3)
Result : 35

Given : (n = 6,k = 4)
Result : 15

Given : (n = 8,k = 2)
Result : 28``````
``````// Include namespace system
using System;
/*
C# Program
Binomial coefficient using dynamic programming
*/
public class BinomialCoefficient
{
public void biCoefficient(int n, int k)
{
//   Formula nCr
//      n!
//   ––––––––––
//   k! (n -k)!
// auxiliary space
int[] c = new int[k + 1];
int j = 0;
// Set initial value
for (j = 0; j <= k; ++j)
{
c[j] = 0;
}
// Set first
c[0] = 1;
// iterate the loop through by n
for (int i = 1; i <= n; i++)
{
// Get minimum
if (k > i)
{
j = i;
}
else
{
j = k;
}
while (j > 0)
{
c[j] = c[j] + c[j - 1];
j--;
}
}
// Display given n , k
Console.Write("\n Given : (n = " + n + ",k = " + k + ") ");
Console.Write("\n Result : " + c[k] + "\n");
}
public static void Main(String[] args)
{
// Test case
}
}``````

#### Output

`````` Given : (n = 7,k = 3)
Result : 35

Given : (n = 6,k = 4)
Result : 15

Given : (n = 8,k = 2)
Result : 28``````
``````<?php
/*
Php Program
Binomial coefficient using dynamic programming
*/
class BinomialCoefficient
{
public	function biCoefficient(\$n, \$k)
{
//   Formula nCr
//      n!
//   ––––––––––
//   k! (n -k)!
// auxiliary space
\$c = array_fill(0, \$k + 1, 0);
\$j = 0;
// Set initial value
for (\$j = 0; \$j <= \$k; ++\$j)
{
\$c[\$j] = 0;
}
// Set first
\$c[0] = 1;
// iterate the loop through by n
for (\$i = 1; \$i <= \$n; \$i++)
{
// Get minimum
if (\$k > \$i)
{
\$j = \$i;
}
else
{
\$j = \$k;
}
while (\$j > 0)
{
\$c[\$j] = \$c[\$j] + \$c[\$j - 1];
\$j--;
}
}
// Display given n , k
echo "\n Given : (n = ". \$n .",k = ". \$k .") ";
echo "\n Result : ". \$c[\$k] ."\n";
}
}

function main()
{
}
main();``````

#### Output

`````` Given : (n = 7,k = 3)
Result : 35

Given : (n = 6,k = 4)
Result : 15

Given : (n = 8,k = 2)
Result : 28``````
``````/*
Node Js Program
Binomial coefficient using dynamic programming
*/
class BinomialCoefficient
{
biCoefficient(n, k)
{
//   Formula nCr
//      n!
//   ––––––––––
//   k! (n -k)!
// auxiliary space
var c = Array(k + 1).fill(0);
var j = 0;
// Set initial value
for (j = 0; j <= k; ++j)
{
c[j] = 0;
}
// Set first
c[0] = 1;
// iterate the loop through by n
for (var i = 1; i <= n; i++)
{
// Get minimum
if (k > i)
{
j = i;
}
else
{
j = k;
}
while (j > 0)
{
c[j] = c[j] + c[j - 1];
j--;
}
}
// Display given n , k
process.stdout.write("\n Given : (n = " + n + ",k = " + k + ") ");
process.stdout.write("\n Result : " + c[k] + "\n");
}
}

function main()
{
// Test case
}
main();``````

#### Output

`````` Given : (n = 7,k = 3)
Result : 35

Given : (n = 6,k = 4)
Result : 15

Given : (n = 8,k = 2)
Result : 28``````
``````#
#   Python 3 Program
#   Binomial coefficient using dynamic programming

class BinomialCoefficient :
def biCoefficient(self, n, k) :
#    Formula nCr
#       n!
#    ––––––––––
#    k! (n -k)!
#  auxiliary space
c = [0] * (k + 1)
j = 0
#  Set initial value
while (j <= k) :
c[j] = 0
j += 1

#  Set first
c[0] = 1
i = 1
#  iterate the loop through by n
while (i <= n) :
#  Get minimum
if (k > i) :
j = i
else :
j = k

while (j > 0) :
c[j] = c[j] + c[j - 1]
j -= 1

i += 1

#  Display given n , k
print("\n Given : (n = ", n ,",k = ", k ,") ", end = "")
print("\n Result : ", c[k] )

def main() :
#  Test case

if __name__ == "__main__": main()``````

#### Output

`````` Given : (n =  7 ,k =  3 )
Result :  35

Given : (n =  6 ,k =  4 )
Result :  15

Given : (n =  8 ,k =  2 )
Result :  28``````
``````#   Ruby Program
#   Binomial coefficient using dynamic programming

class BinomialCoefficient
def biCoefficient(n, k)
#    Formula nCr
#       n!
#    ––––––––––
#    k! (n -k)!
#  auxiliary space
c = Array.new(k + 1) {0}
j = 0
#  Set initial value
while (j <= k)
c[j] = 0
j += 1
end

#  Set first
c[0] = 1
i = 1
#  iterate the loop through by n
while (i <= n)
#  Get minimum
if (k > i)
j = i
else
j = k
end

while (j > 0)
c[j] = c[j] + c[j - 1]
j -= 1
end

i += 1
end

#  Display given n , k
print("\n Given : (n = ", n ,",k = ", k ,") ")
print("\n Result : ", c[k] ,"\n")
end

end

def main()
#  Test case
end

main()``````

#### Output

`````` Given : (n = 7,k = 3)
Result : 35

Given : (n = 6,k = 4)
Result : 15

Given : (n = 8,k = 2)
Result : 28
``````
``````/*
Scala Program
Binomial coefficient using dynamic programming
*/
class BinomialCoefficient
{
def biCoefficient(n: Int, k: Int): Unit = {
//   Formula nCr
//      n!
//   ––––––––––
//   k! (n -k)!
// auxiliary space
var c: Array[Int] = Array.fill[Int](k + 1)(0);
var j: Int = 0;
// Set initial value
while (j <= k)
{
c(j) = 0;
j += 1;
}
// Set first
c(0) = 1;
var i: Int = 1;
// iterate the loop through by n
while (i <= n)
{
// Get minimum
if (k > i)
{
j = i;
}
else
{
j = k;
}
while (j > 0)
{
c(j) = c(j) + c(j - 1);
j -= 1;
}
i += 1;
}
// Display given n , k
print("\n Given : (n = " + n + ",k = " + k + ") ");
print("\n Result : " + c(k) + "\n");
}
}
object Main
{
def main(args: Array[String]): Unit = {
var task: BinomialCoefficient = new BinomialCoefficient();
// Test case
}
}``````

#### Output

`````` Given : (n = 7,k = 3)
Result : 35

Given : (n = 6,k = 4)
Result : 15

Given : (n = 8,k = 2)
Result : 28``````
``````/*
Swift 4 Program
Binomial coefficient using dynamic programming
*/
class BinomialCoefficient
{
func biCoefficient(_ n: Int, _ k: Int)
{
//   Formula nCr
//      n!
//   ––––––––––
//   k! (n -k)!
// auxiliary space
var c: [Int] = Array(repeating: 0, count: k + 1);
var j: Int = 0;
// Set initial value
while (j <= k)
{
c[j] = 0;
j += 1;
}
// Set first
c[0] = 1;
var i: Int = 1;
// iterate the loop through by n
while (i <= n)
{
// Get minimum
if (k > i)
{
j = i;
}
else
{
j = k;
}
while (j > 0)
{
c[j] = c[j] + c[j - 1];
j -= 1;
}
i += 1;
}
// Display given n , k
print("\n Given : (n = ", n ,",k = ", k ,") ", terminator: "");
print("\n Result : ", c[k] );
}
}
func main()
{
// Test case
}
main();``````

#### Output

`````` Given : (n =  7 ,k =  3 )
Result :  35

Given : (n =  6 ,k =  4 )
Result :  15

Given : (n =  8 ,k =  2 )
Result :  28``````
``````/*
Kotlin Program
Binomial coefficient using dynamic programming
*/
class BinomialCoefficient
{
fun biCoefficient(n: Int, k: Int): Unit
{
//   Formula nCr
//      n!
//   ––––––––––
//   k! (n -k)!
// auxiliary space
var c: Array < Int > = Array(k + 1)
{
0
};
var j: Int = 0;
// Set initial value
while (j <= k)
{
c[j] = 0;
j += 1;
}
// Set first
c[0] = 1;
var i: Int = 1;
// iterate the loop through by n
while (i <= n)
{
// Get minimum
if (k > i)
{
j = i;
}
else
{
j = k;
}
while (j > 0)
{
c[j] = c[j] + c[j - 1];
j -= 1;
}
i += 1;
}
// Display given n , k
print("\n Given : (n = " + n + ",k = " + k + ") ");
print("\n Result : " + c[k] + "\n");
}
}
fun main(args: Array < String > ): Unit
{
// Test case
}``````

#### Output

`````` Given : (n = 7,k = 3)
Result : 35

Given : (n = 6,k = 4)
Result : 15

Given : (n = 8,k = 2)
Result : 28``````

## Time Complexity

The time complexity of the provided dynamic programming approach to compute binomial coefficients is O(n * k). This is because the algorithm fills in a 2D array of size (n+1) x (k+1), and each entry is computed once using the recurrence relation. The space complexity is also O(n * k) due to the storage of the dynamic programming table.

## Comment

Please share your knowledge to improve code and content standard. Also submit your doubts, and test case. We improve by your feedback. We will try to resolve your query as soon as possible.

Categories
Relative Post