Permutation Library 1.0E. D. Rivlis © 19971998Download the library.
1. Introduction1.1 What are permutations?
This library deals with permutations. As far as I know it is unique. To
understand permutations one can see them as simple functions of integers. Let A be the
permutation so that
One can easily see that indices for 6 7 8 9 etc. are not really needed to represent the permutation.It's obvious that for any finite permutation exists a interger j such as that for all j < i A(i) = i. It is customery only to reffer to all the i such as 1 < i < j. So we are left with:
/ 1 2 3 4 5 \ But we don't really need the upper indices / 1 2 3 4 5 \ too, because they are just the ordered integer between 1 and i1. And at last we are left with \ 2 5 4 1 3 / or {2 5 4 1 3}.
1.2 Cycles Another way to represent a permutations is a cycle. Look at the following statement: 1 > A(1) = 2 > A(2) = 5 > A(5) = 3 > A(3) = 4 > A(4) = 1 We got a cycle! We can write it in a more compact fashion as {{1 2 5 3 4}}
Let's look at another permutation B = {2 1 3 5 4}. Remember that it means that 1 > B(1) = 2 > B(2) = 1 What now? lets continue. 3 > B(3) = 3 and 4 > B(4) = 5 > B(5) = 4 We got three different cycles! The total cycle is then {{1 2}{3}{4 5}} (now you understand why one uses {{ }} ).
1.3 Composite permuation
What will happen if we'll make a composite function from A and B?
C(1) = B(A(1)) = B(2) = 1 it's really simple then, BA = C = {1 4 5 2 3}, and the cycle is {{1}{2 4}{3 5}}. But what happens if we use B and then A? well...
D(1) = A(B(1)) = A(2) = 5 so AB = D = {5 2 4 3 1}, and the cycle is {{1 5}{2}{3 4}}. This result shows that AB dosn't have to be equal to BA.
1.4 Inverse permutation We'll define now a new permutation M in the following way:
A(M(i)) = i so M = {4 1 5 3 2} while the cycle is {{1 4 3 5 2}}. M is called the inverse permutation of A. From the definition it's easy to see that AM = MA = {1 2 3 4 5}, which is the identity permutation.
2. The FunctionsThe Greek letters (Sigma) and (Tau), are commonly used as symbols of permutations. The library contains the following operators:
