Math Core

To find a probability, you need to know how many outcomes there are. Listing them works when there are only a few, but a $4$ -digit phone passcode has thousands of possibilities. In this lesson you'll learn to count outcomes without listing every one, using tree diagrams and a single multiplication rule.

Tree diagrams

A tree diagram shows every outcome of a process that happens in stages. Each stage branches into all of its possible choices, and each complete path is one outcome.

Worked example: Building a sandwich

A deli offers $3$ breads (white, wheat, rye) and $4$ fillings (turkey, ham, tuna, veggie). How many different sandwiches with one bread and one filling are possible?

Branch on the bread first, then on the filling.

White: turkey, ham, tuna, veggie
Wheat: turkey, ham, tuna, veggie
Rye: turkey, ham, tuna, veggie

Each of the $3$ breads has $4$ branches, so there are $3 \times 4 = 12$ sandwiches.

The tree shows why multiplying works: every choice at the first stage gets the same number of branches at the next stage.

The Fundamental Counting Principle

Fundamental Counting Principle

If one choice can be made in $m$ ways and a second choice can then be made in $n$ ways, the two choices together can be made in $m \times n$ ways. For more stages, keep multiplying: $m \times n \times p \times \dots$

This saves a lot of drawing. A lunch special with $3$ breads, $4$ fillings and $5$ drinks has $3 \times 4 \times 5 = 60$ possible meals, and you don't need to draw $60$ branches.

Worked example: Locker codes

A locker code uses $3$ digits, each from $0$ to $9$ .

How many codes are possible if digits can repeat?
How many codes are possible if no digit can be used twice?

Solutions.

Each of the three positions has $10$ choices: $10 \times 10 \times 10 = 1{,}000$ codes.
The first digit has $10$ choices. Once it's used, the second has only $9$ , and the third has $8$ : $10 \times 9 \times 8 = 720$ codes.

Common mistake

Read carefully to see whether choices can repeat. If they can, every stage has the same number of choices. If they can't, the number of choices drops by one at each stage.

Arrangements

An arrangement puts items in order. Because each item can be used only once, the choices shrink at each step.

Worked example: Books on a shelf and a race

In how many ways can you arrange $5$ different books on a shelf?
Eight runners are in a race. In how many ways can first, second and third place be awarded?

Solutions.

There are $5$ choices for the first spot, then $4$ , then $3$ , then $2$ , then $1$ : $5 \times 4 \times 3 \times 2 \times 1 = 120$ ways.
There are $8$ choices for first place, $7$ for second and $6$ for third: $8 \times 7 \times 6 = 336$ ways.

A product like $5 \times 4 \times 3 \times 2 \times 1$ is written $5!$ and read " $5$ factorial." In general, $n!$ is the number of ways to arrange $n$ different items in a row.

Definition

Factorial

For a whole number $n \ge 1$ , $n! = n \times (n - 1) \times \dots \times 2 \times 1$ . For example, $4! = 4 \times 3 \times 2 \times 1 = 24$ .

Counting to find probability

Once you can count outcomes, probability follows: favorable outcomes over total outcomes.

Worked example: A random arrangement

The letters A, B, C and D are placed in a random order. What is the probability that they end up in alphabetical order?

There are $4! = 24$ possible orders, and only one of them is ABCD. The probability is $\dfrac{1}{24}$ .

What is the probability that the arrangement starts with A? If A is fixed in the first spot, the other $3$ letters can be arranged in $3! = 6$ ways. So the probability is $\dfrac{6}{24} = \dfrac{1}{4}$ , which makes sense: each of the $4$ letters is equally likely to come first.

Tip

When a stage has a restriction (like "the code must be odd" or "the first digit can't be $0$ "), fill in that stage first, then count the others.

Practice

Practice 1

Jordan has $4$ shirts and $3$ pairs of pants. How many different outfits of one shirt and one pair of pants can he make?