Combination
A selection of items from a set where order does not matter.
In mathematics, a combination is a way of picking items from a group where the order doesn't matter—this is what sets it apart from a permutation. Take three fruits: an apple, an orange, and a pear. If you choose two of them, the possible combinations are apple and pear, apple and orange, or pear and orange. More precisely, a k-combination from a set S is a subset containing k distinct elements of S. Two combinations are considered the same only if they contain exactly the same members, regardless of how those members are arranged. When a set has n elements, the number of k-combinations is written as \( C(n,k) \) or \( C_k^n \), and it equals the binomial coefficient: \[ \binom{n}{k} = \frac{n(n-1)\dotsb(n-k+1)}{k(k-1)\dotsb1} = \frac{n!}{k!(n-k)!} \] for \( n \geq k \geq 0 \). This formula comes from the fact that each k-combination has \( k! \) permutations, so \( P_k^n = C_k^n \times k! \), or \( C_k^n = P_k^n / k! \). The collection of all k-combinations of a set S is often shown as \( \binom{S}{k} \).
A combination is essentially a selection of n items taken k at a time without repetition. When repetition is allowed, the terms k-combination with repetition, k-multiset, or k-selection are used. In the fruit example, if you could pick two of the same fruit, you'd get three more selections: two apples, two oranges, and two pears.
While listing all combinations is easy for a small set like three fruits, it becomes impractical as the set grows. For instance, a poker hand is a 5-combination from a 52-card deck—the five cards are all different, and their order doesn't matter. There are 2,598,960 such combinations, so the chance of drawing any specific hand at random is 1 in 2,598,960.
The number of k-combinations from a set of n elements is commonly written in textbooks as \( C(n,k) \), \( C_k^n \), \( {}_nC_k \), \( {}^nC_k \), \( C_{n,k} \), or \( C_n^k \). This same number appears in many other areas of mathematics, where it is denoted by \( \binom{n}{k} \).
- 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
In mathematics, a combination is a selection of items from a set of distinct members where the order of selection is irrelevant, distinguishing it from a permutation. For example, from a set of three fruits—apple, orange, pear—the three possible two-element combinations are apple and pear, apple and orange, and pear and orange. Two combinations are considered identical only if they contain the exact same members, regardless of how those members are arranged. More formally, a k-combination of a set S is a subset containing k distinct elements of S. The number of such k-combinations from an n-element set is given by the binomial coefficient, commonly denoted as C(n,k) or "n choose k," which equals n! / (k!(n-k)!) for n ≥ k ≥ 0. This formula arises because each k-combination corresponds to k! permutations of its elements, and the total number of k-permutations from n items is n!/(n-k)!. The binomial coefficient also appears as the coefficient in the binomial expansion of (1+X)^n, where the term X^k has a coefficient equal to the number of k-combinations. When k exceeds n/2, a symmetry relation holds: C(n,k) = C(n, n-k), as each k-combination has a complementary (n-k)-combination. For practical computation, the formula can be evaluated using integer arithmetic by sequential multiplication and division, ensuring intermediate results remain binomial coefficients. Enumerating all k-combinations of a set establishes a bijection from an interval of integers to the collection of subsets. When repetition of elements is allowed, the terms k-combination with repetition, k-multiset, or k-selection are used; for instance, allowing two of the same fruit in the earlier example adds three more selections.
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
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