Section 1.2. Permutations 15 (ii) Prove that no two of the statements in (i) are equivalent when X is an infinite set. (iii) Suppose there are 501 pigeons, each sitting in some pigeonhole. If there are only 500 pigeonholes, prove that there is a hole containing more than one pigeon. ∗ 1.9. Let Y be a subset of a finite set X, and let f : Y → X be an injection. Prove that there is a permutation α ∈ SX with α|Y = f. ∗ 1.10. Find sgn(α) and α−1, where α = 1 2 3 4 5 6 7 8 9 9 8 7 6 5 4 3 2 1 . 1.11. If α ∈ Sn, prove that sgn(α−1) = sgn(α). ∗ 1.12. If 1 ≤ r ≤ n, show that there are 1 r [n(n − 1) · · · (n − r + 1)] r-cycles in Sn. Hint. There are exactly r cycle notations for any r-cycle. ∗ 1.13. (i) If α is an r-cycle, show that αr = (1). Hint. If α = (i0 . . . ir−1), show that αk(i0) = ij, where k = qr + j and 0 ≤ j r. (ii) If α is an r-cycle, show that r is the smallest positive integer k such that αk = (1). 1.14. Show that an r-cycle is an even permutation if and only if r is odd. ∗ 1.15. (i) Let α = βδ be a factorization of a permutation α into disjoint permutations. If β moves i, prove that αk(i) = βk(i) for all k ≥ 1. (ii) Let β and γ be cycles both of which move i. If βk(i) = γk(i) for all k ≥ 1, prove that β = γ. ∗ 1.16. Given X = {1, 2,... , n}, let us call a permutation τ of X an adjacency if it is a transposition of the form (i i + 1) for i n. (i) Prove that every permutation in Sn, for n ≥ 2, is a product of adjacencies. (ii) If i j, prove that (i j) is a product of an odd number of adjacencies. Hint. Use induction on j − i. ∗ 1.17. (i) Prove, for n ≥ 2, that every α ∈ Sn is a product of transpositions each of whose factors moves n. Hint. If i j n, then (j n)(i j)(j n) = (i n), by Lemma 1.7, so that (i j) = (j n)(i n)(j n). (ii) Why doesn’t part (i) prove that a 15-puzzle with even starting position α which fixes can be solved? ∗ 1.18. Define f : {0, 1, 2,. . . , 10} → {0, 1, 2,..., 10} by f(n) = the remainder after dividing 4n2 − 3n7 by 11. (i) Show that f is a permutation.8 8If k is a finite field, then a polynomial f(x) with coeﬃcients in k is called a permutation polynomial if the evaluation function f : k → k, defined by a → f(a), is a permutation of k. A theorem of Hermite–Dickson characterizes permutation polynomials (Small, Arithmetic of Finite Fields, p. 40).

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.