Counting the options
The product rule, permutations, arrangements and combinations, and at the top level counting with repetitions, stars and bars, and inclusion–exclusion.
How to solve it
Almost every counting problem is solved by two rules: if a choice is made in steps, the options at the steps multiply; if one option is chosen from several non-overlapping sets, they add. Permutations, arrangements and combinations are special cases of the product rule.
Step by step
- Split the choice into steps and count the options at each. Multiply.
- Does order matter? Medals, places, the digits of a number — yes (arrangements); a team, a set, a subset — no (combinations).
- Are repeats allowed? With repeats each step has the same number of options, $n^k$; without, one fewer each time.
- Identical items into different boxes: stars and bars — $n$ stars and $k - 1$ bars, choose the places of the bars.
Common mistakes
- Mixing up whether order matters: “choose two people on duty” is combinations, “choose a head and a deputy” is arrangements.
- Adding where you should multiply: steps of a choice in a row give a product.
- Forgetting that a number cannot start with zero.
- Using $k$ bars instead of $k - 1$ in stars and bars.