# Calculation of binomial Co-efficient using Dynamic Programming

Posted By on November 5, 2014

Following are common definition of Binomial Coefficients.
1) A binomial coefficient C(n, k) can be defined as the coefficient of X^k in the expansion of (1 + X)^n.

2) A binomial coefficient C(n, k) also gives the number of ways, disregarding order, that k objects can be chosen from among n objects; more formally, the number of k-element subsets (or k-combinations) of an n-element set.

The Problem
Write a function that takes two parameters n and k and returns the value of Binomial Coefficient C(n, k). For example, your function should return 6 for n = 4 and k = 2, and it should return 10 for n = 5 and k = 2.

1) Optimal Substructure
The value of C(n, k) can recursively calculated using following standard formula for Binomial Cofficients.

```   C(n, k) = C(n-1, k-1) + C(n-1, k)
C(n, 0) = C(n, n) = 1
```

2) Overlapping Subproblems
Following is simple recursive implementation that simply follows the recursive structure mentioned above.

 `// A Naive Recursive Implementation` `#include` `// Returns value of Binomial Coefficient C(n, k)` `int` `binomialCoeff(``int` `n, ``int` `k)` `{` `  ``// Base Cases` `  ``if` `(k==0 || k==n)` `    ``return` `1;` `  ``// Recur` `  ``return`  `binomialCoeff(n-1, k-1) + binomialCoeff(n-1, k);` `}` `/* Drier program to test above function*/` `int` `main()` `{` `    ``int` `n = 5, k = 2;` `    ``printf``(``"Value of C(%d, %d) is %d "``, n, k, binomialCoeff(n, k));` `    ``return` `0;` `}`

It should be noted that the above function computes the same subproblems again and again. See the following recursion tree for n = 5 an k = 2. The function C(3, 1) is called two times. For large values of n, there will be many common subproblems.

```                             C(5, 2)
/
C(4, 1)                           C(4, 2)
/                             /
C(3, 0)   C(3, 1)             C(3, 1)               C(3, 2)
/                   /                    /
C(2, 0)    C(2, 1)      C(2, 0) C(2, 1)          C(2, 1)  C(2, 2)
/                      /               /
C(1, 0)  C(1, 1)      C(1, 0)  C(1, 1)   C(1, 0)  C(1, 1)
```

Since same suproblems are called again, this problem has Overlapping Subprolems property. So the Binomial Coefficient problem has both properties (see this and this) of a dynamic programming problem. Like other typical Dynamic Programming(DP) problems, recomputations of same subproblems can be avoided by constructing a temporary array C[][] in bottom up manner. Following is Dynamic Programming based implementation.

 `// A Dynamic Programming based solution that uses table C[][] to calculate the ` `// Binomial Coefficient ` `#include` `// Prototype of a utility function that returns minimum of two integers` `int` `min(``int` `a, ``int` `b);` `// Returns value of Binomial Coefficient C(n, k)` `int` `binomialCoeff(``int` `n, ``int` `k)` `{` `    ``int` `C[n+1][k+1];` `    ``int` `i, j;` `    ``// Caculate value of Binomial Coefficient in bottom up manner` `    ``for` `(i = 0; i <= n; i++)` `    ``{` `        ``for` `(j = 0; j <= min(i, k); j++)` `        ``{` `            ``// Base Cases` `            ``if` `(j == 0 || j == i)` `                ``C[i][j] = 1;` `            ``// Calculate value using previosly stored values` `            ``else` `                ``C[i][j] = C[i-1][j-1] + C[i-1][j];` `        ``}` `    ``}` `    ``return` `C[n][k];` `}` `// A utility function to return minimum of two integers` `int` `min(``int` `a, ``int` `b)` `{` `    ``return` `(a

Time Complexity: O(n*k)
Auxiliary Space: O(n*k)

Following is a space optimized version of the above code. The following code only uses O(k). Thanks to AK for suggesting this method.

 `// A space optimized Dynamic Programming Solution` `int` `binomialCoeff(``int` `n, ``int` `k)` `{` `    ``int``* C = (``int``*)``calloc``(k+1, ``sizeof``(``int``));` `    ``int` `i, j, res;` `    ``C[0] = 1;` `    ``for``(i = 1; i <= n; i++)` `    ``{` `        ``for``(j = min(i, k); j > 0; j--)` `            ``C[j] = C[j] + C[j-1];` `    ``}` `    ``res = C[k];  ``// Store the result before freeing memory` `    ``free``(C);  ``// free dynamically allocated memory to avoid memory leak` `    ``return` `res;` `}`

Time Complexity: O(n*k)
Auxiliary Space: O(k)

#### Posted by Akash Kurup

Founder and C.E.O, World4Engineers Educationist and Entrepreneur by passion. Orator and blogger by hobby

Website: http://world4engineers.com