Type 1 - Arrangement with Repetition¶
In this section, we present some tasks involving arrangement with repetition problems. In our 2x2 grid, this is the cell in which unrestricted repetition is allowed, and we are counting ordered outcomes (or arrangements). In problems like these, we can employ multi-stage processes, where we have the same number of options at each stage because repetition is allowed.
For instance, consider the following problem:
1. "How many length 5 binary strings are there?"
Here, we have five positions, and we can employ a five-stage process where we consider the number of options at each position. Since there are 2 options (0 or 1) at each position no matter the choice of any previous position, we use the multiplication principle to yield \(2 \cdot 2 \cdot 2 \cdot 2 \cdot 2 = 2^5 = 32\) total outcomes.
Below is some code that generates all of the outcomes. Notice the nature of the outcomes themselves - repetition is allowed (something like 0 0 0 0 0 is a valid outcome), and we are counting ordered outcomes (outcomes like 1 0 0 0 0 and 0 0 0 0 1 are listed as distinct outcomes).
Active Code 1¶
Now, answer the following questions about these outcomes You can use this analysis tool to answer them.
Quick Check 1.1¶
- 16 outcomes start with 01
- Incorrect.
- 4 outcomes start with 01
- Incorrect.
- 8 outcomes start with 01
- Correct. 8 outcomes start with 01, as there are 8 possible outcomes for the remaining three positions once 0 and 1 are in the first positions.
Q-1: How many outcomes start with 01?
Quick Check 1.2¶
- 10101
- Incorrect. 10101 is the 22nd outcome in the list.
- 10110
- Correct. 10110 is the 23rd outcome in the list.
- 11111
- Incorrect. 11111 is the 32nd outcome in the list.
- 10111
- Incorrect. 10111 is the 24th outcome in the list.
Q-2: Following the process that the code represents, what is the 23rd outcome in the list?
Let’s look at a couple more examples.
2. There are 12 people competing for three different prizes. The same person
can win multiple prizes, but ties are not allowed. How many possible outcomes are
there for how the 3 prizes can be distributed to the 12 people?
Note we can think of a three-stage process, where we give out a first, second, and third prize. For each stage, any of the 12 people can win, no matter who was picked previously. Thus, there are 12 choices for each of the three prizes, so our answer is \(12 \cdot 12 \cdot 12 = 12^3 = 1728\).
Solve the Parson’s problem below to create code that produces all the outcomes for this problem.
Arrange the lines below to create code to print all the possible outcomes for distributing 3 prizes to 12 people.
Now answer the following questions about this code.
Quick Check 2.1¶
- Person A and Person G do not receive prizes
- Incorrect.
- Person A receives the first prize and the third prize, and Person G receives the second prize
- Correct. The each term in the output shows who received each respective prize. Because people can receive multiple prizes, here A won two prizes (first and third) and G won the second prize.
- Person A receives the first prize, and Person G receives the second and third prizes
- Incorrect.
Q-4: What does the outcome AGA represent in the context of the problem?
Now, let’s consider the following problem:
3. I am going to roll a 6-sided dice four consecutive times. How many
possible outcomes are there for that sequence of four rolls?
Quick Check 3.1¶
- 4
- Incorrect. We are rolling four times, but there are 6 options for what can occur on each roll.
- 24
- Incorrect.
- 10
- Incorrect.
- 6
- Correct. There are 6 options for what will come up on a given roll, one for each face of the dice.
Q-5: If you were to write code to produce outcomes, how many elements would you have in your starting column?
Quick Check 3.2¶
- 6
- Incorrect. You have six options per roll, but you are rolling the dice four times.
- 4
- Correct. You are rolling four times, and each roll represents a stage in the counting process.
- 10
- Incorrect.
- 24
- Incorrect.
Q-6: If you were to write code to produce outcomes, how many columns would you have?
Quick Check 3.3¶
- 6 * 6 * 6 * 6
- Correct. Each time you flip, you have 6 possible outcomes (no matter what was rolled previously); as you are rolling 4 times, using the multiplication principle we yield 6*6*6*6.
- 4 * 4 * 4 * 4 * 4 * 4
- Incorrect.
- 6 * 4
- Incorrect.
- 6 + 6 + 6 + 6
- Incorrect.
Q-7: Which of the following is a mathematical expression that gives the total number of outcomes?
If you want more practice and want to check your work, in the space below, write code that generates all possible outcomes for rolling a 6-sided dice four consecutive times.
Active Code¶
Now, consider a couple of variations on this problem.
4. Suppose now I want to roll a 6-sided dice 8 consecutive times. What
is a mathematical expression for the number of outcomes?
Quick Check 4.1¶
- 6 + 6 + 6 + 6 + 6 + 6 + 6 + 6
- Incorrect.
- 8 * 8 * 8 * 8
- Incorrect.
- 6 ^ 8
- Correct. There are eight dice rolls, each of which has 6 options; using the multiplication principle we get 6*6*6*6*6*6*6*6 = 6^8.
- 8 * 8 * 8 * 8 * 8 * 8
- Incorrect.
Q-8: Which of the following is a mathematical expression that gives the total number of outcomes for this problem?
5. How many outcomes are there for rolling a 4-sided dice six consecutive
times? What is a mathematical expression for the number of outcomes?
Quick Check 5.1¶
- 6 + 6 + 6 + 6
- Incorrect.
- 4 * 4 * 4 * 4 * 4 * 4
- Correct. We roll the dice six times, and there are four options at each stage in the process.
- 6 ^ 4
- Incorrect
- 4 + 4 + 4 + 4 + 4 + 4
- Incorrect.
Q-9: Which of the following is a mathematical expression that gives the total number of outcomes for this problem?
6. How many outcomes are there for rolling a 20-sided dice three times? Remix
code from above to write code that would generate all possible outcomes. Then,
select the correct answer in the multiple choice problem below.
Active Code 4¶
- 20 + 20 + 20 + 20
- Incorrect.
- 3^20
- Incorrect.
- 20^3
- Correct. We roll the dice 3 times, and there are 20 options at each stage in the process.
- 3*20
- Incorrect.
Q-10: Which of the following is a mathematical expression that gives the total number of outcomes for this problem?
General formula for Arrangements with Repetition¶
We now discuss a general formula for these kinds of problems.
Notice that there is a commonality among the mathematical expressions that solve this particular kind of problem. In general, if we have \(n\) distinct objects, and we are arranging \(r\) of them, where repetition is allowed, there are \(n^r\) total outcomes.
To see why this works, note that if we are arranging \(r\) elements, we can think of \(r\) stages in our counting process, and at each stage we consider how many options there are at that stage. Since repetition is allowed, we have \(n\) options at each stage. These are independent choices at each stage, and using the multiplication principle, we multiply \(n\) together \(r\) times, giving us \(n^r\).
In terms of coding problems like this, notice that we can have \(n\) elements in our initial list, and we can have \(r\) nested for loops cycling through these elements without restriction. These correspond to the \(r\) stages in our counting process, where at each stage we are cycling through all \(n\) options in our list.
7. How many different license plate are there that consist of three letters,
followed by three numbers?
Solve the following Parson’s Problem for this question.
Coordinating multiple applications of this formula¶
As is often the case, most problems will not be only a direct application of this formula, \(n^r\), but rather they will involve or incorporate it in some way into a broader problem. Here we offer some examples of how this formula might arise or be used in problems.
7. How many different license plates involving three letters and three digits
are there if the three letters appear together, either at the beginning or the end of the license plate?
Notice here that there are two cases, each of which involves our formula. In both cases we are considering 26 options for each letter and 10 options for each digit; the multiplication principle applies in each case.
In one case, the three letters are at the beginning of the license plate. Then there are \(26 \cdot 26 \cdot 26 \cdot 10 \cdot 10 \cdot 10\) or \(26^3 \cdot 10^3 = 17,576,000\) total license plates.
In the other case, the three letters are at the end of the license plate. Then there are \(10 \cdot 10 \cdot 10 \cdot 26 \cdot 26 \cdot 26\) or \(10^3 \cdot 26^3 = 17,576,000\) total license plates.
These are distinct cases, so we can add the total together, so our total number of license plates is \(26^3 \cdot 10^3 + 10^3 \cdot 26^3 = 35,152,000\).
Solve the following Parson’s Problem for this question.
Now let’s try another problem.
8. At my bank, a PIN consists of 4 digits (from 0 to 4). How many PINs
are there with no consecutive digits?
Note, here, we can apply our formula. We can think of a 4-stage process, where in each stage we consider the number of options for each respective digit (first, second, third, and fourth). In the first stage we can choose any number, so there are 5 options. In the second stage, we can choose any number except what was chosen first, so there are 4 options. In the third stage, we can choose any number except what was chosen directly previously, so again there are 4 options. In the fourth stage, again we have 4 options.
So, our final answer is \(5 \cdot 4^3 = 320\).
Run the code and examine the output.
Active Code 5¶
Quick Check 8.1¶
- It makes sure the second digit is not the same as the first digit.
- Incorrect.
- It makes sure the third digit is not the same as the first digit.
- Incorrect.
- It makes sure the third digit is not the same as the second digit.
- Correct. All we need for this problem to ensure non-consecutivity is to have each digit not be equal to the digit directly preceding it.
- It makes sure the third digit is not the same as either of the first two digits.
- Incorrect.
Q-13: What does the statement “minus item2” accomplish?