## 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_{1} >= r_{2} >=
··· >= r_{m} > 0,
where r_{1} + r_{2} +
··· + 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.

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:

**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 9493 visitors to this page since May 16, 2000
.

©Frank Ruskey, 1995-2003.