next up previous
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 tex2html_wrap_inline1045 is denoted by tex2html_wrap_inline1047 . Under the binary operation of function composition, tex2html_wrap_inline1047 is a group and is called the symmetric group on tex2html_wrap_inline1045 . In the case that tex2html_wrap_inline1053 then we customarily write the symmetric group as tex2html_wrap_inline1055 and talk about the symmetric group of degree n. The order of tex2html_wrap_inline1055 is n! as is easily seen using the "two row" method to write a permutation.

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

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

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 tex2html_wrap_inline1055 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 tex2html_wrap_inline1077 , 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.

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 tex2html_wrap_inline1079 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 tex2html_wrap_inline1081 ways, and arrange them in 3!/3 ways. This gives 20 permutations of this type. Finally, for shape 6, there are tex2html_wrap_inline1083 ways to select the integers for the first cycle, tex2html_wrap_inline1085 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 tex2html_wrap_inline1077 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 tex2html_wrap_inline1089 .

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

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