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 k ∈ N_n there is i ∈ N_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.) I 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:

The upper row appears in its natural order: 1, ..., n. Element f(i) appears directly below i. I call this a straight presentation.
The upper row appears in its natural order; so does the lower row. Straight lines connect i to f(i).
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.

This applet requires Sun's Java VM 2 which your browser may perceive as a popup. Which it is not. If you want to see the applet work, visit Sun's website at https://www.java.com/en/download/index.jsp, download and install Java VM and enjoy the applet.

What if applet does not run?

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:

Write 9. Since a₈ = 1, 8 stands to the right of 9. Since a₇ = 2, 7 stands to the right from both 8 and 9. Since a₆ = 2, 6 is to the right of only two of the numbers we already considered. Thus we get 9 8 6 7. Since a₅ = 0, it becomes the leftmost so far: 5 9 8 6 7, etc.

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.

Now, every time you press the Reset button the program produces a new permuation. I borrowed an algorithm from [Angel>]. Assume unperturbed set {1, ..., n} is stored in the array Value whose indices range from 1 through n. Going backwards, one swaps a Value with another one randomly selected among preceding items in the array.


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

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

Permutations

Various ways to define a permutation
Counting and listing all permutations
Johnson-Trotter Algorithm: Listing All Permutations

Transpositions

Groups of Permutations

Sliders

Puzzles on graphs

Equation in Permutations

71940108