Combinations

Let S be a set. The combinations of this set are its subset. A k-combination is a subset of with k elements.

The order of listing of elements in these subsets is not important in combinations, two lists with the same elements in different orders are considered the same combination.

The number of k-combinations of set of n elements if the binomial number 'n over k'.

One method of counting combinations of k elements from a set of n elements proceeds as follows:

1. We count the number of ways in which we can make a list of k elements from the set of n. This is equivalent to calculating the number of Permutations.
2. 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.

• _nC_k = _nP_k / _kP_k

Since _nP_k = n!/(n-k)!, we find

• _nC_k = n!/(k!*(n-k)!)

It is useful to note that _nC_k can be found using the [Pascal Triangle]?.