# 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." } ] ```