An interactive guide — counting without counting
You can count 5 apples by pointing at each one. But how do you count:
You can't list them all — there are too many. You need formulas that count without listing. That's what permutations and combinations are: shortcuts for counting large numbers of arrangements.
The core question is always: "How many ways?"
This is the foundation of everything. It's stupidly simple, but everything else is built on it:
If you make decisions in sequence, multiply the number of choices at each step.
$$\text{Total outcomes} = n_1 \times n_2 \times n_3 \times \cdots$$Think of it as a tree: each branch at step 1 leads to branches at step 2, etc. The total number of leaf nodes is the product.
You have 5 shirts, 3 pants, and 4 shoes.
Each morning you pick one of each: $5 \times 3 \times 4 = 60$ possible outfits.
Add 2 hat options (hat or no hat): $60 \times 2 = 120$.
This is exactly how e-commerce sites calculate "X product configurations available."
A license plate has 3 letters followed by 4 digits:
$26 \times 26 \times 26 \times 10 \times 10 \times 10 \times 10 = 26^3 \times 10^4 = 175{,}760{,}000$
That's ~175 million possible plates. More than enough for most countries.
This is also how you calculate password strength: a 12-character password using lowercase + uppercase + digits + symbols (95 chars) has $95^{12} \approx 5.4 \times 10^{23}$ possibilities.
A factorial is the product of all positive integers from 1 to $n$:
$5! = 5 \times 4 \times 3 \times 2 \times 1 = 120$
Special case: $0! = 1$ (by convention — there's exactly 1 way to arrange 0 things: do nothing)
Factorials answer the question: "How many ways can you arrange $n$ things in a line?"
Why? For position 1 you have $n$ choices. For position 2, $n-1$ remaining. Then $n-2$. And so on. By the counting principle: $n \times (n-1) \times \cdots \times 1 = n!$
Factorials grow absurdly fast:
| $n$ | $n!$ | Context |
|---|---|---|
| 3 | 6 | Ways to arrange 3 podium finishers |
| 5 | 120 | Ways to order 5 playlist songs |
| 10 | 3,628,800 | Ways to seat 10 dinner guests |
| 13 | 6,227,020,800 | Ways to arrange a suit of cards |
| 20 | ~2.4 × 10¹⁸ | More than grains of sand on Earth |
| 52 | ~8.1 × 10⁶⁷ | Ways to shuffle a deck — more than atoms in the universe |
A delivery driver needs to visit 15 addresses. How many possible routes? $(15-1)! = 14! = 87{,}178{,}291{,}200$ (we fix the start, so it's $(n-1)!$ for circular routes).
At 1 million routes evaluated per second, checking all of them takes ~24 hours. Add just 5 more stops: $19! \approx 1.2 \times 10^{17}$ — now it takes 3,800 years.
This is why NP-hard problems matter. Factorial growth makes brute force impossible very quickly. It's why Amazon, UPS, and Google Maps use heuristic algorithms, not exhaustive search.
A permutation is an arrangement where order matters. Choosing 1st, 2nd, and 3rd place is different from just choosing 3 winners.
"From $n$ items, arrange $r$ of them in order."
Why this formula? You have $n$ choices for the first slot, $n-1$ for the second, ..., down to $n-r+1$ for the last slot:
$$P(n,r) = n \times (n-1) \times (n-2) \times \cdots \times (n-r+1) = \frac{n!}{(n-r)!}$$Example: Gold, Silver, Bronze from 8 athletes:
A 4-digit PIN where no digit can repeat:
$P(10, 4) = 10 \times 9 \times 8 \times 7 = 5{,}040$ possible PINs.
Compare: if repetition IS allowed, it's $10^4 = 10{,}000$ PINs. The no-repeat constraint removes almost half the options.
Google has 1,000 relevant pages for a query but shows the top 10 in order. How many different result pages are possible?
$P(1000, 10) = 1000 \times 999 \times \cdots \times 991 \approx 9.6 \times 10^{29}$
Order matters here because result #1 gets ~30% of clicks while result #10 gets ~2%. The ranking is crucial, not just which pages are shown.
An OS has 20 ready processes and needs to decide the next 5 to run in order:
$P(20, 5) = 20 \times 19 \times 18 \times 17 \times 16 = 1{,}860{,}480$ possible schedules.
This is why scheduling algorithms don't try all permutations — they use heuristics (priority, round-robin, etc.).
A combination is a selection where order doesn't matter. Choosing a team of 3 people is the same regardless of the order you pick them.
"From $n$ items, choose $r$ of them." Also read as "$n$ choose $r$."
Why divide by $r!$? Because permutations count every arrangement of the same group as different. A team of {Alice, Bob, Carol} has $3! = 6$ arrangements, but they're all the same team. So:
$$C(n, r) = \frac{P(n, r)}{r!} = \frac{n!}{r!(n-r)!}$$Example: Choose 3 people from a team of 8 for a project:
Compare: $P(8,3) = 336$ permutations but only $56$ combinations. Because $\frac{336}{6} = 56$ — each group of 3 was counted $3! = 6$ times in the permutation count.
Pick 6 numbers from 1-49 (order doesn't matter, like most lotteries):
$\binom{49}{6} = \frac{49!}{6! \cdot 43!} = 13{,}983{,}816$
Your chance of winning: $\frac{1}{13{,}983{,}816} \approx 0.0000072\%$
If you buy one ticket per week, on average you'd win once every 268,919 years. The lottery is a tax on not understanding combinations.
Your team has 12 developers. Each PR needs 2 reviewers. How many different reviewer pairs are possible?
$\binom{12}{2} = \frac{12 \times 11}{2 \times 1} = 66$ possible pairs.
This is useful for building a round-robin review schedule that ensures every developer reviews with every other developer at least once.
An API has 15 endpoints. A tester wants to test every pair of endpoints called in sequence to find race conditions:
Ordered pairs (A then B ≠ B then A): $P(15, 2) = 15 \times 14 = 210$ test cases.
Unordered pairs (if order doesn't matter): $\binom{15}{2} = 105$ test cases.
For 3-endpoint combinations: $\binom{15}{3} = 455$ — still manageable. For all 5-endpoint combos: $\binom{15}{5} = 3003$ — getting expensive.
The hardest part isn't the formula — it's deciding which formula to use. Here's a decision tree:
Quick litmus tests:
1. "How many 3-letter strings from A-Z?" → Order matters (ABC ≠ BAC), repeats allowed → $26^3 = 17{,}576$
2. "How many ways to pick 5 cards from 52?" → Order doesn't matter (a hand is a hand) → $\binom{52}{5} = 2{,}598{,}960$
3. "How many ways can 4 runners finish a race?" → Order matters, no repeats → $P(4,4) = 4! = 24$
4. "How many 3-topping pizzas from 8 toppings?" → Order doesn't matter (pepperoni+mushroom = mushroom+pepperoni) → $\binom{8}{3} = 56$
5. "How many ways to assign 3 bugs to 5 devs?" → Depends! If each bug goes to a different dev AND order matters → $P(5,3)$. If bugs are assigned (order doesn't matter) → $\binom{5}{3}$. If any dev can get multiple bugs → $5^3$.
When order matters and items CAN repeat, it's simply:
$n$ choices for each of $r$ positions, independently.
Password of length 8 using lowercase letters (26 chars):
$26^8 = 208{,}827{,}064{,}576 \approx 2 \times 10^{11}$
Add uppercase (52): $52^8 \approx 5.3 \times 10^{13}$
Add digits (62): $62^8 \approx 2.2 \times 10^{14}$
Add symbols (95 printable ASCII): $95^8 \approx 6.6 \times 10^{15}$
Each extra character type multiplies possibilities enormously. But increasing LENGTH matters even more: $95^{12} \approx 5.4 \times 10^{23}$. Length beats complexity.
How many ways to arrange letters in MISSISSIPPI? Not $11!$, because the repeated letters create duplicates.
Divide by the factorial of each repeated item count.
MISSISSIPPI: 11 letters — M(1), I(4), S(4), P(2):
$$\frac{11!}{1! \cdot 4! \cdot 4! \cdot 2!} = \frac{39{,}916{,}800}{1 \cdot 24 \cdot 24 \cdot 2} = 34{,}650$$A router receives 10 packets: 4 are type-A, 3 are type-B, 3 are type-C. If packets of the same type are indistinguishable, how many distinct orderings?
$\frac{10!}{4! \cdot 3! \cdot 3!} = \frac{3{,}628{,}800}{24 \cdot 6 \cdot 6} = 4{,}200$ distinct sequences.
When order doesn't matter and items CAN repeat (like scooping ice cream flavors — you can pick the same flavor multiple times):
"Choose $r$ items from $n$ types, repetition allowed." Also called "multiset coefficient."
You have 10 identical stickers to distribute among 4 kids. Each kid can get 0 or more.
$n = 4$ types (kids), $r = 10$ items (stickers):
$\binom{4+10-1}{10} = \binom{13}{10} = \binom{13}{3} = 286$ ways.
In CS: this is the same as asking "how many solutions does $x_1 + x_2 + x_3 + x_4 = 10$ have where each $x_i \geq 0$?"
Pascal's Triangle is a visual layout of all binomial coefficients. Each number is the sum of the two above it:
This is why it works: choosing $r$ from $n$ items means either you include item $n$ (then choose $r-1$ from the remaining $n-1$) or you exclude it (choose $r$ from $n-1$).
Useful properties you can see in the triangle:
If you flip a coin 5 times, the number of ways to get exactly $k$ heads is $\binom{5}{k}$:
Row 5 of Pascal's Triangle: 1, 5, 10, 10, 5, 1
0 heads: 1 way | 1 head: 5 ways | 2 heads: 10 ways | 3 heads: 10 ways | 4 heads: 5 ways | 5 heads: 1 way
Total: $1+5+10+10+5+1 = 32 = 2^5$. Makes sense — 5 flips have $2^5$ total outcomes.
Probability of exactly 3 heads: $\frac{10}{32} = 31.25\%$
This is a powerful technique for distributing identical items into distinct groups. The name comes from the visual representation:
Problem: Distribute 7 identical cookies among 3 kids.
Represent cookies as stars (★) and use bars (|) to separate groups:
★★★|★★|★★ → Kid 1 gets 3, Kid 2 gets 2, Kid 3 gets 2
★★★★★★★|| → Kid 1 gets 7, Kid 2 gets 0, Kid 3 gets 0
||★★★★★★★ → Kid 1 gets 0, Kid 2 gets 0, Kid 3 gets 7
★|★★★|★★★ → Kid 1 gets 1, Kid 2 gets 3, Kid 3 gets 3
You always have $n$ stars and $k-1$ bars (where $k$ = number of groups). You're choosing where to place the bars among the $n + k - 1$ total symbols:
For 7 cookies, 3 kids: $\binom{7+3-1}{3-1} = \binom{9}{2} = 36$ ways.
You have $10,000 (in $1,000 units) to allocate among 4 departments. Each can get $0 or more.
$n = 10$ units, $k = 4$ departments:
$\binom{10+4-1}{4-1} = \binom{13}{3} = 286$ possible allocations.
If each department must get at least $1,000: give each $1,000 first (costs 4 units), then distribute remaining 6: $\binom{6+4-1}{4-1} = \binom{9}{3} = 84$ allocations.
A load balancer distributes 20 identical requests across 5 servers. How many possible distributions?
$\binom{20+5-1}{5-1} = \binom{24}{4} = 10{,}626$
If each server must handle at least 2 requests: pre-assign 2 each (uses 10), distribute remaining 10: $\binom{10+5-1}{5-1} = \binom{14}{4} = 1{,}001$.
If you stuff $n+1$ pigeons into $n$ pigeonholes, at least one hole has at least 2 pigeons. Obvious? Yes. Powerful? Incredibly.
Pigeonhole Principle: If $n$ items are placed into $m$ containers and $n > m$, then at least one container has more than one item.
Generalized: If $n$ items are in $m$ containers, at least one container has $\lceil \frac{n}{m} \rceil$ items.
MD5 produces 128-bit hashes = $2^{128}$ possible values. But the number of possible files is infinite. So by the pigeonhole principle, collisions MUST exist — different files that produce the same hash.
For a hash table with 1,000 slots and 1,001 keys: guaranteed at least one collision. With 2,000 keys: at least one slot has ≥ $\lceil 2000/1000 \rceil = 2$ keys.
In a group of 367 people, at least 2 share a birthday (366 possible days including leap day, 367 > 366). Guaranteed.
But — and this is surprising — with only 23 people, there's a >50% chance of a shared birthday. That's not pigeonhole; it's probability (covered in the Probability & Statistics guide).
Can you build a compression algorithm that makes every file smaller? No. There are $2^n$ possible files of length $n$ bits. If you compressed all of them to fewer than $n$ bits, you'd have fewer possible outputs than inputs — by pigeonhole, two different files would compress to the same thing, so you couldn't decompress uniquely.
This is why ZIP sometimes makes files bigger. Compression only works on files with redundancy.
Let's work through complete problems using everything above.
Q: A password must be 8-12 chars, use at least one uppercase, one lowercase, one digit, one symbol. From 95 printable ASCII chars. How many valid passwords?
Strategy: Total passwords minus invalid ones (inclusion-exclusion).
Total passwords of length $k$: $95^k$
Total for lengths 8-12: $\sum_{k=8}^{12} 95^k$
Then subtract passwords missing at least one required character type using inclusion-exclusion. Missing uppercase (69 chars left): $\sum 69^k$. Missing lowercase (69 chars): $\sum 69^k$. Missing digits (85 chars): $\sum 85^k$. Missing symbols (62 chars): $\sum 62^k$.
Then add back the double-missing, subtract triple-missing, etc. This is exactly inclusion-exclusion from set theory.
Q: An API has 20 endpoints. You want to test all possible 3-endpoint sequences (for integration tests). If order matters and repetition is allowed (you might call the same endpoint twice), how many test cases?
$20^3 = 8{,}000$ test cases (permutations with repetition).
If no repetition: $P(20, 3) = 20 \times 19 \times 18 = 6{,}840$
If order doesn't matter and no repetition: $\binom{20}{3} = 1{,}140$
At 2 seconds per test: 8,000 tests = ~4.4 hours. 1,140 tests = ~38 minutes. Knowing which formula to use saves real time and CI costs.
Q: You have 6 microservices to deploy across 3 servers. Each service goes to exactly one server. How many deployment configurations?
Each of 6 services independently chooses 1 of 3 servers: $3^6 = 729$.
If each server must have at least 1 service: subtract configs where a server is empty. By inclusion-exclusion:
$3^6 - \binom{3}{1}2^6 + \binom{3}{2}1^6 - \binom{3}{3}0^6 = 729 - 192 + 3 - 0 = 540$
| Scenario | Formula | Example |
|---|---|---|
| Sequential choices | $n_1 \times n_2 \times \cdots$ | Menu combos |
| Arrange all $n$ | $n!$ | Shuffle playlist |
| Arrange $r$ of $n$ (no repeat) | $P(n,r) = \frac{n!}{(n-r)!}$ | Podium places |
| Choose $r$ of $n$ (no repeat) | $\binom{n}{r} = \frac{n!}{r!(n-r)!}$ | Lottery, teams |
| Arrange $r$ with repeats | $n^r$ | Passwords, PINs |
| Choose $r$ with repeats | $\binom{n+r-1}{r}$ | Ice cream scoops |
| Arrange with identical items | $\frac{n!}{n_1! n_2! \cdots}$ | MISSISSIPPI |
| Distribute $n$ to $k$ groups | $\binom{n+k-1}{k-1}$ | Budget allocation |