Sum & Product Rules
The fundamental building blocks of combinatorial counting
➕ The Sum Rule
Definition
If set \(A\) has \(k\) elements and set \(B\) has \(n\) elements, and these sets are disjoint (have no common elements), then the set \(A \cup B\) has \(n + k\) elements.
Interactive Example: Choosing a Restaurant
Click on the places to count them!
Pizza Places (Set A)
Count: 0
Burger Joints (Set B)
Count: 0
Total Options = 0
Select all places to verify the rule!
🕵️ Spot the Flaw!
The Problem:
Count all integers from 1 to 10 that are divisible by 2 OR by 3.
Proposed Solution (Incorrect):
"There are 5 numbers divisible by 2: {2, 4, 6, 8, 10}.
There are 3 numbers divisible by 3: {3, 6, 9}.
So, by the Sum Rule, the answer is \(5 + 3 = 8\)."
Click on the number that causes the error!
Correct! It's the Inclusion-Exclusion Principle
The number 6 is divisible by BOTH 2 and 3. We counted it twice!
\(|A \cup B| = |A| + |B| - |A \cap B|\)
Correct calculation: \(5 + 3 - 1 = 7\)
✖️ The Product Rule
Definition
If there are \(k\) objects of the first type and \(n\) objects of the second type, then there are \(k \times n\) pairs of objects (one of each type).
Interactive Example: Outfit Picker
Shirts (3 Options)
Pants (2 Options)
Total Combinations: \(3 \times 2 = 6\)
Select a shirt and pants!
Application: Counting Paths
Suppose we want to go from point \(A\) to \(C\), passing through \(B\).
- • Paths from \(A \to B\): 3 routes
- • Paths from \(B \to C\): 2 routes
Total Paths = \(3 \times 2 = 6\)
📝 Test Your Understanding
Question 1:
How many 2-letter passwords can be made using the letters {a, b, c}?
Question 2:
A class has 10 boys and 8 girls. How many ways can we choose a class representative (either a boy OR a girl)?