Combination
Statistics & ProbabilityA combination is a selection of items from a group where order does not matter.
Formula
C(n, r) = \dfrac{n!}{r!(n-r)!}
Definition
A combination is a way to choose items from a group when the order does not matter. It counts how many different selections are possible.
Example
How many ways can you choose $2$ students from a group of $5$ to form a committee? $C(5,2) = 10$. Choosing Alice and Bob is the same as choosing Bob and Alice, so order does not matter.
Key Insight
Use combinations when ORDER does NOT matter. Choosing pizza toppings is a combination: pepperoni-and-mushroom is the same as mushroom-and-pepperoni.
Definition
A combination of $n$ items taken $r$ at a time is an unordered selection: $C(n,r) = n!/(r!(n-r)!)$, also written as "$n$ choose $r$" or $C(n,r)$. Since order does not matter, $C(n,r) = P(n,r)/r!$, dividing by $r!$ to remove duplicate orderings of the same $r$ items.
Example
A lottery requires choosing $6$ numbers from $1$-$49$. $C(49,6) = 49!/(6! \cdot 43!) = 13{,}983{,}816$ possible combinations. Each ticket is one combination; order of selection does not affect whether you win.
Key Insight
$C(n,r) = C(n,n-r)$: choosing $r$ items to include is the same count as choosing $n-r$ items to exclude. This symmetry means $C(10,3) = C(10,7) = 120$.
Definition
The binomial coefficient $C(n,r)$ counts $r$-element subsets of an $n$-element set. Pascal's identity: $C(n,r) = C(n-1,r-1)+C(n-1,r)$ generates Pascal's triangle recursively. The binomial theorem states $(x+y)^n = \sum_{r=0}^{n} C(n,r)x^r y^{n-r}$, connecting combinations to polynomial algebra.
Example
In the binomial distribution $B(n,p)$, the probability of exactly $r$ successes is $C(n,r)p^r(1-p)^{n-r}$. The $C(n,r)$ factor counts the number of ways to arrange $r$ successes and $(n-r)$ failures in $n$ trials.
Key Insight
The Vandermonde identity: $C(m+n,r) = \sum_{k=0}^{r} C(m,k)C(n,r-k)$ combines subsets from two disjoint sets and has applications in combinatorics, generating functions, and hypergeometric functions.