Lesson Video: Permutation Mathematics

Video Transcript

In this video, we will learn how to use permutation properties to solve problems and use permutations to count possible outcomes.

The permutation denoted 𝑛𝑃𝑘 represents the number of different ways to order 𝑘 objects from 𝑛 total distinct objects. When dealing with permutations, the order of each element matters. For example, if we wanted to find the number of ordered triples from the numbers one through five which is given by five 𝑃 three, then the arrangements one, two, three and three, two, one are counted as two different arrangements. It is important to note that for this definition to hold 𝑛 and 𝑘 must be nonnegative integers such that 𝑛 is greater than or equal to 𝑘.

Let’s now consider some key definitions and properties we will use in this video. The task of ordering 𝑘 objects from 𝑛 total objects can be thought of in the context of a race. Let’s assume that 𝑛 students participate in a race where the first 𝑘 finishes will earn medals with their placement printed on it. For example, the first-place student will win a medal printed number one, the second-place student will receive one with number two printed on it, and so on. Students that finish after the 𝑘th one do not receive a medal.

If we count the number of different ways to assign medals at the end of the race, we are counting the number of different ways to order 𝑘 students from a total of 𝑛 students. This number is given by the permutation 𝑛𝑃𝑘. Whilst we will use this notation in this video, it is important to note that there are other ways of writing permutations as shown. In order to understand how to work out this number, we will use the fundamental counting principle.

This states that 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 𝑥 multiplied by 𝑦. We recall that two events are independent if the outcome of one event does not change the number of possible outcomes of the other event.

We will now apply the fundamental counting principle to our example. We will let 𝐴 be the event of assigning medals for the top 𝑘 finishers and 𝐵 be the event of ordering the remaining 𝑛 minus 𝑘 runners. This means that applying both events 𝐴 and 𝐵 is the same as ordering all 𝑛 runners since we order 𝑘 and then we order the remaining 𝑛 minus 𝑘 runners. We note that assigning medals to the top 𝑘 finishers does not affect the order of the remaining 𝑛 minus 𝑘 runners. So, the events 𝐴 and 𝐵 are independent.

By the fundamental counting principle, we have the number of ways of assigning 𝑘 medals multiplied by the number of ways to order 𝑛 minus 𝑘 runners is equal to the number of ways to order 𝑛 runners. We already know that there are 𝑛𝑃𝑘 different ways to assign medals for the top 𝑘 finishers. There are 𝑛 minus 𝑘 factorial different ways to order 𝑛 minus 𝑘 runners and 𝑛 factorial ways to order all runners. This means that 𝑛𝑃𝑘 multiplied by 𝑛 minus 𝑘 factorial is equal to 𝑛 factorial. Dividing both sides by 𝑛 minus 𝑘 factorial, we get 𝑛𝑃𝑘 is equal to 𝑛 factorial divided by 𝑛 minus 𝑘 factorial. This is the general formula for permutations.

We can summarize this as follows. Given nonnegative integers 𝑛 and 𝑘, satisfying 𝑛 is greater than or equal to 𝑘, the permutation 𝑛𝑃𝑘 represents the number of different ways to order 𝑘 objects from a total of 𝑛 distinct objects. 𝑛𝑃𝑘 is equal to 𝑛 factorial divided by 𝑛 minus 𝑘 factorial. We will now consider a variety of examples in different situations.

Evaluate five 𝑃 two multiplied by two factorial.

We recall that the permutation 𝑛𝑃𝑘 is defined by 𝑛𝑃𝑘 is equal to 𝑛 factorial divided by 𝑛 minus 𝑘 factorial. This is the number of different ways to order 𝑘 objects from a total of 𝑛 distinct objects. This means that five 𝑃 two is equal to five factorial divided by five minus two factorial. We are trying to calculate the number of different ways to order two objects from a total of five objects. The denominator simplifies to three factorial, as five minus two is equal to three.

We also recall that where 𝑛 is a positive integer, 𝑛 factorial is the product of all the integers from 𝑛 down to one. 𝑛 factorial is also equal to 𝑛 multiplied by 𝑛 minus one factorial. This means that we can rewrite the numerator of five 𝑃 two as five multiplied by four multiplied by three factorial. Three factorial will then cancel on the numerator and denominator, leaving us with five multiplied by four, which is equal to 20. Five 𝑃 two is equal to 20. And we now need to multiply this by two factorial. Two factorial is equal to two multiplied by one. This is equal to two, and multiplying this by 20 gives us an answer of 40. Five 𝑃 two multiplied by two factorial equals 40.

In our next example, we will look at a real-life problem.

In how many ways can two people sit eight chairs?

In this question, we need to count the number of different ways two people can sit on eight chairs. We will, therefore, rephrase the counting statement to fit our definition of permutations. Let’s assume that the two people are labeled one and two. The task of person one and person two choosing two chairs to sit on is equivalent to the task of labeling two of our chairs one and two. We can, therefore, rephrase the question as follows: Count the number of ways to order two chairs out of eight chairs. This is given by the permutation eight 𝑃 two.

We recall that 𝑛𝑃𝑘 is equal to 𝑛 factorial divided by 𝑛 minus 𝑘 factorial. This means that 𝑛𝑃 two is equal to eight factorial divided by eight minus two factorial, which in turn becomes eight factorial divided by six factorial. We also recall that when 𝑛 is greater than or equal to one, 𝑛 factorial is equal to 𝑛 multiplied by 𝑛 minus one factorial. In turn, when 𝑛 is greater than or equal to two, 𝑛 factorial is equal to 𝑛 multiplied by 𝑛 minus one multiplied by 𝑛 minus two factorial. This means we can rewrite the numerator as eight multiplied by seven multiplied by six factorial. Dividing through by six factorial gives us eight multiplied by seven. This is equal to 56.

So, there are 56 ways to order two chairs out of a total of eight chairs. Going back to the original question, we can therefore conclude there are 56 ways that two people can sit on eight chairs.

In our next example, we will consider a problem involving an unknown parameter of the permutation 𝑛𝑃𝑘.

Find the value of 𝑛 such that 𝑛𝑃 three is equal to 32,736.

We know from the general definition of permutations that 𝑛𝑃𝑘 is equal to 𝑛 factorial divided by 𝑛 minus 𝑘 factorial. This means that we can write 𝑛𝑃 three as 𝑛 factorial divided by 𝑛 minus three factorial. This is equal to 32,736. When 𝑛 is greater than or equal to one, 𝑛 factorial is equal to 𝑛 multiplied by 𝑛 minus one factorial. This means that for 𝑛 greater than or equal to three, we can write 𝑛 factorial as 𝑛 multiplied by 𝑛 minus one multiplied by 𝑛 minus two multiplied by 𝑛 minus three factorial. Dividing the numerator and denominator by 𝑛 minus three factorial gives us 𝑛 multiplied by 𝑛 minus one multiplied by 𝑛 minus two is equal to 32,736.

This means that we need to find three consecutive integers 𝑛, 𝑛 minus one, and 𝑛 minus two whose product is 32,736. The product of these three integers must therefore lie between 𝑛 minus two cubed and 𝑛 cubed. We can then take the cube root of this inequality such that the cube root of 32,736 lies between 𝑛 minus two and 𝑛. The cube root of 32,736 is approximately equal to 31.99, giving us the following inequality. This tells us that 𝑛 must be at least 32. And also that 𝑛 minus two can be at most 31 as 𝑛, 𝑛 minus one, and 𝑛 minus two are integers. If we let 𝑛 minus two equal 31, 𝑛 minus one equal 32, and 𝑛 equal 33, then the product of these three numbers gives us 32,736. This means that 𝑛 is equal to 33 as 33𝑃 three is equal to 32,736. There are 32,736 ways of selecting three items from a total of 33 distinct items.

Before looking at one final example, we will consider what happens when a permutation contains rotational symmetry. This will lead us to a definition when counting circular arrangements. A problem which contains rotational symmetry will reduce the number of permutations as rotating a given circular arrangement leads to an equivalent arrangement.

For example, consider a ring that contains 𝑘 distinct stones that are equally spaced, where there 𝑛 distinct types of stone. We need to count the number of different rings from this context. We already know that there are 𝑛𝑃𝑘 ways we could order 𝑘 stones in a straight line from 𝑛 total stones. Let’s assume that we create a ring by bringing the left and right ends of our straight line together. This creates a circular arrangement. And in this example, let’s assume 𝑘 is equal to four.

The four stones A, B, C, and D can be set out as shown. If we consider a rotation of 90 degrees clockwise, the stones will be set out as shown in the second figure. We can rotate the arrangement a further 90 degrees and repeat this once more so the stones are set out as shown. We observe here that all four circular arrangements are identical. This means that when we count the number of linear arrangements, each distinct ring design is repeated four times. In other words, there are four different linear arrangements that can be made from a distinct circular ring as shown. We can, therefore, say that if we have 𝑘 distinct stones in a ring, then each ring design can form 𝑘 distinct linear arrangements.

Using the fundamental counting principle and letting 𝐴 be the event of creating a ring design and 𝐵 the event of forming a linear arrangement from a given ring design, then as 𝐴 and 𝐵 are independent, the number of different rings with 𝑘 stones multiplied by the number of linear arrangements from a ring is equal to the number of linear arrangements of 𝑘 stones. The right-hand side is equal to 𝑛𝑃𝑘. And we have observed that there are 𝑘 different ways to form linear arrangements from a ring.

This means that the number of different circular arrangements multiplied by 𝑘 is equal to 𝑛𝑃𝑘. Dividing both sides by 𝑘, we obtain that the number of different ways to arrange 𝑘 objects in a circular pattern from a total of 𝑛 distinct objects is 𝑛𝑃𝑘 divided by 𝑘. We will now consider a real-life example of this.

Determine the number of ways six children can sit in a circle.

We recall that the number of different ways to arrange 𝑘 objects in a circular pattern from 𝑛 total distinct objects is 𝑛𝑃𝑘 divided by 𝑘. In our example, we are arranging in a circle six students from a total of six students. This means that 𝑛 is equal to six and 𝑘 is also equal to six. We, therefore, need to calculate six 𝑃 six divided by six. From our knowledge of permutations, 𝑛𝑃𝑘 is equal to 𝑛 factorial divided by 𝑛 minus 𝑘 factorial. This means that six 𝑃 six is equal to six factorial divided by six minus six factorial. The denominator simplifies to zero factorial, and this is equal to one. Six 𝑃 six is, therefore, equal to six factorial.

The number of ways that six children can sit in a circle is, therefore, equal to six factorial divided by six. When 𝑛 is greater than or equal to one, 𝑛 factorial can be rewritten as 𝑛 multiplied by 𝑛 minus one factorial. Therefore, six factorial is equal to six multiplied by five factorial. We can then divide the numerator and denominator by six, leaving us with five factorial. This is equal to 120. So, there are 120 ways that six children can sit in a circle.

We will now summarize the key points from this video. The permutation 𝑛𝑃𝑘 counts the number of different ways to order 𝑘 objects from 𝑛 total distinct objects. The permutation 𝑛𝑃𝑘 is also denoted as shown. To calculate the number of permutations 𝑛𝑃𝑘, we divide 𝑛 factorial by 𝑛 minus 𝑘 factorial. Finally, we saw in the last example that the number of circular arrangements for 𝑘 elements from 𝑛 total elements is given by 𝑛𝑃𝑘 divided by 𝑘.