How many permutations are there on a group of *n* objects?
Since there are *n* possible choices for the first position
and for each of these there are *n-1* choices for the second
position and for each of these *n(n-1)* ways of choosing the
first two there are *n-2* ways of choosing the object for the
third position etc. it turns out that there are *n!*
permutations on *n* objects. The set of all permutations on
*n* objects is called the **symmetric group on n objects**
and is denoted by **S**_{n}. Since the factorial grows
rather quickly **S**_{n} can be very large when *n*
is of only
moderate size. For example **S**_{10} contains
10! = 3,628,800 elements and **S**_{60} contains more
elements than the number of atoms in the universe.

Let's look at **S**_{1}. Its only element is the
permutation

| 1 | | 1 |With only one element there is only one place for it to go. Thus the group for

• | e |

e | e |

Here **e** is the permutation that changes element 1 to element 1.
It's the only permutation possible and it's group under the operation
*followed by* is a trivial one-element group. In fact, there
is (up to isomorphism) only one group with one element. Thus we've
found the structure of all one-element groups. (Big deal!)

With two elements there are two (2!) possible permutations

| 1 2 | | 1 2 | | 1 2 | = e | 2 1 | = aWith the labels

• | e | a |

e | e | a |

a | a | e |

This group has the identity **e** and a non-identity element
**a**. A little reflection on the need for (1) an identity
and (2) the cancellation rule and we realize that this table
represents all groups of two elements. Thus we've "found" the
structure of all groups of order 1 and 2. (Big deal!)

With three elements things begin to become a bit more interesting.
**S**_{3} has 3! = 6 elements. They are

| 1 2 3 | | 1 2 3 | | 1 2 3 | | 1 2 3 | = e | 2 3 1 | = a | 3 1 2 | = b | 1 2 3 | | 1 2 3 | | 1 2 3 | | 1 3 2 | = X | 3 2 1 | = Y | 2 1 3 | = ZNow if we perform permutation

If we're using the "followed by" operation we need to decide on our
notation. If **a** and **b** are two permutations does

mean that permutation **a** is performed first and then permutation
**b** is performed? Or does it mean that **b** is performed
first and then **a**? Since we read English from left to right
there is a strong reason to use the left-most element (in this case,
**a**) as the one performed first. Thus we would read **a •
b** as **a** *followed by* **b**. However in mathematics
the notation for operators and functions usually works differently.
If *f* and *g* are two functions and I *g* to act first
and then have *f* act on the result of *g*'s action then
the usual notation for this is

Thus the element which operates first (*g*) is written to the
right of the element (*f*) which operates last. We must
therefore be clear in our notation. Since both the leftmost-first and
the rightmost-first notations are used in mathematical literature
we'll have to decide which we'll use here. By a coin flip it has
been determined that we will use the "followed by" notation where
the leftmost operation is performed first. Thus **a •
b** will be read as **a** *followed by* **b**; that is,
**a** is performed first *followed by* performing **b**.

With this convention decided upon together with the convention for
Cayley tables that left element in the operation is in the column
to the left of the table and the right element is in the row along
the top of the table we get the following table for
**S**_{3}

• | e | a | b | X | Y | Z |

e | . | . | . | . | . | . |

a | . | . | . | Y | . | . |

b | . | . | . | . | . | . |

X | . | Z | . | . | b | . |

Y | . | . | . | . | . | . |

Z | . | . | . | . | . | . |

I've filled in the elements **a • X** and **X • a**
as well as **X • Y** (which equals **b**) in the table.
As an exercise the student should work out what goes in the other
33 cells of the table. The solution is given below (no peeking)

.

.

.

.

Well have you finished filling in the table yet?

If not then go back and do it. If so then continue on and check your answers.

.

.

.

.

• | e | a | b | X | Y | Z |

e | e | a | b | X | Y | Z |

a | a | b | e | Y | Z | X |

b | b | e | a | Z | X | Y |

X | X | Z | Y | e | b | a |

Y | Y | X | Z | a | e | b |

Z | Z | Y | X | b | a | e |

Does this table look familiar? It's exactly the same table as we gave for the Symmetry Group of the Equilateral Triangle. The two groups are isomorphic. This becomes clear when we realize that any symmetry movement of the equilateral triangle simply permutes the three vertices of the triangle.

[**Exercise: ** Write out the Caley tables for **S**_{4}
and **S**_{5}.]

[Just kidding! **S**_{4} would have 576 entries in its
Cayley table and **S**_{5} would have 14,400 entries.]

The Symmetric Group on n objects, **S**_{n} consists of
all permutations on the n objects. If we limit ourselves to even
permutations then we get an object called **The Alternating Group
on n Objects**. From the name you can guess that the set of
even permutations of n objects forms a group under the "followed
by" operation. In fact this is true. The fact that **e** the
identity permutation is even and that the product of two even
permutations is an even permutation as well as the fact that the
inverse of an even permutation is an even permutation makes the
Alternating Group on n Objects a subgroup of **S**_{n}.

The Alternating Group on n Objects has the symbol **A**_{n}.
And since we know that there are n! permutations (even and odd) in
**S**_{n} then there must be exactly half that many in
**A**_{n}. Or does that need to be proven? Hmmm . . .

**Theorem:** The order of **A**_{n} is half the order
of **S**_{n}.

**Proof:** The way to prove this is to find a one-to-one
correspondence between the even permutations and the odd permutations.
Since the even and odd permutations combine to make **S**_{n}
then if there are as many evens as odds the evens must be half of
the whole.

The trick is to append the transposition **(1, 2)** to the
beginning of an even permutation and thereby turn it into an odd
permutation. If this gives a one to one correspondence between
the even permutations and the odd permutations then we've done it.

But what about those odd permutations that don't "begin" with
**(1, 2)**? Actually there are many different ways to write
any permutation. Appending **(1,2)(1,2)** (which, by the way,
is the identity permutation) to the front of a permutation (or even
inserting it anywhere in the middle) will not change the permutation.
Thus any permutation can be written with **(1, 2)** at its front.

This is the correspondence we seek. Appending **(1, 2)** to
the beginning of any even permutation gives an odd permutation.
Also, we may write any odd permutation beginning with **(1, 2)**
so by removing the **(1, 2)** from the beginning gives an
even permutation. Replacing **(1, 2)** at the beginning gives
us back the odd permutation again. Thus we have found that every
even permutation corresponds to exactly one odd permutation under
this "transformation" of appending **(1, 2)** to the beginning and
every odd permutation is corresponded to by exactly one even
permutation by this method.

Using this Theorem we know now that there are exactly **3**
(half of 3!) even permutations on 3 objects.

Why are permutations so important? Let's look at that question from
another viewpoint. Let's define a *group function*. That is,
a function whose domain is the elements of a group *G* and whose
range is also the elements of *G*. Call this function *f _{a}*
where

For any other element, say **b**, of *G* we can also define *
f _{b}*(

Now we can ask ourselves, "how do these functions behave under
composition--under the operation *followed by*?" The answer
is exactly like the elements of *G* under its group operation.
To see this notice that for any element **x** of *G*

[Remember, *f _{a}*(

**Cycle Notation**

There is another notation for permutations that shows the structure of the permutation a bit more clearly. It's called "cyclic notation." It works like this. In the permutation.

| 1 2 3 4 5 | | 3 5 4 2 1 |

1 goes to 3 which goes to 4 which goes to 2 which goes to 5 which goes to 1 completing the cycle. In cyclic notation this would be written.

(1 3 4 2 5)

Where each element is followed by the one whose place it goes to. The 5 at the end goes back to the 1 at the beginning of the cycle. Now consider the following permutation:

| 1 2 3 4 5 6 7 8 | | 3 5 7 8 4 2 1 6 |

If we begin with 1 we note that 1 goes to 3 which goes to 7 which goes back to 1. Thus we have the cycle (1 3 7). Now we take one of the elements that isn't in the cycle just found, say, 2. 2 goes to 5 which goes to 4 which goes to 6 which goes back to 2. This gives the cycle

(2 5 4 8 6)

Thus we have broken the permutation into two cycles, (1 3 7) and (2 5 4 8 6). There are a few things we should notice about this decomposition into cycles.

**The cycles are disjoint.**

They have no element in common. This is clear because once we find a cycle in a permutation we have found where every element in the cycle goes under the permutation. The "destination" of every element of the cycle is in the cycle. Also the elements that have things in the cycle as their destination are also in the cycle. Thus once we close out a cycle by bringing it back to its first element we have found everything that the permutation does to the elements of that cycle and that they are in that cycle. If an element of one cycle was in another cycle then there would be two (at least) elements that that element was mapped onto by the permutation.

So we can decompose any finite permutation into disjoint cycles. Just choose an element see where it goes and then see where that element goes and on until you close out the cycle. Now if there are any elements that are not in that cycle choose one of those and see where it goes etc. until you close out a second cycle. If there are any remaining elements that are not in either of those two cycles choose one of them and continue constructing cycles until you've exhausted all the elements of the permutation. This gives us the result that

**Theorem: Every permutation can be decomposed into disjoint cycles.**

When we combined permutations with the binary operation "followed by" we found that the order of the permutations mattered. Thus performing

followed by| 1 2 3 | | 2 3 1 |

| 1 2 3 | | 2 1 3 |

was different that performing them in the reverse order. In cyclic notation this would be (1 2 3) followed by (1 2). Let's work out the final permutation from the cyclic notation. In (1 2 3) followed by (1 2) the first cycle takes 1 to 2 and the second cycle takes 2 to 1 so the result is that over all 1 goes to 1. The first cycle takes 2 to 3 and the second cycle does not operate on 3 so the overall effect is to take 2 to 3. finally the first cycle takes 3 to 1 and the second cycle takes 1 to 2 for the overall effect of taking 3 to 2. Thus the result of the combination of the two permutations is (2 3).

If we apply them in reverse order, (1 2) followed by (1 2 3) the result is
(1 3) [work this out!]. The order of permutations matters. The group
**S**_{3} is not Abelian. However if two cycles are disjoint
then they will commute. If the elements moved around by permutation **a**
have no elements in common with those moved around by permutation **b** then
which is performed first doesn't matter. Each cycle operates on different
elements so their actions are independent of each other. They live in different
worlds as it were. Thus performing **a** after performing **b**
will have no affect on the elements permuted by **a**. Thus:

**Theorem: Disjoint permutations commute.**

So when we decompose a permutation into disjoint cycles the order of applying those cycles does not matter.

Now let's study the cycles themselves. The simplist cycle would be (1) which is the identity. Element 1 goes to 1 and the others are unaffected. This is just the identity permutation.

The next simplist is a cycle of length 2, (1 2) This is just a transposition.
Next let's look at a three cycle: (1 2 3) This is equivalent to two transpositions:
(1 2) followed by (1 3) [try it!]. Thus (1 2 3) is the product of two
transpositions and is an *even* permutation. Let's consider a
four cycle: (1 2 3 4) This is equivalent to (1 2) followed by (1 3)
followed by (1 4) [try it!]. Thus it is the product of three transpositions
and is therefore an odd permutation. Notice that to get from (1 2 3) to
(1 2 3 4) we just had to perform one more permutation at the end,
namely (1 4). Similarly to (1 2 3 4 5) = (1 2 3 4) followed by (1 5)
[try it!]. Continuing on we see that (1 2 3 . . . n) followed by
(1 n+1) gives (1 2 3 ... n n+1) [try it!]. Thus by mathematical induction we
come to the conclusion that

**Theorem: A cycle with an even number of elements is an odd permutation.
and a cycle with an odd number of elements is an even permutation.**

So once we have expressed a permutation as the product of disjoint cycles we can determine whether it is an even or odd permutation by noticing the number of cycles with an even number of elements. Since they contribute an odd number of transpositions to the permutation the total parity of transpositions, even or odd, will depend on the number of permutations with an even number of elements. We see that

**Theorem: If a permutation is decomposed into disjoint cycles such that
there is an odd number of cycles with an even number of elements then the
permutation is odd. If there is an even number of cycles with an even
number of elements then the permutation is even.
**

**
**

© 1999 by Arfur Dogfrey