6.1 The Basics of Counting

Every counting problem comes down to one question: am I doing things in a sequence of steps (multiply), or choosing one of several separate cases (add)?

The product rule

Product rule

If a procedure is a sequence of $k$ tasks and task $i$ can be done in $n_{i}$ ways (no matter how the earlier tasks were done), then the procedure can be done in
$n_{1} \cdot n_{2} \dots n_{k} ways.$

Quick product-rule examples from class

Assign 3 employees to 10 different offices: $10 \cdot 9 \cdot 8 = 720$ .
Chair labels "letter + integer 1–99": $26 \cdot 99 = 2574$ .
Bit strings of length 6: $2^{6} = 64$ .
Plates with 4 letters then 5 digits: $2 6^{4} \cdot 1 0^{5}$ .

Counting functions, subsets, and products

Let $∣ A ∣ = n$ and $∣ B ∣ = m$ .

All functions $f : A \to B$ : each of the $n$ inputs picks one of $m$ outputs, so $m^{n} = ∣ B ∣^{∣ A ∣}$ .
One-to-one functions: $m (m - 1) (m - 2) \dots (m - n + 1)$ if $n \leq m$ , and $0$ if $n > m$ .
Subsets of an $n$ -set: $∣ P (A) ∣ = 2^{n}$ . Each element is in or out, like a bit string.
Cartesian product: $∣ A_{1} \times \dots \times A_{k} ∣ = ∣ A_{1} ∣ \dots ∣ A_{k} ∣$ .
Relations from $A$ to $B$ (subsets of $A \times B$ ): $2^{nm}$ .

The sum rule

Sum rule

If a task can be done in one of $n_{1}$ ways or one of $n_{2}$ ways, and none of the $n_{1}$ ways is the same as any of the $n_{2}$ ways, then there are $n_{1} + n_{2}$ ways.

Use it to split into cases (by length, by first letter, …), count each case, then add.

Variable names (class Problem 11)

A name is 1 or 2 alphanumeric characters (case-insensitive), starting with a letter, and 10 two-character names are reserved.

Length 1: $26$ . Length 2: $26 \cdot 36 - 10 = 926$ . Total: $26 + 926 = 952$ .

Passwords (class Problem 12)

6 to 9 characters, each an uppercase letter or digit, with at least one digit.

For length $i$ : all strings minus strings with no digits, $3 6^{i} - 2 6^{i}$ . Total: $i = 6 \sum 9 (3 6^{i} - 2 6^{i})$ .

"At least one" means count the complement

$# (at least one X) = # (all) - # (none X) .$
Counting "at least one" directly usually double counts. The complement is almost always easier.

The subtraction rule (inclusion–exclusion)

Subtraction rule

If a task can be done in $n_{1}$ ways or $n_{2}$ ways, and some ways are shared, subtract the overlap:
$∣ A \cup B ∣ = ∣ A ∣ + ∣ B ∣ - ∣ A \cap B ∣.$

Use it whenever a problem says "or"

"Start with 0 or end with 11": count each, then subtract the strings that do both.

Length-8 bit strings that start with 0 or end with 11:
$2^{7} + 2^{6} - 2^{5} = 128 + 64 - 32 = 160.$

Majors (class Problem 14)

350 applicants: 210 CS, 150 sociology, 50 both. Neither?
$∣ A \cup B ∣ = 210 + 150 - 50 = 310$ , so neither $= 350 - 310 = 40$ .

Counting multiples

Multiples of $d$ in ${1, \dots, N}$ : $⌊ N / d ⌋$ .
Multiples of $d$ in ${a, \dots, b}$ : $⌊ b / d ⌋ - ⌊(a - 1) / d ⌋$ .
"Divisible by both $d$ and $e$ " means divisible by $lcm (d, e)$ . For 4 and 6 that is 12, not 24.

The division rule

Division rule

If every outcome you want is counted exactly $d$ times in your count, divide by $d$ : there are $n / d$ ways.

Circular seating

$n$ people around a round table, rotations considered the same: $\frac{n !}{n} = (n - 1)!$ .
If reflections also count as the same ("same two neighbors, ignoring left/right"): $\frac{( n - 1 )!}{2}$ .

Class Problem 16: 5 people, same right and left neighbor means same seating, so $5! /5 = 4! = 24$ .

Goat legs (class Problem 15)

400 legs counted, each goat counted 4 times, so $400/4 = 100$ goats. That's the division rule.

Tree diagrams

When the choices at each step depend on earlier choices, draw a tree and count the leaves.

Length-4 bit strings with no two consecutive 0s (class Problem 18)

Solution

Branch on each bit, pruning any branch that would create "00":

Start 1: 1010, 1011, 1101, 1110, 1111 (5 strings)
Start 0 (next must be 1): 0101, 0110, 0111 (3 strings)

Total: 8. (These counts are Fibonacci numbers: the answer for length $n$ is $f_{n + 2}$ .)

T-shirts (class Problem 17)

5 sizes; four sizes come in 4 colors, L in 3, XL in 2: $4 + 4 + 4 + 3 + 2 = 17$ . A tree, or the sum rule over sizes.

Strategy

How to attack any counting problem

Decide what one outcome looks like (a string? a set? an arrangement?).
Sequence of choices? Multiply (product rule). Make sure each step's count doesn't depend on which earlier choice was made.
Separate cases? Add (sum rule). Make sure cases don't overlap.
"At least one"? Total minus none.
"Or" with overlap? Inclusion–exclusion.
Each outcome counted $d$ times? Divide.
Sanity check with a tiny case you can list by hand.

Common mistakes

Leading zeros: "positive integers between 100 and 999" have a first digit of 1–9.
"Between 50 and 100": check whether the endpoints matter.
Counting $3$ -digit numbers with distinct digits: $9 \cdot 9 \cdot 8$ , not $10 \cdot 9 \cdot 8$ (first digit nonzero, second can be 0).
Adding overlapping cases without subtracting the overlap.

Fixes to your class notes

Problem 7 ( $∣ P (S) ∣ = 2^{n}$ ): the bit should be $b_{i} = 1$ if $x_{i} \in S^{'}$ , the subset, not $S$ .
Problem 13: $∣ A \cup B ∣ = 2^{7} + 2^{6} - 2^{5} = 160$ . Your notes wrote " $- 2$ " at the end.
Problem 14: the line " $= 350$ " should read $350 - ∣ A \cup B ∣$ ; the final answer 40 is right.
Sum rule note: if $A, B$ are disjoint then $A \cap B = \emptyset$ , so $∣ A \cap B ∣ = 0$ .

Exam checklist

Product rule with restrictions (no repeats, first digit nonzero, fixed positions).
Count functions, one-to-one functions, subsets, relations.
Split into cases and add; use the complement for "at least one."
Inclusion–exclusion for "or," including divisibility counts with floors.
Circular arrangements (division rule).
Small tree-diagram counts.