From Algorithmist
Jump to navigation Jump to search

The Combination function is used in matematics to determine the possible number of available choices from a given group. It has two varibles: n, the number of items available to pick, and k, the number of items to pick.

This function appears in Pascal's Triangle.


Combination is normally calculated by factorials, but the straight forward calculation may cause overflow on some systems:

combination (n, k) = factorial (n) / (factorial(k) * factorial(n-k))

The brute force method, while simple, is highly inefficient, even with dynamic programming:

combination (n, k) = combination (n-1, k) + combination (n-1, k-1)

In most problems, a more efficient method is as follows:

combination (n,k) =
  for (i = 0; i < k; ++i)
    c = c * (n - i)
    c = c / (i + 1)