Product Rule for Counting

From ProofWiki
Jump to navigation Jump to search

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