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.

Purchased from American Mathematical Society for the exclusive use of nofirst nolast (email unknown) Copyright 2010 American Mathematical Society. Duplication prohibited. Please report unauthorized use to cust-serv@ams.org. Thank You! Your purchase supports the AMS' mission, programs, and services for the mathematical community.