Addition and multiplication rules for counting possibilities.
Deep-dive lesson - accessible entry point but dense material. Use worked examples and spaced repetition.
When problems ask “How many ways?”, you usually don’t need to list everything. You need the two counting principles that let you count outcomes safely: add when choices are alternatives, multiply when choices are steps.
Use |S| to mean “how many outcomes are in set S.”
The main skill is recognizing whether the situation is “either/or” (add) or “and then” (multiply), and checking overlap to avoid double-counting.
Counting principles are the basic rules that let you compute the size of a set of outcomes without listing them one by one.
In computer science and math, you constantly face “space of possibilities” questions:
Listing every outcome is often impossible. Counting principles are a shortcut: they let you compute the cardinality of a finite set.
A set S is a collection of distinct elements (outcomes). The notation
Examples:
The word distinct matters: sets do not count duplicates.
Almost all “how many ways” problems at this level reduce to one of two patterns:
1) Alternatives (either/or) → Addition rule
2) Sequential choices (and then) → Multiplication rule
A good mental model is: outcomes are points in a space.
We will build both rules carefully, with examples, and we’ll practice diagnosing which rule applies.
If A and B are sets of outcomes:
Don’t worry if ∩, ∪, and × look unfamiliar: we’ll explain them as we go.
Addition is the right operation when you have alternatives:
If the groups do not overlap (no outcome is counted in both), then total outcomes are just the combined count.
Let A and B be sets of outcomes.
When A and B are disjoint, there is no overlap, so nothing gets double-counted.
If A ∩ B = ∅, then:
This extends to more than two sets: if A₁, A₂, …, Aₖ are pairwise disjoint (no overlaps), then
Suppose you can choose:
If you must choose exactly one of these (sandwich or salad), and no item is both a sandwich and a salad, then
Total lunches = 5 + 3 = 8
The key phrase is “choose one of these categories.”
If A and B overlap (A ∩ B ≠ ∅), then |A| + |B| counts elements in the overlap twice.
At this node, your main task is to learn to check disjointness. If alternatives are not disjoint, you must either:
A useful checklist:
If a problem says:
Those are disjoint sets. But if it says:
A day can be both sunny and warm, so sets overlap.
If A and B are disjoint, every element of A ∪ B is either:
So the total is the sum:
= (number of elements in A) + (number of elements in B)
= |A| + |B|
This is simple, but it’s the pattern you will reuse constantly.
| Situation | What you’re doing | Set operation | Counting rule | ||||||
|---|---|---|---|---|---|---|---|---|---|
| Choose one from category A or one from category B | Alternatives | A ∪ B | If disjoint: | A ∪ B | = | A | + | B | |
| Choose one from A and then one from B | Sequence of choices | A × B | A × B | = | A | · | B |
We’ll now build the multiplication rule, which is the workhorse for multi-step constructions like passwords, IDs, and experiment outcomes.
Multiplication is the right operation when an outcome is built by making several choices in sequence:
Each complete outcome is a combination of one choice from each step.
If A is a set of first-step choices and B is a set of second-step choices, then the set of all two-step outcomes is
A × B = { (a, b) : a ∈ A and b ∈ B }
Important details:
Example:
A = {R, G} (2 colors)
B = {S, M, L} (3 sizes)
A × B has 2·3 = 6 pairs:
(R,S), (R,M), (R,L), (G,S), (G,M), (G,L)
For finite sets A and B:
And for k steps with sets A₁, A₂, …, Aₖ:
Think of a table:
Each cell corresponds to exactly one pair (a, b). The number of cells is:
(number of rows) · (number of columns)
= |A| · |B|
So |A × B| = |A| · |B|.
People often say “independent choices,” but in counting problems this usually means:
If some combinations are forbidden (constraints), then you can’t blindly multiply; you must adjust.
Example: a 3-character code where the first character is a letter (26 choices) and the next two are digits (10 choices each).
Let
Total codes:
= |A₁|·|A₂|·|A₃|
= 26 · 10 · 10
= 2600
Constraints example: “no repeated digits” would change the later step counts (10 then 9, etc.). You can still multiply, but the factors change because the set of allowed choices at step 3 depends on step 2.
Many problems combine both rules:
You’ll practice this blend in worked examples.
| Wording clue | Likely structure | Rule |
|---|---|---|
| “either … or …” | alternatives (union) | add (if disjoint) |
| “choose one of the following types” | disjoint categories | add |
| “and then” / “followed by” / “for each” | sequential steps (product) | multiply |
| “format A or format B, then fill in details” | add outside, multiply inside | both |
At this point you have the two tools. Next we connect them to probability and permutations, where these rules become the backbone of larger formulas.
In basic probability (with equally likely outcomes), you often compute:
P(event E) = |E| / |Ω|
where Ω is the sample space (set of all possible outcomes).
Counting principles are how you find |Ω| and |E|.
Let a coin flip outcome be in C = {H, T} with |C| = 2.
Two flips corresponds to C × C.
|C × C| = |C|·|C| = 2·2 = 4 outcomes:
(H,H), (H,T), (T,H), (T,T)
Now events like “exactly one head” can be counted as a subset.
Permutations are about arrangements (order matters). The multiplication rule is what builds factorial and permutation counts.
For example, how many ways to arrange 3 distinct items {a, b, c}?
You choose:
By multiplication:
3 · 2 · 1 = 6
That becomes 3!.
Many CS objects are built from smaller pieces:
The multiplication rule counts “structured objects” when the structure is sequential. The addition rule counts “choose a type of structure” when there are multiple disjoint types.
If you can rewrite the problem as:
you can count it.
A helpful approach:
1) Define the outcome set precisely.
2) Split it into disjoint cases if needed.
3) Count each case with multiplication.
4) Add the case counts.
This is the same decomposition mindset used in algorithms: break a big problem into pieces that don’t overlap, count or compute each piece, combine results.
These principles unlock:
Even when later topics become more complex (combinations, inclusion–exclusion), the mental habit you build here—add for alternatives, multiply for stages—remains the foundation.
A cafeteria offers:
If you choose exactly one main (sandwich or salad) and also choose 1 drink from 5 options, how many total meals are possible?
Define sets of mains:
Let S be the set of sandwiches, |S| = 4.
Let A be the set of salads, |A| = 3.
Because you choose a sandwich or a salad (and these categories do not overlap), treat as a disjoint union:
Number of possible mains = |S ∪ A| = |S| + |A| = 4 + 3 = 7.
Define set of drinks:
Let D be the set of drinks, |D| = 5.
A full meal is (main, drink), so outcomes correspond to (S ∪ A) × D.
Apply multiplication rule:
= 7 · 5
= 35.
Insight: Use addition to count disjoint main-course alternatives, then multiply because you make an additional drink choice for each main.
A system allows two disjoint license plate formats:
Assume 26 letters (A–Z) and 10 digits (0–9), repetition allowed. How many plates are possible total?
Count Format 1 using multiplication:
Choices: 26 · 26 · 10 · 10
So N₁ = 26² · 10².
Compute N₁:
26² = 676
10² = 100
So N₁ = 676 · 100 = 67,600.
Count Format 2 using multiplication:
Choices: 26 · 26 · 26 · 10
So N₂ = 26³ · 10.
Compute N₂:
26³ = 26 · 26² = 26 · 676 = 17,576
So N₂ = 17,576 · 10 = 175,760.
Formats are disjoint (a plate cannot be both LLDD and LLLD), so add:
Total = N₁ + N₂
= 67,600 + 175,760
= 243,360.
Insight: When there are multiple allowed “shapes” for outcomes, count each shape with multiplication, then add because the shapes are disjoint cases.
You roll a standard 6-sided die, then flip a coin. How many outcomes are in the sample space Ω?
Define the die outcome set:
Let D = {1,2,3,4,5,6}, so |D| = 6.
Define the coin outcome set:
Let C = {H,T}, so |C| = 2.
A full outcome is an ordered pair (d, c) where d ∈ D and c ∈ C.
So Ω = D × C.
Apply multiplication rule:
|Ω| = |D × C| = |D| · |C| = 6 · 2 = 12.
Insight: Sequential experiments multiply because each first-stage result can be paired with each second-stage result.
|S| denotes the cardinality of a finite set S: the number of distinct outcomes in S.
Use the addition rule when outcomes come from disjoint alternatives: if A ∩ B = ∅, then |A ∪ B| = |A| + |B|.
Use the multiplication rule for sequential choices: |A × B| = |A| · |B|, and similarly for more steps.
“Either/or” language usually indicates addition; “and then / followed by / for each” usually indicates multiplication.
Many real problems require both: add across disjoint formats (cases), multiply within a format (steps).
Check for overlap before adding; overlap causes double-counting.
If constraints make later choices depend on earlier ones, you can still multiply, but the counts per step may change.
Adding counts for alternatives that are not disjoint (overlap), which double-counts shared outcomes.
Multiplying when the problem is actually “choose one category,” not “do both steps.”
Forgetting order in sequential outcomes: (a, b) and (b, a) are different when steps have roles.
Ignoring constraints (like “no repeats”) and using the same factor for each step when the allowed set shrinks.
A website password must be either:
Assume 10 digits and 26 letters, repetition allowed. How many passwords are possible?
Hint: Count each format with multiplication, then add because the formats are disjoint.
Let Format A be 6 digits: N₁ = 10⁶.
Let Format B be 4 letters then 2 digits: N₂ = 26⁴ · 10².
Total = N₁ + N₂ = 10⁶ + 26⁴ · 10².
Compute if desired: 10⁶ = 1,000,000. 26⁴ = (26²)² = 676² = 456,976.
So N₂ = 456,976 · 100 = 45,697,600.
Total = 1,000,000 + 45,697,600 = 46,697,600.
How many outcomes are possible when you flip 3 coins (in order)?
Hint: Each coin has 2 outcomes; use a 3-step product C × C × C.
Let C = {H, T}, |C| = 2.
Sample space Ω = C × C × C.
|Ω| = |C|³ = 2³ = 8.
A student can choose one elective from:
How many choices are there if the student must pick exactly one elective?
Hint: These are disjoint categories (you choose one course total).
Let A, M, T be the sets of art, music, and theater electives.
Assuming they are disjoint categories, total choices are
|A ∪ M ∪ T| = |A| + |M| + |T| = 5 + 4 + 3 = 12.
Next nodes you can study:
Related ideas (later in discrete math):