
[Description  Example  History  Applications  Implementation  Classroom  Links]
What are the different ways that Alice, Bob, and Carol can line up at the box office at a theatre? We can simply list the ways: Alice, Bob, Carol, or Alice, Carol, Bob, or Bob, Alice, Carol, or Bob, Carol, Alice, or Carol, Alice, Bob, or Carol, Bob, Alice. There are exactly six ways and each is called a permutation of Alice, Bob, and Carol. We could produce a similar list of permutations no matter how many persons there were. Below we give a mathematical definition of a permutation.
A permutation of objects is an arrangement of those objects in some order; that is, some object is placed in the first position, another in the second position, and so on, until all objects have been placed. (In a kpermutation only the first k positions have objects placed in them.) For our purposes, a permutation is a string a(1), a(2), ..., a(n), where each a(i) is an element of the set [n] = {1,2,...,n} and each element occurs precisely once. For example, the permutations of [3] = {1,2,3} are 123, 132, 213, 231, 312, 321. These permutations correspond to the six permutations given in the first paragraph, with 1 = Alice, 2 = Bob, and 3 = Carol.
The number of permutations for n = 1,2,...,10, is 1, 2, 6, 24, 120, 720, 5040, 40320, 362880, 3628800; these are the factorial numbers n! = n···2·1. The number of k permutations is given by the formula P(n,k) = n·(n1) ···(nk+1) = n!/(nk)!.
Every permutation of [n] corresponds to a unique "permutation matrix". To a mathematician a permutation matrix is an n by n table of 0's and 1's which contains exactly one 1 in each row and column. If a(i) = j then row i contains a 1 in column j. Regarding the 1's as rooks, this is equivalent to a collection of n nontaking rooks on a chessboard. Recall that a rook can take a piece that is in its same row or column. In a kpermutation the chessboard has k rows. As an example, the configuration shown below corresponds to the permutation 543621.
1  2  3  4  5  6  
a(1) = 5  
a(2) = 4  
a(3) = 3  
a(4) = 6  
a(5) = 2  
a(6) = 1 
We generate permutations in 2 different orders.
We have already given several small examples above. Here are a few others.
How many ways are there for Alice, Bob, and Carol, to line up at the box office at the movies? We saw this example before, with a solution in lexicographic order. Here are the six (=3!) possible permutations in transposition order: (A, B, C), (A, C, B), (C, A, B), (C, B, A), (B, C, A), (B, C, A)
How many ways are there to arrange the four letters in the word MATH? There are 24 possible ways to arrange the four letters (or 4!): There are 4 possibilities for the first position, 3 possibilities for the second position, 2 possibilities for the third position, and 1 for the last position (4x3x2x1=24).
Many automobile license plates are combinations of three letters and three numbers. If three letters are displayed first followed by three numbers without any repetition, how many total number of different plates are possible? There are 11,232,000 possible plates: 26 x 25 x 24 x 10 x 9 x 8. In other words this number counts all 3permutations of 26 letters followed by all 3 permutations of 10 digits.
The study of permutations began in ancient times. The number of ways of arranging an n number of items was known to be n! for at least 2500 years.
Mathematics is the science of patterns and permutations are one of the most fundamental of all patterns. It is not surprising, therefore, that permutations occur in much of mathematics. A knowledge of permutations is necessary for understanding basic concepts of discrete mathematics and probability theory.
There are many problems whose solutions are permutations. For example, consider a machine shop that has 10 orders that require the use of its one lathe. Those orders will have to be scheduled in order to meet deadlines, have material available, and satisfy other constraints. The order in which the orders are completed is a permutation. People who do scheduling are really creating permutations.
In the generation page, you will have the choice of listing:
You choose the input value for n for the first and third options. For the second option you must also provide a value for k. Then choose the output format of the solution you wish to see. For example, if you choose to list all kpermutations of {1,2,...,n}, with input values n=3, and k=2, and with output in oneline notation, then AMOF will return all six 2permutations of {1,2,3} in oneline notation as follows:
(1,2), (1,3), (2,3), (2,1), (3,1), (3,2)The maximum allowed value of n is 20, and k cannot exceed n. To see the solution output as a permutation matrix, it is best to limit the value of n to 8 or less since it takes many browsers a long time to render many large chessboards.
All algorithms used by AMOF for generating permutations are recursive. The lexicographic algorithm is described in several computer science texts. The algorithm used for generating kpermutations was developed specifically for AMOF. The algorithm used for generating permutations by transpositions is often called the "JohnsonTrotter" algorithm, but it was discussed earlier in the works of Steinhaus and the some campanologists.
The study of permutations is a part of the grade 11 and 12 math curriculum in British Columbia. The intended outcome is for students to learn how to compute the number of permutations of n things taken k at a time, and to apply the rules of permutations to solve problems. A problemsolving approach with lots of examples that are meaningful to everyday life can make learning this concept more enjoyable.
[NCTM] recommends for students who have finished second year algebra a discrete math course that includes permutations, combinations, Pascal's triangle, and recurrence relations. It also contains a useful chapter "Permutations and Combinations: a Problem Solving Approach for Middle School Students".
The concept of permutation is easily grasped by secondary school children. Try asking how many ways there are to arrange a red, a blue, and a yellow crayon in a row. You should get six as an answer, but adding a fourth color will provide a good challenge for most of them. AMOF can be used to show explicit listings of all 24 such permutations.
AMOF allows students to try many different values of n and k, and very quickly lets them see the number of possible solutions and what those solutions look like. They can test their understanding of generating permutations, and list them in lexicographic and in transposition order.
