4.2Repetition, selection & distribution
The idea
Selection with repetition counts multisets: C(n + k − 1, k). Restrictions are best handled by inclusion-exclusion.
Think of it like this: Choosing scoops of ice cream: you can take the same flavour twice.
Why it exists
Distribution and "no one gets a disliked item" questions appear regularly.
How it works
- k scoops from n flavours: C(n + k − 1, k).
- List the tuples (counts of each flavour) to check.
- For restricted permutations: total − bad + both bad.
- Check against a small case.
Worked example: 3 scoops from 4 flavours
C(6, 3) = 20.
Now play with it
- →List the 20 tuples in the lab.
- →Use the inclusion-exclusion tile for the shirts problem.
Each tuple says how many scoops of flavour 1, 2, 3, ... you take. Order does not matter, only the counts do.
Inclusion-exclusion for the shirts problem: 24 − 6 − 6 + 2 = 14.
Check yourself
Number of non-negative solutions of x + y + z = 4
Exam notes (the dense version)
Choosing k items from n types with repetition and no order: C(n + k − 1, k) (3 scoops from 4 flavours = C(6,3) = 20). This equals the number of non-negative solutions of x₁ + ... + xₙ = k (stars and bars). With each item used at most once it is plain nCk. Handle restrictions by complement or by inclusion-exclusion (24 − 6 − 6 + 2 = 14).
Previous year questions: Counting & Probability (10)
PYQs are grouped by topic, so this is the full set for Counting & Probability; try the ones that match this subtopic. Open all 10 on the topic page.