A committee, a lottery ticket, a hand of cards, a set of pizza toppings: in all of these a group is chosen and the order in which its members were picked does not matter. Such a choice is a combination. Combinations are the most used tool of combinatorics and of probability, and they come straight from arrangements: count the ordered choices, then divide by the number of orders in which each group was counted. This chapter derives the formula, shows how to compute it quickly by hand, and works through the situations exams build on it: two groups at once, "at least one", geometry, lotteries, and problems that mix order and groups.
By the end you can
- Explain why a combination is an arrangement divided by k!, and compute C(n, k) by hand.
- Use the symmetry C(n, k) = C(n, n − k) to save work.
- Count groups chosen in stages from two or more sets, and groups with "at least" or "at most".
- Count segments, diagonals and triangles from points, and matches in a tournament.
- Tell apart, in a mixed problem, the part that is a combination and the part that is an arrangement.
From 8 people, choose a committee of 3 with equal roles. If the roles were different (president, secretary, treasurer), the answer would be the arrangement A(8, 3) = 8 · 7 · 6 = 336. A committee has no roles, though: {Ana, Bruno, Carla} is the same committee whichever order its members were picked in. Among the 336 ordered choices, this one committee appears once for each order of its 3 members, which is 3! = 6 times, and the same is true of every committee. So the number of committees is 336/6 = 56.
Each chip is one possible selection of k letters out of the first n. Switch "order matters" off and AB and BA become the same chip: the list shrinks by a factor of k!, because every set of k different letters can be put in order in k! ways. Switch repetition on and letters may repeat (AA, BB): with order it gives nᵏ sequences, without order it gives the multisets counted by stars and bars.
Do not compute the three factorials. Write k factors counting down from n on top and k factors counting down from k below, then cancel before multiplying. C(10, 4) = (10 · 9 · 8 · 7)/(4 · 3 · 2 · 1): the 8 cancels with 4 · 2, the 9 with 3, leaving 10 · 3 · 7 = 210. The result is always a whole number, because it counts something; if a fraction is left, a factor was dropped.
Symmetry and the edge cases
Choosing the 3 people who go on a trip is the same as choosing the 5 who stay behind, so C(8, 3) = C(8, 5) = 56. In general C(n, k) = C(n, n − k): swapping k and n − k only swaps the two factorials below. Use it to keep k small: C(100, 98) = C(100, 2) = 100 · 99/2 = 4950. The edge cases follow from the formula and from common sense: C(n, 0) = C(n, n) = 1 (one way to choose nothing, one way to choose everything) and C(n, 1) = n. The numbers C(n, k) form Pascal's triangle, studied in the Binomial Theorem chapter.
A committee of 5 must have exactly 3 women and 2 men, chosen from 6 women and 4 men. Build it in two stages: choose the women, C(6, 3) = 20 ways, and then the men, C(4, 2) = 6 ways. Every choice of women combines with every choice of men, so multiply: 20 · 6 = 120. Inside each stage the order does not matter; between the stages, the multiplication principle applies as always.
"At least one man" in a committee of 5 from 6 women and 4 men covers the cases with 1, 2, 3 or 4 men. You could add the four cases, but the opposite of "at least one man" is a single case, "no man", which is much shorter. All committees: C(10, 5) = 252. Committees with no man, all women: C(6, 5) = 6. So 252 − 6 = 246 have at least one man. "At most two men" is the cases 0, 1 and 2 men: C(6, 5) + C(4, 1) · C(6, 4) + C(4, 2) · C(6, 3) = 6 + 60 + 120 = 186.
A set of points determines figures, and the figure does not depend on the order in which its points are named: segment AB is segment BA. So these are combinations. With 10 points on a circle (no three on a line): segments C(10, 2) = 45, triangles C(10, 3) = 120, quadrilaterals C(10, 4) = 210.
| What is counted | How | Example |
|---|---|---|
| diagonals of a convex polygon with n sides | all segments between corners, minus the n sides | C(8, 2) − 8 = 20; n(n − 3)/2 |
| triangles from n points, m of them on one line | all triples, minus the triples on the line (they make no triangle) | C(10, 3) − C(4, 3) = 116 |
| handshakes when n people all greet each other | one handshake per pair | C(10, 2) = 45 |
| matches of a tournament, every team against every other once | one match per pair of teams; twice (home and away) is an arrangement | C(20, 2) = 190; A(20, 2) = 380 |
The Mega-Sena draws 6 numbers out of 60, and the order of the draw does not matter: C(60, 6) = (60 · 59 · 58 · 57 · 56 · 55)/720 = 50 063 860 possible results. A simple bet of 6 numbers covers one of them. A bet of 7 numbers covers every set of 6 inside the 7, which is C(7, 6) = 7 sets: it costs seven simple bets and wins exactly seven times as often. A hand of 5 cards from a 52-card deck: C(52, 5) = 2 598 960. Hands with all 5 cards of the same suit: 4 suits times C(13, 5) = 1287, so 5148.
Many problems have a part where order matters and a part where it does not. Choose a committee of 4 from 10 people and then a coordinator among the 4. Stage 1, the group: C(10, 4) = 210. Stage 2, a role inside the group: 4 options. Total 840. The same count in another order: first the coordinator, 10 options, then the other 3 members with equal roles, C(9, 3) = 84: 10 · 84 = 840. Two correct methods must give the same number, which makes a good check.
| Question | Kind | Count |
|---|---|---|
| 3 prizes, gold, silver and bronze, among 10 students | arrangement | A(10, 3) = 720 |
| 3 equal prizes among 10 students | combination | C(10, 3) = 120 |
| 3 equal prizes, at most one per student, then a photo of the 3 winners in a row | combination, then permutation | 120 · 3! = 720 |
1. A student must answer 7 of the 10 questions of an exam: C(10, 7) = C(10, 3) = 120 ways to choose them. If questions 1 and 2 are compulsory, she chooses the other 5 from the remaining 8: C(8, 5) = 56.
2. From 5 red and 4 blue balls, 3 are drawn at once. Draws with 2 red and 1 blue: C(5, 2) · C(4, 1) = 10 · 4 = 40, out of C(9, 3) = 84 draws in all.
3. A pizzeria offers 8 toppings and a pizza has 3 different ones: C(8, 3) = 56 pizzas. With 2 or 3 toppings: C(8, 2) + C(8, 3) = 28 + 56 = 84.
4. Strings of 8 bits with exactly 3 ones: choosing which 3 of the 8 positions hold the ones fixes the string: C(8, 3) = 56.
5. Lines through pairs of 12 points, 5 of which lie on one line and no other three are collinear: C(12, 2) − C(5, 2) + 1 = 66 − 10 + 1 = 57. The 10 pairs on the special line all give the same line, counted once.
| Wrong | Right | Why |
|---|---|---|
| committees of 3 from 8: 8 · 7 · 6 = 336 | 336/3! = 56 | a committee has no order; each one was counted 3! times |
| 3 women and 2 men: C(6, 3) + C(4, 2) = 26 | C(6, 3) · C(4, 2) = 120 | the two stages are made one after the other: multiply |
| "at least one man": C(4, 1) · C(9, 4) = 504 | 252 − 6 = 246 | choosing "the" man first counts a committee with two men twice |
| diagonals of an octagon: C(8, 2) = 28 | 28 − 8 = 20 | 8 of those segments are sides, not diagonals |
| C(10, 4) = 10!/4! | 10!/(4! · 6!) = 210 | both the chosen and the unchosen orders are divided out |
A round of 10 questions
Answer as many as you can. Mistakes come back at the end for a review round.
Every exercise is made on the spot, so a new round is never the same. The computer picks the answer first and builds the question around it, working with exact fractions, so the answer key is always right. Answers are read exactly: 0.75, 3/4 and 6/8 count as the same number (where lowest terms are asked for, 6/8 just gets a reminder). A wrong answer shows the worked solution line by line, in the order the lesson does it; the new number in each line is coloured.
Key ideas
- A combination is a group with no order: C(n, k) = A(n, k)/k! = n!/(k!(n − k)!).
- By hand: k factors down from n over k!, cancelling first; the result is always whole.
- C(n, k) = C(n, n − k); C(n, 0) = C(n, n) = 1, C(n, 1) = n.
- Groups chosen from separate sets in stages multiply: C(6, 3) · C(4, 2).
- "At least one" is usually all minus none; choosing "the" special member first double counts.
- Points make figures without order: segments C(n, 2), triangles C(n, 3), diagonals C(n, 2) − n.
- In mixed problems, choose the group (combination) and then give roles (arrangement).