Combinations
A combination counts the number of ways to choose \(r\) items from a set of \(n\), when the order of selection does not matter. It is the foundational counting tool in probability, used whenever you need to count subsets, groups, or unordered selections.
Definition
The number of ways to choose \(r\) items from \(n\) distinct items, without repetition and without regard to order, is the binomial coefficient:
\[\binom{n}{r} = \frac{n!}{r!\,(n-r)!}\]
Also written \(C(n,r)\) or \(C_n^r\). Here \(n!\) (n factorial) is the product of all positive integers up to \(n\): \(n! = n \times (n-1) \times \cdots \times 2 \times 1\), with \(0! = 1\) by convention.
How many ways can a 5-person committee be formed from a department of 12 employees?
\[\binom{12}{5} = \frac{12!}{5!\,7!} = \frac{12 \times 11 \times 10 \times 9 \times 8}{5 \times 4 \times 3 \times 2 \times 1} = \frac{95040}{120} = 792\]
There are 792 possible committees. The order in which members are chosen does not matter: {Alice, Bob, Carol, Dan, Eve} is the same committee regardless of selection order.
Combinations vs permutations
The key question is always: does order matter?
- Order does not matter: use combinations. Forming a team, choosing a subset, drawing a hand of cards.
- Order matters: use permutations. Ranking candidates, assigning roles, arranging objects in a sequence.
The relationship between the two:
\[P(n,r) = \binom{n}{r} \times r!\]
Every combination of \(r\) items can be arranged in \(r!\) different orders, giving the number of permutations. Dividing by \(r!\) removes the ordering and gives the combination count.
⚠️ The most common mistake: using permutations when order does not matter
If 3 people are chosen from 10 to form a committee, the answer is \(\binom{10}{3} = 120\), not \(P(10,3) = 720\). Using permutations overestimates by a factor of \(3! = 6\) because it counts {A,B,C}, {A,C,B}, {B,A,C}, {B,C,A}, {C,A,B}, {C,B,A} as six different outcomes when they are all the same committee.
Ask before calculating: if I swap the order of the selected items, do I get a different outcome? If no, use combinations.
Properties
- Symmetry
\[\binom{n}{r} = \binom{n}{n-r}\]
Choosing \(r\) items to include is equivalent to choosing \(n-r\) items to exclude. For example, \(\binom{10}{3} = \binom{10}{7} = 120\). Use the smaller of \(r\) and \(n-r\) in calculations to minimize arithmetic.
- Boundary values
\[\binom{n}{0} = \binom{n}{n} = 1\]
There is exactly one way to choose nothing, and exactly one way to choose everything.
- Pascal’s identity
\[\binom{n}{r} = \binom{n-1}{r-1} + \binom{n-1}{r}\]
Each combination either includes a specific item (the remaining \(r-1\) chosen from \(n-1\)) or excludes it (all \(r\) chosen from \(n-1\)). This identity generates Pascal’s triangle, where each entry is the sum of the two entries above it.
- Sum of all combinations
\[\sum_{r=0}^{n} \binom{n}{r} = 2^n\]
The total number of subsets of a set with \(n\) elements is \(2^n\). Each element is either included or excluded, giving \(2\) choices per element.
Examples
Quality control sampling
A batch of 50 components is received, 6 of which are known to be defective. A quality engineer samples 8 components at random. How many possible samples contain exactly 2 defective items?
Choose 2 defectives from 6, and 6 good from 44:
\[\binom{6}{2} \times \binom{44}{6} = 15 \times 7{,}059{,}052 = 105{,}885{,}780\]
Total possible samples of size 8:
\[\binom{50}{8} = 536{,}878{,}650\]
Probability of exactly 2 defectives in the sample:
\[P(X=2) = \frac{105{,}885{,}780}{536{,}878{,}650} \approx 0.197\]
About 20%. This is the hypergeometric distribution in action.
Clinical trial: treatment assignment
A trial enrolls 20 patients and randomly assigns 8 to the treatment group (the rest receive placebo). How many different treatment groups are possible?
\[\binom{20}{8} = \frac{20!}{8!\,12!} = 125{,}970\]
Every one of these 125,970 assignments is equally likely under proper randomization. The probability that any specific set of 8 patients ends up in the treatment group is \(1/125{,}970\).
Portfolio selection
A fund manager must select 5 stocks from a shortlist of 18. How many different portfolios are possible?
\[\binom{18}{5} = \frac{18!}{5!\,13!} = 8{,}568\]
If 3 of the 18 stocks are technology companies and the manager wants at least 2 tech stocks in the portfolio:
- Exactly 2 tech: \(\binom{3}{2} \times \binom{15}{3} = 3 \times 455 = 1{,}365\)
- Exactly 3 tech: \(\binom{3}{3} \times \binom{15}{2} = 1 \times 105 = 105\)
\[P(\text{at least 2 tech}) = \frac{1365 + 105}{8568} \approx 0.172\]
💡 When to use combinations
Use \(\binom{n}{r}\) when:
- You are choosing a subset, group, committee, or hand of cards.
- The selected items have no assigned roles or positions.
- Swapping two selected items gives the same outcome.
Use permutations when selected items have distinct roles (first place, second place) or when arrangement matters (passwords, sequences, rankings).
A quick test: list two arrangements of your selection. If they represent the same outcome, use combinations.
