Product Rule for Counting

Theorem

Suppose a process can be broken into $m$ successive, ordered, stages, with the $i$th stage having $r_i$ possible outcomes (for $i = 1, \ldots, m$).

Let the number of outcomes at each stage be independent of the choices in previous stages

Let the composite outcomes be all distinct.

Then the total procedure has $\displaystyle \prod_{i \mathop = 1}^m r_i$ different composite outcomes.

Proof

The validity of this rule follows directly from the definition of multiplication of integers.

The product $a b$ (for $a, b \in \N_{>0}$) is the number of sequences $\left({A, B}\right)$, where $A$ can be any one of $a$ items and $B$ can be any one of $b$ items.

$\blacksquare$