Combination
A selection of items from a set where order does not matter.
In mathematics, a combination is a selection of items from a set that has distinct members, such that the order of selection does not matter (unlike permutations). For example, given three fruits—an apple, an orange, and a pear—there are three combinations of two that can be drawn from this set: an apple and a pear; an apple and an orange; or a pear and an orange. More formally, a k-combination of a set S is a subset of k distinct elements of S. Combinations are fundamental in combinatorics and probability, with applications ranging from poker hands to binomial expansions.
- field
- Mathematics
- known_for
- Selection of items from a set where order does not matter; binomial coefficient
- notation
- C(n,k), C_k^n, (n choose k)
- formula
- C(n,k) = n! / (k!(n-k)!) for n ≥ k ≥ 0
Lore & Background
The concept of combination is defined as a selection of items from a set with distinct members, where the order of selection does not matter. For instance, from a set of three fruits—apple, orange, pear—the two-element combinations are apple and pear, apple and orange, and pear and orange. Two combinations are identical if and only if they have the same members, regardless of arrangement. The number of k-combinations from an n-element set is given by the binomial coefficient, denoted C(n,k) or (n choose k), and equals n! / (k!(n-k)!) when n ≥ k ≥ 0.
Reader's Guide
Combinations are a core concept in combinatorics, distinct from permutations in that order is irrelevant. The number of k-combinations from an n-element set is expressed by the binomial coefficient, which also appears as coefficients in the binomial expansion of (1+X)^n. This coefficient counts the number of ways to choose k items from n, and is zero when k > n. The formula can be derived from the fact that each k-combination has k! permutations, so the number of permutations P_k^n equals C_k^n × k!. The notation varies, including C(n,k), C_k^n, and (n choose k), but all refer to the same binomial coefficient.
Did You Know?
- A combination is a selection of items from a set where order does not matter, unlike permutations.
- The number of k-combinations from an n-element set is given by the binomial coefficient n!/(k!(n-k)!).
- The binomial coefficient (n choose k) appears in the expansion of (1+X)^n.
Frequently Asked Questions
What is Combination in combinatorics?
Combination refers to choosing a subset of items from a larger set where the sequence in which you pick them is irrelevant. Formally, a k-combination is simply a subset containing k distinct elements drawn from a set S.
What is the formula for calculating a Combination?
The standard expression is C(n,k) = n! / (k!(n−k)!), valid whenever n ≥ k ≥ 0. It is also commonly written as C_k^n or read aloud as "n choose k."
How does Combination differ from Permutation?
The key distinction is that in a combination the ordering of the selected items carries no meaning, whereas a permutation treats different orderings as distinct outcomes. For instance, picking an apple and a pear is the same combination whether you grab the apple first or the pear first, but they count as two separate permutations.
Why is Combination considered foundational in mathematics?
It underpins probability calculations, the binomial theorem, and a wide range of counting problems in combinatorics. Without the combination framework, fields from statistical mechanics to algorithm design would lack a basic tool for enumerating unordered selections.
More in Combinatorics 1-24
Elsewhere in the Combinatorics universe
Spotted an error? Know more?
This is a living reference — every entry is fact-audited, and reader corrections feed straight into our audit queue. Suggest an edit · See this site's audit record