7.5 Combinations
Learning Objectives
By the end of this section, you will be able to:
- Count the number of combinations of \(r\) items chosen from \(n\) — selections without regard to order.
- Use factorials and the \({}_nC_r\) formula to compute combinations.
In section 7.3 we counted permutations — arrangements where order matters. A committee of two people, though, isn't an arrangement at all: "Al and Bob" is the same committee as "Bob and Al." This section introduces combinations, the right tool for counting unordered selections.
7.5.1 Permutations vs. Combinations
Suppose we have the set \(\{\mathrm{A}, \mathrm{B}, \mathrm{C}\}\) and we want two-letter word sequences. We get six permutations:
$$\mathrm{AB}, \quad \mathrm{BA}, \quad \mathrm{BC}, \quad \mathrm{CB}, \quad \mathrm{AC}, \quad \mathrm{CA}.$$Now treat the letters as people — Al, Bob, Chris — and form two-person committees. This time there are only three:
$$\mathrm{AB}, \quad \mathrm{BC}, \quad \mathrm{AC}.$$The committee "Al and Bob" is identical to "Bob and Al" — order is irrelevant. Each committee corresponds to \(2!\) permutations (the two orders of its members), so the \(6\) permutations collapse into \(6/2! = 3\) committees.
Just as \({}_nP_r\) counts permutations of \(n\) objects taken \(r\) at a time, we write \({}_nC_r\) for the number of combinations of \(n\) objects taken \(r\) at a time. In the example above, \({}_3P_2 = 6\) and \({}_3C_2 = 3\).
Before you pick a formula, ask: if I swap two items, do I have the same thing or a different thing? A password (A-B-C vs C-B-A) is different — use permutations. A committee (Al-Bob vs Bob-Al) is the same — use combinations. Seating arrangements, race finishes, and lineups are permutation problems. Committees, card hands, lottery picks, and "choose \(r\) items" selections are combination problems.
Every \(r\)-element subset can be arranged in \(r!\) different orders. So the \({}_nP_r\) permutations of size \(r\) collapse into \({}_nP_r / r!\) combinations — because each combination was counted \(r!\) times, once per internal ordering. That single observation is the whole formula.
Source: Applied Finite Mathematics
Given the set of letters \(\{\mathrm{A}, \mathrm{B}, \mathrm{C}, \mathrm{D}\}\). List the combinations of three letters, and then from these combinations list the permutations of three letters.
Solution
Step 1 — List the combinations. Pick 3 letters at a time from 4 — ignoring order, we get
$$\mathrm{ABC}, \quad \mathrm{BCD}, \quad \mathrm{ACD}, \quad \mathrm{ABD}.$$That's \(4\) combinations.
Step 2 — Expand each combination into \(3!\) permutations. Each three-letter combination can be arranged in \(3! = 6\) orders:
| Combination | Its \(6\) permutations |
|---|---|
| ABC | ABC, ACB, BAC, BCA, CAB, CBA |
| BCD | BCD, BDC, CBD, CDB, DBC, DCB |
| ACD | ACD, ADC, CAD, CDA, DAC, DCA |
| ABD | ABD, ADB, BAD, BDA, DAB, DBA |
Step 3 — Connect the two counts. There are \(4 \cdot 3! = 24\) permutations total, matching \({}_4P_3 = 24\). Therefore
$$ {}_4P_3 \;=\; 3! \cdot {}_4C_3 \quad \implies \quad {}_4C_3 \;=\; \dfrac{{}_4P_3}{3!} \;=\; \dfrac{24}{6} \;=\; 4. $$Answer: \(4\) combinations, each expanding into \(6\) permutations for \(24\) total.
Source: Applied Finite Mathematics
From the set \(\{\mathrm{P}, \mathrm{Q}, \mathrm{R}, \mathrm{S}\}\), list all combinations of two letters. How many are there, and how many two-letter permutations does this correspond to?
Solution
Step 1 — List the size-2 combinations.
$$\mathrm{PQ}, \quad \mathrm{PR}, \quad \mathrm{PS}, \quad \mathrm{QR}, \quad \mathrm{QS}, \quad \mathrm{RS}.$$That's \(6\) combinations, so \({}_4C_2 = 6\).
Step 2 — Each combination has \(2! = 2\) permutations. Total permutations: \(6 \cdot 2 = 12 = {}_4P_2\). ✓
Answer: \(6\) combinations; \(12\) corresponding permutations.
7.5.2 The Combination Formula
Using the relationship we just derived, \({}_nC_r = {}_nP_r / r!\), we can plug in the permutation formula \({}_nP_r = \dfrac{n!}{(n - r)!}\) to get a clean formula for combinations:
$$ {}_nC_r \;=\; \dfrac{{}_nP_r}{r!} \;=\; \dfrac{n!}{(n - r)!\, r!}. $$Notice that \({}_nC_r = {}_nC_{n-r}\). Choosing \(r\) items to include is the same decision as choosing \(n - r\) items to leave out — either way, you've split the pile into two groups of the same sizes. That's why \({}_6C_4 = {}_6C_2 = 15\) below. Use it to save arithmetic: compute whichever side has the smaller \(r!\).
You may see the same quantity written \(\binom{n}{r}\), "\(n\) choose \(r\)", \(C(n, r)\), or \({}_nC_r\). They all mean the exact same thing: the number of ways to pick \(r\) items from \(n\) without regard to order. In probability and algebra, these are also called binomial coefficients — they're the numbers that appear when you expand \((x + y)^n\).
Source: Applied Finite Mathematics
A combination of a set of elements is a selection where each element is used at most once and order does not matter.
Source: Applied Finite Mathematics
The number of ways to choose \(r\) items from \(n\) distinct items, without regard to order, is
$$ {}_nC_r \;=\; \dfrac{n!}{(n - r)!\, r!}, $$where \(n\) and \(r\) are natural numbers with \(0 \le r \le n\).
Source: Applied Finite Mathematics
Compute each combination.
a) \({}_5C_3\)
b) \({}_7C_3\)
Solution
Step 1 — Apply the formula to (a).
$$ {}_5C_3 = \dfrac{5!}{(5 - 3)!\, 3!} = \dfrac{5!}{2!\, 3!} = \dfrac{120}{2 \cdot 6} = \dfrac{120}{12} = 10. $$Step 2 — Apply the formula to (b).
$$ {}_7C_3 = \dfrac{7!}{(7 - 3)!\, 3!} = \dfrac{7!}{4!\, 3!} = \dfrac{5040}{24 \cdot 6} = \dfrac{5040}{144} = 35. $$Answer: \({}_5C_3 = 10\); \({}_7C_3 = 35\).
Source: Applied Finite Mathematics
In how many different ways can a student select to answer five questions from a test that has seven questions, if the order of the selection is not important?
Solution
Step 1 — Identify order-matters or not. The student just needs to pick which questions to answer; the order of selection doesn't affect which five get answered. This is a combination problem.
Step 2 — Apply the formula.
$$ {}_7C_5 = \dfrac{7!}{(7 - 5)!\, 5!} = \dfrac{7!}{2!\, 5!} = \dfrac{5040}{2 \cdot 120} = \dfrac{5040}{240} = 21. $$Answer: \(21\) ways.
Source: Applied Finite Mathematics
♠ Challenge problem. How many line segments can be drawn by connecting any two of the six points that lie on the circumference of a circle?
Solution
Step 1 — Check for order. The segment from A to B is the same segment as from B to A — order of the endpoints does not produce a new segment. This is a combination problem.
Step 2 — Apply the formula. Choose \(2\) endpoints out of \(6\):
$$ {}_6C_2 = \dfrac{6!}{(6 - 2)!\, 2!} = \dfrac{6!}{4!\, 2!} = \dfrac{720}{24 \cdot 2} = \dfrac{720}{48} = 15. $$Answer: \(15\) line segments.
Source: Applied Finite Mathematics
There are ten people at a party. If they all shake hands, how many handshakes are possible?
Solution
Step 1 — Check for order. Between any two people there is exactly one handshake — "Al shakes Bob" and "Bob shakes Al" is the same event. This is a combination problem.
Step 2 — Apply the formula.
$$ {}_{10}C_2 = \dfrac{10!}{(10 - 2)!\, 2!} = \dfrac{10!}{8!\, 2!} = \dfrac{10 \cdot 9}{2} = \dfrac{90}{2} = 45. $$Answer: \(45\) handshakes.
Source: Applied Finite Mathematics
♠ Challenge problem. The shopping area of a town is in the shape of a square that is 5 blocks by 5 blocks. How many different routes can a taxi driver take to go from one corner of the shopping area to the opposite cater-corner?
Solution
Step 1 — Model the route. To get from point A (lower-left) to point B (upper-right), the driver must travel \(5\) blocks east and \(5\) blocks north — \(10\) blocks total — in any order. Encode a route as a string of \(5\) H's (horizontal) and \(5\) V's (vertical), e.g.
$$\mathrm{HHHHHVVVVV}.$$Step 2 — Count via combinations. Of the \(10\) block-positions, pick which \(5\) are the horizontal moves — the other \(5\) are automatically vertical. That's
$$ {}_{10}C_5 = \dfrac{10!}{5!\, 5!} = \dfrac{3{,}628{,}800}{120 \cdot 120} = \dfrac{3{,}628{,}800}{14{,}400} = 252. $$Step 3 — Confirm via permutations with similar elements (section 7.4). The number of arrangements of \(\mathrm{HHHHHVVVVV}\) is
$$\dfrac{10!}{5!\, 5!} = 252,$$which matches. Indeed, by definition \({}_{10}C_5 = \dfrac{10!}{5!\, 5!}\) — the two methods are the same calculation.
Answer: \(252\) routes.
Source: Applied Finite Mathematics
If a coin is tossed six times, in how many ways can it fall four heads and two tails?
Solution
Step 1 — Solve via similar elements (section 7.4 review). Arranging HHHHTT — \(6\) items, \(4\) H's, \(2\) T's:
$$\dfrac{6!}{4!\, 2!} = \dfrac{720}{24 \cdot 2} = \dfrac{720}{48} = 15.$$Step 2 — Solve via combinations. There are \(6\) toss-positions; choose which \(4\) are heads — the other \(2\) are automatically tails:
$$ {}_6C_4 = \dfrac{6!}{2!\, 4!} = 15. $$Equivalently, pick which \(2\) are tails: \({}_6C_2 = \dfrac{6!}{4!\, 2!} = 15\).
Step 3 — Note the symmetry. Both calculations give \(15\), illustrating \({}_6C_4 = {}_6C_2\) — "choose \(4\) to be H" and "choose \(2\) to be T" are the same decision.
Answer: \(15\) outcomes.
Source: Applied Finite Mathematics
A pizza shop offers \(8\) different toppings. In how many ways can you pick \(3\) toppings for a pizza?
Solution
Step 1 — Order or not? Choosing olives-then-mushrooms gives the same pizza as mushrooms-then-olives. This is a combination problem.
Step 2 — Apply the formula.
$$ {}_8C_3 = \dfrac{8!}{(8 - 3)!\, 3!} = \dfrac{8!}{5!\, 3!} = \dfrac{8 \cdot 7 \cdot 6}{3 \cdot 2 \cdot 1} = \dfrac{336}{6} = 56. $$Answer: \(56\) three-topping pizzas.
Summary
Combination
A selection of items from a set where order does not matter and no item is repeated.
The \({}_nC_r\) Formula
The number of combinations of \(n\) distinct objects taken \(r\) at a time is
$$ {}_nC_r \;=\; \dfrac{n!}{(n - r)!\, r!}. $$
Key Identities
\({}_nC_r = {}_nC_{n-r}\) (symmetry); \({}_nC_0 = {}_nC_n = 1\); \({}_nP_r = r! \cdot {}_nC_r\).
Problem Set 7.5
Source: Applied Finite Mathematics
Do the following problems using combinations.
Problem 1. How many different 3-person committees can be chosen from ten people?
Problem 1 Solution
Step 1 — Identify the type. A committee is an unordered selection — order does not matter. Use combinations.
Step 2 — Apply the formula. Choose \(3\) people from \(10\):
$$ {}_{10}C_3 = \dfrac{10!}{(10 - 3)!\, 3!} = \dfrac{10!}{7!\, 3!} = \dfrac{10 \cdot 9 \cdot 8}{3 \cdot 2 \cdot 1} = \dfrac{720}{6} = 120. $$Answer: \(120\) committees.
Problem 2. How many different 5-player teams can be chosen from eight players?
Problem 2 Solution
Step 1 — Identify the type. A team is an unordered selection.
Step 2 — Apply the formula. Choose \(5\) players from \(8\):
$$ {}_8C_5 = \dfrac{8!}{3!\, 5!} = \dfrac{8 \cdot 7 \cdot 6}{3 \cdot 2 \cdot 1} = \dfrac{336}{6} = 56. $$Answer: \(56\) teams.
Problem 3. In how many ways can a person choose to vote for three out of five candidates on a ballot for a school board election?
Problem 3 Solution
Step 1 — Identify the type. Voting for three candidates means selecting three names — order of selection does not matter. Use combinations.
Step 2 — Apply the formula. Choose \(3\) from \(5\):
$$ {}_5C_3 = \dfrac{5!}{2!\, 3!} = \dfrac{5 \cdot 4}{2 \cdot 1} = \dfrac{20}{2} = 10. $$Answer: \(10\) ways.
Problem 4. Compute the following.
a) \({}_9C_2\)
b) \({}_6C_4\)
c) \({}_8C_3\)
d) \({}_7C_4\)
Problem 4 Solution
Step 1 — Compute (a).
$$ {}_9C_2 = \dfrac{9!}{7!\, 2!} = \dfrac{9 \cdot 8}{2} = \dfrac{72}{2} = 36. $$Step 2 — Compute (b).
$$ {}_6C_4 = \dfrac{6!}{2!\, 4!} = \dfrac{6 \cdot 5}{2} = \dfrac{30}{2} = 15. $$Step 3 — Compute (c).
$$ {}_8C_3 = \dfrac{8!}{5!\, 3!} = \dfrac{8 \cdot 7 \cdot 6}{3 \cdot 2 \cdot 1} = \dfrac{336}{6} = 56. $$Step 4 — Compute (d).
$$ {}_7C_4 = \dfrac{7!}{3!\, 4!} = \dfrac{7 \cdot 6 \cdot 5}{3 \cdot 2 \cdot 1} = \dfrac{210}{6} = 35. $$Answer: (a) \(36\); (b) \(15\); (c) \(56\); (d) \(35\).
Problem 5. How many 5-card hands can be chosen from a deck of cards?
Problem 5 Solution
Step 1 — Identify the type. A poker hand is a set of \(5\) cards — order within a hand doesn't matter. Use combinations.
Step 2 — Apply the formula. Choose \(5\) cards from a \(52\)-card deck:
$$ {}_{52}C_5 = \dfrac{52!}{47!\, 5!} = \dfrac{52 \cdot 51 \cdot 50 \cdot 49 \cdot 48}{5 \cdot 4 \cdot 3 \cdot 2 \cdot 1} = \dfrac{311{,}875{,}200}{120} = 2{,}598{,}960. $$Answer: \(2{,}598{,}960\) five-card hands.
Problem 6. How many 13-card bridge hands can be chosen from a deck of cards?
Problem 6 Solution
Step 1 — Identify the type. A bridge hand is a set of \(13\) cards — order doesn't matter. Use combinations.
Step 2 — Apply the formula. Choose \(13\) cards from \(52\):
$$ {}_{52}C_{13} = \dfrac{52!}{39!\, 13!} = 635{,}013{,}559{,}600. $$Answer: \(635{,}013{,}559{,}600\) bridge hands.
Problem 7. There are twelve people at a party. If they all shake hands, how many different handshakes are there?
Problem 7 Solution
Step 1 — Identify the type. A handshake involves two distinct people; "A shakes B" and "B shakes A" are the same handshake. Use combinations.
Step 2 — Apply the formula. Choose \(2\) people from \(12\):
$$ {}_{12}C_2 = \dfrac{12!}{10!\, 2!} = \dfrac{12 \cdot 11}{2} = \dfrac{132}{2} = 66. $$Answer: \(66\) handshakes.
Problem 8. In how many ways can a student choose to do four questions out of five on a test?
Problem 8 Solution
Step 1 — Identify the type. The student just picks which four questions to do — order doesn't matter. Use combinations.
Step 2 — Apply the formula. Choose \(4\) from \(5\):
$$ {}_5C_4 = \dfrac{5!}{1!\, 4!} = 5. $$Answer: \(5\) ways.
Problem 9. Five points lie on a circle. How many chords can be drawn through them?
Problem 9 Solution
Step 1 — Identify the type. A chord is determined by choosing \(2\) of the \(5\) points — the order of the endpoints doesn't matter. Use combinations.
Step 2 — Apply the formula.
$$ {}_5C_2 = \dfrac{5!}{3!\, 2!} = \dfrac{5 \cdot 4}{2} = 10. $$Answer: \(10\) chords.
Problem 10. How many diagonals does a hexagon have?
Problem 10 Solution
Step 1 — Count all segments connecting two vertices. A hexagon has \(6\) vertices, so the number of segments between pairs of vertices is
$$ {}_6C_2 = \dfrac{6!}{4!\, 2!} = \dfrac{6 \cdot 5}{2} = 15. $$Step 2 — Subtract the sides. A hexagon has \(6\) sides, which are edges of the polygon, not diagonals.
$$15 - 6 = 9.$$Answer: \(9\) diagonals.
Problem 11. There are five teams in a league. How many games are played if every team plays each other twice?
Problem 11 Solution
Step 1 — Count distinct pairings. Each game pairs two teams — order-free — so the number of distinct matchups is
$$ {}_5C_2 = \dfrac{5!}{3!\, 2!} = \dfrac{5 \cdot 4}{2} = 10. $$Step 2 — Each pair plays twice. Multiply by \(2\):
$$10 \cdot 2 = 20.$$Answer: \(20\) games.
Problem 12. A team plays 15 games a season. In how many ways can it have 8 wins and 7 losses?
Problem 12 Solution
Step 1 — Reframe as choosing which games are wins. Of the \(15\) games, pick which \(8\) are wins; the other \(7\) are losses.
Step 2 — Apply the formula.
$$ {}_{15}C_8 = \dfrac{15!}{7!\, 8!} = 6{,}435. $$Answer: \(6{,}435\) ways.
Problem 13. In how many different ways can a 4-child family have 2 boys and 2 girls?
Problem 13 Solution
Step 1 — Reframe as choosing which children are boys. Of the \(4\) children (in birth order), pick which \(2\) are boys; the other \(2\) are girls.
Step 2 — Apply the formula.
$$ {}_4C_2 = \dfrac{4!}{2!\, 2!} = \dfrac{24}{4} = 6. $$Answer: \(6\) different gender sequences.
Problem 14. A coin is tossed five times. In how many ways can it fall three heads and two tails?
Problem 14 Solution
Step 1 — Reframe as choosing which tosses are heads. Of the \(5\) tosses, pick which \(3\) land heads; the other \(2\) are tails.
Step 2 — Apply the formula.
$$ {}_5C_3 = \dfrac{5!}{2!\, 3!} = \dfrac{5 \cdot 4}{2} = 10. $$Answer: \(10\) outcomes.
Problem 15. The shopping area of a town is a square that is six blocks by six blocks. How many different routes can a taxi driver take to go from one corner of the shopping area to the opposite cater-corner?
Problem 15 Solution
Step 1 — Model the route. To go from one corner to the opposite corner of a \(6 \times 6\) grid, the driver travels \(6\) east-blocks and \(6\) north-blocks — \(12\) blocks total — in some order.
Step 2 — Count via combinations. Choose which \(6\) of the \(12\) block-positions are east moves; the other \(6\) are automatically north:
$$ {}_{12}C_6 = \dfrac{12!}{6!\, 6!} = 924. $$Answer: \(924\) routes.
Problem 16. If the shopping area in the previous problem has a rectangular form of 5 blocks by 3 blocks, then how many different routes can a taxi driver take to drive from one end of the shopping area to the opposite kidney corner end?
Problem 16 Solution
Step 1 — Model the route. To cross a \(5 \times 3\) grid, the driver travels \(5\) blocks in one direction and \(3\) in the other — \(8\) blocks total.
Step 2 — Count via combinations. Choose which \(5\) of the \(8\) block-positions are the long-direction moves; the other \(3\) are automatically the short-direction moves:
$$ {}_8C_5 = \dfrac{8!}{3!\, 5!} = \dfrac{8 \cdot 7 \cdot 6}{3 \cdot 2 \cdot 1} = \dfrac{336}{6} = 56. $$Answer: \(56\) routes.
Problem 17. A team of 7 workers is assigned to a project. In how many ways can 3 of the 7 workers be selected to make a presentation to the management about their progress on the project?
Problem 17 Solution
Step 1 — Identify the type. The \(3\) presenters form an unordered selection from the \(7\) workers. Use combinations.
Step 2 — Apply the formula.
$$ {}_7C_3 = \dfrac{7!}{4!\, 3!} = \dfrac{7 \cdot 6 \cdot 5}{3 \cdot 2 \cdot 1} = \dfrac{210}{6} = 35. $$Answer: \(35\) ways.
Problem 18. A real estate company has 12 houses listed for sale by their clients. In how many ways can 5 of the 12 houses be selected to be featured in an advertising brochure?
Problem 18 Solution
Step 1 — Identify the type. Featuring \(5\) houses in the brochure is an unordered selection from the \(12\) listings.
Step 2 — Apply the formula.
$$ {}_{12}C_5 = \dfrac{12!}{7!\, 5!} = \dfrac{12 \cdot 11 \cdot 10 \cdot 9 \cdot 8}{5 \cdot 4 \cdot 3 \cdot 2 \cdot 1} = \dfrac{95{,}040}{120} = 792. $$Answer: \(792\) ways.
Problem 19. A frozen yogurt store has 9 toppings to choose from. In how many ways can 3 of the 9 toppings be selected?
Problem 19 Solution
Step 1 — Identify the type. Selecting \(3\) toppings from \(9\) is an unordered choice.
Step 2 — Apply the formula.
$$ {}_9C_3 = \dfrac{9!}{6!\, 3!} = \dfrac{9 \cdot 8 \cdot 7}{3 \cdot 2 \cdot 1} = \dfrac{504}{6} = 84. $$Answer: \(84\) ways.
Problem 20. A kindergarten teacher has 14 books about a holiday. In how many ways can she select 4 of the books to read to her class in the week before the holiday?
Problem 20 Solution
Step 1 — Identify the type. Selecting \(4\) books from \(14\) is an unordered choice.
Step 2 — Apply the formula.
$$ {}_{14}C_4 = \dfrac{14!}{10!\, 4!} = \dfrac{14 \cdot 13 \cdot 12 \cdot 11}{4 \cdot 3 \cdot 2 \cdot 1} = \dfrac{24{,}024}{24} = 1{,}001. $$Answer: \(1{,}001\) ways.