# Combination

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.

## Calculation[edit]

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) = { c=1 for (i = 0; i < k; ++i) { c = c * (n - i) c = c / (i + 1) } }