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 coefficients 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).
Previous Page Next Page