Combination
A 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 order does not matter; it counts how many different selections are possible. A combination of $n$ items taken $r$ at a time is an unordered selection: $C(n,r) = n!/(r!(n-r)!)$, also written "$n$ choose $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. Formally, 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, and the binomial theorem states $(x+y)^n = \sum_{r=0}^{n} C(n,r)x^r y^{n-r}$.
Example
How many ways can you choose $2$ students from a group of $5$ to form a committee? $C(5,2) = 10$, since choosing Alice and Bob is the same as choosing Bob and Alice. A lottery requiring $6$ numbers from $1$-$49$ has $C(49,6) = 13{,}983{,}816$ possible combinations, with each ticket being one combination regardless of selection order. In the binomial distribution $B(n,p)$, the probability of exactly $r$ successes is $C(n,r)p^r(1-p)^{n-r}$, where $C(n,r)$ counts the number of ways to arrange $r$ successes and $(n-r)$ failures in $n$ trials.
Key Insight
Use combinations when order does NOT matter: choosing pizza toppings is a combination since pepperoni-and-mushroom is the same as mushroom-and-pepperoni, and $C(n,r) = C(n,n-r)$, choosing $r$ items to include is the same count as choosing $n-r$ items to exclude, a symmetry meaning $C(10,3) = C(10,7) = 120$. 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.