Combinatorics & counting
Overview
The mathematics of counting possible configurations: permutations (order matters) and combinations (order doesn't matter).
Many probability and 'find the number of ways' DP problems rely on understanding when to multiply independent choices or how to compute nCr quickly.
Where used: Probability calculations, Dynamic Programming optimizations
Why learn this
- It helps you calculate the theoretical upper bound of Brute Force algorithms before you even code them.
- You need it to solve 'Count the number of valid X' math problems in O(1) instead of using backtracking.
Common mistakes
- Confusing Permutations and Combinations: If the problem asks 'How many ways to select a team of 3 from 10 people?', order doesn't matter (10C3). If it asks 'How many ways to award Gold, Silver, and Bronze?', order matters (10P3). Choosing the wrong one drastically changes the answer.
- Integer Overflow in factorials: Computing `100!` directly is impossible in many languages (e.g., Java, C++) without a BigInt class. You must compute combinations by alternating multiplication and division, or by using Pascal's Triangle (DP).
Recall questions
- What is the formula for 'n choose k' (combinations)?
- If you have 3 shirts and 4 pants, how many outfits can you make, and what rule is this?
Understanding checks
How many ways can you arrange the letters in the word 'DOG'?
6 ways.
It's a permutation of 3 distinct items, so 3! = 3 * 2 * 1 = 6.
When computing combinations `nCr(n, r)` using a loop, why should you interleave multiplying by `(n-i)` and dividing by `(i+1)` instead of doing all multiplications first?
To keep the intermediate values as small as possible and avoid integer overflow.
Factorials grow extremely fast. Interleaving division ensures the running product never gets unnecessarily huge, while mathematically guaranteeing it always remains an integer.
Practice tasks
Unique Paths
A robot is located at the top-left corner of a `m x n` grid. It can only move either down or right at any point in time. Use combinatorics (nCr) to find the number of unique paths to the bottom-right corner in O(m) time.
Continue learning
Previous: Recursive tree thinking