# 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 _{n}_{n}

One way to represent a permutation f is by listing its values at _{1}, ... , f_{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 and thus presents the^{ -1}(1), ..., f^{ -1}(n)}*inverse*permutation of f.

What if applet does not run? |

In the applet, every permutation is also presented as a product of cycles. For every permutation _{1}, ..., a_{n}),_{i} is the number of elements greater than i and located (in

Write 9. Since a_{8} = 1, 8 stands to the right of 9. Since _{7} = 2,_{6} = 2,_{5} = 0,

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-2} may be either 0, 1, or 2 _{i}'s are indeed independent and the total number of different inversion tables is

Now, every time you press the Reset button the program produces a new permuation. I borrowed an algorithm from [Angel>]. Assume unperturbed set

```
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

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

Copyright © 1996-2018 Alexander Bogomolny

63587085 |