Let
S be a
set. The
combinations of this set are its subset. A
k-combination
is a subset of
S with
k elements.
The order of listing the elements is not important in combinations: two lists with the same elements in different orders are considered to be the same combination.
The number of
k-combinations of set with
n elements is the
binomial coefficient "
n choose
k", written as C(
n,
k).
One method of determining a formula for C(n, k) proceeds as follows:
- We count the number of ways in which we can make a list of k different elements from the set of n. This is equivalent to calculating the number of k-permutations.
- Recognizing that we have listed every subset many times, we correct the calculation by dividing by the number of different lists containing the same k elements:
- C(n, k) = P(n, k) / P(k, k)
Since P(
n,
k) =
n! / (
n-k)! (see
factorial), we find
- C(n, k) = n! / (k! * (n-k)!)
It is useful to note that C(n, k) can also be found using the Pascal triangle, as explained in the binomial coefficient article.