[AMOF] [GENERATE] [Schoolnet Icon]


Information on Permutations

[Description | Example | History | Applications | Implementation | Classroom | Links]


Description of the Problem

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 k-permutation 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·(n-1) ···(n-k+1) = n!/(n-k)!.

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 non-taking rooks on a chessboard. Recall that a rook can take a piece that is in its same row or column. In a k-permutation 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.

Lexicographic Order

In lexicographic order, the permutations are listed in numeric or dictionary order: 12...n is first and n...21 is last. Here are the permutations of {1,2,3} listed in lexicographic order: 123, 132, 213, 231, 312, 321.

Transposition Order

In transposition order two successive permutations (including the first and last) differ by the transposition of two adjacent elements. Here are the permutations of {1,2,3} listed by adjacent transpositions (for n = 3 there are exactly two such lists, one the reversal of the other): 123, 132, 312, 321, 231, 213. The figure below indicates the movement of elements in the algorithm when n = 5. Notice how the light blue line, which represents element 5, sweeps back and forth. This is indicative of the general recursive construction in which the largest element n sweeps back and forth in the list of permutations of {1,2,...,n-1}. In AMOF output in one-line notation element n is printed in red.

[Johnson-Trotter

Example

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 3-permutations of 26 letters followed by all 3 permutations of 10 digits.


A Brief History

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.


Applications to Mathematics and other Areas

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.


Explanation of AMOF Implementation

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 k-permutations of {1,2,...,n}, with input values n=3, and k=2, and with output in one-line notation, then AMOF will return all six 2-permutations of {1,2,3} in one-line 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 k-permutations was developed specifically for AMOF. The algorithm used for generating permutations by transpositions is often called the "Johnson-Trotter" algorithm, but it was discussed earlier in the works of Steinhaus and the some campanologists.


In the Classroom

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 problem-solving 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.


Links to Other Relevant Sites and Sources of Information


[AMOF] [GENERATE] [Schoolnet Icon]


This page created by Frank Ruskey and Susan Ruskey, June 1996. © Frank Ruskey and Susan Ruskey, 1996.