Counting without listing
Combinatorics gives rules to count arrangements and selections without enumerating them one by one. A few core principles cover most problems.
The two foundational rules
- Sum rule: if a choice falls into separate, non overlapping cases, add the counts of each case.
- Product rule: if a task is a sequence of independent steps, multiply the number of options at each step.
These combine to count complex structures. The sum rule handles "or" situations; the product rule handles "and then" situations.
Permutations and combinations
- A permutation counts ordered arrangements. Arranging k of n items gives n times n minus one and so on for k terms.
- A combination counts unordered selections and equals the binomial coefficient n choose k, the permutation count divided by k factorial to cancel orderings.
Knowing whether order matters is the crucial decision: it determines whether you divide out the duplicate arrangements.
Common pitfalls
Watch for overcounting, where the same outcome is produced by several paths, and double counting, where overlapping cases inflate the sum. The inclusion exclusion principle exists precisely to correct overlaps.
Key idea
Counting rests on the sum rule for separate cases and the product rule for sequential choices; permutations count ordered arrangements and combinations count unordered selections, and you must guard against overcounting.