Definition
Product Rule (Combinatorics)
Suppose an object is constructed through
successive stages. If every partial construction reaching stage can be extended in exactly ways, then the number of complete constructions is The choices at a later stage may depend on earlier choices; only the number
of available choices must be the same for every partial construction at that stage. For fixed finite choice sets
, this is equivalently the cardinality of their Cartesian product:
Example
Choosing an outfit
Suppose an outfit consists of one of
shirts, one of pairs of trousers, and one of pairs of shoes. The product rule gives possible outfits.