Lesson Explainer: Fundamental Counting Principle

In this explainer, we will learn how to find the number of all possible outcomes in a sample space using the fundamental counting principle.

Let us begin by learning how to use a tree diagram to determine the number of possible outcomes in a sample space with multiple events. Consider a situation where you are buying a new phone; you have two options for size: the 5-inch and the 6-inch models, and there are three color options: black, gold, and white. You would like to know how many options you have in total. One of the easiest ways to represent a situation like this is with a tree diagram. The tree diagram below shows the two options for phone size; then, below each of these we show the three options for color.

We could equally represent these options in a tree diagram where the first choice is the choice of color and the second is the choice of size, as shown below.

In both diagrams, there are 6 different total outcomes at the bottom of the tree diagrams, which means that there are 6 different combinations of these two events where the events are the selection of the size and of the color of the phone. Regardless of which feature of the phone (color or size) we choose first, we obtain the same number of total outcomes. In general, the order of events in a tree diagram does not change the number of total outcomes.

How To: Determining the Number of Possible Outcomes Using Tree Diagrams

To determine the number of possible outcomes resulting from multiple events, we can draw a tree diagram by following the steps listed below:

Choose the order of events. While a specific order of events does not change the number of outcomes in the end, there may be a natural chronological ordering of events in some occasions.
Draw one branch for each outcome of the first event originating from a single point at the top.
Originating from each outcome of the first event, draw a branch for each possible outcome of the second event considering the given outcome of the first event.
Continue down the tree until all events are accounted for.
Count the number of branches at the bottom of the tree diagram.

In our first example, we will draw a tree diagram to determine the number of possible outcomes from two events.

Example 1: Using Tree Diagrams to Determine the Number of Possible Outcomes

Bassem, Mariam, and Mona are playing a game where one of them needs to be a sheriff and one needs to be an outlaw. They each write their name on a piece of paper and place it in a bowl. If two names are picked at random where the first will be a sheriff and the second will be an outlaw, how many different ways are there?

Answer

In this example, we need to determine the number of possible outcomes from two different events. Recall that we can use a tree diagram to count the number of total possible outcomes when there are multiple events. In the given scenario, the two events are the selection of a sheriff and the selection of an outlaw. Since these selections are chronologically determined, the selection of a sheriff should be the first event.

To draw a tree diagram, we begin by drawing one branch for each possible outcome of the first event. We are first selecting a sheriff from Bassem, Mariam, and Mona, so these three individuals are three different outcomes of the first event. Hence, we have the following diagram for the first event.

Now, we can complete the tree diagram by drawing the branches corresponding to the second event, which is the selection of an outlaw. Since a sheriff cannot be an outlaw, each given outcome of the first event eliminates that name from the list of possible outlaws. For instance, if Bassem is selected to be the sheriff, only Mariam or Mona are the possible candidates to be an outlaw. To complete the tree diagram, we draw a branch for each possible outlaw corresponding to the selected sheriff.

The number of total outcomes is given by the number of branches at the bottom of a tree diagram. We can see that there are six branches at the bottom of the tree diagram, which tells us that there are six different outcomes of selecting a sheriff and an outlaw.

Hence, the number of different ways two names are picked at random where the first will be a sheriff and the second will be an outlaw is 6.

In the previous example, we determined the number of possible outcomes from two events using a tree diagram. While drawing a tree diagram is good for a conceptual organization of events, it is not practical when we have a larger number of outcomes. For example, it would be too time consuming to draw a tree diagram to find the number of possible outfits that can be made with 5 tops, 5 skirts, and 5 pairs of shoes. The fundamental counting principle gives a more efficient method in these situations.

If we consider what we are doing when we build a tree diagram, we will quickly see how we can generalize this to work with a larger number of options. For the phone example, we started by considering one of the choices, say the size of the phone. For the size, we have two options: 5 inches and 6 inches. For each of these two options we can choose one of the three colors: black, gold, and white. Hence, we can find the total number of possibilities from the two events by multiplying the number of outcomes for each event, which leads to . This method for finding the number of possible outcomes is the fundamental counting principle, also known as the multiplication rule.

Theorem: The Fundamental Counting Principle for Two Events

If we have two independent events and such that the number of possible outcomes for event is and the number of possible outcomes for event is , the total number of distinct possible outcomes of these two events together is the product .

Here, two events are independent when a specific outcome of one event does not change the number of possible outcomes of the other event.

To understand when two events are independent, let us return to our phone example. We can see from the first tree diagram that, whichever size of phone we choose, there are 3 different colors available to choose from. In other words, the outcome of the first event, which is the selection of the size, does not change the number of outcomes in the second event, which is the selection of the color. This tells us that the two events are independent; hence, we can apply the fundamental counting principle to determine the number of total possible outcomes. Since there are 2 possible outcomes of the first event and 3 possible outcomes of the second event, the number of total possible outcomes from the two events is given by , as expected.

Let us change the context of choosing phones slightly so that pink phones are now exclusively available for 6-inch models, leading to the following tree diagram.

We can see that there are 3 colors available if we choose to buy a 5-inch phone, while 4 colors are available if we choose to buy a 6-inch phone. This means that a specific outcome of the first event, choosing the size of the phone, changes the number of possible outcomes for the second event, choosing the color of the phone. Hence, these two events are not independent when we consider the exclusive 6-inch pink phone. In such cases, we cannot use the fundamental counting principle to determine the number of possible outcomes. However, we can still use a tree diagram to find the number of possible outcomes. From the tree diagram above, we can see that there are 7 branches at the bottom of the tree diagram, which tells us that there are 7 different options for buying a phone in this case.

In the next example, we will determine the number of possible outcomes involving two independent events using the fundamental counting principle.

Example 2: Application of the Fundamental Counting Principle

A cafe offers a choice of 20 meals and 9 beverages. In how many different ways can a person choose a meal and a beverage?

Answer

In this example, we need to determine the number of different ways to choose a meal and a beverage. We can consider the selection of a meal and a beverage to be two separate events. Then, we want to determine the number of possible outcomes in a sample space with two events. Recall that the fundamental counting principle states that the number of possible outcomes from two independent events is given by the product of the number of outcomes from each event.

Before we can apply the fundamental counting principle, we need to know that the two events are independent. We know that two events are independent when a specific outcome of one event does not change the number of possible outcomes of the other event. We can see that, whichever meal a person chooses, there are always 9 beverages that can be selected. In other words, a specific outcome of the first event, choosing a meal, does not change the number of possible outcomes of the second event, choosing a beverage. Hence, the two events are independent.

Since we found that the two events are independent, we can determine the number of total possible outcomes by using the fundamental counting principle. The numbers of outcomes from the two events are 20 and 9 respectively. This means that the number of total possible outcomes from the two events is

Thus, there are 180 different ways a person can choose a meal and a beverage.

In the previous example, we determined the number of possible outcomes from two events using the fundamental counting principle. In this case, we can see that drawing a tree diagram for 20 meals and 9 beverages would be too time consuming. The fundamental counting principle is an efficient method for such counting scenarios.

We can also use the fundamental counting principle to determine the number of possible outcomes when more than two independent events are involved. When we have more than two events, we say that the events are independent if any pair of different events from the collection are independent. For this reason, we sometimes use the term pairwise independent when more than two events are involved.

Theorem: The Fundamental Counting Principle for More Than Two Events

Let be events that are pairwise independent, such that the number of possible outcomes for event is for each . Then, the total number of distinct possible outcomes of these events together is the product .

Here, a collection of events is pairwise independent when any pair of different events from the collection are independent.

In short, the fundamental counting principle tells us that the number of total possible outcomes in a sample space with multiple events is given by the product of individual events, as long as the events are pairwise independent. We can check whether the events are pairwise independent by considering whether or not a specific outcome of one event changes the number of possible outcomes from any other event.

In our next example, we will determine the number of possible outcomes in a sample space with three events by using the fundamental counting principle.

Example 3: Application of the Fundamental Counting Principle

A restaurant serves 2 types of pie, 4 types of salad, and 3 types of drink. How many different meals can the restaurant offer if a meal includes one pie, one salad, and one drink?

Answer

In this example, we need to determine the number of different meals containing one pie, one salad, and one drink. We can consider the selection of a pie, a salad, and a drink to be three separate events, in which case we want to determine the number of possible outcomes in a sample space with three events. Recall that the fundamental counting principle states that the number of possible outcomes from multiple events is given by the product of the number of outcomes from each event, as long as the events are pairwise independent.

We can check whether the events are pairwise independent by considering whether or not a specific outcome of one event changes the number of possible outcomes from any other event. We can see that choosing a specific type of pie does not change the number of possible choices for the other items, which are a salad or a drink. The same can be said for a specific choice of a salad or a drink. This tells us that the three events are pairwise independent.

Since we found that the events are pairwise independent, we can determine the number of total possible outcomes by using the fundamental counting principle. The numbers of outcomes from the three events are 2, 4, and 3 respectively. This means that the number of total possible outcomes from the three events is

Hence, there are 24 different meals in the restaurant including one pie, one salad, and one drink.

We can also use the fundamental counting principle, or multiplication rule, to solve counting problems with replacement, which is a real-world problem where we need to determine the number of different ways to select an object times from a collection where the selected object is replaced each time before the next selection. A counting problem with replacement can be viewed as the problem of finding the number of possible outcomes in a sample space with pairwise-independent events where each event has the same number of outcomes as the others.

If the collection has different outcomes, each of the events has outcomes. Applying the fundamental counting principle gives that the number of total possible outcomes in this scenario is

Theorem: Counting with Replacements

The number of different ways to select an object times from a collection of different objects with replacement is .

In the next example, we will solve a counting problem with replacement.

Example 4: Applications of the Counting Principle with Replacement

In how many ways can a 5-digit code be formed using the numbers 1 to 9?

Note, the code can have repeated digits.

Answer

In this example, we need to find the number of different 5-digit codes from a collection of 9 distinct digits, where repetition of digits is permitted. We can think of this problem as choosing a digit 5 times from 9 different digits, where each selected digit is replaced before the next selection.

Recall that the number of different ways to select an object times from a collection of different objects with replacement is . We can substitute and to obtain

Hence, there are 59‎ ‎049 different ways to form a 5-digit code from the numbers 1 to 9, where repeated digits are allowed.

In the next example, we will find the number of different outcomes in a sample space consisting of two different counting events with replacement.

Example 5: Applications of the Counting Principle with Replacement

Use the fundamental counting principle to determine the total number of outcomes of choosing (with the possibility of repetition) a password that begins with three letters followed by three numbers from 1 to 7. Assume the password can only contain lowercase letters.

Answer

In this example, we need to determine the number of different passwords beginning with three lowercase letters followed by three numbers from 1 to 7. We can consider the selection of the first three letters and the last three digits to be two separate events. Then, we want to determine the number of possible outcomes in a sample space with two events. Recall that the fundamental counting principle states that the number of possible outcomes from two independent events is given by the product of the number of outcomes from each event.

We know that two events are independent when a specific outcome of one event does not change the number of possible outcomes of the other event. We can see that a specific choice of the first three letters does not influence the selection of the last three digits of the password. Hence, the two events are independent, which means that we can determine the number of total possible outcomes by using the fundamental counting principle.

Let us find the number of possible outcomes from each of the events, starting with the selection of the first three letters. To choose the first three letters, we need to select a letter from a collection of 26 letters three times. This is a counting problem with replacement, where a selected object is replaced each time before the selection of the next object. Recall that the number of different ways to select an object times from a collection of different objects with replacement is . Substituting and gives us

Thus, there are 17‎ ‎576 different ways to form the first three letters.

Next, let us find the number of ways to select the last three digits from 1 to 7. We can substitute and into the formula for a counting problem with replacement to obtain

Thus, there are 343 different ways to form the last three digits.

Finally, we can apply the fundamental counting principle to obtain the total number of passwords:

Hence, there are a 6‎ ‎028‎ ‎568 different passwords beginning with three lowercase letters followed by three numbers from 1 to 7.

Let us finish by recapping a few important concepts from this explainer.

Key Points

When the number of outcomes is small enough to be counted by hand, we can determine the number of possible outcomes resulting from multiple events using a tree diagram by following the steps listed below:
- Choose the order of events. While a specific order of events does not change the number of outcomes in the end, there may be a natural chronological ordering of events in some occasions.
- Draw one branch for each outcome of the first event originating from a single point at the top.
- Originating from each outcome of the first event, draw a branch for each possible outcome of the second event considering the given outcome of the first event.
- Continue down the tree until all events are accounted for.
- Count the number of branches at the bottom of the tree diagram.
If we have two independent events and such that the number of possible outcomes for event is and the number of possible outcomes for event is , the total number of distinct possible outcomes of these two events together is the product .
Here, two events are independent when a specific outcome of one event does not change the number of possible outcomes of the other event.
Let be events that are pairwise independent, such that the number of possible outcomes for event is for each . Then, the total number of distinct possible outcomes of these events together is the product .
Here, a collection of events is pairwise independent when any pair of different events from the collection are independent.
The number of different ways to select an object times from a collection of different objects with replacement is .