Proof: Let s=(1, 2,.., n andx be the set of all permutations of s. Then x=n For j=1, 2,e., n, let pi be the property that in a permutation,j is in its natural position. Thus the permutation i1,i2, ...,in of s has property p provided i=j. A permutation of s is a derangement if and only if it has none of the properties p1p2…pn Let ai denote the set of permutations of s with property p; (j=1, 2,., n)
▪ Proof: Let S={1,2,…,n} and X be the set of all permutations of S. Then |X|=n!. ▪ For j=1,2,…,n, let pj be the property that in a permutation, j is in its natural position. Thus the permutation i1 ,i2 ,…,in of S has property pj provided ij=j. A permutation of S is a derangement if and only if it has none of the properties p1 ,p2 ,…,pn . ▪ Let Aj denote the set of permutations of S with property pj ( j=1,2,…,n)
Example: (dEtermine the number of permutations of (1, 2, 3, 4, 5, 6, 7, 8, 9 in which no odd integer is in its natural position and all even integers are in their natural position. (2) Determine the number of permutations of 1, 2, 3, 4, 5, 6, 7, 8, 9 in which four integers are in their natural position
▪ Example:(1)Determine the number of permutations of {1,2,3,4,5,6,7,8,9} in which no odd integer is in its natural position and all even integers are in their natural position. ▪ (2) Determine the number of permutations of {1,2,3,4,5,6,7,8,9} in which four integers are in their natural position