Product Rule For Counting

Theorem

Suppose a process can be broken into $m$ successive, ordered, stages, with the $i^{\text{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=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^*$) 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$

Sources

• A. Tucker: Applied Combinatorics 5th Edition (2007) p. 178