Permutations

A permutation is a special case of a k-permutation, where we have a set of size n and want to know the number of all different n-tuples.

The formula

Let’s recall k-permutations. Take the set of digits {1, 2, 3, 4, 5}. How many three-digit numbers can we make from them if no digit may be repeated? This is a typical k-permutation problem, which can be solved with the familiar formula

$$P(n,k)=\frac{n!}{(n-k)!}=\frac{5!}{(5-3)!}=60.$$

How many five-digit numbers could we make?

$$P(5,5)=\frac{5!}{(5-5)!}=\frac{5!}{0!}=5!=120.$$

We can see that if we have a set of five elements and look for all the different 5-tuples, the result is 5!. We can generalise this: if we have a set of n elements, there are n! different n-tuples in total. This brings us to the idea of a permutation.

What is a permutation

If we have a set M of size n, then a permutation is any n-tuple made from the elements of M in which no element is repeated. For example, if M = {a, b, c, d}, then (a, b, d, c) and (d, b, a, c) are permutations. The number of all different permutations is

$$P(n)=P(n,n)=n!$$

Worked examples

1. You have six books and want to put them on a shelf in some order. How many different orders are there? We have six books and always arrange all of them, so the result is P(6) = 6! = 720.

2. Four books written in Latin have been added to your 6 English books from the previous example. In how many different ways can you put these 10 books on a shelf if you want all the English books together and all the Latin books together?

   What are our options for arranging the books? We can put the six English books first and then the four Latin ones, or the other way round – the four Latin books first and then the six English ones. There are 6! ways to arrange the English books and 4! ways to arrange the Latin books. Using the product rule for counting, we multiply these results: 6! · 4! = 17,280. Since there are two options for the order of the groups (English then Latin, and vice versa), we multiply this number by two as well. The final result is 17,280 · 2 = 34,560.