Computing binomial coefficient is very fundamental problem of mathematics and computer science. Binomial coefficient C(n, k) defines coefficient of the term xn in the expansion of (1 + x)n. 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 || 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 DP_BINOMIAL(n, k) // n is total number of items // k is the number of items to be selected from n for i ← 0 to n do for j ← 0 to k do if i ==j || j==0 then C[i, j] ← 1 else C[i, j] ← C[i – 1, j – 1] + C[i – 1, j] end end end return C[n][k]
- 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
Additional Reading: Read the applications of binomial coefficient