Chapter 1: Counting Principles
1.1 What does it mean to "count"?
Combinatorics is the mathematics of counting. But it is not simply counting 1, 2, 3, ...; the goal is to count efficiently, completely, and without duplication.
Consider the following problem.
Example. When a die is rolled twice, how many possible outcomes are there in total?
One could enumerate every case, but that is inefficient. Instead, we learn to use rules to compute the count.
1.2 The Addition Rule
We begin with the most basic rule: the addition rule.
Addition Rule (Sum Rule)
If event $A$ can occur in $m$ ways and event $B$ in $n$ ways, and $A$ and $B$ cannot occur simultaneously (i.e. they are mutually exclusive), then the number of ways that $A$ or $B$ occurs is
$$m + n \text{ ways}$$This is intuitive: if $A$ and $B$ do not overlap, simply add the counts.
Example 1. Choose one integer from 1 to 10. How many ways are there to choose a multiple of 3 or a multiple of 5?
Solution.
First, count each case.
- Multiples of 3: 3, 6, 9 → 3 ways
- Multiples of 5: 5, 10 → 2 ways
Check whether any number is shared. There is no multiple of 15 in the range 1–10, so the two sets are mutually exclusive.
By the addition rule:
$$3 + 2 = 5 \text{ ways}$$Note. Always confirm mutual exclusivity before applying the addition rule. If the events are not mutually exclusive, use the inclusion-exclusion principle introduced later.
1.3 The Multiplication Rule
Next, the multiplication rule, used for sequential choices.
Multiplication Rule (Product Rule)
If operation $A$ can be performed in $m$ ways and, for each of those, operation $B$ in $n$ ways, then performing $A$ followed by $B$ can be done in
$$m \times n \text{ ways}$$Why multiplication? Let us see it visually.
Example 2. When a die is rolled twice, how many outcomes are possible?
Solution.
Think in stages.
Step 1. Outcomes of the first roll.
Six outcomes: 1 through 6.
Step 2. Outcomes of the second roll.
Six outcomes again, regardless of the first roll.
Step 3. Apply the multiplication rule.
For each first-roll outcome there are six second-roll outcomes:
$$6 \times 6 = 36 \text{ outcomes}$$Example 3. From five people A, B, C, D, E, choose a chair and a vice-chair (no one may hold both posts). How many ways are there?
Solution.
Stage by stage:
Step 1. Choose the chair.
Five choices, one from five people.
Step 2. Choose the vice-chair.
The chair is excluded, leaving four choices.
Step 3. Apply the multiplication rule.
$$5 \times 4 = 20 \text{ ways}$$Notice that "whoever the chair is, there are always four choices for vice-chair." The multiplication rule applies whenever the count at each stage does not depend on the outcome of the previous stage.
1.4 Tree Diagrams
A tree diagram is a way to organize counts visually.
A tree diagram draws each stage of a choice as branches of a tree, listing every possibility once and only once.
Example 4. When a coin is tossed three times, list every possible sequence of heads (H) and tails (T).
The tree diagram shows that there are 8 sequences. The multiplication rule confirms it:
$$2 \times 2 \times 2 = 2^3 = 8 \text{ sequences}$$Strengths of tree diagrams
- All cases are visible at a glance.
- Easy to confirm there are no omissions or duplicates.
- Conditional problems are also handled naturally.
Limitations
- Impractical when the count is large.
- Time-consuming to draw.
1.5 Combining Sums and Products
Real problems often combine the addition and multiplication rules.
Example 5. Among the integers from 1 to 100, how many are divisible by 2 or by 5?
Solution.
Naively applying the addition rule gives the wrong answer because multiples of 2 and multiples of 5 overlap (multiples of 10).
Step 1. Count each set.
- Multiples of 2: $\lfloor 100/2 \rfloor = 50$
- Multiples of 5: $\lfloor 100/5 \rfloor = 20$
- Multiples of 10 (overlap): $\lfloor 100/10 \rfloor = 10$
Step 2. Apply inclusion-exclusion.
Subtract the overlap:
$$50 + 20 - 10 = 60$$Inclusion-exclusion (two sets)
$$|A \cup B| = |A| + |B| - |A \cap B|$$where $|X|$ denotes the size of set $X$.
1.6 Counting by Complement
For conditions of the form "not ...", using the complement often simplifies the count.
Counting by complement
Number of cases not satisfying $A$ = Total number of cases − Number of cases satisfying $A$.
$$|\overline{A}| = |U| - |A|$$Example 6. When a die is rolled twice, in how many outcomes does at least one 1 appear?
Solution.
Counting "at least one 1" directly is tedious. Use the complement.
Step 1. Total outcomes.
$$6 \times 6 = 36$$Step 2. Outcomes with no 1 at all.
Each roll must give 2, 3, 4, 5, or 6:
$$5 \times 5 = 25$$Step 3. Subtract.
$$36 - 25 = 11$$1.7 Chapter Summary
| Rule | When to use | Formula |
|---|---|---|
| Addition rule | "A or B" (mutually exclusive) | $m + n$ |
| Multiplication rule | "A then B" | $m \times n$ |
| Inclusion-exclusion | "A or B" (overlapping) | $|A| + |B| - |A \cap B|$ |
| Complement | "not ..." | $|U| - |A|$ |
Exercises
Problem 1
There are 3 roads from city A to city B and 4 roads from B to C. How many ways are there to go from A to C via B?
Problem 2
Among the integers from 1 to 20, how many are multiples of 3 or 4?
Problem 3
Using the digits 0, 1, 2, 3, 4 (with repetition allowed), how many three-digit integers can be formed? (Numbers whose hundreds digit is 0 do not count as three-digit integers.)
Problem 4
A coin is tossed four times. In how many of the outcomes does at least one head appear?
Solutions
Solution 1
By the multiplication rule: $3 \times 4 = 12$.
Solution 2
Multiples of 3: 3, 6, 9, 12, 15, 18 → 6.
Multiples of 4: 4, 8, 12, 16, 20 → 5.
Multiples of 12 (overlap): 12 → 1.
By inclusion-exclusion: $6 + 5 - 1 = 10$.
Solution 3
Hundreds digit: 4 choices (1, 2, 3, 4; not 0).
Tens digit: 5 choices (0, 1, 2, 3, 4).
Units digit: 5 choices.
By the multiplication rule: $4 \times 5 \times 5 = 100$.
Solution 4
Total outcomes: $2^4 = 16$.
Outcomes with no head (all tails): 1.
By the complement: $16 - 1 = 15$.