Product Rule (Combinatorics)

combinatorics

Definition

Product Rule (Combinatorics)

Suppose an object is constructed through $r$ successive stages. If every partial construction reaching stage $i$ can be extended in exactly $n_i$ ways, then the number of complete constructions is

$$N=\prod _{i=1}^r{n}_i=n_1{n}_2\cdots n_r.$$

The choices at a later stage may depend on earlier choices; only the number $n_i$ of available choices must be the same for every partial construction at that stage.

For fixed finite choice sets $S_1,\dots ,S_r$, this is equivalently the cardinality of their Cartesian product:

$$|S_1\times \cdots \times S_r|=\prod _{i=1}^r|S_i|.$$

Example

Choosing an outfit

Suppose an outfit consists of one of $3$ shirts, one of $2$ pairs of trousers, and one of $4$ pairs of shoes. The product rule gives

$$3\cdot 2\cdot 4=24$$

possible outfits.