Combinatorics and computing

Example 9.4.1 How many anagrams (permutations of the letters) are there of the following words?


(a) ANSWER (b) PERMUTE (c) LITTLE


(a) Since ANSWER has 6 different letters, the number of anagrams is 6! = 720.
(b) There are 7! ways of arranging 7 letters; however, this assumes that all the letters are different. In the present case, the number of anagrams is only half that number, because interchanging the two Es in an anagram does not produce a new anagram. The answer is 7!/2 = 2520.
(c) There are 6! permutations of six letters, but again we need to take care to avoid double counting. In each of these 6! arrangements, we can swap the Ts or the Ls or both without obtaining new anagrams. The number of different anagrams is therefore 6! / 4 = 180.
Note that in each case the original word is counted as one of the anagrams.


A more general permutation problem arises if the elements to be arranged are chosen from a larger set. Suppose we want to select r elements from a set with n elements (where n > r), and arrange those r elements in a particular order. In how many ways can this be done?
This question can be answered in a similar manner to the previous one. The first element of the permutation can be any one of the n elements in the larger set. The second element must then be chosen from the remaining n – 1 elements, the third element from the remaining n – 2 elements, and so on, until r elements have been chosen. The last (r th) element is chosen from the n – r + 1 elements remaining at that stage. By the Multiplication principle, the total number of ways this can be done is:


n(n - 1)(n - 2) ... (n – r + 1)


This expression is denoted by n P r . It is not difficult to see that we can also write n P r in terms of factorials in the following way:

Example 9.4.2 As part of a market research survey, you are shown a list of 20 types of chocolate bar, and asked to list your five favourite bars in order of preference. How many different responses to this question are there?


Solution You are selecting five bars from a larger set of 20 bars. Since the order in which the five bars are listed is important (that is, the same selection in a different order counts as a different response), this is a problem involving permutations. The answer is:


ⁿP₅ = 20 × 19 × 18 × 17 × 16 = 1 860 480