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.

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.

An old bar bet involves three glasses on the bar. They are in a row in front of the sucker -- er, I mean client, but the first and third glasses are mouth-down on the bar. Let "D" stand for a mouth-down glass and "U" stand for a mouth-up glass. Then the client sees the following row of glasses:

            D U D

            U D D

            D D U

            U U U

            U D U

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 |

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 |

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 |

If the grand total is an odd number then the permutation is of odd parity. If the grand total is an even number then the permutation is of even parity.

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.

Each number in the string of numbers can affect the grand total in two ways. First when it is the number we're using to count how many smaller numbers are beyond it and second when it is one of the numbers "beyond" whatever number we're using to count how many smaller numbers are beyond.

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.

1. The numbers either before both x and y or after both x and y
2. The numbers between x and y.
3. x and y.

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.

Back to the Index:

© 1998 by Arfur Dogfrey