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:
- Alice, Bob, Carol
- Alice, Bob, David
- Alice, Bob, Emma
- Alice, Bob, Frank
- Alice, Bob, Grace
- Alice, Carol, David
- Alice, Carol, Emma
- Alice, Carol, Frank
- Alice, Carol, Grace
- Alice, David, Emma
- Alice, David, Frank
- Alice, David, Grace
- Alice, Emma, Frank
- Alice, Emma, Grace
- Alice, Frank, Grace
- Bob, Carol, David
- Bob, Carol, Emma
- Bob, Carol, Frank
- Bob, Carol, Grace
- Bob, David, Emma
- Bob, David, Frank
- Bob, David, Grace
- Bob, Emma, Frank
- Bob, Emma, Grace
- Bob, Frank, Grace
- Carol, David, Emma
- Carol, David, Frank
- Carol, David, Grace
- Carol, Emma, Frank
- Carol, Emma, Grace
- Carol, Frank, Grace
- David, Emma, Frank
- David, Emma, Grace
- David, Frank, Grace
- 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
- Initialize a 2D array
dp
of size (n+1) x (k+1) to store the binomial coefficients. - 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]
.
- 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)
{
BinomialCoefficient task = new BinomialCoefficient();
// Test case
task.biCoefficient(7, 3);
task.biCoefficient(6, 4);
task.biCoefficient(8, 2);
}
}
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()
{
BinomialCoefficient task = BinomialCoefficient();
// Test case
task.biCoefficient(7, 3);
task.biCoefficient(6, 4);
task.biCoefficient(8, 2);
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)
{
BinomialCoefficient task = new BinomialCoefficient();
// Test case
task.biCoefficient(7, 3);
task.biCoefficient(6, 4);
task.biCoefficient(8, 2);
}
}
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()
{
$task = new BinomialCoefficient();
$task->biCoefficient(7, 3);
$task->biCoefficient(6, 4);
$task->biCoefficient(8, 2);
}
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()
{
var task = new BinomialCoefficient();
// Test case
task.biCoefficient(7, 3);
task.biCoefficient(6, 4);
task.biCoefficient(8, 2);
}
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() :
task = BinomialCoefficient()
# Test case
task.biCoefficient(7, 3)
task.biCoefficient(6, 4)
task.biCoefficient(8, 2)
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()
task = BinomialCoefficient.new()
# Test case
task.biCoefficient(7, 3)
task.biCoefficient(6, 4)
task.biCoefficient(8, 2)
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
task.biCoefficient(7, 3);
task.biCoefficient(6, 4);
task.biCoefficient(8, 2);
}
}
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()
{
let task: BinomialCoefficient = BinomialCoefficient();
// Test case
task.biCoefficient(7, 3);
task.biCoefficient(6, 4);
task.biCoefficient(8, 2);
}
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
{
var task: BinomialCoefficient = BinomialCoefficient();
// Test case
task.biCoefficient(7, 3);
task.biCoefficient(6, 4);
task.biCoefficient(8, 2);
}
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.
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.
New Comment