Advanced Mathematics

6.3Permutation Groups

Purpose of Section

To introduce the idea of a permutation of a set and how a composition of permutations can be interpreted as a binary operation yielding a new permutation. This binary operation gives rise to an important group of permutations called the symmetric group S_n.

6.3.1 Permutations and Their Products

In Section 2.3, we introduced the concept of a permutation (or arrangement) of a set of objects. We now return to the subject, but now our focus is different. Instead of thinking of a permutation as an arrangement of objects (which it is, of course), we think of a permutation as a one‐to‐one correspondence (bijection) from a set onto itself. For example, a permutation of elements of the set A = {1, 2, 3, … , n} can be thought of a one‐to‐one mapping of the set onto itself, represented by

which gives the image k^p of each element k ∈ A in the first row as the element directly below it in the second row.

For example, a typical permutation of the four elements A = {1, 2, 3, 4} is

A good way to think about this permutation is to think of a tomato, strawberry, lemon, and apple, arranged from left to right in positions we call 1, 2, 3, and 4. If we apply the permutation P mapping, we get the new arrangement shown in Figure 6.34.

Figure 6.34 Permutation ...