# Binomial Coefficient

Hello Everyone,

A binomial coefficient, C(n, k) can be defined as the coefficient of x^k in the expansion of (1 + x)^n.

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 a 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 be recursively calculated using the following standard formula for Binomial Coefficients.

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

Following is a simple recursive implementation that simply follows the recursive structure mentioned above.

`// A naive recursive C++ implementation`

`#include <bits/stdc++.h>`

`using` `namespace` `std;`

`// Returns value of Binomial Coefficient C(n, k)`

`int` `binomialCoeff(` `int` `n, ` `int` `k)`

`{`

` ` `// Base Cases`

` ` `if` `(k > n)`

` ` `return` `0;`

` ` `if` `(k == 0 || k == n)`

` ` `return` `1;`

` ` `// Recur`

` ` `return` `binomialCoeff(n - 1, k - 1)`

` ` `+ binomialCoeff(n - 1, k);`

`}`

`/* Driver code*/`

`int` `main()`

`{`

` ` `int` `n = 5, k = 2;`

` ` `cout << ` `"Value of C("` `<< n << ` `", "` `<< k << ` `") is "`

` ` `<< binomialCoeff(n, k);`

` ` `return` `0;`

`}`

Output

Value of C(5, 2) is 10

2) Overlapping Subproblems
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.

Binomial Coefficients Recursion tree for C(5,2)

Since the same subproblems are called again, this problem has Overlapping Subproblems property. So the Binomial Coefficient problem has both properties, re-computations of the same subproblems can be avoided by constructing a temporary 2D-array C[][] in a bottom-up manner. Following is Dynamic Programming based implementation.

`// A Dynamic Programming based solution that uses`

`// table C[][] to calculate the Binomial Coefficient`

`#include <bits/stdc++.h>`

`using` `namespace` `std;`

`// 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 previously`

` ` `// 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 < b) ? a : b; }`

`// Driver Code`

`int` `main()`

`{`

` ` `int` `n = 5, k = 2;`

` ` `cout << ` `"Value of C["` `<< n << ` `"]["` `<< k << ` `"] is "`

` ` `<< binomialCoeff(n, k);`

`}`

Output

Value of C[5][2] is 10

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