Permutation vs. Combination

Permutation vs. Combination

After our lesson on factorials we are ready to learn about the most important part of combinatorics: permutations and combinations; in reality, what we learned about the factorial notation in our past lesson (please make sure you read that lesson first!) provides the basis for these two new concepts, which are deeply intertwined with each other.

Therefore, we have decided to dedicate this lesson to introduce both concepts together, the permutation and the combination, and later, we will have a lesson dedicated to each one and a variety of example problems to practice them further. Without further ado, let us start by introducing permutations and combinations separately.

What is a permutation?

The idea of permutation is rooted in the process of arranging and finding how many total possible arrangements exist for a group of items in a set. If you think about it, it sounds exactly the same as what we have seen before in our lesson about factorials, because it actually is in specific cases!

Let us explain, we have seen example problems where we had to find out all of the different possible arrangements of items from a set that are ordered side by side. A permutation refers to this order and all of the possible arrangements of the items according to specific conditions, which limit the amount of items from the set that will be used in the arrangements. You may be wondering then, how is this different from the method to compute all the possible arrangements of a list of items side by side that we have seen before? Well, in simple words, when all of the objects from the set will be arranged side by side, permutations produce the total quantity exactly in the same way as we have calculated it before, the difference comes when you have a list of items and you will not be arranging them all.

Sounds confusing? Lets expand:
Think on the next example (very similar to what we have seen so far): 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 saw this process before, 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 only have one possible box left. When multiplying the number of possible boxes for each of the positions, you will find all the ways in which the arrangements of the boxes can be done, which is equal to 4! = 4 × 3 × 2 × 1 = 24 (24 different ways).
This is a type of permutation calculation because each arrangement is defined by the order in which the boxes have been ordered; this is also the simplest type of permutation calculation, since you have four items, all of them to be ordered in different ways (the number of items, is equal to the number of possible positions).

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.
So we have imposed a condition: only two out of the four boxes will be arranged, but 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. Notice 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.

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.


With this in mind, we define permutation in the following way:

$\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 the permutation formula, 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, so:

$\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 (and so, you have the same amount of items as the amount of positions in which they will be ordered) the process is exactly the same as what we had seen in our factorial lesson (process to calculate the total amount of ways in which items can be arranged without repetition).

Definition of combinations

Now let us take a look to combinations, you may be wondering, if permutations are the way a group of objects from a set can be arranged, wouldnt this calculate the amount of combinations you can make with those items? NO, to introduce this idea simple remember: permutations are arrangements (ordering) of items, NOT combinations.

To clearly show how combinations work, let us go back to our set of four boxes from above:


You were asked to find out all of the possible arrangements of only two of these boxes at the time, and so, you found the permutations of two out of four boxes this way:


Now, what if you were asked to find how many possible combinations can you do with two (any two) boxes out of these four instead?
Notice that in permutations, the pairs of A B and B A are counted as different even when you have the exact same two letters involved; the same goes for the case of B C and C B, D B and B D, A C and C A, etc. In the case of combinations, a combination is taken as a selection of two distinct items from the set, no matter the order in which they are arranged (therefore A B and B A are the same and counted as one combination only!); thus, combinations are actually about how we select items from a set, not how we arrange them!

A formal combination definition would be that when selecting items from a set, each combination is a group (the size of the group depending on what is asked) consisting of distinct items from a set no matter in which order they are arranged. Therefore, when using two out of the four boxes shown in figure 4 we have the following:


The formula for combinations goes as follows:

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

From figure 5 we can obtain a few conclusions: Permutations are about arranging or ordering items obtained from a set, combinations are about selecting distinct items from a set. When looking at the results from combinations and permutations, the main difference between a permutation and combination is that the first pays attention to the order in which the subset of items picked from a total set is arranged, while how many combinations can be done in a subset are characterized by not noticing the way the objects are arranged, just the distinction between the ones selected (no matter how they are placed in positions).

Permutations vs combinations

Once we have seen the concepts for both permutations and combinations, let us take a look at an example where we can see the comparison of permutation vs combination in action. Remember! the difference between permutation and combination is that permutations care about the order of the items, while combinations do not!

Example 1

There are 8 runners for an olympic 100m race. Each of the runners is from one of the next 8 countries: Canada (CA), Mexico (MX), China (CH), Japan (JP), United Kingdom (UK), Kenya (KN), Ethiopia (ET) and Jamaica (JM). Use the permutations or combinations formula to solve each case properly.

On this case we are focused to find not only which three countries will win an olympic medal, but also in which order (who will win first, who second and who third). Therefore, we are in the need to find out the possible arrangements of three athletes nationality out of 8 possible.

In this case, the total distinct athletes are 8, one from each country, and so $n$ = 8; while those who will win a medal (and for which we are looking at the possible positions) are 3, and so $r$ = 3. Using the permutations formula from equation 1 we have that:

$\large _{8}P_{3} = \frac{8!}{(8\,-\,3)! } = \frac{8!}{5!} = \frac{8\times 7 \times 6 \times 5 \times 4 \times 3 \times 2 \times 1}{5 \times 4 \times 3 \times 2 \times 1} =$ 8 × 7 × 6 = 336
336 total possible arrangements for the composition of the medal podium in this olympic race.

On this question now we do not care about who gets in first, second or third place, we just care to find out the different combinations of three countries that would end up with an olympic medal. For that we use the combination formula shown in equation 4, where we have that $n$ = 8 and $r$ =3

$\large _{8}C_{3} = \frac{8!}{(8\,-\,3)! \cdot 3!} = \frac{8!}{5! \cdot 3!} = \frac{8\times 7 \times 6 \times 5 \times 4 \times 3 \times 2 \times 1}{(5 \times 4 \times 3 \times 2 \times 1) (3\times 2 \times 1)} = \frac{8 \times 7 \times 6}{3 \times 2 \times 1} =$ 8 × 7 = 56
For a total of 56 possible country combinations in the olympic podium for this race.

We recommend you to graphically work out this problem by following the fundamental counting principle just as is done in figures 2 and 3.

***
To finalize our lesson, we recommend you to visit the next review handout on how to count where you will have a very nice explanation of both processes along with examples. Also, this article on permutations and combinations can be of use while you study.
For more on combination vs permutation, keep on reading the next two lessons on our statistics course, where we will continue to add many more examples on each topic.