# Product Rule for Counting

## Contents

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

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

## Also see

## Sources

- 1971: George E. Andrews:
*Number Theory*... (previous) ... (next): $\text {3-1}$ Permutations and Combinations