Product Rule for Counting

Theorem

Let it be possible to choose an element $\alpha$ from a given set $S$ in $m$ different ways.

Let it be possible to choose an element $\beta$ from a given set $T$ in $n$ different ways.

Then the ordered pair $\tuple {\alpha, \beta}$ can be chosen from the cartesian product $S \times T$ in $m n$ different ways.

General 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

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 $\sequence {A, B}$, where $A$ can be any one of $a$ items and $B$ can be any one of $b$ items.

$\blacksquare$

Also known as

Some sources give this as the General Combinatorial Principle.

Some sources call it the $r$, $s$ principle: if one operation can be performed in $r$ different ways, and if another operation can be performed in $s$ different ways, the two operations can be performed in succession in $r \times s$ different ways.

Examples

Choices from $2$ and $3$

The canonical example concerns choices from the menu at a restaurant:

You may select exactly one dish from each category:

Starters
$(1): \quad$ Crottled Greeps
$(2): \quad$ Stone Soup
$(3): \quad$ Petty-Dwarf Roots
Main Course
$(1): \quad$ Hufu Salad
$(2): \quad$ Braised Trake in Funistrada

The diner then has $2 \times 3 = 6$ possible different meals:

$(1): \quad$ Crottled Greeps with Hufu Salad
$(2): \quad$ Crottled Greeps with Braised Trake in Funistrada
$(3): \quad$ Stone Soup with Hufu Salad
$(4): \quad$ Stone Soup with Braised Trake in Funistrada
$(5): \quad$ Petty-Dwarf Roots with Hufu Salad
$(6): \quad$ Petty-Dwarf Roots with Braised Trake in Funistrada