Info on Permutations

Information on Permutations

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

The number of permutations for n = 1,2,...,10, is 1, 2, 6, 24, 120, 720, 5040, 40320, 362880, 3628800; these, of course, are the factorial numbers n! = n···2·1. This is sequence A000142(M1675) in Neil J. Sloane's database of integer sequences.

Every permutation of [n] corresponds to a unique permutation matrix; that is, a 0-1 matrix 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. As an example, the configuration shown below corresponds to the permutation 543621.

We generate permutations in 2 different orders.

Lexicographic Order

In lexicogrphic order, the permutations are listed in numeric 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. The algorithm used is often called the "Johnson-Trotter" algorithm but it was discussed earlier in the works of Steinhaus and the campanologist ???. 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 (reading left-to-right). 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 recursively constructed list of permutations of {1,2,...,n-1}. The blue and green lines, representing 1 and 2, swap positions only once, at the center of the figure.

Young Tableau

A standard Young tableau of shape r₁ >= r₂ >= ··· >= r_m > 0, where r₁ + r₂ + ··· + r_m = n, is an arrangement of the integers 1,2,...,n into m rows, with the i-th row containing r_i elements. The rows are left justified, the numbers increase along rows, and the numbers increase down the columns. The illustration below shows two tableau, both of shape 3,1,1.

1	4	5
2
3

1	3	4
2
5

To every permutation there corresponds in a natural way a pair of tableau, both of the same shape. The two tableau above are the ones corresponding to the permutation 32451. This correspondence is known as the Schensted correspondence and is explained in many combinatorics texts. See, for example, Knuth vol. 3 Sorting and Searching, or Stanton and White, Constructive Combinatorics (Section 3.6, pg. 85-87).

There is a fascinating connection between lists of permutations and the art of Bell Ringing known as Campanology. Here is a collection of web pages connected to bells and ringing.

Programs available:

Permutations in lexicographic order: Pascal program . C program .
Permutations by transpositions (Steinhaus-Johnson-Trotter algorithm): (Pascal program ) (C program ).

Questions?? Email The wizard of COS.

(Please note that the suffix XXXX must be removed from the preceeding email address.)
It was last updated Wednesday, 10-May-2006 10:32:14 PDT.
There have been 24859 visitors to this page since May 16, 2000 .
©Frank Ruskey, 1995-2003.