Rule of product

The elements of the set {A, B} can combine with the elements of the set {1, 2, 3} in six different ways.

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][2]

Examples

${\begin{matrix}&\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}}\end{matrix}}$

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

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 sets, 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.

As another example, when you decide to order pizza, you must first choose the type of crust: thin or deep dish (2 choices). Next, you choose one 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.

Applications

In set theory, this multiplication principle is often taken to be the definition of the product of cardinal numbers.^[1] 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.

Related concepts

The rule of sum is another basic counting principle. Stated simply, it is the idea that if we have a ways of doing something and b ways of doing another thing and we can not do both at the same time, then there are a + b ways to choose one of the actions.^[3]

See also

• Combinatorial principles

References

1. Johnston, William, and Alex McAllister. A transition to advanced mathematics. Oxford Univ. Press, 2009. Section 5.1
2. "College Algebra Tutorial 55: Fundamental Counting Principle". Retrieved December 20, 2014. line feed character in |title= at position 17 (help)
3. Rosen, Kenneth H., ed. Handbook of discrete and combinatorial mathematics. CRC press, 1999.