Source: CS182 Quiz 8 Solutions, Purdue University
Tags: counting, product rule, sum rule, subtraction rule, complement counting, pigeonhole principle, subsets, discrete mathematics, combinatorics
Difficulty: Introductory to Intermediate Prerequisites: Basic set theory, familiarity with exponents and factorials.
Counting is one of the foundational pillars of discrete mathematics, and nearly every topic that follows in CS182 builds on it. These principles give you systematic ways to count the number of outcomes in a scenario, rather than listing them by hand. If you can recognise which rule applies, the arithmetic is usually the easy part. You should already be comfortable with sets, basic probability language, and the idea of choosing from a collection of options.
The product rule multiplies independent choices. The sum rule adds mutually exclusive cases. The subtraction rule counts what you want by removing what you do not want from the total. The pigeonhole principle guarantees a collision when you have more items than categories.
Product rule
If one task can be done in m ways and a second, independent task can be done in n ways, the two tasks together can be done in m × n ways. In simple terms, multiply when choices happen one after another and do not affect each other.
Sum rule (addition rule)
If a task can be done in one of two mutually exclusive ways, with m outcomes in the first way and n in the second, the total number of outcomes is m + n. Think of it as: when you have an "either/or" situation with no overlap, you add.
Subtraction rule (complement counting)
The number of outcomes satisfying a condition equals the total number of outcomes minus the number that do not satisfy the condition. In simple terms, if counting what you want directly is hard, count everything and subtract what you do not want.
Pigeonhole principle
If you place n items into k categories (pigeonholes) and n > k, then at least one category must contain more than one item. Think of it as: if you have more socks than colours, two socks must match.
Mutually exclusive events
Events that cannot occur at the same time. If event A happens, event B cannot, and vice versa. This is the condition that lets you apply the sum rule safely.
When a process has multiple stages and each stage's options are independent of the others, multiply the number of options at each stage.
Example: choosing a shirt (5 options) and trousers (3 options) gives 5 × 3 = 15 outfits.
When outcomes fall into non-overlapping categories, add the counts of each category.
The critical check: make sure there is no double-counting. If a single outcome could appear in both categories, the sum rule alone will overcount.
Useful when the condition you want is awkward to count directly, but the opposite condition is simple.
Formula: |desired outcomes| = |total outcomes| − |undesired outcomes|
Worked example, bit strings: How many 12-bit strings contain at least two 0s?
Total 12-bit strings: 2¹².
Strings with zero 0s (all 1s): 1.
Strings with exactly one 0: 12 (the single 0 can sit in any of the 12 positions).
Strings with fewer than two 0s: 1 + 12 = 13.
Answer: 2¹² − 13.
Problem: plates use either two uppercase letters then five digits, or two digits then five uppercase letters. How many plates are possible?
These two formats are mutually exclusive (a plate starting with a letter cannot also start with a digit), so the sum rule applies across the two cases. Within each case, positions are independent, so the product rule applies.
Case I (two letters, five digits): 26² × 10⁵ = 67,600,000
Case II (two digits, five letters): 10² × 26⁵ = 1,188,137,600
Total: 67,600,000 + 1,188,137,600 = 1,255,737,600
Problem: you draw cards one at a time without replacement from a standard 52-card deck. What is the minimum number of cards you must draw to guarantee two cards share the same rank?
There are 13 distinct ranks (the "pigeonholes"). In the worst case, you could draw 13 cards, all of different ranks. The 14th card must share a rank with one already drawn.
Answer: 13 + 1 = 14.
Problem: how many subsets of S = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10} contain neither 5 nor 6 nor 7?
Fix 5, 6, and 7 as excluded. That leaves 7 elements, each independently included or excluded.
Answer: 2⁷ = 128.
Product rule: if stage 1 has a options and stage 2 has b options, total = a × b
Sum rule: if case A has a outcomes and case B has b outcomes (mutually exclusive), total = a + b
Subtraction rule: |at least k| = |total| − |fewer than k|
Pigeonhole: with k pigeonholes, you need k + 1 items to guarantee a repeat
Subsets of an n-element set: 2ⁿ total subsets (each element is in or out)
The product rule is behind every password-strength calculation: if a password has 8 characters, each from a set of 62 (uppercase, lowercase, digits), the total is 62⁸. The pigeonhole principle appears in networking (the birthday paradox for hash collisions) and in file compression (you cannot losslessly compress every possible file).
Students often apply the sum rule when choices are not mutually exclusive, leading to double-counting. Always verify that the two cases share no outcomes before adding.
The subtraction rule requires you to count everything you are subtracting, not just some of it. Forgetting one of the "undesired" sub-cases (e.g., forgetting the zero-0s case when subtracting from the total) is a common slip.
The pigeonhole principle tells you a repeat exists; it does not tell you which item repeats or when. Students sometimes confuse "at least one repeat is guaranteed" with "every draw after k is a repeat."
When counting subsets, students sometimes confuse "subsets that exclude element x" with "subsets of the remaining elements." They are the same thing, but thinking of it as "remove x first, then count all subsets of what is left" is cleaner.
⚠️ Recognising which rule to apply is the single most tested skill. The quiz will not label the problem "product rule problem"; you must identify it from context.
⚠️ Complement counting (subtraction rule) appears in nearly every exam because "at least" conditions are awkward to count directly.
⚠️ The pigeonhole principle questions are often short but easy to overthink. If you see "guarantee" or "must," think pigeonhole.
True or false: the product rule applies when outcomes in one stage depend on choices made in an earlier stage. (False, the stages must be independent.)
Fill in the blank: the number of subsets of a set with n elements is ____. (2ⁿ)
True or false: to guarantee two people in a room share a birth month, you need at least 12 people. (False, you need 13.)
Fill in the blank: when counting "at least two," a clean approach is to compute ____ minus the count of "fewer than two." (The total.)
Q: How many 8-bit strings contain at least three 1s?
A: Total 8-bit strings: 2⁸ = 256. Strings with zero 1s: 1. With exactly one 1: 8. With exactly two 1s: C(8,2) = 28. Fewer than three 1s: 1 + 8 + 28 = 37. Answer: 256 − 37 = 219.
Q: A menu offers 4 starters, 6 mains, and 3 desserts. How many three-course meals (one of each) are possible?
A: 4 × 6 × 3 = 72 (product rule, independent choices).
Q: You have 5 pairs of socks, each a different colour. What is the minimum number of individual socks you must pull from a drawer (in the dark) to guarantee a matching pair?
A: There are 5 colours (pigeonholes). You need 5 + 1 = 6 socks.
Q: How many subsets of {a, b, c, d, e} contain the element a?
A: Fix a as included. Each of the remaining 4 elements is independently in or out. Answer: 2⁴ = 16.
These counting rules feed directly into probability: once you can count favourable and total outcomes, probability is just the ratio. The pigeonhole principle reappears in algorithm analysis (e.g., proving that a certain hash table must have collisions). Complement counting is also the backbone of inclusion-exclusion, which extends the subtraction idea to overlapping sets.
counting principles, product rule, multiplication principle, sum rule, addition principle, subtraction rule, complement counting, pigeonhole principle, Dirichlet's box principle, subsets, power set, bit strings, licence plate counting, CS182, discrete math, Purdue, combinatorics basics