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.

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 are 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.

Other typical example is using it with the rule of sum, in this case we have two groups, the group A with 3 elements and the group B with 10 elements. We want to pick one element ( we don't care if it is from group A or B) and a second element that must be from the group B. The way that we can choose the elements are:

$\mathrm {Total} \ \mathrm {ways} =(3*10)+(10*9)$

First, we use the rule of product to get the number of ways if we pick an element from group A and then from group B. After this, we repeat the process but now choosing the first element from group ‘’’B’’’ and the second element, different from the one we now chose, also from group ‘’’B’’’ (as required) so we get ‘’’B’’’ times ‘’’B-1’’’ for the second product in the addition.

Applications

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.

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.

See also

• Combinatorial principles