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

• C
• Java
• C++
• C#
• Php
• Node Js
• Python
• Ruby
• Scala
• Swift 4
• Kotlin

// 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;
}

 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);
	}
}

 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;
}

 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);
	}
}

 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();

 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();

 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()

 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()

 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);
	}
}

 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();

 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);
}

 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.