Chapter 15 — Key Takeaways

The Basics of Counting: Product Rule, Sum Rule, and Inclusion-Exclusion. A one-page reference — reread before an exam.

The four rules (plus one corollary) at a glance

Rule Trigger word Formula The proviso that makes it valid
Product rule "and" / a sequence of steps $n_1 \times n_2 \times \cdots \times n_k$ #options at each step is the same regardless of earlier choices
Sum rule "or" / a split into cases $n_1 + n_2 + \cdots + n_k$ cases are mutually exclusive (pairwise disjoint)
Inclusion-exclusion (2 sets) union of two overlapping sets $\lvert A \rvert + \lvert B \rvert - \lvert A \cap B \rvert$ always valid; subtracts the double-counted overlap
Inclusion-exclusion (3 sets) union of three overlapping sets $\sum\lvert\text{single}\rvert - \sum\lvert\text{pair}\rvert + \lvert\text{triple}\rvert$ always valid; signs alternate
Division rule each object listed multiple times $N / d$ over-count $d$ is the same for every object (uniform)
Subtraction principle "at least one …" $\lvert U \rvert - \lvert U \setminus \text{property}\rvert$ objects live in a known finite universe $U$

Set-language statements (the rigorous skeleton)

$$\lvert A_1 \times \cdots \times A_k \rvert = \lvert A_1 \rvert \cdots \lvert A_k \rvert \quad \text{(product)}$$ $$A_i \cap A_j = \emptyset \ (i \ne j) \ \Rightarrow\ \lvert A_1 \cup \cdots \cup A_k \rvert = \lvert A_1 \rvert + \cdots + \lvert A_k \rvert \quad \text{(sum)}$$ $$\lvert A \cup B \rvert = \lvert A \rvert + \lvert B \rvert - \lvert A \cap B \rvert$$ $$\lvert A \cup B \cup C \rvert = \lvert A \rvert + \lvert B \rvert + \lvert C \rvert - \lvert A \cap B \rvert - \lvert A \cap C \rvert - \lvert B \cap C \rvert + \lvert A \cap B \cap C \rvert$$ $$f : S \twoheadrightarrow T,\ \lvert f^{-1}(t)\rvert = d\ \forall t \ \Rightarrow\ \lvert T \rvert = \lvert S \rvert / d \quad \text{(division)}$$

Decision aid: which rule?

Reading the problem statement:

  "do step 1 AND step 2 AND ..."        → PRODUCT RULE   (multiply)
        ↳ but do later step-counts depend on earlier choices?
              yes → split into cases / count complement / divide instead

  "case A OR case B OR ..."             → are the cases disjoint?
        ↳ yes → SUM RULE                (add)
        ↳ no  → INCLUSION-EXCLUSION     (add, then subtract overlaps)

  "how many in A ∪ B (∪ C)"            → INCLUSION-EXCLUSION
  "at least one X"                      → SUBTRACTION PRINCIPLE  (universe − none)
  "I counted each object d times"       → DIVISION RULE (÷ d, if d is uniform)

Worked numbers to recognize

Quantity Setup Value
8 lowercase letters, repeats OK $26^8$ $208{,}827{,}064{,}576$
8 lowercase letters, all distinct $26\cdot25\cdots19 = P(26,8)$ $62{,}990{,}928{,}000$
bytes / 32-bit values $2^8$ / $2^{32}$ $256$ / $4{,}294{,}967{,}296$
integers $1$-$100$ divisible by 2 or 5 $50 + 20 - 10$ $60$
integers $1$-$100$ divisible by 2, 3, or 5 $103 - 32 + 3$ $74$
seatings of $n$ around a round table $n!/n$ $(n-1)!$
$P(n, k)$, ordered, no repetition $n(n-1)\cdots(n-k+1)$ $n!/(n-k)!$

Counting multiples of $d$ up to $N$: $\lfloor N/d \rfloor$. Divisible by both $a$ and $b$: divisible by $\operatorname{lcm}(a, b)$ (= $ab$ when $a, b$ are coprime).

Common pitfalls

Pitfall Symptom Fix
Hidden dependence in a product #choices at a step depends on earlier picks split into cases, or count complement, or divide
Overlapping "cases" with the sum rule answer too big use inclusion-exclusion (subtract the overlap)
Non-uniform over-count with division some objects have extra symmetry division rule fails; need Burnside-style tools
Forgetting to add back the triple answer too small by $\lvert A\cap B\cap C\rvert$ follow the +/−/+ sign pattern
Counting "at least one" directly messy case explosion complement: universe − "none"

Keyspace / state-space sizing (the CS payoff)

  • Keyspace size = a product. Brute-force time $\approx$ (keyspace size) $/$ (guesses per second).
  • $26^8$ at $10^6$/s $\approx$ 58 hours; $95^{10}$ at $10^9$/s $\approx$ 1,900 years.
  • Combinatorial explosion = the product rule with many factors. One extra independent field multiplies the space — a 32-bit field can take a space from testable ($\sim 10^3$) to impossible ($\sim 10^{11}$).
  • "At least one digit" = subtraction: $\text{(all strings)} - \text{(strings with no digit)}$.

Toolkit additions — combinatorics.py (begun this chapter)

Function Signature Returns
product rule product_rule(*step_counts) $\prod n_i$
sum rule sum_rule(*case_counts) $\sum n_i$ (caller ensures disjoint)
inclusion-exclusion inclusion_exclusion_2(a, b, a_and_b) $\lvert A\rvert+\lvert B\rvert-\lvert A\cap B\rvert$
permutation count perm_count(n, k) $n(n-1)\cdots(n-k+1)$; $0$ if $k>n$

perm_count(n, n) = n!, perm_count(n, 0) = 1 (empty product). Chapter 16 adds comb_count(n, k) and the generators permutations, combinations.

One-sentence summary

Multiply for sequences of independent choices, add for disjoint cases, subtract overlaps with inclusion-exclusion, divide out uniform over-counts — and to size "at least one," count the universe minus the complement.