|
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 or
k-subsets of set with n elements is the binomial coefficient "n choose k", written as
nCk, nCk or as
-
or occasionally as C(n, k).
For more information, see Combinations and
permutations.
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:
-
Since
-
(see factorial), we find
-
It is useful to note that C(n, k) can also be found using Pascal's triangle, as explained in the binomial coefficient article.
|