Explainer: Counting Outcomes with Restrictions

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 10=1,000. 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 10Γ—9Γ—8=720. 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:

  1. with replacement: where the number of items we are choosing form 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 π‘šοŠ.
  2. 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 π‘šβˆ’1 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 π‘šΓ—(π‘šβˆ’1)Γ—(π‘šβˆ’2)Γ—β‹―Γ—(π‘šβˆ’(π‘›βˆ’1)).

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 4Γ—3=12.

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 number again so we only have three possible choices. Hence, by the fundamental counting principle, we have a total of 4Γ—3=12 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 10=1,000,000,000.

The previous example demonstrates the general approach to solving counting problems with restrictions.

How to: Solve 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:

  1. Count the number of possible outcomes for the restricted items.
  2. Count the number of possible outcomes for the remaining nonrestricted items.
  3. 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 {7,1,9}?

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 number left for the final digit.

Hence, by the fundamental counting principle, the total number of numbers we can form is 2Γ—2Γ—1=4.

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 1,2,3,4,5,6,7,8?

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 4Γ—7Γ—6=168.

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, Matthew and Benjamin do not want to sit next to each other. How many ways can the children sit in the five seats so that Matthew and Benjamin are not sitting next to each other?

Answer

We begin by considering the restriction. Since Matthew and Benjamin 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 Benjamin’s seat; if he sits in the first seat, Matthew could sit in any of the last three seat. So there are three options if Benjamin is in the first seat.

If Benjamin is in the second seat. Matthew can only be in one of the two end seats. Hence, there are only two options if Benjamin sits in the second seat.

If Benjamin sits in the middle seat, Matthew can sit in either of the end seats, so there are two options in this case.