Combination

In combinatorial mathematics, a combination is an un-ordered collection of unique elements. Given S, the set of all possible unique elements, a combination is a subset of the elements of S. The order of the elements in a combination is not important (two lists with the same elements in different orders are considered to be the same combination). Also, the elements cannot be repeated in a combination (every element appears uniquely once). A k-combination (or k-subset) is a subset with k elements. The number of k-combinations (each of size k) from a set S with n elements (size n) is the binomial coefficient "n choose k", written as nCk, nCk or as

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 = P(n,k).
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 = P(k,k):

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.

[edit]
Efficient calculation
In trying to find the value of (for example) one should not compute 20!, which is a huge number. Instead, an initial cancellation of 20! with 16! yields

which can be further cancelled before multiplying. The denominator in every case cancels out completely.

The following arrangement is also convenient: ((((((17/1)18)/2)19)/3)20)/4.

Page1

Page2

Page3

Page4

Page5