Count On
Explorer
Permutations
A permutation is a re-ordering of a list of items. Suppose we have 3 books to put on a shelf. How many orders can we arrange them in (permute them) on the shelf? There are six ways. First, let's call the books A, B and C. The 6 possible permutations of A,B and C can then be described by:
Suppose we find book D needs to be put on the same shelf. In how many ways can we permute the 4 books? There is a simple method of using the answer to the 3-book problem to find all the answers to the 4-book problem. Take any of the 3-book permutations, say B A C.
We can insert D either before all of them | D B A C |
or between the first and second: | B D A C |
or between the second and last: | B A D C |
or as the final one: | B A C D |
We can make 4 new and different permutations for each of the 6 previous ones, so there are 24 permutations of 4 books. In the same way there are 5 positions to insert book E into each of these 24, giving 5 x 24 = 120 permutations of 5 objects. The symbol that is used to count the number of permutations of n objects is n! called n factorial. Here is a table of its values:
n | n! |
---|---|
1 | ? |
2 | ? |
3 | 6=2x3 |
4 | 24=2x3x4 |
5 | 120=2x3x4x5 |
6 | ? |
Permutations play a big part in the mathematics of chance events and probability, in gambling and in simulating complex real-world situations using computers.
How many ways can a deck of
52 playing cards be laid out in a single row?
Answer: 52! (a number with 68 digits!)
In a permutation items cannot be repeated. The answer to questions such as How many 3 letter words can be formed from the letters a,b,c,d and e? involves repeating letters such as aaa or aba and so the n! formula does not apply.
Can you... ..write down all the permutations of the letters S,T,A,R? First calculate how many there should be and then say how many of them are words you would find in the dictionary. Such words (or phrases) which are just rearrangements of the letters of another word (or phrase) are called anagrams so ARTS is an anagram of STAR.
Crossword puzzles often rely on a particularly apt anagram to give cryptic clues such as astronomers being the answer to the clue "Mixed up moon starers?" where the words "mixed up" are the hint that an anagram is involved and the letters of moon starers can be rearranged to form astronomers.
Patterns