Day 47 — Product & sum rules

Updated

July 30, 2026

Day 47 — Product & sum rules

Stage V · concept day
Goal: Count systematically with the product rule, sum rule, complementary counting, decision trees, and justified mixed arguments; diagnose overcounts before they become habits.

Why this matters

Every password policy, test-suite size estimate, state-machine enumeration, and “how many configurations?” question is a counting problem. The product and sum rules are the two primitive operations: a sequence of independent choices multiplies; mutually exclusive cases add. Later tools (permutations, combinations, inclusion–exclusion) are special cases or corrections of these two ideas. If your product/sum story is wrong, no amount of binomial algebra saves the answer.

Theory

What “counting” means

We count finite sets of outcomes. An outcome is a complete description of a configuration (a password string, a seating, a bit-string satisfying a constraint). Two descriptions that look different but represent the same object must not both be counted (overcount); two that represent different objects must not be collapsed (undercount).

Principle of bijection. If you build a 1–1 correspondence between the set you care about and a set you already know how to count, the sizes match. Writing a clear “story” of how each outcome is built is how you prove the correspondence.

Product rule (multiplication principle)

Statement. Suppose a process of constructing an outcome has $k$ stages, and:

stage $1$ can be completed in $n_1$ ways,
after stage $1$ is fixed, stage $2$ can be completed in $n_2$ ways,
…
after stages $1,\ldots,k-1$ are fixed, stage $k$ can be completed in $n_k$ ways,

and every outcome arises from exactly one sequence of stage choices. Then the number of outcomes is

\[ n_1 n_2 \cdots n_k. \]

Why it is true (decision tree). Draw a rooted tree: the root has $n_1$ children; every node at depth $i-1$ has $n_i$ children. A full $k$-level tree of this shape has exactly $n_1\cdots n_k$ leaves, and each leaf is one outcome.

Why it is true (induction on stages). For $k=1$ the claim is trivial. If the first $k-1$ stages can be completed in $N=n_1\cdots n_{k-1}$ ways and each such history leaves $n_k$ options, total $= \sum_{\text{histories}} n_k = N\cdot n_k$.

Independence note. The $n_i$ need not be “independent of everything”—they may depend on which previous choices were made, as long as every history still leaves the same number $n_i$ of options. If the count of options depends on the history, you must case-split (sum rule) or use a more careful product with different branches.

Sum rule (addition principle)

Statement. If a set of outcomes can be partitioned into $m$ pairwise disjoint classes $C_1,\ldots,C_m$, and $|C_i|=n_i$, then

\[ |C_1\cup\cdots\cup C_m| = n_1+\cdots+n_m. \]

Why it is true. Partition means every outcome is in exactly one class: no overlap, no omission. Cardinality of a disjoint union is the sum of cardinalities.

Warning. If classes overlap, plain addition overcounts. That is why inclusion–exclusion (Day 52) exists. If classes miss some outcomes, you undercount.

Complementary counting

Often the easiest count of $A$ is

\[ |A| = |U| - |U\setminus A| \]

for a simple universe $U$ that contains $A$. Complementary counting is product/sum applied to the complement. Classic pattern: “at least one $X$” $= $ total $-$ “no $X$.”

Decision tree discipline

Before writing a formula:

Name what an outcome is (exact type of object).
Stages or cases: sequential structure → product; mutually exclusive types → sum.
Check once: every legal outcome counted once; no illegal outcome counted.
Sanity: small $n$ enumeration matches the formula.
Order matters? If the final object is a set/multiset vs a sequence, the story differs.

Overcount diagnosis

When two methods disagree:

Symptom	Likely cause	Fix
Answer too large vs listing	Double-counted overlapping cases, or counted ordered when object is unordered	Partition more carefully; divide by symmetry if justified
Answer too small	Missed a case; illegal constraint too strong	Re-check partition covers $U$
Product used on OR of properties	Sum-rule violation	Cases or IE
Sum used on sequential stages	Product-rule violation	Stages in order

Functions as product

If $|A|=n$ and $|B|=m$, the set of all functions $f:A\to B$ has size $m^n$: for each of $n$ domain elements independently choose one of $m$ images. Specializations:

injections (no collisions): $P(m,n)$ if $n\le m$ (Day 48);
all binary strings of length $n$: $2^n$ (functions $[n]\to\{0,1\}$);
power set of an $n$-set: $2^n$ (characteristic functions).

Inclusion–exclusion preview

For two properties $A,B$ that may overlap:

\[ |A\cup B| = |A|+|B|-|A\cap B|. \]

Today: recognize when you need the third term. Full IE on Day 52.

Linking to earlier days

Cartesian products (Day 37) are pure product: $|A\times B|=|A|\,|B|$. Power sets give $|\mathcal{P}(S)|=2^{|S|}$. Pigeonhole (Day 45) says when collisions must exist; counting says how many configurations avoid them.

Worked examples

Example 1 — Pure product: license plates

A plate is three letters (A–Z) followed by three digits (0–9), repetition allowed.

Stages 1–3: letter, 26 choices each → $26^3$.
Stages 4–6: digit, 10 choices each → $10^3$.
Product: $26^3\cdot 10^3 = 17{,}576{,}000$.

If letters must be distinct but digits free: $26\cdot 25\cdot 24\cdot 10^3$.

Example 2 — Pure sum: bit-strings by length

Count bit-strings of length exactly $1$ or exactly $2$.

Length 1: $2^1=2$; length 2: $2^2=4$.
Disjoint by length: $2+4=6$.

Wrongly multiplying $2\cdot 4=8$ counts ordered pairs of (len-1 string, len-2 string)—a different set.

Example 3 — Mix: passwords with structure

Length-4 passwords over letter/digit classes (26 letters, 10 digits). Pattern LLDD: $26\cdot 26\cdot 10\cdot 10=67{,}600$.

Exactly two letters and two digits in some order:

Choose 2 positions for letters: $\binom{4}{2}=6$ patterns (or list LLDD, LDLD, LDDL, DLLD, DLDL, DDLL).
Each pattern: $26^2\cdot 10^2$.
Sum: $6\cdot 26^2\cdot 10^2=405{,}600$.

Example 4 — Dependent counts that still multiply

Seat 5 people in a row of 5: first seat 5 choices, then 4, then 3, then 2, then 1: $5!=120$. Counts depend on prior choices, but the number remaining is fixed at each stage.

Example 5 — Complementary count

Bit-strings of length $n$ that are not all zeros: $2^n-1$.
Length-5 strings over $\{0,1\}$ with at least one $1$: $32-1=31$.

Example 6 — When product fails without cases

Length-3 strings over $\{A,B,C\}$ with no two consecutive equal:

Pos 1: 3; pos 2: 2 ($\neq$ first); pos 3: 2 ($\neq$ second) → $3\cdot 2\cdot 2=12$.

Constraint “not all three equal”: complement $3^3-3=24$. Different constraint → different method.

Example 7 — CS-shaped state space

Feature flags $(f_1,f_2,f_3)$ each boolean, but $(0,0,0)$ disabled: $2^3-1=7$.

Example 8 — Nested cases

IDs: either (a) 2 letters + 2 digits, or (b) 4 digits.

(a): $26^2\cdot 10^2$; (b): $10^4$; disjoint formats → $67{,}600+10{,}000=77{,}600$.

Example 9 — Functions

Maps $\{1,2,3\}\to\{a,b,c,d\}$: $4^3=64$. With $f(1)=a$ forced: $4^2=16$. Constant maps: 4.

Example 10 — Complement with larger alphabet

Length-4 strings over $\{0,1,2\}$ with ≥ one $2$: $3^4-2^4=81-16=65$.

Example 11 — Optional fields

Main dish 5 ways; starter optional among 3 (or absent = 4 choices); dessert optional among 2 (or absent = 3): $5\cdot 4\cdot 3=60$.

Example 12 — Dependent digits, no leading zero

3-digit strings, distinct digits, no leading zero: hundreds $9$ choices ($1$–$9$); tens $9$ (remaining including $0$); units $8$: $9\cdot 9\cdot 8=648$.

Example 13 — Case on pattern

Length-3 over letter/digit with exactly one digit: choose digit position (3); that pos $10$ ways; others $26$ each: $3\cdot 10\cdot 26^2$.

Example 14 — Grid enumeration (product/sum story)

From $(0,0)$ to $(2,1)$ with unit Right/Up only: need 2 R and 1 U in some order. Sequences: RRU, RUR, URR — 3 ways. (Tomorrow’s combinations will say $\binom{3}{1}$.)

Example 15 — Overcount diagnosis

Count length-3 bit-strings that start with 1 or end with 1.

Start with 1: $2^2=4$; end with 1: $4$; sum $8$.
But 1x1 counted twice; listing: total $8$, start-or-end: all except 000,010 wait—length 3: universe $8$; neither property: start $0$ and end $0$ → $0x0$ with middle free: $2$ strings 000,010. So $|A\cup B|=8-2=6$.
Correct: $4+4-2=6$ (IE preview). Naive sum overcounted by $2$.

Exercises

Solve by hand. Write a short justification (stages or partition) for each answer.

How many length-$4$ bit-strings start with $1$? With $01$?
A 4-digit PIN (digits $0$–$9$). Count with repetition allowed; with all digits distinct; with digits strictly increasing (think: choose 4 digits then only one order works).
Menu: 3 starters, 5 mains, 2 desserts. Full meals (one of each)? Meals that skip dessert? Total with dessert optional?
Passwords length 5 from 26 letters + 10 digits (each char either). How many? How many if first char must be a letter?
License plates: 2 letters then 3 digits, letters distinct, digits free.
Bit-strings length $n$ with first bit $0$ or last bit $1$—for $n=3$ list and compute; explain why plain sum fails.
Functions $f:\{1,2,3\}\to\{a,b\}$: count all by product. How many are constant? How many are surjective?
A byte is 8 bits. How many have MSB $=1$? How many have even parity (even number of $1$s)?
Paths on a grid from $(0,0)$ to $(2,1)$ moving only right or up—enumerate.
Explain two mistakes: adding when stages are sequential; multiplying when cases overlap. One numeric micro-example of each.
Count strings of length 3 over $\{1,2,3,4\}$ with all characters different.
Outcomes of rolling a fair 6-sided die then flipping a coin (ordered pair).
Protocol version $(major,minor,patch)$ with $major\in\{0,1,2\}$, $minor,patch\in\{0,\ldots,9\}$. How many versions? How many with $major\ge 1$?
Shelf A: 4 distinct books left-to-right; shelf B: 3 different books. Arrangements if shelves are distinguishable.
Length-4 passwords over 62 alphanumeric chars with at least one digit: set up with complement (symbolic OK).
Count $n$-tuples in $\{1,\ldots,m\}^n$ with first coordinate fixed to $1$.
Letter-digit-letter-digit plates, distinct letters and distinct digits.
Assign 5 distinct bugs to 3 severity levels (all functions).
Length-6 bit-strings starting with $1$ or ending with $00$ (handle overlap carefully).
Prove the $k$-stage product rule by induction on $k$.
Invent a problem needing a 2-way sum and a 3-stage product; solve it.
Password space $N=36^8$; write $\log_2 N$ as an expression (entropy bits).
How many nonempty subsets does an $n$-set have? (Product or sum of binomials.)
Two distinguishable dice: total outcomes; outcomes with sum $\ge 10$.
CS: pairs $(a,b)$ with $a\in\{0,\ldots,255\}$, $b\in\{0,\ldots,15\}$, $a\neq 0$.

CS connection

Test matrices: each factor with $n_i$ levels → $\prod n_i$ full factorial designs; incomplete designs are deliberate undercounts.
API keys / tokens: alphabet size $\times$ length → product; entropy $\approx k\log_2 |\Sigma|$.
Feature flags & enums: configuration space is a product of option sets; illegal combos force complement or IE.
FSM / protocol states: reachable configurations ⊆ product of local variables; exhaustive testing needs the product size first.
Type systems: product types (struct) multiply; sum types (enum/Result) add.

Common pitfalls

Pitfall	What to do instead
Multiplying overlapping cases	Partition first; or use inclusion–exclusion later
Forgetting order of stages changes the story not always the count	Name the object; check with small $n$
“Independent” misread as “unrelated quantities”	Product needs fixed option counts along a construction
Losing the empty/all-zero case	Explicitly include or complement
Double-counting symmetry (arrangements vs sets)	Ask: does order matter in the final object?
Using sum for sequential stages	Stages → product
Ignoring leading-zero constraints	Case the first digit separately

Checkpoint

State product and sum rules without notes
Give one pure-product and one pure-sum example with numbers
Explain complementary counting in one sentence
Diagnose the overcount in Example 15 cold
Rework Examples 3, 6, and 12 cold
Exercises 1–15 done with justifications
One sentence: where product/sum appears in a system you use

Two personal takeaways:

Selected mini-solutions

Start 1: $2^3=8$; start 01: $2^2=4$.
PINs: $10^4$; distinct $P(10,4)=5040$; strictly increasing $\binom{10}{4}=210$.
Functions $2^3=8$; constants $2$; surjections $8-2=6$.
MSB $1$: $2^7=128$; even parity: $2^7=128$.
$P(4,3)=24$.
$6\cdot 2=12$.
$62^4-52^4$.
$2^n-1$.

Deepening notes

Product rule as iterated sum (formal)

If stage 1 has $n_1$ options and every history leaves $n_2$ options at stage 2, total $=\sum_{i=1}^{n_1} n_2 = n_1 n_2$. Induct on stages for the $k$-fold product. The constant-branch-count hypothesis is what factors the sum.

When option counts depend on history

Suppose after choosing the first letter, the number of legal second letters depends on which letter you chose (not just “how many left”). Then you cannot write a single product $n_1 n_2$. Case-split on first letter (sum rule), or group histories that share the same remaining count.

Bijection discipline example

To count length-$n$ bit-strings with even parity: map strings ending in 0 with even weight on the prefix ↔︎ fix last bit to force parity. Standard bijection shows exactly half are even: $2^{n-1}$.

IE preview fully written

$|A\cup B\cup C|$ expands to seven Venn regions counted once each after the alternating sum. Draw the Venn diagram once and mark the coefficient each region gets at each stage of IE—muscle memory for Day 52.

Exam micro-drills (extra)

D1. Count length-4 strings over $\{0,1,2\}$ with no two consecutive equal.
D2. Feature flags 5 booleans with not-all-true and not-all-false.
D3. Two distinguishable dice showing different faces.
D4. Functions $[n]\to[2]$ that are surjective.
D5. IDs of form letter+digit or digit+letter (disjoint formats).
D6. Prove by induction: number of subsets of an $n$-set is $2^n$ via product of in/out choices.
D7. Where does the product rule hide in $|A\times B\times C|$?
D8. Deliberately overcount length-2 bit-strings starting with 1 or ending with 0; fix with IE.

Flash formulas

Situation	First try
Sequence of free choices	$\prod n_i$
Partition into types	$\sum n_i$
At least one $X$	total − none
All maps $A\to B$	$\\|B\\|^{\\|A\\|}$
Overlapping properties	IE

Reflection prompts

Rewrite Example 15 without looking.
Invent a password policy and count it two ways (should match).
Explain to a peer why “or” is not multiply.

Tomorrow

Day 48 — Permutations: ordered selections, $P(n,k)=n!/(n-k)!$, with repetition $n^k$, circular $(n-1)!$, and derangements.