Binomial Coefficient using Dynamic Programming

Computing binomial coefficient is very fundamental problem of mathematics and computer science. Binomial coefficient C(n, k) defines coefficient of the term xⁿ in the expansion of (1 + x)ⁿ. C(n, k) also defines the number of ways to select any k items out of n items. Mathematically it is defined as,

C(n, k) can be found in different ways. In this article we will discuss divide and conquer as well as dynamic programing approach.

Binomial Coefficient using Divide and Conquer

• Divide and conquer divides the problem of size C(n, k), in two sub problems, each of size C(n – 1, k – 1) and C(n – 1, k) respectively. Solution of larger problem is build by adding solution of these two sub problems.
• Structure of binomial coefficient problem using divide and conquer approach is described as :

Where      n > k > 0

• Recursive algorithm of solving binomial coefficient problem using divide and conquer approach is described below :

Algorithm BINOMIAL_DC (n, k)
// n is total number of items
// k is the number of items to be selected from n

if k == 0 or k == n  then
    return 1
else
    return DC_BINOMIAL(n – 1, k – 1) + DC_BINOMIAL(n – 1, k)
end

Following tree shows how problem subdivision occurs and how solutions are merged to build the final solution

As we can see, we have to do lots of rework in calculation, due to independent sub problems. While in case of dynamic programming, problems are dependent, and we can utilize previously calculated result for future use.

Binomial Coefficient using Dynamic Programming

• Many sub problems are called again and again, since they have an overlapping sub problems property. Re-computations of the same sub problems is avoided by storing their results in the temporary array C[i, j] in a bottom up manner.
• The optimal substructure for using dynamic programming is stated as,

In Table, index i indicates row and index j indicates column

• This tabular representation of binomial coefficients is also known as Pascal’s triangle.
• Algorithm to solve this problem using dynamic programming is shown below

Algorithm BINOMIAL_DC (n, k)
// n is total number of items
// k is the number of items to be selected from n

if k == 0 or k == n then
    return 1
else
    return DC_BINOMIAL(n – 1, k – 1) + DC_BINOMIAL(n – 1, k)
end

Complexity analysis

• The cost of the algorithm is cost of filing out the table. Addition is the basic operation. Because k ≤ n, the sum needs to be split into two parts, only the half of the table needs to be filled out for i < k and the remaining part of the table is filled out across the entire row.
• The growth pattern of these numbers is shown in the following figure.

T(n, k) = sum for upper triangle + sum for the lower rectangle

Some Popular Problems Solved using Dynamic Programming

• Binomial Coefficient
• Making a Change
• Knapsack Problem
• Multistate Graph Problem
• Optimal Binary Search Tree
• Matrix Chain Multiplication
• Longest Common Subsequence
• Bellman-Ford (Single Source Shortest Path) Algorithm
• Floyd-Warshall (All Pair Shortest Path) Problem
• Assembly Line Scheduling
• Travelling Salseman Problem
• Flow Shop Scheduling

---

Additional Reading: Read the applications of binomial coefficient