Product Rule for Counting/General Theorem

From ProofWiki
Jump to navigation Jump to search



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 $\ds \prod_{i \mathop = 1}^m r_i$ different composite outcomes.


Proof



Also known as

Some sources give this as the General Combinatorial Principle.


Also see


Sources