Counting & Combinatorics
Systematic counting underpins probability, algorithms and security. Learn the sum and product rules, permutations and combinations, arrangements with repetition, the binomial theorem and Pascal's triangle, inclusion–exclusion, the pigeonhole principle, and recurrence relations.
How many test cases cover all configuration options? How long would a brute-force password attack take? How many ways can a sample be drawn for inspection? Combinatorics gives exact answers.
An analogy
Permutations count ways to line people up (order matters); combinations count ways to pick a team (order doesn't).
Rules of counting
Sum rule for either/or choices, product rule for sequences of choices. Draw a decision tree when unsure.
Order and repetition
Decide: does order matter? Is repetition allowed? That picks nʳ, P(n, r), C(n, r) or multiset formulas.
Binomial coefficients
Pascal's triangle C(n, k) = C(n − 1, k − 1) + C(n − 1, k). They appear in the binomial distribution and polynomial expansions.
Recurrences and pigeonhole
Recurrences (Fibonacci, Tower of Hanoi aₙ = 2aₙ₋₁ + 1) describe algorithm costs. Pigeonhole proves collisions must exist (hash tables, birthday problem).
Formulas
- Product rule:
k independent choices with n₁, n₂, … options → n₁n₂… outcomes - Permutations / combinations:
P(n, r) = n!/(n − r)!; C(n, r) = n!/(r!(n − r)!) - With repetition:
nʳ sequences; C(n + r − 1, r) multisets - Binomial theorem:
(a + b)ⁿ = Σ C(n, k) aⁿ⁻ᵏ bᵏ - Pigeonhole:
n + 1 items in n boxes ⇒ some box has ≥ 2
Worked example: Selections
Given: 10 candidates
Find: Ways to fill 3 distinct posts; ways to pick a 3-person team.
- P(10, 3) = 720
- C(10, 3) = 120
Answer: 720 and 120
Worked example: Binomial coefficient
Given: (2x + 1)⁵
Find: Coefficient of x³.
- C(5, 3)(2x)³(1)² = 10 × 8x³
Answer: 80
Common mistakes
- Wrong: Using permutations when order doesn't matter. — Right: Divide by r! → combinations.
- Wrong: Forgetting repetition is allowed. — Right: Passwords allow repeats: nʳ.
Applications
- Test coverage: Combinatorial and pairwise testing.
- Security: Key and password space sizes.
- Reliability: k-out-of-n system configurations.
Key takeaways
- Sum and product rules.
- Order? repetition? → pick the formula.
- Binomial theorem and Pascal.
- Pigeonhole and recurrences.
Going further
- Generating functions: Solve recurrences and counting problems.
- Stirling's approximation: n! ≈ √(2πn)(n/e)ⁿ.
- Birthday paradox: Hash collision probabilities.