Combinations are studied in
combinatorics: let
S be a
set; the combinations of this set are its subsets. 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
nC
k,
nC
k or as
- <math>{n \choose k},</math>
or occasionally as C(
n,
k).
One method of deriving a formula for nCk proceeds as follows:
- Count the number of ways in which one can make an ordered 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:
- <math> {n \choose k} = \frac{P(n,k)}{P(k,k)} </math>
Since
- <math> P(n,k) = \frac{n!}{(n-k)!} </math>
(see
factorial), we find
- <math> {n \choose k} = \frac{n!}{k! \cdot (n-k)!} </math>
It is useful to note that C(n, k) can also be found using Pascal's triangle, as explained in the binomial coefficient article.