Video: Properties of Permutations

Video Transcript

In this video, we will learn how to use properties of permutations to simplify expressions and solve equations involving permutations. First, let’s consider what we know about permutations. A permutation is an arrangement of a collection of items where order matters and repetition is not allowed. So we say permutations represent counting without replacement in which order matters.

We calculate the number of possible permutations for a collection of items with the formula 𝑛P𝑟 equals 𝑛 factorial over 𝑛 minus 𝑟 factorial. This is the number of ways we select 𝑟 elements from a collection of 𝑛 elements. For example, if we have four P two, we have a collection of four objects, and we want to know how many different ways we can select just two of the objects. If in our box we have four letters and we’re going to choose two randomly, there would be 12 different sets of two, 12 different permutations.

Notice here since we’re dealing with permutation and order does matter, 𝐴𝐵 is not the same ordering as 𝐵𝐴, which means we get 12 different ways of choosing two out of four. If we wanna see this with our formula, that would be four factorial over four minus two factorial, four factorial over two factorial, and we expand that to be four times three times two times one over two times one. The two times one in the numerator and the denominator cancel out, and we get four times three, which is 12.

Before we move on, we should say that there are quite a few different notations for permutations. The one we’ll primarily use looks like this, 𝑛P𝑟. But you might also see it written like this where 𝑛 is a superscript and 𝑟 is a subscript. P𝑛𝑟 can also mean this where the 𝑛 and the 𝑟 are on the same side or P𝑛,𝑟 or even P open parentheses 𝑛, 𝑟 closed parentheses.

Now we’ll move on and look at properties that all permutations share. We use these properties to solve different types of equations. The first property we’ll consider looks like this. For a permutation 𝑛P𝑟, it will be equal to 𝑛 times the permutation of 𝑛 minus one 𝑟 minus one. Let’s consider this for six P three. According to this property, six P three will be equal to six times the permutation of five choose two. Six P three will be equal to six factorial over six minus three factorial. And the other side of the equation will be six times five factorial over five minus two factorial.

If we do a bit of simplifying and then expand the factorials, on both sides of the equation, three factorial in the numerator and the denominator cancel out, leaving us with six times five times four on the left and six times five times four on the right, which will be equal to one another, which shows us that 𝑛P𝑟 is equal to 𝑛 times 𝑛 minus one P𝑟 minus one.

Another property we want to consider has to do with 𝑛 factorial. 𝑛 factorial plays a big role in permutations, and 𝑛 factorial is equal to 𝑛 times 𝑛 minus one factorial. We use this property very often to simplify expressions that have factorials in the numerator and the denominator. We could say four factorial is equal to four times four minus one factorial, which is four times three factorial. By expanding both sides of the equation, we get four times three times two times one equals four times three times two times one.

And there might be times when we want to even further extend this property. 𝑛 factorial is equal to 𝑛 times 𝑛 minus one times 𝑛 minus two factorial. Using our example of four, that’s four factorial is equal to four times three times two factorial. Using this property of factorials, we can show that zero factorial equals one. Since we know that 𝑛 factorial equals 𝑛 times 𝑛 minus one factorial, one factorial will be equal to one times one minus one factorial. One factorial equals one times zero factorial. Then zero factorial must be equal to one, which means we’ll need to remember that both zero factorial and one factorial are equal to one.

We wanna develop fluency and using the definition of permutation and its properties along with these factorials, using all of that we’ll be able to solve equations involving permutations. So let’s consider some examples.

Solve the following equation for 𝑟: five P𝑟 is equal to 120.

We know that we calculate 𝑛P𝑟 by taking 𝑛 factorial over 𝑛 minus 𝑟 factorial. In this case, we don’t know the 𝑟-value. We know that our set has five elements, but we don’t know how many we’re trying to choose. To find 𝑟, we need to find out how many decreasing consecutive integers, starting with five, we should multiply together to equal 120. We know that 𝑛 factorial is equal to 𝑛 times 𝑛 minus one factorial. Five P𝑟 is then equal to five factorial over five minus 𝑟 factorial. If we expand the factorial in the numerator, we get five times four times three times two times one. And we know that five P𝑟 must be equal to 120, but five factorial equals 120. So we end up with the equation 120 equals 120 over five minus 𝑟 factorial.

If we multiply both sides of the equation by five minus 𝑟 factorial, we get 120 times five minus 𝑟 factorial equals 120. And then if we divide both sides by 120, on the left, we have five minus 𝑟 factorial, and on the right, 120 divided by 120 equals one. This means we need an 𝑟-value that will make five minus 𝑟 factorial equal to one. Based on the properties of factorials, we know that there are two places where a factorial equals one, zero factorial and one factorial, which means five minus 𝑟 must be zero or five minus 𝑟 must be one. If five minus 𝑟 is zero, then 𝑟 equals five. And if five minus 𝑟 is one, then 𝑟 equals four.

Remember, at the beginning, we said that 𝑟 would be equal to the number of decreasing consecutive integers beginning with five we multiply together to get 120. And so there is one other strategy we can use when we know the 𝑛-value of a permutation but we don’t know the 𝑟-value. We know the number of permutations we can have is 120. And we know that we are beginning with a set of five. If we start by dividing 120 by five, we get 24. Now we take 24 and we divide by the consecutive integer below five. So 24 divided by four equals six.

Again, we’ll take that value and divide it by the integer that is below four. So six divided by three equals two. Two divided by the integer below three, which is two, equals one, which shows us that 𝑟 could equal four, that four consecutive decreasing integers beginning with five multiply together to equal 120. Two times three times four times five does equal 120. However, we could follow the pattern one final time because one divided by one equals one and one times two times three times four times five also equals 120, which gives us 𝑟 equals four or 𝑟 equals five.

In our next example, we’ll look at a case when we aren’t given the number of elements we started with.

Find the value of 𝑛 given that 𝑛P four equals 24.

We know that 𝑛P𝑟 equals 𝑛 factorial over 𝑛 minus 𝑟 factorial and that 𝑛P four equals 24, which means we don’t know how many items our original set held, but we do know we’re selecting four of them. In cases where we aren’t given the 𝑛-value, it might not seem obvious where we should start, so let’s start by plugging in what we know into our formula, which will give us 𝑛P four equals 𝑛 factorial over 𝑛 minus four factorial. We know that 𝑛 factorial equals 𝑛 times 𝑛 minus one factorial. We can use this property to rewrite our numerator so that 𝑛 factorial is equal to 𝑛 times 𝑛 minus one factorial.

But that doesn’t get us any closer to simplifying the fraction. But we can expand 𝑛 minus one factorial, which would be 𝑛 minus one times 𝑛 minus one minus one factorial, which would be 𝑛 minus two factorial. And we could expand 𝑛 minus two factorial to be 𝑛 minus two times 𝑛 minus three factorial. And 𝑛 minus three factorial would be equal to 𝑛 minus three times 𝑛 minus four factorial. This allows us to cancel out the 𝑛 minus four factorial in the numerator and the denominator. And since we know that 𝑛P four equals 24, we can say that 24 will be equal to 𝑛 times 𝑛 minus one times 𝑛 minus two times 𝑛 minus three. This expression tells us we need four consecutive integers that multiply together to equal 24. And the 𝑛-value will be the starting point, the largest of those four values.

For smaller numbers like 24, we can try to solve this with a factor tree. 24 equals two times 12, 12 equals two times six, and six is two times three. So we can say 24 equals two times three times four. But remember, for this problem, we need four consecutive integers that multiply together to equal 24 and not three. One, two, three, and four are four consecutive integers, and when multiplied together, they equal 24. Remember that our 𝑛-value is the largest value. If we let 𝑛 equal four, 24 does equal four times three times two times one and confirms that 𝑛 equals four.

This strategy worked when we were dealing with a set of a small size. In our next example, we’ll again look at a case when we don’t know the number in our set, the 𝑛-value, but we’re dealing with a much larger set of permutations.

Find the value of 𝑛 such that 𝑛P three equals 32,736.

We know the 𝑛P𝑟 equals 𝑛 factorial over 𝑛 minus 𝑟 factorial. And we’ve been given that 𝑛P three equals 32,736. We don’t know how many items are in our original set, but we do know that we’ll be choosing three of them. So we can set up an equation that says 𝑛 factorial over 𝑛 minus three factorial. And because we know the property 𝑛 factorial equals 𝑛 times 𝑛 minus one factorial, we can do some expanding and simplifying. We can expand 𝑛 factorial to be 𝑛 times 𝑛 minus one factorial, which is further expanded to 𝑛 times 𝑛 minus one times 𝑛 minus two factorial, and finally to 𝑛 minus three factorial. From there, we’re able to cancel out the terms 𝑛 minus three factorial in the numerator and the denominator.

We know that 𝑛P three equals 32,736. This 𝑛 times 𝑛 minus one times 𝑛 minus two tells us we need three consecutive integers that multiply together to equal 32,736. Sometimes when we’re looking for this 𝑛-value, we might use a factor tree. However, with a number this large, this would be pretty difficult. But there is another strategy we can use. Since we know we’re looking for three consecutive integers, we can try to estimate one of those by taking the cube root of 32,736. When we do that, we get 31.9895 continuing.

And so we can try to divide 32,736 by the integers on either side of this value, 31 or 32. If we start with 32, 32,736 divided by 32 equals 1,023. And we’ll take that 1,023 and divide it by the integer below 32. 1,023 divided by 31, when we do that, we get 33. And so, if we’re looking carefully, we end up with 31, 32, and 33 as factors of 32,736. We’re saying 32,736 is equal to 33 times 32 times 31. And these are three consecutive integers that multiply together to equal 32,733 [32,736]. 𝑛 will be the largest of these three values. We’re saying that if we have a set of size 33 and we’re choosing three of them, we will end up with 32,736 permutations.

In our final example, we’ll look at how we would simplify a ratio between two different permutations.

Evaluate 123P10 over 122P nine.

We know to calculate 𝑛P𝑟, we have 𝑛 factorial over 𝑛 minus 𝑟 factorial, which means the numerator is 123 factorial over 123 minus 10 factorial. And our denominator is 122 factorial over 122 minus nine factorial, which we simplify to be 123 factorial over 113 factorial all over 122 factorial over 113 factorial. If we rewrite this with division, it looks like this. And we know dividing by a fraction is multiplying by the reciprocal, which will be 123 factorial over 113 factorial times 113 factorial over 122 factorial. And then we have 113 factorial in the numerator and the denominator. So we have 123 factorial over 122 factorial. And we know that 𝑛 factorial equals 𝑛 times 𝑛 minus one factorial, which means we could rewrite the numerator as 123 times 122 factorial. The 122 factorial in the numerator and the denominator cancel out, and this ratio simplifies to 123.

However, we could have saved ourselves some work by remembering an additional property of permutations. And that is that 𝑛P𝑟 is equal to 𝑛 times 𝑛 minus one P𝑟 minus one. If we notice that 122 equals 123 minus one and nine equals 10 minus one, we could rewrite our numerator as 123 times 122P nine, which would mean we would have a permutation of 122P nine in the numerator and in the denominator. And so the fraction would reduce to 123. When it comes to evaluating and simplifying permutations, we always want to look for patterns that can lead us back to properties which will help us simplify.

Before we finish, let’s review our key points. The number of permutations of size 𝑟 taken from a set of size 𝑛 is given by 𝑛P𝑟 equals 𝑛 factorial over 𝑛 minus 𝑟 factorial. Some properties we use for solving problems involving permutations are as follows: 𝑛 factorial equals 𝑛 times 𝑛 minus one factorial and 𝑛P𝑟 equals 𝑛 times 𝑛 minus one P𝑟 minus one.