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)
	{
		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.

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.

New Comment