Next: Cayley's Theorem Up: PERMUTATION GROUPS Previous: Finding the inverse permutation

## Symmetric, Alternating and Permutation groups

The set of all permutations on a set is denoted by . Under the binary operation of function composition, is a group and is called the symmetric group on . In the case that then we customarily write the symmetric group as and talk about the symmetric group of degree n. The order of is n! as is easily seen using the "two row" method to write a permutation.

The set of even permutations in forms a subgroup. This subgroup is called the Alternating Group and is denoted by . Its order is n!/2.

A permutation group is a subgroup of a symmetric group on some set .

Recall that the cycle (1 2 3) can also be written as (3 1 2) or (2 3 1). In general, there are n ways to write a cycle of length n. We can list the types of permutations in and count the number of each type. By the shape of a cycle we mean its length and not the particular integers that are used. We will refer to such a cycle as (. . .), say, for a cycle of length 3. The shape of a permutation will be the different combinations of cycle shapes that can be used. For example, in , a permutation written as a product of disjoint cycles must have one of the following shapes:

shape 1.
(. . . . .) where '.' represents a position to be filled with an integer between 1 and 5 inclusive.
shape 2.
(. . . .)
shape 3.
(. . .)
shape 4.
(. .)
shape 5.
(. . .)(. .)
shape 6.
(. .)(. .)
shape 7.
IDENTITY ELEMENT

There is only one permutation of shape 7. The dots in shape 1 can be filled by the integers 1 through 5. So there are 5! ways to place the integers in the positions occupied by the dots. However, each cycle can be written with any one of the integers written leftmost (a cicular permutation) and so there are 5!/5 or 4! permutations of shape 1. That is, there are 24 permutations of this shape. The order of such a permutation is 5. For permutations of shape 2 there are ways to select the integers to fill the cycle, 4!/4 ways to arrange them in the cycle. This gives 30 permutations of this type. For shapes 3 and 4 there are 20 and 10 permutations, respectively. For shape 5, we can select the integers for the cycle of length 3 in ways, and arrange them in 3!/3 ways. This gives 20 permutations of this type. Finally, for shape 6, there are ways to select the integers for the first cycle, ways to select integers for the second cycle, but as the shapes are identical, we must divide by the number of ways to arrange the cycles (2 in this case) and finally arrange the integers within each cycle in 1 way. This gives 15 permutations.

In total then, we have accounted for 1+24+30+20+10+20+15 which is 120 or 5!. Note then that has elements of order 1, 2, 3, 4, 5 and 6. Also, of these shapes, only shapes 1, 3, 6 and 7 are elements of .

Next: Cayley's Theorem Up: PERMUTATION GROUPS Previous: Finding the inverse permutation

Peter Williams
Sun Mar 30 14:48:35 PST 1997