Product rule, sum rule, and the pigeonhole principle
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.
In this lesson, you will build intuition for multiplicative and additive counting, see why collisions are inevitable when there are more objects than containers, and apply these principles to real-world counting 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.
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|.
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.
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.
If you place more than k items into k boxes, at least one box must contain two or more items.
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.
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.
Each letter slot has 26 choices (A-Z) and each digit slot has 10 choices (0-9). Without repetition, available choices decrease per slot.
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.