Permutations of distinct objects

Order matters

Three friends, Anu, Bilal and Chitra, finish a race. The results Anu first, Bilal second and Bilal first, Anu second are different results. The same people, in a different order, give a different outcome.

An arrangement of objects in a definite order is called a permutation. This course counts permutations without listing them all.

Filling places

Seven letter tiles, A to G, lie on a table. Gauri makes a code by placing four of them in a row. How many codes can she make?

Think of four empty places.

• The 1st place can take any of the $7$ tiles.
• The 2nd place can take any of the $6$ tiles left.
• The 3rd place has $5$ choices, and the 4th has $4$.

By the multiplication principle, the number of codes is $7 \times 6 \times 5 \times 4 = 840$.

The tree shows the same idea for three letters. Each level has one choice fewer than the level above.

The formula for nPr

The number of permutations of $n$ different objects taken $r$ at a time is written ${}^nP_r$. Filling $r$ places gives $r$ factors, each one less than the last:

Multiply the top and the bottom by $(n - r)!$. The top becomes $n!$, so

For Gauri, ${}^7P_4 = \dfrac{7!}{3!} = \dfrac{5040}{6} = 840$.

Why 0! is 1

Arranging all $n$ objects means $r = n$. Filling $n$ places gives $n!$ ways, so ${}^nP_n = n!$. The formula gives $\dfrac{n!}{0!}$. The two agree only if $0! = 1$. That is why we take $0! = 1$.

Also ${}^nP_0 = \dfrac{n!}{n!} = 1$: there is exactly one way to fill no places at all.

When repeats are allowed

Suppose a tile can be used again, like the digits of a bicycle lock. Then every place has all $n$ choices. Filling $r$ places gives

A lock with $3$ dials, each showing $0$ to $9$, has $10^3 = 1000$ settings. If no digit may repeat, it has only ${}^{10}P_3 = 10 \times 9 \times 8 = 720$.

Set $r$ larger than $n$. With no repeats, you run out of objects, and there is no way to fill the places.

A useful relation

Take the first place on its own. It has $n$ choices, and the other $r - 1$ places are filled from the $n - 1$ objects left. So

A worked example

Eight students reach a hall with $5$ chairs in a row. In how many ways can $5$ of them be seated?

Step 1. Does order matter? Yes. Swapping two seated students gives a new seating.

Step 2. Count. Fill the chairs from left to right: ${}^8P_5 = 8 \times 7 \times 6 \times 5 \times 4 = 6720$.

Answer: $6720$ seatings.

Finding n

Sometimes $n$ is the unknown. If ${}^nP_2 = 56$, then $n(n - 1) = 56$. Two whole numbers in a row multiply to $56$, so $n = 8$.

Practise with new numbers

Try it in Python

The program lists the codes of four tiles from seven with itertools.permutations, then counts them by the formula.

Common mistakes

• Using $n^r$ when repeats are not allowed. Each object can fill only one place.
• Writing $\dfrac{n!}{r!}$. The bottom is $(n - r)!$, the orders of the objects left out.
• Stopping the product one factor early. ${}^8P_5$ has five factors, ending at $4$.
• Thinking $0! = 0$. It is $1$, so that ${}^nP_n = n!$.

Remember these

• A permutation is an arrangement in a definite order.
• ${}^nP_r = n(n - 1)\cdots(n - r + 1) = \dfrac{n!}{(n - r)!}$.
• ${}^nP_n = n!$ and $0! = 1$.
• With repeats allowed, $r$ places from $n$ objects give $n^r$ arrangements.
• ${}^nP_r = n \times {}^{n-1}P_{r-1}$.

Check yourself

Try each one on your own first. If you are stuck, open a hint. Then check with Show the answer.

1. Find ${}^6P_3$.

2. A shelf has room for $3$ of Farhan's $5$ different books. In how many orders can he fill it?

3. How many $2$ letter strings can be made from the $5$ vowels if a vowel may repeat?

4. Explain in one line why ${}^nP_r = \dfrac{n!}{(n - r)!}$ needs $0! = 1$.

5. Solve ${}^nP_2 = 30$ for the whole number $n$.