12 Chapter 1. Groups I Example 1.11. The 15-puzzle has a starting position that is a 4 × 4 array of the numbers between 1 and 15 and a symbol , which we interpret as “blank.” For example, consider the following starting position: 12 15 14 8 10 11 1 4 9 5 13 3 6 7 2 A move interchanges the blank with a symbol adjacent to it for example, there are two beginning moves for this starting position: either interchange and 2 or interchange and 3. We win the game if, after a sequence of moves, the starting position is transformed into the standard array 1, 2, 3, . . . , 15, . To analyze this game, note that the given array is really a permutation α S16 (if we now call the blank 16 instead of ). More precisely, if the spaces are labeled 1 through 16, then α(i) is the symbol occupying the ith square. For example, the given starting position is 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 12 15 14 8 10 11 1 4 9 5 13 3 6 7 2 16 . Each move is a special kind of transposition, namely, one that moves 16 (remember that the blank = 16). Moreover, performing a move (corresponding to a special transposition τ) from a given position (corresponding to a permutation β) yields a new position corresponding to the permutation τβ. For example, if α is the position above and τ is the transposition interchanging 2 and , then τα( ) = τ( ) = 2 and τα(2) = τ(15) = 15, while τα(i) = α(i) for all other i. That is, the new configuration has all the numbers in their original positions except for 2 and being interchanged. To win the game, we need special transpositions τ1,τ2,...,τm such that τm · · · τ2τ1α = (1). It turns out that there are some choices of α for which the game can be won, but there are others for which it cannot be won, as we shall see in Example 1.15. Definition. A permutation α Sn is even if it is a product of an even number of transpositions α is odd if it is not even. The parity of a permutation is whether it is even or odd. It is easy to see that (1 2 3) and (1) are even permutations, for there are factor- izations (1 2 3) = (1 3)(1 2) and (1) = (1 2)(1 2) as products of two transpositions. On the other hand, we do not yet have any examples of odd permutations! It is clear that if α is odd, then it is a product of an odd number of transpositions. The converse is not so obvious: if a permutation is a product of an odd number of transpositions, it might have another factorization as a product of an even number of transpositions. After all, the definition of an odd permutation says that there does not exist a factorization of it as a product of an even number of transpositions. Proposition 1.12. Let α, β Sn. If α and β have the same parity, then αβ is even, while if α and β have distinct parity, then αβ is odd.
Previous Page Next Page