1
The sum rule needs disjointness
|A ∪ B| = |A| + |B| only when nothing is in both. Overlap means double-counting, and “The Inclusion-Exclusion Principle” is the general repair.
Lesson · Combinatorics and Counting · Basic counting
The Sum and Product Rules
Two rules underlie all of counting. The sum rule handles disjoint alternatives; the product rule handles independent successive choices. Almost every error in this course is applying one where the other belongs.
SUM disjoint alternatives: |A ∪ B| = |A| + |B| when A ∩ B = ∅
PRODUCT successive choices: |A × B| = |A| · |B|
"or" usually means add. "and then" usually means multiply.
The sum rule REQUIRES disjointness. Check it.
Two rules, one distinction
Core ideas
What this lesson establishes
The arithmetic is trivial. Deciding which rule applies is the entire content of the lesson.
2
The product rule needs independence of counts
The number of second choices must not depend on which first choice was made. The number itself may vary if it varies uniformly — but then say so.
3
Most problems combine both
Split into disjoint cases (sum), count each by stages (product), and add. That template solves most of this course.
The material
The two rules
Statements, the conditions they need, and how they combine.
Theorem · Sum rule
If a task can be done in one of n₁ ways or in one of n₂ ways, and the two sets of ways are disjoint, then there are n₁ + n₂ ways to do it. For k pairwise disjoint sets, |A₁ ∪ ⋯ ∪ A_k| = |A₁| + ⋯ + |A_k|.
Theorem · Product rule
If a task consists of two successive choices, with n₁ ways to make the first and, for each of those, n₂ ways to make the second, then there are n₁n₂ ways in total. For k stages the count is the product of the stage counts.
The product rule is where |A × B| = |A| · |B| came from in Sets, Relations, and Functions, and where truth tables get their 2ⁿ rows: n successive independent binary choices.
Example · Both rules in one problem
How many strings of length 3 over {a,…,z} start with a vowel or end with z? Vowel first: 5 · 26 · 26 = 3380. Ending z: 26 · 26 · 1 = 676. These overlap — strings starting with a vowel AND ending in z, of which there are 5 · 26 · 1 = 130. So the answer is 3380 + 676 − 130 = 3926, not 4056.
That subtraction is “The Inclusion-Exclusion Principle” arriving early. The sum rule as stated does not apply, because the two sets are not disjoint; using it anyway over-counts by exactly the size of the overlap.
When the second count depends on the first
The product rule is often stated as needing "independent" choices, which is imprecise. What it needs is that the number of second choices is the same whichever first choice was made. Choosing an ordered pair of distinct letters has 26 first choices and 25 second ones — the second count is 25 regardless of the first — so the product rule applies and gives 650.
When the count genuinely varies, split into cases and use the sum rule on the cases. That is the standard repair and it is what makes the two rules a complete toolkit rather than two heuristics.
Complementary counting
Theorem · Counting the complement
|A| = |U| − |Ā|. When the objects satisfying a condition are hard to count and those failing it are easy, count the failures.
Example · At least one
How many 4-digit PINs contain at least one 7? Directly this needs cases for one, two, three or four sevens. By complement: all PINs number 10⁴ = 10000, and those with no 7 number 9⁴ = 6561, so the answer is 3439. "At least one" is almost always a signal to count the complement.
Interactive
The four counting rules
Enumerated while enumeration is possible
Method
Choosing a rule
Ask two questions before writing any arithmetic.
1
Are these alternatives or stages?
"Either… or…" suggests the sum rule; "first… then…" suggests the product rule. Most problems have both, nested.
2
If alternatives: are they disjoint?
If an object could be counted in two cases, the sum rule over-counts. Fix the cases or use “The Inclusion-Exclusion Principle”.
3
If stages: does the second count vary?
It must be the same number for every first choice. If not, split into cases where it is constant.
4
Consider the complement
"At least one", "not all" and "at least two" usually count more easily as total minus failures.
Sum and product
Score 0 / 0Choose the answer you can justify.
Passwords
Length 6 to 8, from 26 letters and 10 digits, containing at least one digit.
Alphabet size 36. Split by LENGTH — disjoint, so add.
length 6: 36⁶ − 26⁶ = 2 176 782 336 − 308 915 776 = 1 867 866 560
length 7: 36⁷ − 26⁷ = 78 364 164 096 − 8 031 810 176 = 70 332 353 920
length 8: 36⁸ − 26⁸ = 2 821 109 907 456 − 208 827 064 576
= 2 612 282 842 880
total = 1 867 866 560 + 70 332 353 920 + 2 612 282 842 880
= 2 684 483 063 360
Two rules, each used once. The sum rule handled the three lengths, which are disjoint because a password has exactly one length; complementary counting handled "at least one digit" within each length. Counting the digit-containing passwords directly would need eight overlapping cases.
Common mistakes
1
Adding when the cases overlapThe over-count equals the size of the intersection. Either redefine the cases to be disjoint or subtract the overlap explicitly.
2
Multiplying when the second count variesIf the number of second choices depends on the first, split into cases where it does not, then add.
3
Counting "at least one" directlyIt almost always produces overlapping cases. Total minus none is one subtraction and cannot double-count.
Check your understanding
✓
Finish when you state the rule and its condition before computing.
Count the 4-digit PINs with at least two identical digits. Do it by complement, and say in one sentence why the direct count would be harder. That sentence is the skill.
Note: Both rules are theorems about sets: the sum rule is additivity of cardinality over disjoint unions, and the product rule is |A × B| = |A| · |B| from “Cartesian Products and Tuples” in Sets, Relations, and Functions. Counting is set theory with the sets kept small enough to measure.