Product rule, sum rule, and the pigeonhole principle
Two simple rules and one obvious-sounding principle count huge sets without listing a single element.
Slide the sizes of A and B and watch the grid of pairs grow as m × n, while the either-or total grows only as m + n.
Product rule: If task 1 has |A| choices and task 2 has |B| choices, doing both = |A| x |B|. Sum rule: If choosing from disjoint sets A or B, total choices = |A| + |B|.
Counting is the foundation of combinatorics. Two simple but powerful rules -- the product rule and the sum rule -- let us calculate the size of complex sets without listing every element. Combined with the pigeonhole principle, these tools solve a remarkable range of problems.
The product rule says: if task A can be done in m ways and task B in n ways, then doing both tasks in sequence can be done in m × n ways. The sum rule says: if tasks A and B are mutually exclusive, the total number of ways to do one or the other is m + n. Adjust the set sizes to see how these rules scale.
Key insight: The product rule multiplies because each choice in the first set pairs independently with every choice in the second set. The sum rule adds because the two sets are disjoint -- no outcome belongs to both.
Drop balls into the boxes one at a time and change the number of boxes. Once there are more balls than boxes, some box must hold two.
If you place more than k items into k boxes, at least one box must contain two or more items.
If you place n + 1 objects into n containers, at least one container must hold two or more objects. This seemingly obvious statement -- the pigeonhole principle -- is surprisingly powerful. It proves that in any group of 13 people, at least two share a birth month; and that in any set of 11 integers, at least two have the same last digit.
Key insight: The pigeonhole principle guarantees existence without telling you which box has the collision. Its generalized form says that with kn + 1 objects in n boxes, some box has at least k + 1 objects.
Set how many letters and digits the plate or password has, then toggle off repetition and watch the count shrink.
Each letter slot has 26 choices (A-Z) and each digit slot has 10 choices (0-9). Without repetition, available choices decrease per slot.
Real counting problems often have constraints: a password must mix letters and digits, or a license plate follows a specific format. By breaking the problem into independent slots and applying the product rule, we can count the total outcomes efficiently. Toggle repetition to see how the count changes when characters cannot be reused.
Key insight: With repetition allowed, each slot has the same number of choices (26 letters, 10 digits). Without repetition, available choices decrease for each subsequent slot -- this is exactly the falling factorial.
Spot a mistake or have an idea?