combination

In mathematics, a k-element combination drawn from a set S with n elements, is a subset of S having k elements that is unordered and without repetitions.

Combinations are closely related to k-permutations, the difference being that for k-permutations order matters.

k-combinations of n are denoted C^n_k\text{, } {}_nC_k\text{, } {}^nC_k\text{, } C_{n,k}\text{, } C(n,k)

The number of possible k-combinations of n is:

{}_nC_k = \dfrac{n!}{k!(n-k)!}

This is derived from what we know about k-permutations of n, specifically that the number of k-permutations of n is:

{}_nP_k = \dfrac{n!}{(n-k)!}

For each k-sized subset of S there are k! permutations. Since order does not matter with combinations, these k! permutations are actually all the same combination. This explains the k! term in the denominator of the {}_nC_k – it accounts for the fact that there are k! permutations for every k-sized subset we can choose from set S.

The values represented by {}_nC_k are also known as the binomial coefficients, denoted {n \choose k} and read, “n choose k.”

« Back to Glossary Index