Combination

This is an AoPSWiki Word of the Week for Nov 1-7

A combination is a way of choosing $r$ objects from a set of $n$ where the order in which the objects are chosen is irrelevant. We are generally concerned with finding the number of combinations of size $r$ from an original set of size $n$

Notation

The common forms of denoting the number of combinations of ${r}$ objects from a set of ${n}$ objects is:

$\binom{n}{r}$
${C}(n,r)$
$\,_{n} C_{r}$
$C_n^{r}$

Formula

${{n}\choose {r}} = \frac {n!} {r!(n-r)!}$

Derivation

Consider the set of letters A, B, and C. There are $3!$ different permutations of those letters. Since order doesn't matter with combinations, there is only one combination of those three. In general, since for every permutation of ${r}$ objects from ${n}$ elements $P(n,r)$ , there are ${r}!$ more ways to permute them than to choose them. We have ${r}!{C}({n},{r})=P(n,r)$ , or ${{n}\choose {r}} = \frac {n!} {r!(n-r)!}$ .

Formulas/Identities

$\binom{n-1}{r-1}+\binom{n-1}{r}=\binom{n}{r}$

$\binom{n}{r}=\frac{n}{r}\binom{n-1}{r-1}$

$\sum_{x=0}^{n} \binom{n}{x} = 2^n$

One of the many proofs is by first inserting $a = b = 1$ in to the binomial theorem. Because the combinations are the coefficients of $2^n$ , and a and b cancel out because they are 1, the sum is $2^n$ .

$\sum_{i=0}^{k}\binom{m}{i}\binom{n}{k-i}=\binom{m+n}{k}$

Examples

Links

[1]

Page

Toolbox

Search