7.2 Tree Diagrams and the Multiplication Axiom

Learning Objectives

In this section, you will learn to:

Use tree diagrams to count possible outcomes in a multi-step process.
Use the multiplication axiom to count possible outcomes in a multi-step process.

7.2.1 Counting with Tree Diagrams

Counting techniques are the backbone of probability. Before we can ask "what are the chances…?" we need to know how many outcomes are possible in total. A tree diagram is a visual method that lays out every outcome of a multi-step process, step by step, so we can count them directly.

Context Pause: Why count first? Every probability in the next chapter has the form $P(\text{event}) = \dfrac{\text{favorable outcomes}}{\text{total outcomes}}$. If you can't count the total, you can't compute the probability. Counting techniques — trees, the multiplication axiom, permutations, and combinations — are the toolkit for the denominator. They're worth mastering.

Insight Note: A tree grows one level per step If a process has $k$ steps, the finished tree has $k$ levels of branches: each level represents one decision. The leaves of the tree (the endpoints of the final level) are the complete outcomes. Count the leaves and you've counted every possibility.

Example 7.2.1

Source: Applied Finite Mathematics

James has two blouses and three skirts. How many different outfits consisting of a blouse and a skirt can he wear?

Solution

Step 1 — Enumerate directly. Call the blouses $b_1, b_2$ and the skirts $s_1, s_2, s_3$:

$$b_1 s_1,\ b_1 s_2,\ b_1 s_3,\ b_2 s_1,\ b_2 s_2,\ b_2 s_3.$$

That's six outfits. The tree diagram above organises the same six outfits visually.

Step 2 — Confirm by multiplication. The method has two steps: first pick a blouse ($2$ choices), then pick a skirt ($3$ choices for each blouse). Because every blouse can be paired with every skirt, the total is

$$2 \cdot 3 = 6 \text{ possibilities.}$$

Answer: $6$ outfits.

Try It Now 7.2.1

Source: Applied Finite Mathematics

Malik is building a snack plate with one fruit (apple, banana, or cherry) and one cracker (wheat or rye). Draw a tree diagram and count the possible snack plates.

Solution

Two steps: fruit ($3$ choices) then cracker ($2$ choices per fruit). The tree has 3 top branches, each splitting into 2, so there are $3 \cdot 2 = 6$ snack plates.

7.2.2 The Multiplication Axiom

Tree diagrams are great for visualization but painful once the numbers grow. A shortcut is hiding in the arithmetic we just did: we multiplied the number of choices at each step. That shortcut is called the multiplication axiom.

Context Pause: Adding the third step doesn't double the work

Adding a new step to a counting problem doesn't mean we redraw everything — it just means we multiply in one more factor. If we add shoes to the outfit problem above with $2$ choices, the total becomes $2 \cdot 3 \cdot 2 = 12$, not a new tree to enumerate by hand.

Insight Note: The axiom abstracts the tree

The multiplication axiom doesn't replace the tree — it summarises it. Every time you multiply, you're counting branches at a level of the tree you could have drawn. When a problem gets too big for a tree, the axiom is what the tree would have told you if you'd drawn it.

Example 7.2.2

Source: Applied Finite Mathematics

Aanya has two blouses, three skirts, and two pairs of pumps. How many different outfits (blouse + skirt + pumps) can they wear?

Solution

Step 1 — Label the items. Let $b_1, b_2$ be the blouses, $s_1, s_2, s_3$ the skirts, and $p_1, p_2$ the pumps. The tree diagram adds a third level to the two-step tree from Example 7.2.1.

Step 2 — Count the branches. The tree now has $12$ leaves, so there are $12$ outfits.

Step 3 — Confirm with the multiplication axiom. Listing the choices at each step:

Step	Blouse	Skirt	Pumps
Choices	2	3	2

$$2 \cdot 3 \cdot 2 = 12.$$

Answer: $12$ possible outfits.

The Multiplication Axiom

If a first task can be done in $m$ ways, and for each of those a second task can be done in $n$ ways, then the two-task process can be completed in $m \cdot n$ ways.

The axiom extends to any number of tasks: multiply the number of choices at each step.

Show visualization

Try It Now 7.2.2

Source: Applied Finite Mathematics

A family dinner consists of one entree (4 choices), one side (3 choices), and one drink (2 choices). How many distinct dinners are possible?

Solution

Three steps with $4$, $3$, and $2$ choices. By the multiplication axiom,

$$4 \cdot 3 \cdot 2 = 24 \text{ dinners.}$$

7.2.3 Applying the Multiplication Axiom

With the axiom in hand, we can count the outcomes of processes where a tree diagram would be unwieldy. The examples that follow illustrate three common patterns: fixed slots with repetition, restricted slots (no repetition), and the full enumeration of short arrangements.

Context Pause: Watch for "no repetition" wording

Many counting problems turn on one phrase: with repetition (each step has the same number of choices every time) or without repetition (each choice removes one option from the next step). The arithmetic changes from $n \cdot n \cdot n \cdots$ to $n \cdot (n-1) \cdot (n-2) \cdots$. Read the wording carefully.

Insight Note: Multiplication doesn't care about order

The multiplication axiom counts the number of ordered outcomes. If the problem says "how many arrangements?" you use multiplication. If the problem says "how many unordered selections?" that's a different counting technique we'll develop in later sections. For now, the axiom applies whenever order matters.

Example 7.2.3

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

Solution

Step 1 — Count the slot options. There are $26$ letters and $10$ digits. Each slot is independent (repetition is allowed):

| Slot | Letter | Digit | Digit | Digit | Digit | |---|---|---|---|---|---| | Choices | 26 | 10 | 10 | 10 | 10 |

Step 2 — Multiply.

\[26 \cdot 10 \cdot 10 \cdot 10 \cdot 10 = 260{,}000.\]

Answer: $260{,}000$ plates.

Example 7.2.4

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

Solution

Step 1 — Count the slot options. Each question has $2$ independent choices (true or false):

| Question | 1 | 2 | 3 | |---|---|---|---| | Choices | 2 | 2 | 2 |

Step 2 — Apply the multiplication axiom.

\[2 \cdot 2 \cdot 2 = 8 \text{ ways.}\]

Step 3 — Enumerate for confidence.

\[\text{TTT, TTF, TFT, TFF, FTT, FTF, FFT, FFF}.\]

Each letter is the answer to the corresponding question (first letter = question 1's answer, etc.).

Answer: $8$ ways.

Example 7.2.5

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

Solution

Step 1 — Track the shrinking pool. There are $4$ choices for the first chair. Once one person sits, only $3$ remain for the second chair, then $2$ for the third, and $1$ for the last:

| Chair | 1st | 2nd | 3rd | 4th | |---|---|---|---|---| | Choices | 4 | 3 | 2 | 1 |

Step 2 — Multiply.

\[4 \cdot 3 \cdot 2 \cdot 1 = 24.\]

Answer: $24$ arrangements.

Example 7.2.6

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

Solution

Step 1 — Track the shrinking pool. Three slots, no repetition. Like stacking three lettered blocks: $3$ choices for the first, $2$ remaining for the second, $1$ for the last.

| Slot | 1st | 2nd | 3rd | |---|---|---|---| | Choices | 3 | 2 | 1 |

Step 2 — Multiply.

\[3 \cdot 2 \cdot 1 = 6 \text{ sequences.}\]

Step 3 — Enumerate. The six sequences (shown in the tree above): ABC, ACB, BAC, BCA, CAB, CBA.

Answer: $6$ sequences.

Try It Now 7.2.3

A coffee shop is running a giveaway: the prize is an ordered sequence of three different beverages chosen from a menu of $5$. How many distinct prize sequences are possible?

Solution

Three slots, no repetition, from a pool of $5$ beverages:

\[5 \cdot 4 \cdot 3 = 60 \text{ sequences.}\]

Problem Set 7.2

Source: Applied Finite Mathematics

Problems 1–6: Use a tree diagram or the multiplication axiom.

Problem 1. Layla has 3 shirts and 2 pairs of pants. Use a tree diagram to determine the number of possible outfits.

Problem 1 Solution

Step 1 — Identify the choices at each stage: Layla must choose one shirt and one pair of pants. She has 3 choices for the shirt and 2 choices for the pants.

Step 2 — Draw the tree diagram structure: The first level of branches represents the 3 shirts (call them $S_1, S_2, S_3$). From each shirt branch, two sub-branches represent the 2 pairs of pants ($P_1, P_2$). This gives $3 \times 2 = 6$ paths through the tree.

Step 3 — List all outfits: The six complete paths are: $S_1P_1,\; S_1P_2,\; S_2P_1,\; S_2P_2,\; S_3P_1,\; S_3P_2$

Step 4 — Apply the multiplication axiom: By the multiplication axiom, the total number of outfits is $3 \times 2 = 6$.

Answer: 6 possible outfits

Problem 2. In a city election, there are 2 candidates for mayor and 3 for supervisor. Use a tree diagram to find the number of ways to fill the two offices.

Problem 2 Solution

Step 1 — Identify the choices at each stage: There are 2 candidates for mayor and 3 candidates for supervisor. A voter (or selection process) must choose one for each office.

Step 2 — Draw the tree diagram structure: The first level has 2 branches (one for each mayoral candidate). From each of those, 3 sub-branches represent the supervisor candidates. This gives $2 \times 3 = 6$ paths.

Step 3 — List all combinations: If the mayoral candidates are $M_1, M_2$ and the supervisor candidates are $S_1, S_2, S_3$, the six outcomes are: $M_1S_1,\; M_1S_2,\; M_1S_3,\; M_2S_1,\; M_2S_2,\; M_2S_3$

Step 4 — Apply the multiplication axiom: By the multiplication axiom, the total number of ways is $2 \times 3 = 6$.

Answer: 6 ways to fill the two offices

Problem 3. There are 4 roads from Town A to Town B and 2 roads from Town B to Town C. Use a tree diagram to find the number of ways one can travel from Town A to Town C (passing through Town B).

Problem 3 Solution

Step 1 — Identify the choices at each stage: To travel from Town A to Town C (through Town B), a traveler must first choose one of 4 roads from A to B, then choose one of 2 roads from B to C.

Step 2 — Draw the tree diagram structure: The first level has 4 branches (one for each A-to-B road). From each of those, 2 sub-branches represent the B-to-C roads. This gives $4 \times 2 = 8$ paths.

Step 3 — List all routes: If the A-to-B roads are $R_1, R_2, R_3, R_4$ and the B-to-C roads are $T_1, T_2$, the eight routes are: $R_1T_1,\; R_1T_2,\; R_2T_1,\; R_2T_2,\; R_3T_1,\; R_3T_2,\; R_4T_1,\; R_4T_2$

Step 4 — Apply the multiplication axiom: By the multiplication axiom, the total number of routes is $4 \times 2 = 8$.

Answer: 8 possible routes from Town A to Town C

Problem 4. Brown Home Construction offers a selection of 3 floor plans, 2 roof types, and 2 exterior wall types. Use a tree diagram to determine the number of possible homes available.

Problem 4 Solution

Step 1 — Identify the choices at each stage:

A home buyer must choose: 3 floor plans, then 2 roof types, then 2 exterior wall types.

Step 2 — Draw the tree diagram structure:

The first level has 3 branches (floor plans). Each of those splits into 2 sub-branches (roof types). Each of those splits into 2 more sub-branches (exterior wall types). This gives $3 \times 2 \times 2 = 12$ paths.

Step 3 — Apply the multiplication axiom:

By the multiplication axiom, the total number of possible homes is:

$3 \times 2 \times 2 = 12$

Answer: 12 possible homes

Problem 5. For lunch, a small restaurant offers 2 types of soups, 3 kinds of sandwiches, and 2 types of soft drinks. Use a tree diagram to determine the number of possible meals consisting of a soup, a sandwich, and a soft drink.

Problem 5 Solution

Step 1 — Identify the choices at each stage:
A meal consists of one soup (2 choices), one sandwich (3 choices), and one soft drink (2 choices).

Step 2 — Draw the tree diagram structure:
The first level has 2 branches (soups). Each of those splits into 3 sub-branches (sandwiches). Each of those splits into 2 more sub-branches (soft drinks). This gives $2 \times 3 \times 2 = 12$ paths.

Step 3 — Apply the multiplication axiom:
By the multiplication axiom, the total number of possible meals is:
$2 \times 3 \times 2 = 12$

Answer: 12 possible meals

Problem 6. A California license plate consists of a number from 1 to 5, then three letters followed by three digits. How many such plates are possible?

Problems 7–10: Use the multiplication axiom.

Problem 6 Solution

Step 1 — Identify the choices at each position on the plate:

A California license plate has the format: [number 1–5][letter][letter][letter][digit][digit][digit].

Step 2 — Count the choices for each position:

Position 1 (number 1–5): 5 choices
Positions 2–4 (three letters, with repetition allowed): $26 \times 26 \times 26$ choices
Positions 5–7 (three digits, with repetition allowed): $10 \times 10 \times 10$ choices

Step 3 — Apply the multiplication axiom:

\[ 5 \times 26^3 \times 10^3 = 5 \times 17{,}576 \times 1{,}000 = 87{,}880{,}000 \]

Answer: 87,880,000 possible license plates

Problem 7. A license plate consists of three letters followed by three digits. How many license plates are possible if no letter may be repeated?

Problem 7 Solution

Step 1 — Identify the choices for each position: A license plate has three letters followed by three digits. The constraint is that no letter may be repeated, but there is no restriction on the digits.

Step 2 — Count the choices for the letter positions:

First letter: 26 choices (any letter A–Z)
Second letter: 25 choices (cannot repeat the first letter)
Third letter: 24 choices (cannot repeat either of the first two letters)

Step 3 — Count the choices for the digit positions: Each of the three digit positions has 10 choices (0–9), with repetition allowed: $10 \times 10 \times 10 = 1{,}000$

Step 4 — Apply the multiplication axiom:

\[ 26 \times 25 \times 24 \times 10 \times 10 \times 10 = 15{,}600 \times 1{,}000 = 15{,}600{,}000 \]

Answer: 15,600,000 possible license plates

Problem 8. How many different 4-letter radio station call letters can be made if the first letter must be K or W and no letters can be repeated?

Problem 8 Solution

Step 1 — Identify the constraints:

We need a 4-letter sequence. The first letter must be K or W, and no letter can be repeated.

Step 2 — Count the choices for each position:

First letter: 2 choices (K or W)
Second letter: 25 choices (any of the remaining 25 letters)
Third letter: 24 choices (remaining letters after two are used)
Fourth letter: 23 choices (remaining letters after three are used)

Step 3 — Apply the multiplication axiom:

\[ 2 \times 25 \times 24 \times 23 = 27{,}600 \]

Answer: 27,600 different call letters

Problem 9. How many seven-digit telephone numbers are possible if the first two digits cannot be ones or zeros?

Problem 9 Solution

Step 1 — Identify the constraints:

A seven-digit telephone number has 7 positions. The first two digits cannot be 0 or 1, so they must be chosen from $\{2, 3, 4, 5, 6, 7, 8, 9\}$.

Step 2 — Count the choices for each position:

First digit: 8 choices (digits 2–9)
Second digit: 8 choices (digits 2–9)
Digits 3–7: 10 choices each (digits 0–9, no restrictions)

Step 3 — Apply the multiplication axiom:

\[ 8 \times 8 \times 10^5 = 64 \times 100{,}000 = 6{,}400{,}000 \]

Answer: 6,400,000 possible telephone numbers

Problem 10. How many 3-letter word sequences can be formed using the letters $\{a, b, c, d\}$ if no letter is to be repeated?

Use a tree diagram for problems 7.2.11 and 7.2.12:

Problem 10 Solution

Step 1 — Identify the constraints:

We need to form a 3-letter sequence using the letters $\{a, b, c, d\}$ with no letter repeated.

Step 2 — Count the choices for each position:

First position: 4 choices (a, b, c, or d)
Second position: 3 choices (any of the remaining 3 letters)
Third position: 2 choices (any of the remaining 2 letters)

Step 3 — Apply the multiplication axiom:

\[ 4 \times 3 \times 2 = 24 \]

Answer: 24 different 3-letter word sequences

Problem 11. A family has two children. Use a tree diagram to determine all four possible outcomes by gender.

Problem 11 Solution

Step 1 — Set up the tree diagram:
The first child can be either a boy (B) or a girl (G). The second child can also be either B or G.

Step 2 — Draw the branches:

First branch: B or G (for the first child)
From each first branch, two sub-branches: B or G (for the second child)

Step 3 — List all four outcomes:
Reading each path from root to leaf:

BB (first child is a boy, second child is a boy)
BG (first child is a boy, second child is a girl)
GB (first child is a girl, second child is a boy)
GG (first child is a girl, second child is a girl)

Step 4 — Verify by the multiplication axiom:
$2 \times 2 = 4$ outcomes, which matches our list.

Answer: The four possible outcomes are BB, BG, GB, and GG.

Problem 12. A coin is tossed three times and the sequence of heads and tails is recorded. Use a tree diagram to list all the possible outcomes.

Problem 12 Solution

Step 1 — Set up the tree diagram:
Each toss has two possible outcomes: heads (H) or tails (T). With three tosses, the tree has three levels.

Step 2 — Draw the branches:

First toss: 2 branches (H, T)
Second toss: each branch splits into 2 (H, T), giving 4 paths so far
Third toss: each of those splits into 2 (H, T), giving 8 total paths

Step 3 — List all eight outcomes:
Reading each path from root to leaf:

Step 4 — Verify by the multiplication axiom:
$2 \times 2 \times 2 = 2^3 = 8$ outcomes, which matches our list.

Answer: The eight possible outcomes are HHH, HHT, HTH, HTT, THH, THT, TTH, TTT.

Problems 13–18: Use the multiplication axiom.

Problem 13. In how many ways can a 4-question true/false test be answered?

Problem 13 Solution

Step 1 — Identify the choices for each question:

Each of the 4 questions has 2 possible answers: True (T) or False (F).

Step 2 — Apply the multiplication axiom:

Since each question is independent, the total number of ways to answer the test is:

\[ 2 \times 2 \times 2 \times 2 = 2^4 = 16 \]

Answer: 16 possible ways to answer the test

Problem 14. In how many ways can three people be arranged to stand in a straight line?

Problem 14 Solution

Step 1 — Identify the choices for each position in the line: Three people are to be arranged in a line. We fill the positions one at a time.

Step 2 — Count the choices for each position:

First position: 3 choices (any of the 3 people)
Second position: 2 choices (either of the remaining 2 people)
Third position: 1 choice (the last remaining person)

Step 3 — Apply the multiplication axiom:

\[ 3 \times 2 \times 1 = 6 \]

Answer: 6 possible arrangements

Problem 15. A combination lock is opened by first turning to the left, then to the right, and then to the left again. If there are 30 digits on the dial, how many possible combinations are there?

Problem 15 Solution

Step 1 — Identify the choices for each turn:

The lock requires three turns: left, right, left. Each turn selects one of the 30 digits on the dial.

Step 2 — Count the choices for each turn:

First turn (left): 30 choices
Second turn (right): 30 choices
Third turn (left): 30 choices

There is no restriction stated that digits cannot be repeated, so each turn independently has 30 choices.

Step 3 — Apply the multiplication axiom:

\[ 30 \times 30 \times 30 = 30^3 = 27{,}000 \]

Answer: 27,000 possible combinations

Problem 16. How many different answers are possible for a multiple-choice test with 10 questions and five possible answers for each question?

Problem 16 Solution

Step 1 — Identify the choices for each question:

Each of the 10 questions has 5 possible answers (A, B, C, D, E).

Step 2 — Apply the multiplication axiom:

Since each question is independent, the total number of different answer sheets is:

\[ 5 \times 5 \times 5 \times 5 \times 5 \times 5 \times 5 \times 5 \times 5 \times 5 = 5^{10} = 9{,}765{,}625 \]

Answer: 9,765,625 different possible answer sheets

Problem 17. In the past, a college required students to use a 4-digit PIN (Personal Identification Number) as their password for its registration system. How many different PINs are possible if each must have 4 digits with no restrictions on selection or arrangement of the digits used?

Problem 17 Solution

Step 1 — Identify the choices for each digit:

A 4-digit PIN uses digits 0–9. There are no restrictions on selection or arrangement, meaning digits may be repeated.

Step 2 — Count the choices for each position:

Each of the 4 positions has 10 choices (digits 0 through 9).

Step 3 — Apply the multiplication axiom:

\[ 10 \times 10 \times 10 \times 10 = 10^4 = 10{,}000 \]

Answer: 10,000 different PINs are possible

Problem 18. The college decided that a more secure password system is needed. New passwords must have 3 numerical digits followed by 6 letters. There are no restrictions on the selection of the numerical digits. However, the letters I and O are not permitted. How many different passwords are possible?

Problem 18 Solution

Step 1 — Identify the structure of the password:

A password consists of 3 numerical digits followed by 6 letters. We must determine the number of choices for each position.

Step 2 — Count the choices for the digit positions:

Each of the 3 digit positions has 10 choices (0–9), with no restrictions:

\[ 10 \times 10 \times 10 = 10^3 = 1{,}000 \]

Step 3 — Count the choices for the letter positions:

The letters I and O are not permitted, so each letter position has $26 - 2 = 24$ choices. There are 6 letter positions, and there is no restriction on repetition:

\[ 24 \times 24 \times 24 \times 24 \times 24 \times 24 = 24^6 = 191{,}102{,}976 \]

Step 4 — Apply the multiplication axiom:

\[ 10^3 \times 24^6 = 1{,}000 \times 191{,}102{,}976 = 191{,}102{,}976{,}000 \]

Answer: 191,102,976,000 different passwords are possible