Arrangements (k-permutations)

We use k-permutations (arrangements) when we choose a certain number of objects from a set and the order in which we choose them matters.

Deriving the formula

Let’s start with a typical problem: every year a village holds a pie-eating contest. Seven greasy contestants have reached the final. Work out how many ways these seven contestants can fill the first three places.

It is important to realise that order matters in this example. For instance, if we know that Oliver, Harry and George finish in the top three, these three give us six different finishing orders:

• Oliver, Harry, George;
• Oliver, George, Harry;
• Harry, Oliver, George;
• Harry, George, Oliver;
• George, Oliver, Harry;
• George, Harry, Oliver.

These are all different results, and we want to count how many different results we can make when there are 7 contestants.

We use the product rule for counting. We say that we are choosing triples of the form (x₁, x₂, x₃), where x₁ is the contestant who finished first, and so on. Which contestants can we put in place of x₁? All of them, so there are 7 choices for x₁. Which can we put in place of x₂? All except the one we have already put in first place, so there are 7 − 1 = 6 choices for x₂. For x₃ we can use the contestants who are not in first or second place, so we have 7 − 2 = 5 options. Applying the product rule, we get the total number of possibilities: 7 · 6 · 5 = 210.

We can see that if we wanted the number of possibilities for the first 4 places, there would be 7 − 3 = 4 choices for x₄, so the total would be 7 · 6 · 5 · 4 = 840. What can we conclude from this?

If we have a set of n elements (here, in the example, 7 eaters) and choose 3 of them, where order matters, the result is n · (n − 1) · (n − 2). Everybody can finish in first place, one fewer in the next, and so on. From this we can derive the general formula for choosing k elements from a set of n elements: the number of possibilities is n · (n − 1) · (n − 2) · … · (n − k + 1).

We can simplify this formula further using the factorial. Look at the factorial of seven, 7! = 7 · 6 · 5 · 4 · 3 · 2 · 1, and at how we counted the medal places, 7 · 6 · 5. There is a clear similarity. We only need to get rid of the tail, that is, divide 7! by 4 · 3 · 2 · 1, which leaves just 7 · 6 · 5. And what is 4 · 3 · 2 · 1 equal to? It is 4!.

So we can write that if we have a set of n elements and choose k of them, where order matters, there are

$$P(n,k)=\frac{n!}{(n-k)!}$$

possibilities. Here P(n, k) means that n items are available and k of them are arranged; note the order of the arguments (on a calculator this is the nPr button). Substituting the numbers from the pie-eating contest into the formula:

$$P(7,3)=\frac{7!}{(7-3)!}=\frac{7\cdot 6\cdot 5\cdot 4\cdot 3\cdot 2\cdot 1}{4\cdot 3\cdot 2\cdot 1}=7\cdot 6\cdot 5=210.$$

Calculator

The following calculator works out the number of k-permutations for given n and k.

Worked examples

1. Let’s stay with the pie-eating contest. How would the number of possible medal results change if we knew that Jack, a champion who always wins, has entered? That is, how many different medal results are there if we have 7 contestants and Jack is certain to win?

To work this out we need another simple k-permutation: first place is certain, and from the remaining 6 contestants we have to decide how they can fill second and third place. So we choose 2 elements from a set of 6, which leads to

$$P(6,2)=\frac{6!}{(6-2)!}=30$$

2. Long ago, before Jack became such a champion, he regularly finished in the top three. How many different medal results are there if we have 7 contestants and Jack is certain to get a medal?

   This example differs from the previous one in that we don’t know which place Jack finished in; he might have come second or even third, which he is still embarrassed about. So we have to count three different k-permutations: one where Jack won, one where Jack got the silver medal and finally one where he got the bronze. But each time there are only two places left for the others. For example, if Jack was second, the other contestants could finish in first or third place. So again we count 2-permutations of 6, only we have to count them three times, for the three different places Jack could take. The total number of results is therefore

   $$3\cdot P(6,2)=3\cdot \frac{6!}{(6-2)!}=3\cdot 30=90$$

   Notice that the 3 in front can be written as P(3, 1), because we are really choosing one element (one particular place) from a set of three (the three medal positions).

3. There are 20 teachers at a school. A-level exams are coming up and a panel has to be put together as follows: one chair, one kind assessor and one strict assessor. How many possibilities are there in total?

   First we have to answer the question of whether order matters. It does, because we can shuffle three teachers around in six different ways. Now it is simple – we choose a 3-permutation of 20 elements:

   $$P(20,3)=\frac{20!}{17!}=6840.$$

4. How many three-digit numbers can we make from the digits {0, 1, 2, 3, 4, 5} if no digit may be repeated?

   Does order matter? Yes, 123 is a different number from 321. How many different triples are there? That is a simple 3-permutation of 6:

   $$P(6,3)=\frac{6!}{3!}=120.$$

   But we still have to subtract the arrangements that start with zero, because 012 is not a three-digit number. So the question is: how many different triples start with zero? In that case the digits only vary in the remaining two places (the triples have the form (0, x₂, x₃)), so we want to know how many different pairs we can make using the digits {1, 2, 3, 4, 5}. That is again simple: P(5, 2) = 5!/3! = 20. So there are 20 triples that start with zero.

   The total number of three-digit numbers made from the digits {0, 1, 2, 3, 4, 5} is therefore 120 − 20 = 100.

5. How many different three-digit numbers can we make from the digits {1, 2, 3, 4, 5} if no digit may be repeated and the number has to be odd?

   Order matters, because 123 is a different number from 321. We are building a three-digit odd number, which means that the first two places can hold any digit, but the last must be one of the digits {1, 3, 5}. First we count all the triples we can make from five digits: P(5, 3) = 5! / 2! = 60.

   Each digit appears in the last place equally often, so with 5 digits, each digit appears in the last place 60 / 5 = 12 times. We have three digits {1, 3, 5} that can appear in the last place, so there are 12 different numbers ending in 1, 12 ending in 3 and 12 ending in 5. Using the addition rule, we get 12 + 12 + 12 = 36 possibilities in total.

6. Find x given that P(x, 2) = 72. In other words: we choose pairs from a set of size x and we know that we can choose 72 different pairs in total. How big was the set we chose the pairs from? Let’s write it out:

   $$P(x,2)=\frac{x!}{(x-2)!}=72$$

   Next we simplify:

   $$\begin{array}{rcl}\frac{x!}{(x-2)!}& =& 72\\ \frac{x\cdot (x-1)\cdot (x-2)!}{(x-2)!}& =& 72\\ x\cdot (x-1)& =& 72\\ x^2-x& =& 72\\ x^2-x-72& =& 0\end{array}$$

   This is now a standard quadratic equation, so we can solve it using the discriminant, or we can rewrite the equation in the form

   $$(x+8)\cdot (x-9)=0$$

   from which we can read off the solutions: x₁ = −8 and x₂ = 9. The negative solution is of no interest, because a set cannot have a negative size, so the solution of the original equation is x = 9: the set had nine elements.