Combinations

A combination is a way of selecting items from a larger collection where the order of selection does not matter. For example, choosing a committee of 3 students from a class of 20 is a combination problem: the group {Alice, Bob, Carol} is exactly the same committee as {Carol, Alice, Bob}. Because order is irrelevant, combinations always produce fewer distinct selections than permutations of the same size. Combinations appear throughout mathematics, probability, and everyday life. Any time you ask 'how many ways can I choose k things from n things, without caring about sequence?', you are counting combinations. They form the foundation for calculating probabilities of card hands, lottery outcomes, and sampling problems, and they appear as the binomial coefficients in Pascal's triangle and the Binomial Theorem. The notation for the number of combinations of n objects taken k at a time is written C(n, k), nCk, or most commonly as the binomial coefficient \binom{n}{k}, read 'n choose k'. Mastering combinations requires understanding the relationship between permutations and combinations, and recognising when a counting problem requires ordered versus unordered selection.

Key takeaways
  • Start with Permutations
  • Identify the Overcounting
  • Derive the Combination Formula
  • Key Symmetry Property
  • Boundary Cases

Start with Permutations

Recall that the number of ordered arrangements of k items chosen from n distinct items is the permutation P(n, k) = n! / (n - k)!. For example, choosing a president, vice-president, and secretary from 5 candidates gives P(5, 3) = 5!/2! = 60 ordered arrangements.

Identify the Overcounting

If we only want an unordered group of k items, every single group of k has been counted k! times in P(n, k) — once for each way those same k items can be rearranged. For k = 3, each unordered set has been counted 3! = 6 times. To correct for this, we divide P(n, k) by k!.

Derive the Combination Formula

Dividing the permutation count by k! cancels the overcounting: C(n, k) = P(n, k) / k! = n! / [k!(n - k)!]. This is the combination formula. For the example of choosing any 3 candidates from 5: C(5, 3) = 5! / (3! × 2!) = 120 / (6 × 2) = 10.

Key Symmetry Property

Notice that C(n, k) = C(n, n - k). Choosing 3 items to include from 5 is equivalent to choosing 2 items to exclude. This symmetry is visible in Pascal's triangle: each row is a palindrome. For instance, C(5, 3) = C(5, 2) = 10.

Boundary Cases

C(n, 0) = 1 for any n ≥ 0: there is exactly one way to choose nothing — the empty selection. Similarly, C(n, n) = 1: there is exactly one way to choose all n items. These boundary cases are important when working with sums like the Binomial Theorem, where all values from k = 0 to k = n appear.

The Key Equation

(nk)=n!k!(n−k)!\binom{n}{k} = \frac{n!}{k!(n-k)!}
  • n — Population size (dimensionless (count)): The total number of distinct items available for selection. Must be a non-negative integer.
  • k — Selection size (dimensionless (count)): The number of items chosen in each combination. Must satisfy 0 ≤ k ≤ n.
  • n! — n factorial (dimensionless): The product of all positive integers from 1 to n. For example, 5! = 5 × 4 × 3 × 2 × 1 = 120. By convention, 0! = 1.
  • k! — k factorial (dimensionless): Accounts for the k! orderings of the selected items that are all considered identical in a combination, effectively dividing out the overcounting.

Worked Example

Problem. A standard deck has 52 playing cards. A poker hand consists of 5 cards dealt to a player. How many distinct 5-card hands are possible? (Order does not matter — {A♠, K♠, Q♠, J♠, 10♠} is the same hand regardless of the order the cards were dealt.)

(525)=52!5!⋅47!=52×51×50×49×48120=2,598,960\binom{52}{5} = \frac{52!}{5! \cdot 47!} = \frac{52 \times 51 \times 50 \times 49 \times 48}{120} = 2{,}598{,}960

Answer. There are 2,598,960 distinct 5-card poker hands.

Figure
Diagram
Pascal's Triangle — Binomial Coefficients C(n,k)Each entry = C(row, position), row n from 0 to 511112113311464115101051n=0n=1n=2n=3n=4n=5C(5,2)=C(5,3)=10 — symmetry: C(n,k)=C(n,n−k)Each entry = sum of the two entries directly above it
Origins · 1 minBlaise Pascal and how this was discovered
BP
Blaise Pascal
1623–1662 · French

Pascal systematically studied the arithmetic triangle (now called Pascal's Triangle) in his 1653 work Traité du triangle arithmétique, connecting its entries to combinatorics and probability. He showed that the entries are exactly the binomial coefficients and used them to solve probability problems, including the famous Problem of Points about dividing stakes in an unfinished game. His work, conducted partly in correspondence with Pierre de Fermat, laid the groundwork for modern probability theory and combinatorics. Pascal built one of the first mechanical calculators, the Pascaline, at age 18 to help his father with tax computations — making him a pioneer in both pure mathematics and computing machinery.

  • Permutations — Combinations are derived directly from permutations by dividing out the k! orderings of the chosen items. Understanding permutations is essential for deriving and applying the combination formula.
  • Factorial Notation — The combination formula is expressed using factorials. Fluency with factorial notation and computation is required to evaluate C(n, k) correctly.
  • Binomial Theorem — The coefficients in the expansion of (a + b)^n are exactly the binomial coefficients C(n, k), so combinations are central to expanding powers of binomials.
  • Basic Probability — Many classical probability calculations — such as the probability of a specific poker hand or lottery outcome — require counting combinations in both numerator and denominator.