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:

  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.


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 http://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 (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

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

Permutations

  • Transpositions
  • Groups of Permutations
  • Sliders
  • Puzzles on graphs
  • Equation in Permutations

    |Contact| |Front page| |Contents| |Algebra| |Up| |Store|

    Copyright © 1996-2017 Alexander Bogomolny

  •  61173634

    Search by google: