# Product Rule for Counting

## Contents

## 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$

## Also see

## Sources

- 2007: Alan Tucker:
*Applied Combinatorics*(5th ed.) p. 178