Rule of product
Encyclopedia
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 we have a ways of doing something and b ways of doing another thing, then there are a · b ways of performing both actions.
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 number
s. We have
where
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
.
Using the rule of product, you know that there are 2 × 3 = 6 possible combinations of ordering a pizza.
Combinatorics
Combinatorics is a branch of mathematics concerning the study of finite or countable discrete structures. Aspects of combinatorics include counting the structures of a given kind and size , deciding when certain criteria can be met, and constructing and analyzing objects meeting the criteria ,...
, the rule of product or multiplication principle is a basic counting principle
Combinatorial principles
In proving results in combinatorics several useful combinatorial rules or combinatorial principles are commonly recognized and used.The rule of sum, rule of product, and inclusion-exclusion principle are often used for enumerative purposes. Bijective proofs are utilized to demonstrate that two sets...
(a.k.a. the fundamental principle of counting). Stated simply, it is the idea that if we have a ways of doing something and b ways of doing another thing, then there are a · b ways of performing both actions.
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
Ordered pair
In mathematics, an ordered pair is a pair of mathematical objects. In the ordered pair , the object a is called the first entry, and the object b the second entry of the pair...
each of whose components is in {A, B, C}, is 3 × 3 = 9.
In set theory
Set theory
Set theory is the branch of mathematics that studies sets, which are collections of objects. Although any type of object can be collected into a set, set theory is applied most often to objects that are relevant to mathematics...
, this multiplication principle is often taken to be the definition of the product of cardinal number
Cardinal number
In mathematics, cardinal numbers, or cardinals for short, are a generalization of the natural numbers used to measure the cardinality of sets. The cardinality of a finite set is a natural number – the number of elements in the set. The transfinite cardinal numbers describe the sizes of infinite...
s. We have
where
is the Cartesian productCartesian product
In mathematics, a Cartesian product is a construction to build a new set out of a number of given sets. Each member of the Cartesian product corresponds to the selection of one element each in every one of those sets...
operator. These sets need not be finite, nor is it necessary to have only finitely many factors in the product; see cardinal number
Cardinal number
In mathematics, cardinal numbers, or cardinals for short, are a generalization of the natural numbers used to measure the cardinality of sets. The cardinality of a finite set is a natural number – the number of elements in the set. The transfinite cardinal numbers describe the sizes of infinite...
.
Simple example
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.