Definition of Permutation
- Permutation is an order arrangement of a group of objects.
permutations examples:
- Suppose Amy, Brian, and Charles are to sit side by sides. There are 6 different types of orders in which they can be arrange themselves.
ABC, ACB, BAC, BCA, CAB, CBA each of these permutation are different from the others.
More about Permutation.
More about Permutation
- The permutation of the n objects taken r at a time is represented as nPr.
- The permutation or the arrangement of 9 different types of balls in 3 different rows can be done in 9P3 = 504 ways.
- The permutation of n objects taken all at a time is represented as nPn = n!.
- Factorial:
- Factorial means the series of multiplications from 1 up to some number. An exclamatory symbol (!) indicates a factorial.
For example,
- 3! means 3 × 2 × 1.
- 7! = 7 × 6 × 5 × 4 × 3 × 2 × 1
permutations examples:
Find the number of the 7-letter permutation from a letters of the word FORMULA.
Choices:
A. 5,040
B. 7
C. 1
D. 49
B. 7
C. 1
D. 49
Correct Answer: A
Solution:Step 1: The number of the letters in the word FORMULA is 7.[Writen the number of letters of the word.]
Step 2: The number of 7 letter permutations is the 7 distinct letters of the word is 7P7 = 7! = 5,040. [nPn = n!.]
Step 3: The number of the 7 letter permutations from the 7 distinct letters is the word FORMULA is 5,040.
Step 2: The number of 7 letter permutations is the 7 distinct letters of the word is 7P7 = 7! = 5,040. [nPn = n!.]
Step 3: The number of the 7 letter permutations from the 7 distinct letters is the word FORMULA is 5,040.
Introduction to Permutation Matrices:
Matrices, though they may appear unearthly objects at first, are a very important tool in expressing and discussing problems which arise from real life cases. Matrices find applications in almost every branch of science, engineering, economics, probability, theory, and statistics to mention a few. The aim of this section is to know the permutation of matrices.
Permutation of a Matrix:-
The real and complex numbers are the possible elements in the matrices, the valued functions involves the real and complex numbers. Matrices are done through the brackets. The matrices can be denoted by capital letters like A, B, C. M are denoted as rows and N is denoted as columns. Then the form of the matrices will be M*N.
In the below example, A is of form of the matrices are 2*2.
Example:
A =
A permutation matrix is in which each column and row has one 1 compulsory. In addition, the matrix should be square matrix.
Properties of Permutation Matrices:
1) A matrix is made to multiply with a permutation then the matrix obtained will be a permutation.
2) The identity matrix and permutation matrix are the similar matrices.
3) Also 2x2, 3x3 identity matrices are also preffered as permutation matrix.
4) All types of I elementary matrix are multiplied and the values are known as permutation matrices.
5) Every results of the product of I elementary matrices are known as permutation matrices.
6) The transpose of the permutation matrices is nothing but the inverse of the permutation matrix. pT=P-1
Properties for Permutation Matrix:
1. |A| |B| = |AB|
2. |AT| = |A|
3. |A-1| = 1 / |A|
4. | I | = 1
5. Don’t even try to find a formula for |A+B|.
---------------------------------------------------------------------------------------------------------
The "old shell game" is an example of a permutation. Three shells, one containing a pea, are in a row in front of the sucker -- er, I mean, client. The operator then changes the order of the shells and challenges the client to tell which one contains the pea. The changing of the order constitutes a permutation. In the shell game there are 6 possible permutations. The operator may do nothing. This would be the identity permutation where shell 1 stays in its position, shell 2 stays in its position and shell 3 also stays in its position. We can notate this permutation as
| 1 2 3 |
| 1 2 3 |
The top row of numbers indicates the starting position of a shell. The bottom row indicates the final position of the shell. Thus to find where an object went under a permutation look up its number in the top row and its final place will be under that number. Thus if the shell-game operator switches shells 1 and 2 we can notate this permutation by
| 1 2 3 |
| 2 1 3 |
Shell 1 went to the place formerly occupied by shell 2 (the 2 in the bottom row is below the 1) and shell 2 went to the place formerly occupied by shell 1 (the 1 in the bottom row is below the 2). Since there are six different orders that the numerals "1, 2" and "3" can be ordered in the bottom row [the 1 2 3 in the top row is fixed] there are 6 permutations of 3 objects.
The main reasons for interest in permutations are
- They form a group when we use the operation "followed by."
- Understanding them helps to solve Rubik's Cube.
- There is a theorem due to Arthur Cayley that says that every group is isomorphic to a permutation group.
- Permutations are everywhere whether we know it or not.
For a given set the permutations on it form a group with the operation followed by. This is because (a) permutations are closed under the operation followed by, (b) since the operation is "followed by" it is associative, (c) the "leave everything where it is" permutation is the identity and (c) every permutation can be undone by "running the film backwards" thus all permutations have inverses. In a Cayley table for a group each element appears exactly once in each row and exactly once in each column (Latin square property). This is a "pictorial" representation of the cancellation property. If I take a group element a and multiply it on the right to every element of a group I'll get all the elements of the group back again. For any element x of G x • a will be in G (This is just the closure property).
Furthermore any element of G will be one of the x • a's since for any b in G the equation x • a = b has a solution. Thus multiplication on the right by a permutes the elements of G. What if we were to first permute the elements of G by multiplying on the right by a followed by multiplying on the right by b? That would give us a new permutation which would (by the associative property) be the same as multiplying on the right by a • b.
Thus each element of G corresponds to a unique permutation of the elements of g. And the permutation corresponding to the product of two elements of G is the composition under followed by of the permutations corresponding to the two elements singly. This fits the definition of an isomorphism. Thus every group is isomorphic to a permutation group. This result is known as Cayley's Theorem.
Rubik's Cube and similar puzzles are examples of permutation puzzles. The challenge is to form a certain permutation from the composition of a limited set of permutations. The permutation you are challenged to find is the one that permutes everything into the solved state. Exactly which permutation that is depends on the initial state. We will have much more to say concerning Rubik's Cube in a later chapter.
D U D
"The object of the game," you tell him, "is to get all the glasses mouth-up in exactly three moves. A move consists of turning two glasses over together, one in each hand." Then you demonstrate by turning over the first two glasses to reach
U D D
Then you turn over the 1st and 3rd glasses
D D U
Finally you turn over the first two glasses again
U U U
All very clean and simple. You now turn over the middle glass and bet your "friend" that he can't do what he just saw you do. He, having had a few drinks, pulls out his wallet and bets you. He begins facing
U D U
and no matter what he tries he can't get them all mouth-up in exactly three moves. The secret of the trick is parity. The number of mouth-up glasses is either even or odd. Turning over one glass will change the number of mouth-up glasses from odd to even or else from even to odd since you will be either adding a mouth-up glass or subtracting a mouth-up glass. In the game you must turn over two glasses simultaneously and therefore the parity, either odd or even of the number of mouth-up glasses does not change. Now the desired final position has 3 (an odd number) of mouth up glasses. The trick is that you start with 1 (an odd number) of mouth-up glasses but you have your "friend" begin with 2 (an even number) of mouth up glasses. He can't win.
Permutations also have a parity which is changed by a transposition. A transposition is a permutation which exchanges the place of two objects whilst leaving all the other objects unmoved. Thus
| 1 2 3 4 5 |
| 1 5 3 4 2 |
is a transposition as it swaps elements 2 and 5 and does not change the positions of 1, 3 and 4. An important fact is that any permutation on n objects can be done with a series of transpositions. It is a further fact that if it can be done in an even number of permutations then it can't be done in an odd number and vice versa. Theorem: Every permutation is equivalent to a product of transpositions.
Proof: A simple way to see this is to think of how you might reorder a dozen eggs in an egg carton. Suppose the eggs were numbered 1 to 12. If you were given a permutation of the eggs and told to rearrange the eggs into that permutation you might begin with the first place in the egg carton, find the numbered egg that went into that place and traded the egg in the first place with the egg that belonged there. Repeat this process with the second place then the third place etc. After a minimum of 11 transpositions you would be done. (Why a minimum of ll and not 12?)
The same could be done with any permutation on n objects. First note the object that 1 goes to. If necessary exchange it for object 1. Next note the object that 2 goes to. If necessary exchange it for object 2 etc. After, at most, n-1 such transpositions you will have the desired permutation.
[Exercise: Use the above procedure to express the permutation
| 1 2 3 4 5 6 7 8 |
| 4 5 6 3 8 7 1 2 |
as the product of transpositions.] The second fact is that if a permutation can result from an odd number of transpositions then it can't result from an even number of permutations and vice versa. To see this we will define the parity of a permutation: For each element count up the number of elements that were before it in the order before the permutation which are after it after the permutation has been applied. For instance in the permutation
| 1 2 3 4 5 6 7 |
| 1 4 6 3 5 2 7 |
there are no elements before 1 before the permutation so the total for 1 is zero. There are two elements after 4 that were before 4 to begin with, namely 2 and 3 so the total for 4 is 2. Continuing in this manner we find that the total for 6 is 3, the total for 3 is 1, the total for 5 is 1, the total for 2 is zero, and the total for 7 is zero. Adding up these totals we get a grand total:
7 is an odd number so the example is an odd permutation. If you apply any transposition to this permutation you will end up with an even permutation. (Try it!).
Why is this so? Why does each transposition change the parity of a permutation? Let's look at what a transposition does to the parity. Let the following represent an ordering of the n numbers 1 to n.
Now if we exchange elements labeled x and y how will the parity of the grand total change? Let's break up the numbers into three groups.
- The numbers either before both x and y or after both x and y
- The numbers between x and y.
- x and y.
The same numbers will be before and after the numbers in group 1 so their contribution to the grand total will not change. The numbers in group 2 will each contribute to the grand total twice once for the change in x's position (either they were less than x or x was less than them.) and again for the change in y's position. Thus their total contribution will be to change the grand total by an even number. This will not affect the parity of the permutation. Finally, x and y switching places will add or subtract 1 from the grand total depending on whether x or y is greater. Thus the parity of the grand total (odd or even) will change. Now we are in a position to appreciate Samuel Loyd's famous challenge with his 14-15 puzzle back in the 1800's. The puzzle consisted of 15 sliding tiles in a square frame with an empty space which a tile could slide into. The tiles were numbered from 1 to 15. The task was to get the tiles into the normal order:
| 1 | 2 | 3 | 4 |
| 5 | 6 | 7 | 8 |
| 9 | 10 | 11 | 12 |
| 13 | 14 | 15 | . |
Sliding a tile into the empty space is equivalent to a transposition of the moved tile and the "ghost" tile in the empty space. Thus every move is a transposition. (read the numbers from right to left, top row to bottom to get the permutation).
Sam Loyd offered $1000 to any one who could find a way to solve the puzzle from the position shown below.
| 1 | 2 | 3 | 4 |
| 5 | 6 | 7 | 8 |
| 9 | 10 | 11 | 12 |
| 13 | 15 | 14 | . |
Note that this is a transposition away from the solution. However it is impossible to solve from this position since it would take an odd number of transpositions to go from the 13-15-14 position to the solved 13-14-15 position. But the empty square can only return to the lower right-hand corner after an even number of moves. The simplest way to see this is to imagine a checkerboard pattern of light and dark squares painted beneath the tiles. Then each move would change the color of the background square that is showing from light to dark or from dark to light. Loyd sold a pavillion of the puzzles to suckers -- er, I mean puzzle fans eager to win the prize. He reported that
A prize of $1,000 offered for the first correct solution to the problem, has never been claimed, although there are thousands of persons who say they performed the required feat. People became infatuated with the puzzle and ludicrous tales are told of shopkeepers who neglected to open their stores; of a distinguished clergyman who stood under a street lamp all through a wintry night trying to recall the way he had performed the feat. The mysterious feature of the puzzle is that none seem to be able to remember the sequence of moves whereby they feel sure they succeeded in solving the puzzle. Pilots are said to have wrecked their ships, and engineers rush their trains past stations. A famous Baltimore editor tells how he went for his noon lunch and was discovered by his frantic staff long past midnight pushing little pieces of pie around on a plate!
A particularly insidious version of the puzzle has letters on the tiles instead of numbers. One of its "solved" configurations is
| R | A | T | E |
| Y | O | U | R |
| M | I | N | D |
| P | A | L | . |
Notice that there are two 'R's and two 'A's. If the "wrong" 'R' and 'A' are used to begin the word "RATE" it will be impossible to get the "PAL" to come out correctly in the last row. With this version the group theorist "bets" the sucker -- er, I mean friend, that although the friend is accomplished at solving the 13-14-15 puzzle the use of letters rather than numbers will throw him off psychologically. The group theorist mixes up the tiles in front of the friend's eyes but leaves the 'R' in the upper left-hand corner in place while taking the 'A' next to it far down to the lower row. At the same time the 'A' in "PAL" is transferred near the upper left-hand corner. The friend is given a time limit to solve the puzzle. If he uses the 'R' and 'A' together that the group theorist has so kindly put almost into place for him he cuts his own throat. To solve the puzzle with the 'R' and 'A' as given is equivalent to making a transposition of the 'A's. As we now know, this is not possible.
