Algorithms: Binomial Coefficients

Algorithms

Binomial Coefficients

Wikipedia "In mathematics, any of the positive integers that occurs as a coefficient in the binomial theorem is a binomial coefficient. Commonly, a binomial coefficient is indexed by a pair of integers n ≥ k ≥ 0 and is written .It is the coefficient of the x^k term in the polynomial expansion of the binomial power (1 + x)ⁿ, and it is given by the formula

Arranging binomial coefficients into rows for successive values of n, and in which k ranges from 0 to n, gives a triangular array called Pascal's triangle.
As with the Fibonacci numbers, the binomial coefficients can be calculated recursively - making use of the relation:

ⁿC_m = ^n-1C_m-1 + ^n-1C_m A similar analysis to that used for the Fibonacci numbers shows that the time complexity using this approach is also the binomial coefficient itself.

If we construct Pascal's triangle, the n^th row gives all the values,
ⁿC_m, m = 0,n:

              1
            1   1
          1   2   1
        1   3   3   1
      1   4   6   4   1
    1   5  10  10   5   1
  1   6  15  20  15   6   1
1   7  21  35  35  21   7   1

Each entry takes O(1) time to calculate and there are O(n²) of them. So this calculation of the coefficients takes O(n²) time. But it uses O(n²) space to store the coefficients.

Continue on to Optimal Binary Search Trees