Combinatorics and computing

9.4 Permutations


A common task in computing is that of sorting a list of items into order according to some criterion, such as alphabetical or numerical order. We will look at sorting algorithms in Chapter 13. In the meantime, a question that arises in this context is: in how many different orders can a set of items be listed?
If there are three items, for example, say a, b and c, then a bit of trial and error reveals that there are six different ways in which they can be arranged:


abc, acb, bac, bca, cab, cba


An arrangement of the elements of a set into a particular order is called a permutation of that set. We have just listed the six permutations of the set {a, b, c}.
How many permutations are there of a set with n elements? We can answer this question by applying the Multiplication principle in the following way. The first element of the permutation can be any one of the n elements. Once this element has been chosen, the second element can be any one of the remaining n – 1 elements. Continuing in this way, the third element can be any one of the remaining n – 2 elements, the fourth element can be any one of the remaining n – 3 elements, and so on. Of course, there is only one possible choice for the last element. According to
the Multiplication principle, the total number of permutations is:


n(n – 1)(n – 2) ... × 3 × 2 × 1


We recognise this from our earlier work as n factorial (n!). The result can be stated as follows: The number of permutations of a set with n elements is n!.