In this explainer, we will learn how to count the number of possible outcomes when we have restrictions.
The fundamental counting principle is really useful for counting the number of outcomes when we have independent events.
Definition: The Fundamental Counting Principle
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 .
In this explainer, we would like to consider the cases where the outcome of one event affects the outcomes of other events and where we have events with restrictions. In these cases, we can still apply the fundamental counting principle. However, we might need to analyze the problem carefully to state the number of possible outcomes of each event.
Imagine we have to pick a three-digit pin number; if there are no restrictions on the type of number we can pick, the fundamental counting principle tells us that the total number of possible choices is . However, what would the total number of possible outcomes be if we were restricted to not using any repeat digits (which is equivalent to enforcing that each digit be unique)? In this case, the choice of the first digit reduces the number of possible choices for the second, and the choice of the second digit reduces the number of possible choices for the third. In particular, we have 10 choices for the first digit, 9 for the second, and 8 for the third. At this point, we can apply the fundamental counting principle and find that the total number of possible outcomes is . These two scenarios are so common that we distinguish them with the following terminology.
Definition: Counting with and without Replacement
When picking items from a collection of items, there are two different possible methods:
- with replacement: where the number of items we are choosing from remains fixed. Hence, each time we pick a new item, there are choices. It is as if, each time we choose an item, we replace it with an identical copy. In this case, the total number of possible outcomes is .
- without replacement: where the number of items we are choosing from reduces each time we pick an item. Hence, we have choices for our first pick and for our second. It is as if we are choosing marbles from a bag without returning them. In this case, the number of items we are picking needs to be less than or equal to the total number of items and the total number of possible outcomes is .
Example 1: Counting without Replacement
Find the number of ways to form a 2-digit number, with no repeated digits, given 4 different nonzero digits to choose from.
Answer
We are choosing 2 digits from a collection of 4 distinct digits. Since we are not allowed any repeated digits, we are counting without replacement. Therefore, the total number of possible outcomes is .
An alternative way to think about this is that, for the first digit, we have 4 possible choices. Then, once we have selected this digit, we choose the second. For the second, we cannot pick the same digit again so we only have three possible choices. Hence, by the fundamental counting principle, we have a total of distinct ways to form the two-digit number.
We will now consider a different way that our choices could be restricted by means of a simple example.
Example 2: Counting Outcomes with Restrictions
Phone numbers on a particular network are twelve digits long, where the first three digits are always 072. Calculate the total number of different phone numbers which the network can use.
Answer
We are told that all the phone number are twelve digits long. However, there is a restriction on the first three digits. In particular, the first three digits must be 072. Therefore, for these three digits, we actually have no choices to make. Hence, we only need to consider the possibilities of the remaining nine digits. For each of these digits, there are ten options. Hence, by the fundamental counting principle, the total number of possible phone numbers will be .
The previous example demonstrates the general approach to solving counting problems with restrictions.
How To: Solving Counting Problems with Restrictions
When faced with counting problems with restrictions, it is usually best to start with the most restricted outcomes. The general method we follow is as follows:
- Count the number of possible outcomes for the restricted items.
- Count the number of possible outcomes for the remaining nonrestricted items.
- Find their product, which by the fundamental counting principle will be the total number of possible outcomes.
We will now look at a number of examples where we apply this technique.
Example 3: Counting without Replacement with Restricted Outcomes
How many three-digit numbers, which are less than 900 and have no repeated digits, can be formed using the elements of the set ?
Answer
We begin by considering how the restriction affects the number of possible outcomes. We are told that the number must be less than 900. This means that the first digit cannot be a nine. Hence, there are two possible choices for the first digit: 7 or 1.
Once we have chosen this digit, since we are choosing without replacement, we have two choices left for the second digit, and then there is only one choice left for the final digit.
Hence, by the fundamental counting principle, the total number of numbers we can form is .
Example 4: Counting with Restrictions
In how many ways can a three-digit number, starting with an even digit and containing no repeated digits, be formed from the numbers ?
Answer
We begin by considering the number of possible options for the restricted digit. We are told that the first digit needs to be an even digit. The collection of numbers we have been given contains four even digits: 2, 4, 6, and 8.
Since we are counting without replacement, after choosing the first digit, we have 7 options for the second digit and 6 options for the third digit.
Hence, by the fundamental counting principle, the total number of numbers we can form is .
Let’s consider a real-world example of a counting problem with multiple restrictions.
Example 5: Counting with Multiple Restrictions
Five children need to sit at the back of a coach. There are five seats next to one another. However, Sameh and Nader do not want to sit next to each other. How many ways can the children sit in the five seats so that Sameh and Nader are not sitting next to each other?
Answer
We begin by considering the restriction. Since Sameh and Nader do not want to sit next to each other, we need to consider all the possible arrangements for the two of them whereby they are not next to each other. We start by picking Nader’s seat; if he sits in the first seat, Sameh could sit in any of the last three seat. So there are three options if Nader is in the first seat.
If Nader is in the second seat. Sameh can only be in one of the two end seats. Hence, there are only two options if Nader sits in the second seat.
If Nader sits in the middle seat, Sameh can sit in either of the end seats, so there are two options in this case.
If Nader sits in the fourth seat, Sameh could sit in either of the first two seats. Hence, there are two options if Nader is in the fourth seat. Notice that this is the same scenario as when Nader sat in the second seat.
Finally, Nader could sit in the last seat, which leaves Sameh the option of any of the first three seats. Hence, there are three options if Nader sits in the last seat.
Hence, the total number of options for Sameh and Nader is the sum of these options: .
In all cases, there are three seats left and three children to sit in them. Since we are counting without replacement, the total number of ways the remaining three children can fill the last three seats is . Hence, by the fundamental counting principle, the total number of ways the children can sit in the five seats such that Sameh and Nader are not sat next to each other is .
An alternative way to calculate this is to consider the total number of ways that the children could sit in the seats and the number of ways that they could sit in the seats so that Sameh and Nader are next to each other and then take the difference. We will demonstrate this method too.
First, we calculate the total number of ways the children could sit in the seats. Since we are counting without replacement, the total number of outcomes will be given by . We now consider the configurations in which Sameh and Nader are sat next to each other. There are four options for two people to be sat next to each other.
For each of these four options, there are two options for Sameh and Nader: either Sameh on the left of Nader or Nader on the left of Sameh. Hence, the total number of options for Sameh and Nader to be sat next to each other is . Then, the three seats can be filled by the remaining children; the number of options for these children is . Hence, the total number of options for Sameh and Nader to be sat next to each other is . Finally, we can calculate the total number of ways that the children can sit in the seat such that Sameh and Nader are not sat next to each other by subtracting this number from the total number of possibilities as follows: .
As we have seen, there are often multiple ways to calculate the number of options. Growing in confidence using different methods will significantly help.
We finish with one more involved example to demonstrate how we can apply this technique even to fairly complex scenarios.
Example 6: Counting with Multiple Restrictions
Rania and Adam are planning their wedding. They are working on the seating plan for the top table at the reception. Their top table is a straight table with 8 seats down one side. It needs to sit the bride and groom, the bride’s parents, the groom’s parents, the best man, and the maid of honor. Given that all couples need to sit next to each other and that the best man and maid of honor are not a couple, how many different options are there for seating everyone on the top table?
Answer
We begin by considering the most restricted options: the three couples that need to be sat together. We will first consider the number of options whereby we could seat the three couples. Considering the couples as a unit, we can consider arranging three items in three spaces. This is counting without replacement; therefore, the number of options is . However, for each couple, there are two ways they could sit next to each other. Therefore, for each of these six options, there are ways the couples could choose to sit. Therefore, the total number of possibilities is . Finally, we can consider the best man and maid of honor. Starting with the best man, he could be placed at either end between any pair of couples.
Hence, there are four options of chair for him. Finally the maid of honor could be placed at either end of between any of the couple–couple or couple–best man pairs.
Hence, there are five options for the maid of honor. Hence, by the fundamental counting principle, the total number of layouts for the top table is .
An alternative way to look at this problem is to first ignore the arrangement of the couples and simply state that there are five groups (three couples and two individuals) which we need to arrange in five places. The number of possibilities for this is . Now we can consider the arrangement of the couples: for each couple, there are two possible arrangements giving a total of arrangements for the couples. Hence, by the fundamental counting principle, the total number of layouts for the top table is .
Let’s recap a few important concepts from this explainer.
Key Points
- We can extend the use of the fundamental counting principle to scenarios where there are different restrictions on the possible outcomes.
- When counting with replacement, the total number of outcomes from repeated events of choosing from items is given by .
- When counting without replacement, the total number of outcomes of choosing items from a collection of items is given by .
- When counting outcomes with restrictions, we should start from the most restricted and work our way to the least restricted.
- Using these techniques, we are able to tackle relatively complex scenarios.
