Introduction to the Rule of Products

If there is some number of different operations, and each operation can be performed in different ways, how many combinations of operations can be performed when the operations are not dependent on one another? This is an important question when trying to determine the number of outcomes for which one must account.

Enumerative Combinatorics


Enumerative combinatorics

Date back to the first prehistorics

Who counted; relations

Like sets' permutations

To them were part cult, part folklorics.

Michael Toalster, The Omnificent English Dictionary In Limerick Form

 

Throughout this book we will be counting things. In this chapter we will outline some of the tools that will help us count.

Counting occurs not only in highly sophisticated applications of mathematics to engineering and computer science but also in many basic applications. Like many other powerful and useful tools in mathematics, the concepts are simple; we only have to recognize when and how they can be applied.

 

2.1 Basic Counting Techniques - The Rule of Products


2.1.1 What is Combinatorics?

One of the first concepts our parents taught us was the "art of counting". We were taught to raise three fingers to indicate that we were three years old. The question of "how many" is a natural and frequently asked question. Combinatorics is the "art of counting". It is the study of techniques that will help us to count the number of objects in a set quickly. Highly sophisticated results can be obtained with this simple concept. The following examples will illustrate that many questions concerned with counting involve the same process.


Example 2.1.1: How many lunches can you have? A snack bar serves five different sandwiches and three different beverages. How many different lunches can a person order? One way of determining the number of possible lunches is by listing or enumerating all the possibilities. One systematic way of doing this is by means of a tree, as in the following figure.


Figure 2.1.2 Tree diagram to enumerate the number of possible lunches.

Every path that begins at the position labeled START and goes to the right can be interpreted as a choice of one of the five sandwiches followed by a choice of one of the three beverages. Note that considerable work is required to arrive at the number fifteen this way; but we also get more than just a number. The result is a complete list of all possible lunches. If we need to answer a question that starts with "How many . . . ", enumeration would be done only as a last resort. In a later chapter we will examine more enumeration techniques.

An alternative method of solution for this example is to make the simple observation that there are five different choices for sandwiches and three different choices for beverages, so there are 5 · 3 = 15 different lunches that can be ordered.


Example 2.1.3: Counting elements in a cartesian product. Let A {a, b, c, d, e} and B = {1 , 2, 3} . From Chapter 1 we know how to list the elements in A × B = { (a, 1), ( a, 2), (a, 3) , ..., (e, 3)} . Since the first entry of each pair can be any one of the five elements a, b, c, d, and e , and since the second can be any one of the three numbers 1, 2, and 3, it is quite clear there are 5 · 3 = 15 different elements in A × B.


Example 2.1.4: A True-False Questionnaire. A person is to complete a true-false questionnaire consisting of ten questions. How many different ways are there to answer the questionnaire? Since each question can be answered in either of two ways (true or false), and there are ten questions, there are

2 · 2 · 2 · 2 · 2 · 2 · 2 · 2 · 2 · 2 = 210 = 1024

 different ways of answering the questionnaire. The reader is encouraged to visualize the tree diagram of this example, but not to draw it!

We formalize the procedures developed in the previous examples with the following rule and its extension.


2.1.2 The Rule Of Products

If two operations must be performed, and if the first operation can always be performed p1 different ways and the second operation can always be performed p2 different ways, then there are p1 · p2 different ways that the two operations can be performed.

Note: It is important that p2 does not depend on the option that is chosen in the first operation. Another way of saying this is that p2 is independent of the first operation. If p2 is dependent on the first operation, then the rule of products does not apply.


Example 2.1.5: Reduced Lunch Possibilities. Assume in Example 2.1.1, coffee is not served with a beef or chicken sandwiches. Then by inspection of Figure 2.1.2 we see that there are only thirteen different choices for lunch. The rule of products does not apply, since the choice of beverage depends on one's choice of a sandwich.

Extended Rule Of Products. The rule of products can be extended to include sequences of more than two operations. If n operations must be performed, and the number of options for each operation is p1p 2 , . . . , pn respectively, with each pi independent of previous choices, then the n operations can be performed p 1 · p2 · · · · · p n different ways.


Example 2.1.6: A Multiple Choice Questionnaire. A questionnaire contains four questions that have two possible answers and three questions with five possible answers. Since the answer to each question is independent of the answers to the other questions, the extended rule of products applies and there are 2 · 2 · 2 · 2 · 5 · 5 · 5 = 24 · 53 = 2000 different ways to answer the questionnaire.

In Chapter 1 we introduced the power set of a set A, \wp(A), which is the set of all subsets of A. Can we predict how many elements are in \wp(A) for a given finite set A ? The answer is yes, and in fact if |A= n , then \left | \wp(A) \right | = 2^n. The ease with which we can prove this fact demonstrates the power and usefulness of the rule of products. Do not underestimate the usefulness of simple ideas.


Theorem 2.1.7: Power Set Cardinality Theorem. If A is a finite set, then \left | \wp(A) \right | = 2^{\left | A \right |}.

Proof. Proof: Consider how we might determine any B P (A), where |A| = n. For each element x A there are two choices, either x B or x B. Since there are n elements of A we have, by the rule of products,

\frac{2 \cdot 2 \cdot . . . \cdot 2}{n \; \mathrm{factors}} = 2^n

different subsets of A. Therefore, \wp(A) = 2^n.



Source: Al Doerr and Ken Levasseur, http://faculty.uml.edu/klevasseur/ads-latex/ads.pdf
Creative Commons License This work is licensed under a Creative Commons Attribution-NonCommercial-ShareAlike 3.0 License.

Last modified: Monday, August 10, 2020, 2:47 PM