# Counting & Combinatorics > How to count possibilities without listing them: multiply independent choices, and know when order matters (permutations) versus when it doesn't (combinations). It's the math behind probability, password strength, and why brute force blows up. --- # Counting & Combinatorics "How many ways are there to…?" sounds like a question you answer by listing them all and counting. For anything real - possible passwords, lottery tickets, ways to seat a team - that list is astronomically long, and listing is hopeless. Combinatorics is the art of getting the count *without* the list, and it rests on a few small, powerful rules. This guide builds them up: the multiplication principle (the engine behind almost all counting), then the crucial fork between **permutations** (when order matters) and **combinations** (when it doesn't), and finally why this matters far beyond puzzles - it's the foundation of probability, the reason a long password is strong, and the reason some problems are too big to brute-force. By the end, "how many ways" becomes a calculation, not a guess. ## How to read this - **Want the one rule that does the most?** [Phase 1](01-the-multiplication-principle.md) - the multiplication principle. - **Want the whole toolkit?** Read in order - permutations and combinations (Phase 2) build on it. ## The phases 1. **[The Multiplication Principle](01-the-multiplication-principle.md)** - counting independent choices by multiplying, and the "and vs or" rule. 2. **[Permutations & Combinations](02-permutations-and-combinations.md)** - order matters vs order doesn't, factorials, and the formulas (with runnable code). 3. **[Why Counting Matters](03-why-counting-matters.md)** - the bridge to probability, password strength, and combinatorial explosion (why brute force fails). > This builds on [Numbers & Number Systems](/guides/numbers-and-number-systems) and the set idea from > [Sets, Relations & Functions](/guides/sets-relations-and-functions). It sets up the last foundation: > probability and statistics. --- # The Multiplication Principle ## "How many ways…?" and the urge to list Someone asks: how many outfits can you make from your shirts and pants? Your instinct is to start listing. Blue shirt with jeans, blue shirt with khakis, white shirt with jeans… and around outfit five you lose track of what you've already counted. That instinct - *list everything, then count the list* - works for tiny problems and collapses for real ones. How many 4-digit PINs are there? How many ways can a deck of cards be shuffled? You can't list those by hand in one lifetime. The point of counting (the branch of math, not the nursery-rhyme kind) is to get the exact number *without ever writing the list down*. The good news: most of counting rests on one short rule. Once it clicks, a surprising amount of "how many ways" falls out of it. If numbers still feel shaky, [Why math isn't your enemy](/guides/why-math-isnt-your-enemy) is a gentle warm-up - but you don't need it to follow along here. ## The multiplication principle The rule, in one sentence: > If you make one choice that has **m** options, and then a second choice that has > **n** options, the two choices **together** can be made in **m × n** ways. Back to the outfits. Say you have 2 shirts and 3 pants. Pick a shirt (2 ways), then pick pants (3 ways). The total is 2 × 3 = **6**. Not 2 + 3 = 5 - multiply, don't add. Here's why, drawn as a tree: ```text shirt pants outfit ┌ jeans → shirt A + jeans ┌ shirt A ────┼ khakis → shirt A + khakis │ └ shorts → shirt A + shorts start ──┤ │ ┌ jeans → shirt B + jeans └ shirt B ────┼ khakis → shirt B + khakis └ shorts → shirt B + shorts ``` Look at the structure. For **each** of the 2 shirts, the same 3 pants branch out. You get 3 outfits, then another 3 - the 3 repeats once per shirt. "The same n options, repeated for each of the m" is what multiplication means. The tree has 6 leaves, and m × n gives 6 without drawing anything. The word that signals multiplication is **and then**: shirt *and then* pants. ## Extending to many stages Nothing stops at two choices. Add a third choice with **p** options, a fourth with **q**, and so on, and you keep multiplying: > total = m × n × p × q × … Each new stage multiplies the running total by its own option count, because the tree branches out again for every leaf you already had. A clean example: a **4-digit PIN** where each digit can be 0 to 9. That's 4 stages, each with 10 options: ```text 10 × 10 × 10 × 10 = 10,000 ``` So there are exactly **10,000** possible PINs (0000 through 9999 - count them, that's ten thousand numbers). You found that without listing one. That's the multiplication principle earning its keep. ## The sum rule: "and" multiplies, "or" adds The multiplication principle has a sibling that trips people up, so let's separate them cleanly. - **Multiplication (the "and then" rule):** you make a sequence of choices, all of which happen. Shirt **and then** pants. These are *stages* of one combined choice → **multiply**. - **Addition (the "or" rule, also called the sum rule):** you pick **one** option from two separate, non-overlapping groups. These are *alternatives*, only one happens → **add**. Concretely. For lunch you order from the soup menu (4 soups) **or** the salad menu (3 salads), and you get exactly one item. ```text 4 soups OR 3 salads → 4 + 3 = 7 possible lunches ``` You add, because you choose a single lunch from one list *or* the other - never both. Contrast: if lunch is a soup **and** a salad together, you multiply: 4 × 3 = 12 combos. The test: do the choices stack up (and → multiply) or compete as alternatives (or → add)? Keep this sharp - mixing them up is the single most common counting mistake. > ℹ️ The two rules combine freely. "A main dish, plus a soup **or** a salad" is > mains × (soups + salads). Group the "or" with parentheses, then multiply the stages. ## For builders If you write code, you already use the multiplication principle, maybe without naming it. - **Nested loops multiply.** A loop of 1,000 iterations inside a loop of 1,000 runs the inner body 1,000 × 1,000 = 1,000,000 times. The total work is the product of the loop counts - that's the multiplication principle, and it's why innocent-looking nesting blows up. - **State spaces are products.** A struct with 3 boolean fields has 2 × 2 × 2 = 8 possible states. A config with one of 4 log levels and one of 5 regions has 4 × 5 = 20 combinations. Counting reachable states is a multiplication. - **Input space sizing.** "How many distinct inputs could hit this function?" is a multiplication-principle count over each parameter's range. It tells you at once why exhaustive testing is usually impossible. If choices remind you of picking elements from sets, that's no coincidence - [Sets, relations, and functions](/guides/sets-relations-and-functions) frames a combined choice as picking one element from each of several sets, and the size of all such combinations is exactly the product of the set sizes. ## ⚠️ The one assumption: options must not depend on history Multiplication has a quiet requirement. It works only when the option count for the next choice **does not depend on what you chose before**. The PIN example fits: after the first digit, you still have all 10 digits for the second, because repeats are allowed. Break that assumption and the rule changes. Say you're seating 4 different people in 4 chairs, one per chair, **no repeats**. The first chair has 4 candidates. But once someone sits, only 3 remain for the second chair, then 2, then 1. The options shrink: ```text 4 × 3 × 2 × 1 = 24 (not 4 × 4 × 4 × 4) ``` You still *multiply* - but you multiply the *actual* number of options at each stage, which now decreases because each pick removes a candidate. That adjustment, where order matters and repeats aren't allowed, is exactly what **permutations** are about, and it's where the next phase picks up. ## Recap - **Multiply independent choices.** m options then n options → m × n total. The signal word is **and then**. - **Extend across stages:** m × n × p × … A 4-digit PIN (0–9 each) gives 10 × 10 × 10 × 10 = 10,000. - **"And" multiplies, "or" adds.** Sequential stages that all happen → multiply; mutually exclusive alternatives where only one happens → add. - **For builders:** nested-loop counts, state spaces, and input spaces are all products. - **The catch:** multiplication assumes the next choice's option count is fixed. When picks remove options (no repeats), you adjust each factor - that's permutations, next. A quick check before you move on: ```quiz [ { "q": "You can pick one of 5 appetizers and then one of 4 mains. How many appetizer-and-main meals are possible?", "choices": ["9", "20", "5", "1"], "answer": 1, "explain": "Two stages that both happen ('and then'), so multiply: 5 × 4 = 20. Adding (5 + 4 = 9) would be the answer only if you picked one item OR the other, not both." }, { "q": "How many different 4-digit PINs are there if each digit can be 0 through 9?", "choices": ["40", "1,000", "10,000", "100,000"], "answer": 2, "explain": "Four stages, 10 options each, repeats allowed: 10 × 10 × 10 × 10 = 10,000 (the PINs 0000 through 9999)." }, { "q": "A coffee comes in 3 sizes, and separately you may add 1 of 2 syrups OR skip syrup entirely. How many size-and-syrup choices are there?", "choices": ["6", "5", "9", "3"], "answer": 2, "explain": "Syrup is an 'or': 2 syrups or none = 2 + 1 = 3 syrup options. Size is an 'and then': 3 sizes × 3 syrup options = 9. The 'or' adds inside the parentheses; the stages multiply." } ] ``` --- # Permutations & Combinations In [Phase 1](01-the-multiplication-principle.md) you learned to count step by step: if a choice has *a* options and the next has *b* options, the two together have *a × b* outcomes. That idea powers everything here. This phase asks two of the most common counting questions you'll ever meet - and the only thing separating them is a question you have to learn to ask out loud. ## The two questions Almost every "how many ways…" problem is one of these: - **Order matters.** Gold, silver, bronze are different. Seat 1 and seat 2 are different. Counting these is **permutations**. - **Order doesn't matter.** A handful of pizza toppings is the same handful in any order. A committee is the same committee no matter who you name first. Counting these is **combinations**. Same raw ingredients - pick *r* things from *n* - but two very different counts. Before any formula, build the reflex: *does swapping two of my chosen things change the answer?* If yes, order matters. If no, it doesn't. ## Factorial: counting orderings Start with the simplest "order matters": arrange *all* of your items. How many ways can 3 books sit on a shelf? Pick the leftmost: 3 choices. The next: 2 books remain. The last spot: 1 book left. By the multiplication principle that's `3 × 2 × 1 = 6`. That product - multiply every whole number from *n* down to 1 - is the **factorial**, written `n!`: ``` n! = n × (n − 1) × (n − 2) × … × 1 ``` So `5! = 5 × 4 × 3 × 2 × 1 = 120`. Factorials grow ferociously fast: `10!` is already over three million. One value surprises people: `0! = 1`. Read it as "how many ways are there to arrange nothing?" Exactly one - the empty arrangement. It isn't a typo or a special case bolted on; it's the value that keeps the formulas below from breaking, as you'll see in a moment. ## Permutations: arranging a few of many Often you arrange a *few* items, not all of them. **Eight runners, and you want the top three: gold, silver, bronze.** Order absolutely matters (gold is not bronze). Walk it like Phase 1: - Gold: 8 runners could win it. - Silver: 7 remain. - Bronze: 6 remain. That's `8 × 7 × 6 = 336` possible podiums. Notice you multiplied only 3 of the factors of `8!`, then stopped. The formula captures exactly that "stop early": ``` nPr = n! / (n − r)! ``` The `(n − r)!` in the denominator cancels off the factors you *didn't* use. Check it: `8! / 5! = (8 × 7 × 6 × 5!) / 5! = 8 × 7 × 6 = 336`. The 5! divides clean away, leaving the three factors you actually counted. Here *n* = 8 (the pool), *r* = 3 (the spots), and the order of those 3 is part of what makes each podium distinct. ## Combinations: choosing without order Now change one word in the question. **Eight pizza toppings, and you want three of them.** Mushroom-pepper-onion is the *same pizza* as onion-mushroom-pepper. Order doesn't matter, so we should count *fewer* than 336 - because we decided a bunch of those 336 were duplicates. How many duplicates? Any single group of 3 toppings can be listed in `3! = 6` orders, and the permutation count treated all 6 as separate. So we overcounted every real selection by a factor of `3!`. Divide it back out: ``` 336 / 6 = 56 ``` That's the **combination** count, and the formula bakes in that division: ``` nCr = n! / (r! (n − r)!) ``` It's `nPr` with one extra `r!` in the denominator - the exact factor by which order inflated the count. Same eight things, same three picks, but 56 instead of 336. ## See it run Python has all three built in. Run this: ```python runnable import math print(math.factorial(5)) # 120 print(math.perm(8, 3)) # ordered: 8*7*6 = 336 print(math.comb(8, 3)) # unordered: 56 ``` *What just happened:* `math.factorial(5)` printed **120** - the orderings of 5 items. `math.perm(8, 3)` printed **336** - the ordered top-3 podiums (`8 × 7 × 6`). `math.comb(8, 3)` printed **56** - the unordered 3-topping selections. The permutation count is larger than the combination count because order multiplies in extra arrangements: every one of those 56 selections shows up `3! = 6` times when order is tracked, and `56 × 6 = 336`. ## The deciding question, side by side Hold the contrast in your head - the numbers are identical and the answers are not: | Question | Order? | Count | |---|---|---| | Top-3 finishers (gold/silver/bronze) from 8 runners | matters | 336 | | 3-person committee from 8 people | doesn't | 56 | Both pick 3 from 8. The committee is six times smaller for one reason: a committee of {Ana, Ben, Cleo} is one committee, but as a ranking it's six different podiums. Decide *order or not* first; the formula is the easy part. ## For builders This shows up the moment you count possibilities in code or size a problem: - **Choosing a subset → combinations (`nCr`).** Feature flags turned on, cards dealt from a deck, which sensors to sample, which test cases to bundle. The selection is a *set*; order is meaningless. - **Arranging or ranking → permutations (`nPr`).** Tournament seedings, leaderboard top-N, the order tasks run in, password/PIN spaces where position matters. Gut check before you reach for a library: if reordering your answer gives you "the same thing," you want `comb`. If reordering gives you "a different thing," you want `perm`. Both live in Python's `math` module, so you rarely write the factorials by hand. > ⚠️ **The classic mistake:** using permutations when order doesn't matter. You'll overcount > by exactly a factor of `r!`. That isn't a coincidence - it *is* the `r!` sitting in the > denominator of `nCr`. If a count comes out suspiciously large (your 56 committees ballooned > to 336), ask whether you accidentally counted the same group in every possible order. ## Recap - `n!` counts the orderings of *n* distinct items; `0! = 1`. - **Permutations** (`nPr = n! / (n − r)!`) count arrangements - order matters. - **Combinations** (`nCr = n! / (r! (n − r)!)`) count selections - order doesn't. - The difference between them is the factor `r!`, the number of ways to reorder your *r* picks. - Always ask the deciding question first: *does order matter?* Everything else follows. This whole machine is built from the multiplication principle and the idea of distinct items - if "distinct" feels slippery, [Sets, relations, and functions](/guides/sets-relations-and-functions) makes the notion of a set (order-free, no repeats) precise. And if the formulas still feel like spells, [Why math isn't your enemy](/guides/why-math-isnt-your-enemy) is worth a detour. Quick check before moving on: ```quiz [ { "q": "What does n! (n factorial) count?", "choices": [ "The number of ways to arrange n distinct items in order", "The number of ways to choose some of n items, ignoring order", "The sum of all whole numbers from 1 to n", "The number of subsets of an n-item set" ], "answer": 0, "explain": "n! = n × (n−1) × … × 1 multiplies the choices at each position, which is exactly the count of orderings of n distinct items." }, { "q": "You're choosing a 3-person committee from 10 people. Permutation or combination?", "choices": [ "Permutation, because you pick people one at a time", "Combination, because the committee is the same regardless of the order you name people", "Permutation, because 3 is smaller than 10", "Neither - it's a plain factorial" ], "answer": 1, "explain": "Reordering the committee members gives the same committee, so order doesn't matter. That's a combination (nCr)." }, { "q": "How many ways can you choose 2 toppings from 4 (order doesn't matter)?", "choices": [ "12", "8", "6", "4" ], "answer": 2, "explain": "nCr = 4! / (2! · 2!) = 24 / 4 = 6. (As a permutation it would be 4 × 3 = 12, which double-counts each pair.)" } ] ``` --- # Why Counting Matters You spent two phases learning to count carefully - the multiplication principle, factorials, permutations, combinations. If a quiet voice has been asking *but why does any of this matter?*, this is the phase where it pays off. The straight answer up front: counting is rarely the destination. It's the floor that three much bigger ideas stand on. When you can count the number of ways something can happen, you can suddenly reason about how *likely* it is, how *hard* it is to break, and how *impossible* it is to brute-force. Same skill, three payoffs. Let's walk through each. ## The probability bridge Imagine a bag with 10 marbles: 3 red, 7 blue. You reach in without looking. What's the chance you pull a red one? Most people feel the answer before they can justify it: 3 out of 10. But notice what your brain did. It counted two things - the outcomes you'd be happy with (3 reds) and the total outcomes possible (10 marbles) - and divided one by the other. That's the whole idea. When every outcome is **equally likely**, the probability of an event is: ``` probability = (favorable outcomes) / (total outcomes) ``` Both halves of that fraction are *counts*. The top is "how many ways can the thing I care about happen." The bottom is "how many ways can anything happen at all." Probability is two counting problems wearing a trench coat. The equally-likely part matters, so be clear about it. This formula works cleanly when no outcome is favored - a fair coin, a well-shuffled deck, marbles you can't see. If the dice are loaded, you need heavier machinery. But an enormous slice of real probability starts right here, with careful counting on top and bottom. Now the payoff. Think about a lottery where you pick 6 numbers out of 49, order not mattering. That's a combination - the kind you learned to count in Phase 2: ``` C(49, 6) = 13,983,816 ``` There is exactly **one** winning combination. So your probability of winning with a single ticket is: ``` 1 / 13,983,816 ``` That bottom number isn't a vague "it's really unlikely." It's a count - the precise number of distinct tickets that could be drawn - and it's why the odds feel so brutal once you see them written out. The lottery isn't magic. It's a counting problem, and counting tells you the truth. > **The bridge in one line:** every probability question is secretly asking "favorable count over > total count." If you can count both, you can find the probability. This is where the next Mathematics foundation picks up - taking this favorable-over-total idea and building real probability and statistics on top of it. For now, sit with the bridge: counting is the thing that makes probability *computable* instead of a gut feeling. ## Password and key strength Here's a place where counting protects you personally. When someone tries to guess your password by brute force, they walk through every possibility one at a time. So the strength of a password is, very literally, **how many possibilities there are** - a counting problem you already know how to solve. If your password is `length` characters long, and each character is drawn from a set of `charset` possible symbols, then by the multiplication principle (one choice per position, multiplied together) the number of possible passwords is: ``` charset ^ length ``` That little `^` is doing something dramatic. Multiplication grows fast; repeated multiplication (exponentiation) grows *terrifyingly* fast. Let's compute real numbers instead of arm-waving. ```python runnable # Lowercase letters only: 26 possible characters per position. charset = 26 short = charset ** 8 # an 8-character password longer = charset ** 12 # a 12-character password print("8 lowercase chars: ", short) print("12 lowercase chars:", longer) print("ratio:", longer // short, "times bigger") ``` *What just happened:* we counted the password space for two lengths using the same `charset ^ length` rule. Going from 8 to 12 characters - only four more letters - multiplied the number of possibilities by `26**4`, which is `456,976`. The longer password isn't a little stronger. It's hundreds of thousands of times harder to brute-force, and we used nothing fancier than the multiplication principle from Phase 1. This explains advice that sounds backwards until you do the counting. A long passphrase of plain lowercase words often beats a short password stuffed with symbols. Symbols grow the `charset`; length grows the *exponent*. And the exponent wins, because it multiplies the entire space every time you add a character. > **The lesson:** every extra character multiplies the search space. Length is leverage, and the > leverage is exponential. ## Combinatorial explosion The same exponential growth that protects your password also makes some problems flat-out impossible to solve by trying everything. You met two fast-growing creatures in earlier phases. Let's watch them run. `n!` (factorial) counts the arrangements of `n` distinct items - the permutations from Phase 2. It starts gently, then leaves the building: ``` 5! = 120 10! = 3,628,800 20! = 2,432,902,008,176,640,000 ``` `2^n` counts the number of subsets of an `n`-item set (each item is either in or out - two choices per item, multiplied together): ``` 2^10 = 1,024 2^20 = 1,048,576 2^50 = 1,125,899,906,842,624 ``` Look at `20!` and `2^50`: numbers so large that a computer checking a billion options per second would still be working long after you've retired. This runaway growth has a name - **combinatorial explosion** - and it's not a rare edge case. It shows up the moment a problem involves "try every arrangement" or "try every subset." That's why "brute-force it" stops being a real plan. Say you want the shortest route that visits 20 cities and returns home. There are `20!` possible orderings. You could buy every computer on Earth and still not finish checking them in your lifetime. The problem isn't that you're not clever enough to write the loop. The loop is fine. The *count* is the wall. This is the secret link between counting and computational complexity - the study of why some problems are easy and others are hard. When you hear that an algorithm is "exponential" or "factorial" time, that phrase describes exactly the explosion you watched. Counting is how you *see* a problem's difficulty before you write a line of code. (You'll meet big-O notation properly elsewhere; for now, the felt sense - "this count grows faster than any machine can keep up with" - is the real prize.) ## For builders This stops being abstract the moment you ship software. Say you add five on/off feature flags. How many distinct combinations of flags can a user end up in? Each flag is on or off - two choices, five flags - so it's `2^5 = 32` states. Add five more flags and you're at `2^10 = 1,024`. This is **state-space explosion**, and it's why "we'll test every combination" quietly becomes a lie as your config grows. You can't test all 1,024 by hand, and the number doubles with every flag you add. The same wall explains why you can't test every possible *input* to a function. A function taking a single 32-bit integer already has over four billion possible inputs. Counting tells you at once that exhaustive testing is off the table - which is why we lean on chosen examples, edge cases, and property-based tests instead of brute force. One more place this intuition pays rent: hashing. A hash maps a giant space of inputs down into a much smaller space of fixed-size outputs. The instant the input space is bigger than the output space - which counting makes obvious - two different inputs *must* eventually land on the same output. That unavoidable overlap is a **collision**, and the reason it's unavoidable is a pure counting argument: you can't fit more pigeons than holes without doubling up. > **For builders, in one breath:** if a feature multiplies your states, count them before you promise > to test them all. ## What we've built Three phases, one skill, and now you can see what it was for: - **Probability** is favorable counts over total counts. Counting makes "how likely" into a number. - **Security** is a counting problem in disguise - `charset ^ length` - and length is exponential leverage. - **Hard problems** are problems whose answer space explodes (`n!`, `2^n`) faster than any machine can search. Counting is how you spot that wall in advance. If Phase 1 taught you *how* to count and Phase 2 taught you *what* to count for arrangements and selections, this phase was the *why*: counting is the quiet foundation under probability, under security, and under the very idea of what computers can and can't do. That first payoff - favorable over total - is the doorway to the last Mathematics foundation: probability and statistics, where you'll take this exact fraction and build a whole way of reasoning about uncertainty on top of it. You've already done the hard part. You learned to count. A quick check before you go: ```quiz [ { "q": "For equally likely outcomes, the probability of an event equals:", "choices": [ "total outcomes divided by favorable outcomes", "favorable outcomes divided by total outcomes", "favorable outcomes minus total outcomes", "favorable outcomes multiplied by total outcomes" ], "answer": 1, "explain": "Probability for equally likely outcomes is (favorable outcomes) / (total outcomes) - both halves are counts, which is why counting is the bridge to probability." }, { "q": "A password has 'length' characters, each chosen from 'charset' possible symbols. How many possible passwords are there, and what does adding length do?", "choices": [ "charset times length; adding length adds a fixed amount", "length raised to charset; adding length barely changes it", "charset raised to length; adding length multiplies the space exponentially", "charset plus length; adding length grows the space linearly" ], "answer": 2, "explain": "By the multiplication principle the count is charset ^ length, so each extra character multiplies the entire space - length is exponential leverage, which is why a longer password beats a short complex one." }, { "q": "Why can't you brute-force the shortest route through 20 cities by checking every ordering?", "choices": [ "Because 20! is so enormous that no machine can check all the orderings in any reasonable time", "Because computers cannot store routes between cities", "Because the multiplication principle does not apply to routes", "Because there is no way to count the orderings at all" ], "answer": 0, "explain": "There are 20! orderings - combinatorial explosion. The answer space grows far faster than any computer can search, so brute force hits a wall made of counting, not cleverness." } ] ```