Various ways to define a permutation

Permutation of the set N_n is a 1-1 correspondence from N_n onto itself. Let f be such a permutation. The fact that it's onto means that for any kN_n there exists iN_n such that f(i) = k.

One way to represent a permutation f is by listing its values at i = 1,...,n: {f(1),f(2),...,f(n)}. It would not be incorrect but rather inappropriate to use vector notations (f₁,...,f_n) because, say, vector addition of two permutations is unlikely to be 1-1. A more explicit way to present a permutation is to use a two row table (a row per a copy of N_n.) We shall always assume that the elements of the upper row correspond (via f) to the elements in the lower row. However, this fact may be expressed in three different ways:

1. The upper row appears in its natural order: 1,...,n. Element f(i) appears directly below i. I call this a straight presentation.
2. The upper row appears in its natural order; so does the lower row. Straight lines connect i to f(i).
3. The lower row appears in its natural order. The upper row is ordered in such a manner as to have all the links between the elements vertical. This is a straight upside down presentation. In this case, the upper row is actually {f ^-1(1),...,f ^-1(n)} and thus presents the inverse permutation of  f.

In the applet, every permutation is also presented as a product of cycles. For every permutation {f(1),f(2),...,f(n)} we may also define a list of inversions (a₁,...,a_n), where a_i is the number of elements greater than i and located (in {f(1),f(2),...,f(n)}) to the left of i. for example, (2,3,6,4,0,2,2,1,0) is the list of inversions of {5,9,1,8,2,6,4,7,3}. A remarkable fact discovered by Marshall Hall, Jr. in 1956 is that the list of inversions uniquely represents the corresponding permutation. You may start reconstructing f from (2,3,6,4,0,2,2,1,0) in the following manner:

In a table of inversions the last element a_n is always 0. For there is no element greater than n and, therefore, no element greater than n may be found to the left of n. a_n-1 may be either 0 or 1 depending on how (n-1) is placed relative to n. a_n-2 may be either 0,1, or 2 ((n-2) is to the left of both n and (n-1), between them, or to their right.) Continuing in this manner we may surmise that a_i's are indeed independent and the total number of different inversion tables is 1·2·3·...·n = n! as expected.

for (int i = n; i > 1; i--)
{
    r = (int)(Math.random()·i);
    copy = Value[i];
    Value[i] = Value[r];
    Value[r] = copy;
}

Remark: there is another auspicious representation of permutations. If all the elements are placed on a circle then arrows may point from an element to its image. An entertaining shuttle puzzle leads to a presentation of permutations as a product of transpositions that are useful in investigating Sam Loyd's Fifteen among others.

Reference

1. A.Angel, Exploring Mathematics with Your Computer, MAA, 1993
2. D.E.Knuth, The Art of Computer Programming, v3, Addison-Wesley, 1973

Copyright © 1996-2008 Alexander Bogomolny