Various ways to define a permutation
Permutation of the set Nn is a 1-1 correspondence from Nn onto itself. Let f be such a permutation. The fact that it's onto means that for any k ∈ Nn there is i ∈ Nn 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 (f1, ... , fn) 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 Nn.) 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.
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 (a1, ..., an), where ai 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 a8 = 1, 8 stands to the right of 9. Since a7 = 2, 7 stands to the right from both 8 and 9. Since a6 = 2, 6 is to the right of only two of the numbers we already considered. Thus we get 9 8 6 7. Since a5 = 0, it becomes the leftmost so far: 5 9 8 6 7, etc.
In a table of inversions the last element an 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. an-1 may be either 0 or 1 depending on how (n - 1) is placed relative to n. an-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 ai'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
Transpositions
Groups of Permutations
Sliders
Puzzles on graphs
|Contact|
|Front page|
|Contents|
|Algebra|
|Up|
|Store|
Copyright © 1996-2012 Alexander Bogomolny
|
