Permutations, arrangements and combinations cover most counting problems, but a few situations need one more idea. Items that may be chosen more than once in a group with no order. Objects shared out among people or boxes. Groups that overlap, so that adding their sizes counts some results twice. Letters that must all miss their own envelopes. And questions that ask not "how many" but "is it certain that…". This chapter gives the standard method for each: stars and bars, splitting into groups, inclusion–exclusion, derangements and the pigeonhole principle.
By the end you can
- Count choices with repetition and no order with stars and bars, and whole-number solutions of x + y + z = s.
- Share different objects among labelled groups, with or without a condition, and handle groups with no labels.
- Count a union of overlapping sets with inclusion–exclusion.
- Count derangements, orders in which no item is in its own place.
- Use the pigeonhole principle to prove that some coincidence must happen.
An ice-cream shop has 5 flavours and you want a cup with 3 scoops. Flavours may repeat and the order of the scoops does not matter: two scoops of chocolate and one of lemon is one cup. This is neither an arrangement nor an ordinary combination. The trick is to draw each cup in a code. Line up the 5 flavours as boxes separated by 4 walls (bars), and draw each scoop as a star in its box. ★★|★||| means two scoops of flavour 1 and one of flavour 2. Every cup gives exactly one row of 3 stars and 4 bars, and every such row gives one cup.
Top: the k identical items shared out among the n boxes; a box may stay empty. Bottom: the same thing written as one row, a star for each item and a bar for each wall between two boxes. Every sharing gives one row and every row gives one sharing, so counting rows is enough. A row has n + k − 1 places, and it is fixed by choosing which k of them hold stars.
A row has 3 + 4 = 7 places, and it is completely fixed once you say which 3 of the 7 places hold stars. So there are C(7, 3) = 35 cups. In general, choosing k items from n kinds with repetition and no order means k stars and n − 1 bars.
Whole-number solutions of an equation
How many solutions does x + y + z = 10 have in whole numbers x, y, z ≥ 0? Read it as 10 identical stars shared among 3 boxes x, y and z: 10 stars and 2 bars, C(12, 2) = 66 solutions. If every variable must be at least 1, give each one its 1 first. That uses 3 of the 10, and the remaining 7 are shared freely.
| no repetition | repetition allowed | |
|---|---|---|
| order matters | A(n, k) = n!/(n − k)! | nᵏ |
| order does not matter | C(n, k) = n!/(k!(n − k)!) | C(n + k − 1, k) |
Labelled groups: choose in stages
Seven different gifts go to three children: the oldest gets 3, the middle one 2 and the youngest 2. The children are different people, so the groups are labelled. Choose the oldest child's gifts, C(7, 3) = 35, then the middle child's from the 4 left, C(4, 2) = 6, and the youngest takes the last 2, C(2, 2) = 1: 35 · 6 · 1 = 210. The same number is 7!/(3! · 2! · 2!): ordering all the gifts in a row and cutting the row into pieces of 3, 2 and 2, where the order inside each piece does not matter.
A condition on one group
Among the seven gifts are a tablet and a ball, and the oldest child must get exactly one of them, not both. Handle the condition first. Which of the two goes to the oldest: 2 options. The oldest's other 2 gifts come from the 5 ordinary gifts (the other special one is not allowed): C(5, 2) = 10. That leaves 4 gifts, the other special one included, for the middle child: C(4, 2) = 6. The youngest gets the rest.
Groups without labels
Six players are split into 3 pairs for a doubles tournament. Counted in stages, C(6, 2) · C(4, 2) · C(2, 2) = 15 · 6 · 1 = 90, but that is the count for labelled pairs (pair 1, pair 2, pair 3). The pairs have no names: the same three pairs listed in another order are the same split. Three groups of the same size can be listed in 3! = 6 orders, so there are 90/6 = 15 splits. Divide by the factorial of the number of groups only for groups that have the same size and no labels.
How many whole numbers from 1 to 100 are divisible by 2 or by 3? There are 50 multiples of 2 and 33 multiples of 3 (100/3 = 33.3…, rounded down). But 50 + 33 = 83 is too many: the multiples of 6 (6, 12, …, 96, which is 16 numbers) are in both lists and were counted twice. Subtract them once: 50 + 33 − 16 = 67. This is the addition principle repaired for groups that overlap. With three sets, add the three sizes, subtract the three pairwise overlaps, and add back the triple overlap, which the subtractions removed once too often.
A secretary puts n letters into n addressed envelopes completely at random. In how many ways does no letter reach its own envelope? Such an order is a derangement, and the count is written Dₙ. With 3 letters, of the 3! = 6 orders only 2 move every letter (BCA and CAB), so D₃ = 2. Inclusion–exclusion gives the general count: start from all n! orders, take away those that fix letter 1, letter 2 and so on, add back those that fix two letters, and continue.
| n | 1 | 2 | 3 | 4 | 5 | 6 |
|---|---|---|---|---|---|---|
| Dₙ | 0 | 1 | 2 | 9 | 44 | 265 |
| Dₙ / n! | 0 | 0.5 | 0.333 | 0.375 | 0.367 | 0.368 |
The bracket is the start of the series for 1/e, where e ≈ 2.718 is the base of natural logarithms. So, for any number of letters above a handful, the chance that none reaches its envelope is almost exactly 1/e ≈ 36.8%, whether there are 6 letters or a million.
If more than n pigeons fly into n holes, at least one hole holds two pigeons. It sounds too obvious to be useful, but it proves things without counting them. Among any 13 people, two were born in the same month: 13 people, 12 months. A drawer has socks of 3 colours, mixed in the dark: taking 4 socks guarantees a pair of the same colour, and 3 do not. The stronger form: if more than n · k objects go into n boxes, some box holds at least k + 1 of them. Among 367 people, two share a birthday; among 1000 people, some date is shared by at least 3, because 1000 > 366 · 2.
1. 6 identical sweets are shared among 4 children, and a child may get none: 6 stars and 3 bars, C(9, 3) = 84 ways. If every child must get at least one: give one to each first, 2 sweets are left: C(2 + 3, 3) = C(5, 3) = 10.
2. A bakery sells 4 kinds of bread, and a bag holds 6 breads: C(4 + 6 − 1, 6) = C(9, 6) = 84 different bags.
3. 12 students are split into 3 working groups of 4 with no names: C(12, 4) · C(8, 4) · C(4, 4)/3! = 495 · 70 · 1/6 = 5775. If the groups get different topics, do not divide: 34 650.
4. Of 40 students, 25 study English, 18 study Spanish and 10 study both. Those who study at least one: 25 + 18 − 10 = 33; those who study neither: 40 − 33 = 7.
5. Four friends each bring a gift and draw one at random, Secret-Santa style. The chance that nobody draws their own: D₄/4! = 9/24 = 37.5%.
| Wrong | Right | Why |
|---|---|---|
| 3 scoops from 5 flavours, repeats allowed: C(5, 3) = 10 | C(7, 3) = 35 | C(5, 3) forbids repeated flavours; use stars and bars |
| x + y + z = 10 with x, y, z ≥ 1: C(12, 2) | C(9, 2) = 36 | hand out the compulsory 1s before sharing |
| 6 players into 3 pairs: 15 · 6 · 1 = 90 | 90/3! = 15 | the pairs have no names; listing them in another order is the same split |
| English or Spanish: 25 + 18 = 43 | 25 + 18 − 10 = 33 | the 10 who study both were counted twice |
| socks of 3 colours: 6 socks guarantee a pair | 4 | 3 socks can be all different; the 4th must repeat a colour |
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
- k items from n kinds, repeats allowed, no order: k stars and n − 1 bars, C(n + k − 1, k).
- Whole-number solutions of x₁ + … + xₙ = s: C(s + n − 1, n − 1); with each xᵢ ≥ 1, hand out the 1s first.
- Labelled groups: choose them in stages and multiply; unlabelled groups of equal size: divide by the number of their orders.
- Inclusion–exclusion: add the sets, subtract the pairwise overlaps, add back the triple overlap.
- Derangements: Dₙ = n!(1 − 1/1! + 1/2! − … ± 1/n!), and Dₙ/n! is almost 1/e.
- Pigeonhole: more objects than boxes forces two objects into one box.