5.2: Tree Diagrams and the Multiplication Axiom

Last updated
Save as PDF

Page ID: 40143

$ \newcommand{\vecs}[1]{\overset { \scriptstyle \rightharpoonup} {\mathbf{#1}} } $ $ \newcommand{\vecd}[1]{\overset{-\!-\!\rightharpoonup}{\vphantom{a}\smash {#1}}} $$\newcommand{\id}{\mathrm{id}}$ $ \newcommand{\Span}{\mathrm{span}}$ $ \newcommand{\kernel}{\mathrm{null}\,}$ $ \newcommand{\range}{\mathrm{range}\,}$ $ \newcommand{\RealPart}{\mathrm{Re}}$ $ \newcommand{\ImaginaryPart}{\mathrm{Im}}$ $ \newcommand{\Argument}{\mathrm{Arg}}$ $ \newcommand{\norm}[1]{\| #1 \|}$ $ \newcommand{\inner}[2]{\langle #1, #2 \rangle}$ $ \newcommand{\Span}{\mathrm{span}}$ $\newcommand{\id}{\mathrm{id}}$ $ \newcommand{\Span}{\mathrm{span}}$ $ \newcommand{\kernel}{\mathrm{null}\,}$ $ \newcommand{\range}{\mathrm{range}\,}$ $ \newcommand{\RealPart}{\mathrm{Re}}$ $ \newcommand{\ImaginaryPart}{\mathrm{Im}}$ $ \newcommand{\Argument}{\mathrm{Arg}}$ $ \newcommand{\norm}[1]{\| #1 \|}$ $ \newcommand{\inner}[2]{\langle #1, #2 \rangle}$ $ \newcommand{\Span}{\mathrm{span}}$$\newcommand{\AA}{\unicode[.8,0]{x212B}}$

Learning Objectives

In this section you will learn to:

Use trees to count possible outcomes in a multi-step process.
Use the multiplication axiom to count possible outcomes in a multi-stop process.

In this chapter, we are trying to develop counting techniques that will be used in the next chapter to study probability. One of the most fundamental of such techniques is called the Multiplication Axiom. Before we introduce the multiplication axiom, we first look at some examples using tree diagrams.

A tree diagram is a visual way to show all possible outcomes of a certain event. Each event represents a split in the branches with each possible outcome listed at the end of a branch.

Example $\PageIndex{1}$

If a food truck sells 2 types of appetizers and 4 types of sandwiches, how many different meal options can be ordered? Construct a tree diagram to represent this scenario.

Solution

Suppose we call the appetizers $a_1$ and $a_2$, and sandwiches$s_1$, $s_2$, $s_3$, and $s_4$.

We can draw a tree diagram:

$Example7.2.1.png$

The tree diagram shows us all eight possible meals:

\[a_1s_1, a_1s_2, a_1s_3, a_1s_4, a_2s_1, a_2s_2, a_2s_3, a_2s_4 \nonumber\]

The method involves two events: choosing an appetizer and choosing a sandwich. Each events is represented by a group of branches, with each possible outcome listed at the end of a branch. The tree diagram helps us visualize these possibilities.

If, in the previous example, we add the desserts to the meal, we have the following problem.

Example $\PageIndex{2}$

If a food truck sells 2 types of appetizers, 4 types of sandwiches, and 2 types of desserts, how many different meal options can be ordered? Construct a tree diagram to represent this scenario.

Solution

Suppose we call the appetizers $a_1$ and $a_2$, the sandwiches$s_1$, $s_2$, $s_3$, and $s_4$, and the desserts $d_1$ and $d_2$.

The following tree diagram results.

$Example7.2.2.png$

We count the number of branches in the tree, and see that there are 16 different possibilities.

The method involves three events: choosing an appetizer, choosing a sandwich, and choosing a dessert. Each eventnis represented by a group of branches, with each possible outcome listed at the end of a branch.

All in all, we have $2 \cdot 4 \cdot 2 = 16$ different possibilities.

Tree diagrams help us visualize the different possibilities, but they are not practical when the possibilities are numerous. Besides, we are mostly interested in finding the number of elements in the set and not the actual list of all possibilities; once the problem is envisioned, we can solve it without a tree diagram. The two examples we just solved may have given us a clue to do just that.

Let us now try to solve Example $\PageIndex{2}$ without a tree diagram. The problem involves three steps: choosing an appetizer, choosing a sandwich, and choosing a dessert. The number of ways of choosing each are listed below. By multiplying these three numbers we get 16, which is what we found when we did the problem using a tree diagram.

The number of ways of choosing an appetizer	The number of ways of choosing a sandwich	The number of ways of choosing a dessert
2	4	2

The procedure we just employed is called the multiplication axiom.

The Multiplication Axiom

If a task can be done in $m$ ways, and a second task can be done in $n$ ways, then the operation involving the first task followed by the second can be performed in $m \cdot n$ ways.

The general multiplication axiom is not limited to just two tasks and can be used for any number of tasks.

Example $\PageIndex{3}$

A truck license plate consists of a letter followed by four digits. How many such license plates are possible?

Solution

Since there are 26 letters and 10 digits, we have the following choices for each.

Letter	Digit	Digit	Digit	Digit
26	10	10	10	10

Therefore, the number of possible license plates is $26 \cdot 10 \cdot 10 \cdot 10 \cdot 10=260,000$.

Example $\PageIndex{4}$

In how many different ways can a 3-question true-false test be answered?

Solution

Since there are two choices for each question, we have

Question 1	Question 2	Question 3
2	2	2

Applying the multiplication axiom, we get $2 \cdot 2 \cdot 2 = 8$ different ways.

We list all eight possibilities: TTT, TTF, TFT, TFF, FTT, FTF, FFT, FFF

The reader should note that the first letter in each possibility is the answer corresponding to the first question, the second letter corresponds to the answer to the second question, and so on. For example, TFF, says that the answer to the first question is given as true, and the answers to the second and third questions false.

Example $\PageIndex{5}$

In how many different ways can four people be seated in a row?

Solution

Suppose we put four chairs in a row, and proceed to put four people in these seats.

There are four choices for the first chair we choose. Once a person sits down in that chair, there are only three choices for the second chair, and so on. We list as shown below.

So there are altogether $4 \cdot 3 \cdot 2 \cdot 1 = 24$ different ways.

Example $\PageIndex{6}$

How many three-letter word sequences can be formed using the letters { A, B, C } if no letter is to be repeated?

Solution

The problem is very similar to the previous example.

Imagine a child having three building blocks labeled A, B, and C. Suppose he puts these blocks on top of each other to make word sequences. For the first letter he has three choices, namely A, B, or C. Let us suppose he chooses the first letter to be a B, then for the second block which must go on top of the first, he has only two choices: A or C. And for the last letter he has only one choice. We list the choices below.

Therefore, 6 different word sequences can be formed.

Finally, we'd like to illustrate this with a tree diagram showing all six possibilities.

$Example7.2.6.png$