The Sum and Product Rules

The sum and product rules are simply the two ways counts combine: "this or that" means add, and "this and then that" means multiply. They're good for counting things you could never list by hand, like every possible license plate or password, and the whole unit rests on them. The formula has just two pieces: $|A \cup B| = |A| + |B|$ (if you pick from one pile or the other, and nothing is in both, the totals add) and $|A \times B| = |A| \cdot |B|$ (if you pick one from each pile, every first pick pairs with every second pick). The bars $|\;|$ just mean "how many." Bear with the notation; it's only bookkeeping for things you already do without thinking.

Product rule. Say you have 4 shirts and 3 pairs of pants. Each shirt can go with any of the 3 pants, so you get 3 outfits per shirt, and 4 shirts give $4 \cdot 3 = 12$. That's all the product rule is: if a choice is made in stages, and the number of options at each stage doesn't depend on what you picked earlier, multiply. A license plate with 3 letters and then 3 digits is six stages, so it has $26^3 \cdot 10^3 = 17{,}576{,}000$ possibilities.

Sum rule. If the possibilities split into cases that don't overlap, add the cases. A starter that's either one of 5 appetizers or one of 3 soups has $5 + 3 = 8$ options. Notice the difference: you pick an appetizer or a soup, not one of each, so nothing pairs up and there's nothing to multiply.

The complement trick. Sometimes counting what you don't want is much easier. How many 3-letter strings contain at least one A? "At least one" splits into messy cases (one A, two A's, three A's, in various spots). But the strings with no A are easy: 25 choices per letter, so $25^3$. Subtract from all strings and you get $26^3 - 25^3$.

A tree diagram draws the product rule: each stage branches, and the leaves at the end are the outcomes. There's an interactive one further down where you can change the number of branches at each stage.

A common mistake. It's tempting to reuse the same count at every stage, or to add whenever you see "or." Both can go wrong. If a 4-digit PIN can't repeat digits, the second digit has 9 choices, not 10, because one digit is already used up; the count still doesn't depend on which digit you picked, so you can multiply $10 \cdot 9 \cdot 8 \cdot 7$. That idea grows into permutations in the next lesson. And if you count "cards that are red or kings" as $26 + 4$, you've counted the two red kings twice, because those cases overlap. Fixing overlaps is what inclusion–exclusion does, later in this unit.

Password policies, IP address ranges and license plate formats are all sized with the product rule.