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

"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 reachD U D

Then you turn over the 1st and 3rd glassesU D D

Finally you turn over the first two glasses againD D 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 facingU U U

and no matter what he tries he can't get them all mouth-up in exactly three moves.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 |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 transpositions 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 11 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 transpositions 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

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.

- The numbers either before both
**x**and**y**or after both**x**and**y** - The numbers between
**x**and**y**. **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 no one 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.

Permutation Groups

Back to the Index

© 1998 by Arfur Dogfrey