Permutations

Permutations

Although we have seen an introduction to the topic of permutations during our lesson on permutation vs. combination, today we will focus on expanding a little bit on the topic and providing many more permutation examples for you to solve and gain practice.
Thus, without further ado, let us start by with a review on what a permutation is!

What is a permutation?

As we saw in our past lesson, a permutation is a process in charge of finding how many total possible arrangements exist for a group of items from a set that are being ordered either side by side or following a particular position succession. The most important characteristic of a permutation is that each possible arrangement pays attention to the order of the items, and so, even when the same items are involved having them ordered in a different way creates different arrangements and thus, different permutations.
Notice that when we define permutation, we talk about a group of items from a set because the process of calculating permutations originated from our need of counting the different ways in which a group of items coming from a set can be ordered, when we are NOT using the complete original set of items; still, permutations CAN be calculated when using the complete set.

Recall the example combinatorics problems using factorials from our lesson on the factorial notation; there, we learnt about the process to calculate the total amount of ways in which a set of objects can be arranged using the fundamental counting principle as a basis. With such method, we can calculate the ways in which a set can be ordered when the whole set is being used in the arrangements; using such knowledge, we saw in our past lesson that the calculation translates into the same expression when using the permutations formula.
Therefore, always remember that you can calculate permutations of objects in a set being arranged, it doesnt matter if the whole set is being used in the arrangement, or if only some of the items from the set are used (the calculation gets to be very simple when all of the objects from the set are used, we will come back to that later on this lesson).

Let us go back to the permutation definition to review what the process entails.

• A permutation focuses on all of the possible ways in which a set (or part of a set) of items can be arranged.
• The order in which the items are positioned produces all of the different arrangements, each change in position defines a new arrangement.
• When all of the objects from the set are used in the arrangements, permutations produce the total quantity of arrangements by multiplying the possible items per each possible position producing a factorial product.
• When only certain items from the set are used while making the arrangements, the calculation of the total possible ways is calculated by a particular division of factorials.

The permutation formula will be explained in the next section, for now, let us review how to obtain permutations in both of the cases mentioned just by following the logic of factorials and the counting principle.

Imagine we have four boxes (A, B, C and D) and we will arrange them side by side.


How many possible different arrangements are there for these four boxes, when ALL of them will be arranged side by side in different ways? Well, the answer is very simple, is just 4!


We learnt this on our factorials lesson. We know that in the first position you have four possible boxes to be used, therefore you pick one and move to the next position, where you will have only three possible boxes to choose (having used one in the first position); pick one once more, move to the next position where you will be left with two possible boxes, pick one and then for the last position you will only have one possible box left.
Having all of those possibilities per each position (which statistically speaking can be said to be the possible outcomes per each position location, marking each of them a different event), we follow what we learnt from the fundamental counting principle and multiply the total possible outcomes (possible boxes) per each position to obtain all of the arrangements that the four boxes can have, which is equal to 4! = 4 × 3 × 2 × 1 = 24 (24 different ways).

Now let us keep those same 4 boxes, but we will order ONLY TWO of them and see how many different ways we can arrange them. Notice that we didn't say WHICH boxes! Therefore, all of the four boxes are still up for the arrangement, is just that you can only use two at a time.

This time, you have four boxes to be arranged in two positions, therefore, you know that in the first position you have 4 possible boxes to be put in there; while in the second position, you are left with three possible boxes to arrange since you have already used one.
You can see the process is EXACTLY the same as before, but with less possible positions! Therefore, we multiply the possible ways for each position and obtain 4 × 3 = 12, for a total of 12 possible different arrangements of two boxes out of a set of four.

As we mentioned at the beginning of this lesson, this is exactly what permutations are all about! To find all the possible ways in which a group of items from a set (could be all of the items from the set, or could be just some of them) can be arranged side by side. Take a look at the figure below to see the process of arranging only two out of four boxes from the set above, and see how the amount of different possible ways for this changes.


On the bottom part of this second figure, we have already noted the permutation equation, let us go to a new section to talk about the calculations for this process.

How to calculate permutations?

The formula for permutations, also called the formula to calculate the number of arrangements of $r$ items taken from a set of $n$ distinct items (where the order in which the items are arranged matters), goes as follows:

$\large _{n}P_{r} = \frac{n!}{(n\,-\,r)!}$
$\quad$Where:
$\quad \large _{n}P_{r}$ = Permutations of $r$ items from a set of $n$ items
$\qquad n$ = number of total items in a set
$\qquad r$ = items being arranged

And so, using this permutation definition, we can go ahead and check for the process shown in figure 2: for four boxes being arranged side by side (all four boxes) meaning you have to fill four positions, we have that $n$ = 4 and $r$ = 4, therefore:

$\large _{4}P_{4} = \frac{4!}{(4\,-\,4)!} = \frac{4!}{0!} = \frac{4!}{1} =$ 4! = 4 × 3 × 2 × 1 = 24
While the process shown in figure 3, with four boxes for two positions, goes as follows:

$\large _{4}P_{2} = \frac{4!}{(4\,-\,2)!} = \frac{4\, \times \, 3 \, \times \,2 \, \times \, 1}{2!} = \frac{24}{2\, \times \, 1 } = \frac{24}{2} =$ 12
In this way, we can clearly see that when we are calculating the permutations of a list of objects, where ALL of the objects will be ordered, you can simply count how many objects are contained in the list (or set) and then compute the factorial of this number to find out the number of permutations. Just remember that, if only a few objects from the list will be used, you have to use equation 1.

And so, if you think about it the permutation algorithm (the instructions to follow) is very simple, when having a set of items to be distributed in a certain number of positions, just follow the next steps:

1. The first position has as possible outcomes as items are available on the full set.
2. The next position has as possible outcomes as items are on the full set minus one
3. The next position has as possible outcomes as items are on the full set minus 2
4. And continue this until you have no other position to fill.
5. Notice, that when there are the same number of positions to fill as items in the full set, the very last position will only have one possible outcome (or item to be put in there) since all the other ones have been used in the positions before.
6. To calculate the final amount of options permuted, you just multiply the possible outcomes in each position and you will obtain the result.

Notice that this process has been explained logically, you can quickly just grab equation 1 and calculate the total amount of permutations easily without having to worry about all of this explanation; still, we think it is important you see where the formula comes from.

If you have doubts or questions about the steps we just listed, take a look at figure 3 so you can see how it was done (since it followed exactly this same logic and computation).

Permutation examples

For these permutation problems we will be using equation 1 to save time, but we encourage you to use the algorithm described in the last section for you to check the understanding of each of them.

Example 1

How many ways can a president, a vice president, and a treasurer be selected from a class of 20 students?

For this case you have a total of 20 students which is your whole set, only three of them can obtain a class committee position, and they have to be in specific order since each position is different. Therefore, you have that $n$ = 20 and $r$ = 3.
Using the permutations definition in mathematical form as seen in equation 1 we have that:

$\large _{20}P_{3} = \frac{20!}{(20\,-\,3)!} = \frac{20!}{17!} =$ 20 × 19 × 18 = 6,840
Therefore, there are 6,840 different ways in which the class committee can be selected in a class of 20 students. Good luck to all!

Example 2

There are 10 different books. A bookshelf can only hold 6 books in a row. How many ways can 6 of these books be arranged on a bookshelf?
In order to find how many ways we can permute the books while being arranged on this shelf, we once more use the formula from equation 1, where $n$ = 10 and $r$ = 6, to compute:

$\large _{10}P_{6} = \frac{10!}{(10\,-\,6)!} = \frac{10!}{4!} =$ 10 × 9 × 8 × 7 × 6 × 5 = 151,200
And so, there are 151,100 ways in which six out of ten books can be arranged in the bookshelf.

***
To finalize this lesson let us provide you with some link recommendations:
This article on permutations introduces the topic of transpositions, a particular type of permutations. And this link on permutations and combinations gives an introduction of both processes while comparing them with one another.

You will notice all of these lessons on combinatorics sound a little repetitive, in reality, for these section on combinatorics we are just learning about four things: the fundamental counting principle, the factorial notation, permutations and combinations; still, we have more lessons repeating on them because the different ways one must complete the calculations on combinatorics can get tricky and lengthy depending on the problems you have to solve, and so, we recommend you to pay attention to all of the problem examples and figures in detail, and check out the last lesson on this chapter, which contains two long problem examples combining different concepts we are learning here.

This is it for this lesson, see you in the next one!