Counting principles
Combinatorics is the art of counting without listing. It answers 'how many?' for passwords, schedules, molecules, and algorithms.
Sum and product rules
If a task can be done in one of \(m\) ways or one of \(n\) ways (no overlap), there are \(m + n\) ways: the sum rule. If it is done in two stages with \(m\) and then \(n\) choices, there are \(mn\) ways: the product rule. An 8-character password of lowercase letters has \(26^8 \approx 2 \times 10^{11}\) possibilities.
Permutations
An arrangement of \(r\) items chosen from \(n\) in order is a permutation: \(P(n, r) = \frac{n!}{(n-r)!}\). Arranging 3 of 7 books on a shelf: \(7 \cdot 6 \cdot 5 = 210\). All \(n\) items can be arranged in \(n!\) ways.
P(n,r) = \frac{n!}{(n-r)!}Combinations
Choosing \(r\) items from \(n\) when order does not matter: \(\binom{n}{r} = \frac{n!}{r!(n-r)!}\). A 5-card poker hand from 52 cards: \(\binom{52}{5} = 2{,}598{,}960\). Symmetry: \(\binom{n}{r} = \binom{n}{n-r}\), since choosing what to take is the same as choosing what to leave.
\binom{n}{r} = \frac{n!}{r!(n-r)!}Arrangements with repetition
The number of distinct arrangements of the letters of MISSISSIPPI is \(\frac{11!}{1!\,4!\,4!\,2!} = 34{,}650\): divide by the factorials of repeated letters, because swapping identical letters gives the same word. This is the multinomial coefficient.
Stars and bars
How many ways can 10 identical sweets be shared among 4 children? Represent sweets as stars and dividers as bars: \(\binom{10 + 3}{3} = 286\). In general, distributing \(n\) identical items into \(k\) groups gives \(\binom{n + k - 1}{k - 1}\) ways. This also counts solutions of \(x_1 + \cdots + x_k = n\) in non-negative integers.
\binom{n+k-1}{k-1}Complementary counting
Sometimes counting what you do not want is easier. How many 4-digit PINs have at least one repeated digit? Total \(10^4 = 10{,}000\), minus those with all different digits, \(10 \cdot 9 \cdot 8 \cdot 7 = 5{,}040\), gives \(4{,}960\).
Inclusion-exclusion for three sets
\(|A \cup B \cup C| = |A| + |B| + |C| - |A \cap B| - |A \cap C| - |B \cap C| + |A \cap B \cap C|\). Example: integers from 1 to 100 divisible by 2, 3, or 5: \(50 + 33 + 20 - 16 - 10 - 6 + 3 = 74\).
Choosing the right tool
Ask: does order matter (permutation versus combination)? Can items repeat? Are items identical or distinct? Are there restrictions best handled by complements or cases? Writing a small example by hand often reveals which formula applies.
Key takeaways
Add for alternatives, multiply for stages. Permutations count ordered selections and combinations unordered ones. Divide by factorials of repeats. Stars and bars distributes identical items. Complements and inclusion-exclusion handle 'at least' and overlapping conditions.
Flashcard
m + n ways for non-overlapping alternatives
Check your understanding
How many ways can 4 people be chosen from 9 for a team (order irrelevant)?