Introduction to counting and the pigeonhole principle

Counting starts this week. It is not on this semester’s midterm, it is a final exam topic. But combinatorics is one of the places where the most marks turn on an exam, because the questions are short and the answer is a single number. The point is choosing the right rule to apply. Golden rules:

1. “And” multiplies, “or” adds (if the options do not overlap).
2. If there is overlap, use inclusion-exclusion: subtract once what you counted twice.
3. An “at least one” question is solved with the complement: everything minus the ones with none.
4. If order matters it is a permutation, if not a combination. Ask yourself in every question: “are AB and BA different?”
5. In the pigeonhole principle, name the box and the object explicitly. Half the marks are in that sentence.

Basic counting rules

Product rule

If a task is done in two consecutive steps, and the first step can be done in $n_1$ ways and the second step (in every case) in $n_2$ ways, the task can be done in $n_1 \cdot n_2$ ways.

Example: a menu with one of 3 starters, 4 main courses and 2 desserts: $3 \cdot 4 \cdot 2 = 24$ menus. If you draw a tree diagram you get 24 leaves.

The most important consequences of the product rule:

• Bit strings of length $n$: $2^n$.
• Functions from an $m$-element set to an $n$-element set: $n$ choices for each element, $n^m$.
• Subsets of an $n$-element set: each element is either in or out, $2^n$ (the power set of week 4).

Sum rule

If a task is done either in the first way ($n_1$ options) or in the second way ($n_2$ options), and there are no common options: $n_1 + n_2$. Example: project list A has 12 topics, list B has 9, and there are no common topics. There are $12 + 9 = 21$ ways to choose a topic.

Subtraction rule (inclusion-exclusion)

If there are common options you count them twice, so you subtract them once:

$\lvert A \cup B \rvert = \lvert A \rvert + \lvert B \rvert - \lvert A \cap B \rvert.$

Example. How many 7-bit strings begin with 1 or end with 00?

begin with 1:             the remaining 6 bits are free  -> 2^6 = 64
end with 00:              the remaining 5 bits are free  -> 2^5 = 32
both (1....00):           the 4 middle bits              -> 2^4 = 16
Total: 64 + 32 - 16 = 80

“At least one” and the complement

Example. A 4-character password, where each character is an uppercase letter (26) or a digit (10). How many passwords contain at least one digit?

Counting directly is messy (one digit, two digits, …). With the complement:

$\underbrace{36^4}_{\text{all}} - \underbrace{26^4}_{\text{no digit}} = 1679616 - 456976 = 1222640.$

PITFALL · Doing “at least one” with the product rule. Computing $4 \cdot 10 \cdot 36^3$ by “make one position a digit (4 ways), 10 digits for that position, the other 3 positions 36” is wrong: it counts passwords with two digits more than once. The complement method is always safe.

Division rule

If you count every outcome exactly $d$ times, you divide the total by $d$. Example: 5 people at a round table. In a straight line it is $5! = 120$, but rotations count as the same seating, and each seating was counted 5 times: $120/5 = 24$.

The pigeonhole principle

Principle. If you put $k + 1$ (or more) objects into $k$ boxes, at least one box has at least two objects.

Proof. Suppose, for contradiction, that k + 1 objects are placed
into k boxes and no box contains more than one object.
Then the total number of objects is at most k * 1 = k.
This contradicts having k + 1 objects. Hence some box contains
at least two objects. ∎

Generalized principle. If you put $N$ objects into $k$ boxes, some box has at least $\lceil N/k \rceil$ objects.

Example: in a class of 40 students, at least $\lceil 40/12 \rceil = 4$ were born in the same month. Reason: if each month had at most 3 people, the total would be at most $12 \cdot 3 = 36 < 40$.

“At least how many to guarantee?” questions

Recipe: set up the worst case, add one. Grades are 5 letters (A, B, C, D, F). How many students must a class have to guarantee that 5 students got the same grade? Worst case: 4 students of each grade, $5 \cdot 4 = 20$ students and still no 5 the same. One more person: $21$.

General pattern: $k$ boxes, if you want $r$ of the same, the answer is $k(r-1) + 1$.

TIP · choose the box correctly. If the question says “two numbers whose difference is divisible by 4”, the boxes are the remainders mod 4. If it says “two numbers whose sum is 10”, the boxes are the pairs $\{1, 9\}, \{2, 8\}, \dots$. The moment you find the box, the question is over.

Permutations and combinations

Permutation (r-permutation): arranging $r$ of $n$ distinct objects in order.

$P(n, r) = n(n-1)\cdots(n-r+1) = \frac{n!}{(n-r)!}.$

Combination (r-combination): choosing $r$ of $n$ distinct objects without order (a subset).

$C(n, r) = \binom{n}{r} = \frac{n!}{r!\,(n-r)!}.$

Connection: $P(n, r) = C(n, r) \cdot r!$. First which $r$ objects (combination), then in how many ways you arrange them ($r!$).

$C(n, r) = C(n, n - r)$: choosing 4 people is the same job as choosing the 6 who stay out.

TIP · simplify factorials by hand. There is no calculator. For $C(10,4)$ don’t compute $10!$: write $\frac{10 \cdot 9 \cdot 8 \cdot 7}{4 \cdot 3 \cdot 2 \cdot 1}$ and simplify first. $8 / (4 \cdot 2) = 1$, $9 / 3 = 3$, leaving $10 \cdot 3 \cdot 7 = 210$. The denominator always divides evenly, because the result is a count.

Worked example: restricted ordering

6 people line up, and A and B must be next to each other.

1) Make A and B a single block: [AB] + 4 people = 5 objects
2) Arrange the 5 objects: 5! = 120
3) Inside the block AB or BA: 2
4) Product rule: 2 * 120 = 240

If it asks for A and B not next to each other, use the complement: $6! - 240 = 720 - 240 = 480$.

Which rule? Decision order

When you read the question, ask yourself in this order:

1. How many steps is it built in? If there are consecutive steps, the product rule.
2. Are there separate cases? If it splits into “either this or that”, count each case separately and add.
3. Do the cases overlap? If they overlap, subtract the intersection.
4. Is there the word “at least” or “at most”? The complement is usually shorter.
5. Does the order of the chosen items matter? If it matters, $P$; if not, $C$.

Worked example. How many of the 5-element subsets of $\{1, 2, \dots, 10\}$ contain 1 or 2?

All 5-element subsets:                  C(10,5) = 252
Containing neither 1 nor 2 (5 of 8):    C(8,5)  = 56
Containing at least one (complement):   252 - 56 = 196

Find the same answer with inclusion-exclusion too: containing 1 is $C(9,4) = 126$, containing 2 is $126$, containing both is $C(8,3) = 56$. $126 + 126 - 56 = 196$. If you get the same number two ways, write it with confidence. If you have time on the exam, do this cross-check.

Common mistakes