combination

In mathematics, a combination is a selection of k items from a set of n distinct elements where the order of selection does not matter. This concept is contrasted with a permutation, where order is important. For example, choosing 3 players from a team of 5 focuses on who is chosen, not the sequence in which they are picked.

The number of k-element combinations from an n-element set is given by the binomial coefficient C(n, k) = n! / (k!(n − k)!). This counts combinations without repetition (each item can be chosen at most once). When k > n, the value is zero. If repetition is allowed (forming multisets), the number of size-k selections from n types is C(n + k − 1, k).

Combinations have wide applications in probability, statistics, and counting problems. They are used to determine the number of possible committees, lottery tickets, or card hands when the order of selection is irrelevant. In probability, ratios of combinations often yield the likelihood of events such as drawing a given hand or sample.

These ideas connect to broader mathematical results. The binomial coefficient C(n, k) appears as coefficients in the expansion of (x + y)^n, a relationship summarized by Pascal’s triangle. Notation varies, with C(n, k) or “n choose k” commonly used to denote the same quantity.

Common cautions include distinguishing combinations from permutations and recognizing whether repetition is allowed. For large n, factorials can become unwieldy, so iterative, multiplicative, or recursive methods are used to compute C(n, k) efficiently.