In mathematics, Binomial Coefficients are the positive integers that occur as coefficients in the binomial theorem.
A binomial coefficient is the coefficient of the term (x^{k}) in the polynomial expansion of (1 + x)^{n} and is indexed by a pair of integers n >= k >= 0
In this post, we will denote it as bc(n, k).
For example: The fourth power of (1 + x) is –
(1 + x)^{4} = 1 + 4x + 6x^{2} + 4x^{3} + x^{4} Writing this expression in terms of Binomial Coefficients - (1 + x)^{4} = bc(4,0) * x^{0} + bc(4,1) * x^{1} + bc(4,2) * x^{2} + bc(4,3) * x^{3} + bc(4,4) * x^{4} (1 + x)^{4} = 1 * x^{0} + 4 * x^{1} + 6 * x^{2} + 4 * x^{3} + 1 * x^{4} The Binomial coefficient for n=4 and k=2 is bc(4, 2) = 6, the coefficient of (x^{2}) in the expansion of (1+x)^{4}.
Problem is – given values of n and k, find the binomial coefficient bc(n, k).
Let’s have a look at few (1+x)^{n} expansions:
N | Expression |
0 | (1+x)^{0} = 1 |
1 | (1+x)^{1} = (1+x) |
2 | (1+x)^{2} = (1 + 2x + x^{2}) |
3 | (1+x)^{3} = (1+ 3x + 3x^{2} + x^{3}) |
4 | (1+x)^{4} = (1 + 4x + 6x^{2} + 4x^{3} + x^{4}) |
5 | (1+x)^{5} = (1 + 5x + 10x^{2} + 10x^{3} + 5x^{4} + x^{5}) |
6 | (1+x)^{6} = (1 + 6x + 15x^{2} + 20x^{3} + 15x^{4} + 6x^{5} + x^{6}) |
7 | (1+x)^{7} = (1 + 7x + 21x^{2} + 35x^{3} + 35x^{4} + 21x^{5} + 7x^{6} + x^{7}) |
The binomial coefficients from these expansions can be arranged to form following triangle like structure called Pascal’s Triangle:
From Pascal’s triangle, we observe that an entry in any of the rows is addition of two entries from the row above –
bc(n, k) = bc(n-1, k-1) + bc(n-1, k)
This shows this problem has optimal substructure (i.e. an optimal solution can be constructed from optimal solutions of subproblems). Also we can observe that first and last binomial coefficients of each are 1 i.e. –
Recursive Approach C++ implementationbc(n, 0) = bc(n, n) = 1
long long int findBinomialCoeff (int n, int k){ if(k == 0 || n == k) return 1; return findBinomialCoeff (n-1, k-1) + findBinomialCoeff (n-1, k); } int main(void){ int n = 4, k=2; long long int binomialCoeff = findBinomialCoeff(n, k); printf("%lld", binomialCoeff); return 0; }
Same can be implemented in Java as well.
Recursive Approach Java implementationimport java.util.*; class BinomialCoefficient { static int findBinomialCoeff (int n, int k){ if(k == 0 || n == k) return 1; return findBinomialCoeff (n-1, k-1) + findBinomialCoeff (n-1, k); } public static void main(String[] args){ int n = 4, k=2; int binomialCoeff = findBinomialCoeff(n, k); System.out.printf("%d", binomialCoeff); } }
The recursive code has exponential time complexity, let’s have a look at the reasoning behind this:
In this example of finding Binomial coefficient for n=5 and k=3, subproblems such as bc(3,2) and bc(2,2) are calculated again and again. Our recursive algorithm for this problem solves the same subproblem over and over. These are called overlapping subproblems.
As the two properties required for using Dynamic Programming : optimal substructure and overlapping subproblems are holding here, we can use DP for this problem.
Binomial coefficient : Dynamic Programming Approach
In DP, we start calculating from the bottom and move up towards the final solution. Solution of all subproblems are stored in a 2D array / DP table so that they can be reused when required.
Binomial coefficient with dynamic programming C++long long int findBinomialCoeff (int n, int k){ long long int DP_table[n+1][k+1]; for(int i=0; i<=n; ++i){ for(int j=0; j <= min(i,k); ++j){ if (j == 0 || i == j) dp[i][j] = 1; else dp[i][j] = dp[i-1][j-1] + dp[i-1][j]; } } return dp[n][k]; }
Java implementation is very similar. Java implementation
class BinomialCoefficient{
static int min(int a, int b){
return (a<b) ? a : b;
}
static int findBinomialCoeff (int n, int k){
int dp[][] = new int [n+1][k+1];
for(int i=0; i<=n; ++i){
for(int j=0; j <= min(i,k); ++j){
if (j == 0 || i == j) dp[i][j] = 1;
else dp[i][j] = dp[i-1][j-1] + dp[i-1][j];
}
}
return dp[n][k];
}
[/code]
The time complexity of the dynamic programming approach to implementing the binomial coefficient is O(nk) whereas space complexity is O(nk)
The space complexity can be reduced by storing just the last row of Pascal’s triangle and that too just the (k+1) elements from the last row are required, with this approach instead of a 2D array we can work with a 1D array.
This article is contributed by Bhushan Aggrawal.