container 1 2 3 4 5 before: white blue red yellow green after: yellow green red white blueThis means that the white ball moved from container 1 to container 4, the blue from 2 to 5, the yellow from 4 to 1, the green from 5 to 2. The red ball in 3 is left there (fixed) This "movement" can be defined by the following table of two rows: [5.1]
1 2 3 4 5 4 5 3 1 2This table is called a permutation of length 5 in the form of two rows An important fact is that a permutation does not depend on what the objects are. It merely says how to re-arrange five objects. Five different pictures could be on 5 pieces of paper could be the objects. Then the pictures are taken out of the five containers, and put back into the containers according to the table, what was in contaier 1 is moved to container 4, what was in container 2 is moved to container 5, 4 to 1 and 5 to 2. Five different cars could be parked in grarages numbers 1,2,3,4,5. They could taken out and rearranged according to the above permutation.
[5.2] This can be written in the vertical arrow notation:
In general for n containers marked 1,2,...,n, a permutation of length n tells how to move n objects already in n containers back into the same n containers.
[5.1a] A permutation of length n is a one-to-one correspondence between a finite set of n distinct elements and itself.
An equivalent definition is the following: [5.1b] A permutation of length n is a non-singular transformation on a finite set of n elements.
In many situations the permutations act on the set Pn = {1,2,...,n} of the first n positive integers. This is because any finite set of n distinct elements, by definition, is in a one-to-one correspondence with Pn, and the action on that finite set can be "transferred" to Pn. In the opening example the containers were labeled 1,2,3,4,5 and not a,b,c,d,e, or with some other symbols. If a desk, lamp, sofa, chair, table in a room are to be rearranged, then positive integers 1,2,3,4,5 can be attached to these objects.There are a few situations where the set Jn = {0,1,2,...,n-1} integers mod n is more convenient to use.
It goes almost without saying that equal permutations have the same length, and move the objects in the containers 1,2,...,N into the same containers. The two row table for equal permutations is the same for both. Also the one row table is the same for both. 4 5 3 1 2 and 4 5 3 1 2 are equal permutations. The top row is always the first positive integers in order: 1 2 3 4 5 ... and need not be written. This notation is called a permutation in the form of an array. It is the most convenient form for entry to a computer as data. It also uses the least space in a data file.
The permutation
1 2 3 4 5 6 7 8 4 2 7 1 8 6 3 5leaves 2 and 6 fixed. While other objects "move" about, objects in containers 2 and 6 "stay in" or are returned to their containers: 2->2, 6->6. A permutation leaves an object in container x fixed if the object is returned to container x after the permutation has taken effect. In the spirit of omitting the objects as much as possible in discussions. it will be said that a permutation leaves an integer fixed if the permutation does not move the object in container x to any another container.
When a permutation of length N is written as two rows of integers, the top row consists of the first N integers in normal order 1,2,3,...,N. Often it can be omitted, and just the bottom row is given: 4 2 7 1 8 6 3 5. When needed the top row is easily written over the integers. The length of the permutation is also obvious. In these discussions it is called the permutation in the form of a single row of integers.
In a permutation the integers are separated by spaces. In a non-mathematical listing they are separated by commas. 3, 2, 4, 1 and 3, 5, 7, 6, 1, 2, 4 are listings of the mixed up integers of the above permutations.
Regular plane geometric figures provide interesting applications of permutations.
The adjoining figure shows two congruent equilateral triangles. At the vertices of both are the containers marked 1,2,3 in the fixed places. Both triangles have vertices A,B,C.
For the left triangle its vertices are in containers 1,2,3. The following permutation of length 3 has changed the contents of the containers:
1 2 3 2 3 1The contents of container 1 is moved to the container 2, the contents of container 2 is moved to container 3, and the contents of container 3 is moved to container 1, all done simultaneously. The movement actually moves the entire triangle, rotating it through 120°.
The rotation could be summarized as A -> B -> C -> A. But this shortened form does not show how the permutation, defined with integers, causes this rotation. It would be better to erase the letters and containers, and keep the container numbers as vertices. Then 1 -> 2 -> 3 -> 1, where -> means "moves to."
If the permutation is applied again, then the triangle is rotated through another 120°. Click here for more discussions of more geometric applications of permutations.
The permutation:
1 2 3 4 5 6 7
3 5 7 2 6 1 4
"moves" integers as follows:
1 -> 3, 2 -> 5, 3 -> 7, 4 -> 2, 5 -> 6, 6 -> 1, 7 -> 4Re-arrange these so that on both sides of each comma, the two integers are identical::
1 -> 3, 3 -> 7, 7 -> 4, 4 -> 2, 2 -> 5, 5 -> 6, 6 -> 1This can be shortened into:
1 -> 3 -> 7 -> 4 -> 2 -> 5 -> 6 -> 1The notation stops at 1 because any steps further would repeat 3,7,4,2,5,6,1. It is customary to write this as:
(1 3 7 4 2 5 6)It is understood that the last integer 6 is moved into the first integer 1. This notation is called cyclic notation of a permutation. It could be written outside and around a circle. The above forms one cycle of seven integers.
The permutation:
1 2 3 4 5 6 7 4 6 5 2 3 1 7This permutation is made up of three cycles: 1->4->2->6->1, 3->5->3, 7->7. In cyclic notation the permutation can be written as:
It is often convenient to have a name of a permutation. Let P be such a name of an above permutation. The notations for P are:
P: 4 6 5 2 3 1 7 (single row notation) P: 1 2 3 4 5 6 7 (two row notation) 4 6 5 2 3 1 7 P: (1 4 2 6)(3 5) (cyclic notation)Notice that parentheses distinguish the cyclic notation from the single row notation.
Intuitively speaking, equal permutations do the same things, they carry the same object out of the same container into the same container. Let P and Q be permutations of length 5. P = Q means
(1)P = (1)Q and (2)P = (2)Q and (3)P = (3)Q and (4)P = (4)Q and (5)P = (5)Q. Obviously this definition of equality can be extended to permutations of any finite length N. Just confirm (x)P = (x)Q for x = 1,2,3,...,N.
There is a special permutation for each length N, that leaves each integer fixed. It will be given the name IN.
I1: 1
I2: 1 2
I3: 1 2 3
.......
IN: 1 2 ... N
In cyclic notation, IN: (1)
The reason for the name "identity" will be made clear in Chapter 3. If there is no ambiguity the subscript on IN usually will be omitted.
In these discussions the idea of adjacent permutations is introducd. Two permutations (of the same length) are adjacent if either permutation can be obtained from the other by a simple interchange of two integers. The symbol ~ means "adjacent to" For example, .permutations P ~ Q defined by
P: 1 2 5 3 4 Q:1 2 4 3 5are adjacent because either permutation is obtained from the other by interchanging the integers 3 and 5. For permutation
R: 2 1 5 3 4it is easily verified that R ~ P ~ Q ~ I. By three interchanges R becomes I. Count the symbols ~. Comparing the two permutations, it is seen that Q leaves more integers fixed than P does. Intuitively speaking Q is closer to the identity permutation I: 1 2 3 4 5. In fact Q is adjacent to I, but P is not adjacent to I.
A path between two permutations (which may be the same) is a chain of adjacent permutations of the same length joining the two permutations.
Example R ~ P ~ Q ~ I shown above.
Theorem. Any path joining a permutation and itself always contains an even number of (adjacent) permutations.
This theorem is assumed here without proof. It applies to the identity permutation. It allows the following definition to be unambiguous.
A permutation is odd if there is a path of an odd number of adjacent permutations between it and the identity permutation. A permutation is even if there is an even number of adjacent permutations in the chain.
Suppose there are two different paths betwen a permutation P and the identity permutation I. If one path contains an even number of adjacent permutations and the other path contains an odd number, then it is possible for the identity permutation to have a path of an odd number of adjacent permutations joining the identity permutation with itself. This contradicts the theorem.
This means that any permutation is even or odd. It can be tested by constructing a path to the identity permutation and counting the number of ~ marks. In particular the Identity permutation is even, because any two integers in it can be interchanged to get an adjacent permutation, and interchanging them again gives another adjacent permutation, which is the identity permutation:
1 2 3 4 5.... N ~ 2 1 3 4 5...N ~ 1 2 3 4 5...NThere are two ~ marks, and two is even. Click here for more examples of determining whether any given permutation is even or odd..
For any positive integer N a computer program (to run it click here) produces a path from the identity permutation (of length N) back to itself. The following is a printout for length N=4 ( the first identity permutation is not in the printout, but supplied here to show the complete path:
1 2 3 4,
2 1 3 4, 2 3 1 4, 2 3 4 1, 3 2 4 1, 3 2 1 4, 3 1 2 4, 1 3 2 4, 1 3 4 2, 3 1 4 2, 3 4 1 2, 3 4 2 1, 4 3 2 1,
4 3 1 2, 4 1 3 2, 1 4 3 2, 1 4 2 3, 4 1 2 3, 4 2 1 3, 4 2 3 1, 2 4 3 1, 2 4 1 3, 2 1 4 3, 1 2 4 3 , 1 2 3 4
An enumeration of permutations of length N is a listing of all permutations of length N without repeats. The order of the permutations in the enumeration is any order. It happens that the above listing, excluding either the first identity permutation 1 2 3 4 or the last, is an enumeration of permutations of length 4. The above enumeration is called in these discussions the odd-even enumeration. For a lexicographical (alphabetical) enumeration click here.
A different enumeration is given here because it gives some information about constructing an enumeration. From an enumeration of permutations of length N-1 it is possible to construct an enumeration of permutations of leng N.
[1] For N=1, there is only one permutation: 1
[2] For N=2, there are two permutations: 1 2 and 2 1
[3} For N=3, six permutations: 1 2 3, 2 1 3, 1 3 2, 2 3 1, 3 1 2, 3 2 1
[4] For N=4, twenty-four arrangements:
1 2 3 4, 2 1 3 4, 1 3 2 4, 2 3 1 4, 3 1 2 4, 3 2 1 4
1 2 4 3, 2 1 4 3, 1 3 4 2, 2 3 4 1, 3 1 4 2, 3 2 4 1
1 4 2 3, 2 4 1 3, 1 4 3 2, 2 4 3 1, 3 4 1 2, 3 4 2 1
4 1 2 3, 4 2 1 3, 4 1 3 2, 4 2 3 1, 4 3 1 2, 4 3 2 1
If we have all six permutations for N=3, then attach a 4 to the end of all six to get the first row for N=4. Then place a 4 in the next to last position and let the six permutations for N=3 "flow" around the 4 two integers before 4 and one integer after it. This produces the second row. Place 4 in the second position, and let the six permutations for N=3 flow about 4 to get the third row. Finally to get the last row place 4 in the first position and let the six permutations for N=3 occupy the remaining three positions after 4.
To enumerate all permutations of length five, place 5 after each permutation in N=4, then in put it in the next to last position and let the permutations in N=4 flow around the 5... etc. Note: the permutations in these enumerations (of lengths N>2) are not adjacent. For N= 1,2,3,4, the enumerations produce 1,2,6,24 permutations. For N=5, the integer 5 will occupy 5 positions, and the permutations for N=4 will flow in the empty positions. Therefore there will be 24x5 = 120 permutations for N=5.
In general for N=1,2,3,4,5,6,... there are 1, 1x2, 1x2x3, 1x2x3x4, 1x2x3x4x5, 1x2x3x4x5x6,... enumerations. It is common to let N! = 1x2x3x...xN. N! is called
N! = number of all permutations of length N.
Here is a list of values of some factorials:
The values of factorials grow fast. The list here ends at the evaluation of 13! for two reasons. Many home and school computers cannot compute 14! or higher without special tricks of programming. Moreover, the computation of all permutations of a large length demands much time on a home computer, some even years. For a very large length it may require more than a billion years to enumerate all the permutations!
1!=1, 2!=2, 3!=6, 4!=24, 5!=120, 6!=720; 7!=5040; 8!=40320, 9!=362880; 10!=3628800,
11!=39916800, 12!=479001600, 13!=1932053504