Counting Principles Reference
Counting Principles and the Pigeonhole Principle
Counting principles find the size of a finite collection by organizing choices, removing overlaps, or proving that repetition must occur.
Solved Examples
Jump directly to a worked example by type.
Fact Table
| Idea | Meaning | Use or Check |
|---|---|---|
| Sum rule | Add the sizes of disjoint choices. | The cases must not overlap. |
| Product rule | Multiply the number of choices made in successive steps. | Each complete outcome is one choice from every step. |
| Complement | Count everything, then subtract the outcomes that fail the condition. | Useful for “at least one.” |
| Inclusion-exclusion | Add two set sizes and subtract their overlap. | Without subtraction, shared elements count twice. |
| Pigeonhole principle | More objects than boxes forces some box to contain at least two objects. | The boxes must model the category being counted. |
Content Formulas
Product Rule
$$N=n_1n_2\cdots n_k$$
Complement Rule
$$|A^c|=|U|-|A|$$
Two-Set Inclusion-Exclusion
$$|A\cup B|=|A|+|B|-|A\cap B|$$
Pigeonhole Bound
$$N>k\quad\Longrightarrow\quad\text{some one of }k\text{ boxes holds at least 2 objects}$$
When a count seems ambiguous, define what one outcome is and check that every outcome is counted exactly once.
Classic Examples
Use the Product Rule
A meal offers 3 sandwiches and 4 drinks. How many sandwich-and-drink meals can be made?
Solution Steps
- Choose a sandwich.
- For each sandwich choice, choose one drink.
- Multiply the independent stage counts.
$$N=3\cdot4$$
$$N=12\text{ meals}$$
Count With an Overlap
In a class of 30 students, 18 study French, 14 study Spanish, and 6 study both. How many study at least one?
Solution Steps
- Add the two group sizes.
- Subtract the 6 students counted in both groups twice.
$$|F\cup S|=18+14-6$$
$$|F\cup S|=26$$
Apply the Pigeonhole Principle
Show that among 13 people, at least two were born in the same month.
Solution Steps
- Treat the 12 months as boxes.
- Place each person in the box for their birth month.
- There are more people than boxes.
$$13\text{ people}>12\text{ months}$$
At least one month contains birthdays of at least two people.
Count by the Complement
How many three-digit strings made from digits 0 through 9 contain at least one zero? Repetition is allowed.
Solution Steps
- Count all three-digit strings; leading zero is allowed because these are strings.
- Subtract strings with no zero.
$$10^3-9^3=1000-729$$
$$271\text{ strings}$$