Rule of product

From Wikipedia, the free encyclopedia
Jump to: navigation, search

In combinatorics, the rule of product or multiplication principle is a basic counting principle (a.k.a. the fundamental principle of counting). Stated simply, it is the idea that if there are a ways of doing something and b ways of doing another thing, then there are a · b ways of performing both actions.[1]

& \underbrace{ \left\{A,B,C\right\} }
& & \underbrace{ \left\{ X,Y\right\} } \\
\mathrm{To}\ \mathrm{choose}\ \mathrm{one}\ \mathrm{of} & \mathrm{these} &
\mathrm{AND}\ \mathrm{one}\ \mathrm{of} & \mathrm{these}

\mathrm{is}\ \mathrm{to}\ \mathrm{choose}\ \mathrm{one}\ \mathrm{of} & \mathrm{these}. \\
& \overbrace{ \left\{ AX, AY, BX, BY, CX, CY \right\} }

In this example, the rule says: multiply 3 by 2, getting 6.

The sets {A, B, C} and {X, Y} in this example are disjoint, but that is not necessary. The number of ways to choose a member of {A, B, C}, and then to do so again, in effect choosing an ordered pair each of whose components is in {A, B, C}, is 3 × 3 = 9.

In set theory, this multiplication principle is often taken to be the definition of the product of cardinal numbers. We have

|S_{1}|\cdot|S_{2}|\cdots|S_{n}| = |S_{1} \times S_{2} \times \cdots \times S_{n}|

where  \times is the Cartesian product operator. These sets need not be finite, nor is it necessary to have only finitely many factors in the product; see cardinal number.


When you decide to order pizza, you must first choose the type of crust: thin or deep dish (2 choices). Next, you choose the topping: cheese, pepperoni, or sausage (3 choices).

Using the rule of product, you know that there are 2 × 3 = 6 possible combinations of ordering a pizza.

See also[edit]