Combinations
Choosing groups where order doesn’t matter.
Pen and paper is fine · no calculator needed why?
Opens at level 25. You're level 1. You can read and practice here now.
the idea
A combination is a choice where order doesn't matter: a team of 3, not gold, silver and bronze. Count the ordered picks, then divide by the number of ways to order the group you picked. The result is written C(n, k), said "n choose k".
Grid paths and shares of identical items turn into choosing too: which moves go right, and where the dividers go.
techniques
Ordered picks, then divide
- Multiply k numbers, counting down from n.
- Divide by k × (k − 1) × … × 1, the orders of the group you chose.
- A committee from two groups: find the count for each group, then multiply.
worked example
A pizza place offers 8 toppings. How many different pizzas can you make with exactly 3 different toppings?
- 8 × 7 × 6 = 336 ordered picks.
- Each set of 3 comes in 3 × 2 × 1 = 6 orders.
- 336 ÷ 6 = 56.
Answer: 56
Choose the right moves
- A grid w wide and h tall: every shortest path has w + h moves.
- Exactly w of them go right.
- The number of paths is C(w + h, w).
worked example
On a grid 3 blocks wide and 2 blocks tall, how many shortest paths go from the bottom-left corner to the top-right corner, moving only right or up?
- Each path is 5 moves, 3 of them right.
- C(5, 3) = (5 × 4 × 3) ÷ (3 × 2 × 1) = 10.
Answer: 10
Items and dividers
- Line up the n items with k − 1 dividers between the shares.
- Shares may be empty: choose k − 1 divider places out of n + k − 1.
- Each gets at least one: choose k − 1 of the n − 1 gaps between items.
worked example
In how many ways can 6 identical coins be put into 3 different jars if a jar may stay empty?
- 6 coins and 2 dividers make 8 places.
- Choose 2 for the dividers: 8 × 7 ÷ 2 = 28.
Answer: 28
watch out for
- Counting ordered picks for a group. Each team of 3 gets counted in 6 orders.
- Adding the counts for two groups. Every choice from one group goes with every choice from the other.
- Multiplying the width by the height for grid paths.
- Mixing up "may get none" with "at least one each".
practice
Choose k of n
worked example
In how many ways can you choose 4 people from 11 for a team, if order doesn’t matter?
Answer: 330
- C(11, 4) = (11 × 10 × 9 × 8) ÷ (4 × 3 × 2 × 1)
- = 7,920 ÷ 24 = 330.
Committees
worked example
A squad needs 1 defender chosen from 4 and 2 forwards chosen from 5. How many different squads are possible?
Answer: 40
- Choose each group separately, then multiply: every choice of defenders goes with every choice of forwards.
- C(4, 1) × C(5, 2) = 4 × 10 = 40.
Grid paths
worked example
On a grid 6 blocks wide and 4 blocks tall, how many shortest paths go from the bottom-left corner to the top-right corner, moving only right or up?
Answer: 210
- Every path is 10 moves: 6 right and 4 up. Choose which 6 of the 10 moves go right:
- C(10, 6) = 210.
Sharing identical items
worked example
In how many ways can 7 identical cookies be shared among 4 children if each child gets at least one?
Answer: 20
- Line up the 7 cookies. Put 3 dividers into the 6 gaps between them, at most one per gap, so no share is empty.
- C(6, 3) = 20.