19. List the even permutations of 1, 2, 3, 4. 20. List the odd permutations of 1, 2, 3, 4. R 21. Let P be a permutation i, j, h, ... k of 1, 2, 3, ... , n. (a) Show that if i and j are interchanged, P changes from odd to even or from even to odd. (b) Show that if any two adjacent terms in P are interchanged, P changes from odd to even or from even to odd. (c) Show that the interchange of any two terms in P can be considered to be the result of an odd number of interchanges of adjacent terms. (d) Show that if any two terms in the permutation P are interchanged, P changes from odd to even or from even to odd.
Arrangements of n objects. We may also consider the possibility of arranging, in a row, r objects chosen from a set of n. We have n choices for the first space, n - 1 for the second, n - 2 for the third, and so on. Finally we have n - r + 1 choices for the rth space, giving a total of n(n - 1)(n - 2)ÿ(n - r + 1) possible arrangements (or permutations). This can be written in terms of factorials as follows: n(n & 1)(n & 2)ÿ(n & r % 1) ' n(n & 1)(n & 2)ÿ(n & r % 1)(n & r)(n & r & 1)ÿ[email protected]@1 (n & r)(n & r & 1)ÿ[email protected]@1 ' n!
K % 1)! (k & r % 1)! Since the formula k%1 (k % 1)! (k & r % 1)! is the theorem for n = k + 1, the formula is proved for all integers n $ 0, with the exception that our proof tacitly assumes that r is neither 0 nor k + 1; that is, it deals only with the coefficients inside the border of 1's. But the formula k%1 r ' (k % 1)! (k & r % 1)! 42 shows that each of k%1 0 and k%1 k%1 is (k % 1)! ' 1. (k % 1)! Hence the theorem holds in all cases. The above theorem tells us that the coefficient of x ry s in (x % y)n is n!