Lesson 36 — Fundamental Counting Principle

FCP and trees

Statement

If an experiment consists of $k$ successive and independent stages, with $n_1$ outcomes in the first, $n_2$ in the second, ..., $n_k$ in the $k$-th, then the total number of possible outcomes is: $N = n_1 \cdot n_2 \cdots n_k$

Additive principle (alternative)

If a task can be done by method A in $m$ ways OR by method B in $n$ ways (mutually exclusive), the total is $m + n$.

Archetypal example

4-character password: each can be A-Z (26 options). Total: $26^4 = 456\,976$.

Tree of possibilities

Each stage "branches" — the tree has $n_1$ roots, each with $n_2$ children, and so on. Leaves = total of outcomes.

Constraints — "no repetition"

If shoes can't repeat, the first has 5 options, the second 4, the third 3 — combinations without repetition. Generalizes to permutation/arrangement (Lesson 37).

Functions between sets

• Total functions $f: A \to B$ with $|A| = m, |B| = n$: $n^m$.
• Injective functions ($f: A \to B$ with $m \leq n$): $n!/(n-m)!$ (arrangement).
• Bijective functions ($m = n$): $n!$ (permutation).