2. Derangements A derangement of (1, 2,..., n is a permutation ii2.in of (1, 2,.., n in which no integer is in its natural position i11,2≠2,…n≠n We denote by d the number of derangements of{1,2,…,n} Theorem4.l5:Forn≥1, D=n!(1 ∴ l!2!13
▪ 2.Derangements ▪ A derangement of {1,2,…,n} is a permutation i1 i2…in of {1,2,…,n} in which no integer is in its natural position: ▪ i11,i22,…,inn. ▪ We denote by Dn the number of derangements of {1,2,…,n}. ▪ Theorem 4.15：For n1, ) ! 1 ( 1) 3! 1 2! 1 1! 1 !(1 n D n n n = − + − ++ −
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
3. Permutations with relative forbidden position A Permutations of (1, 2,e., n with relative forbidden position is a permutation in which none of the patterns i, i+l(i=l, 2,.., n)occurs. We denote by Qn the number of the permutations of (1, 2,, n with relative forbidden position Theorem4.16:Forn≥1, Qn=n!-C(n-1,1)(n-1)+C(n-1,2)(n-2)!-…+(-1)m1 C(n-1,n-1)1!
▪ 3. Permutations with relative forbidden position ▪ A Permutations of {1,2,…,n} with relative forbidden position is a permutation in which none of the patterns i,i+1(i=1,2,…,n) occurs. We denote by Qn the number of the permutations of {1,2,…,n} with relative forbidden position. ▪ Theorem 4.16：For n1, ▪ Qn=n!-C(n-1,1)(n-1)!+C(n-1,2)(n-2)!-…+(-1)n-1 C(n-1,n-1)1!
Proof: Let s=(1, 2,.o, n and x be the set of all permutations of s. Then x=n j〔j+1),p(1,2,…,n-) Q=D,+D
▪ Proof: Let S={1,2,…,n} and X be the set of all permutations of S. Then |X|=n!. ▪ j(j+1), pj (1,2,…,n-1) ▪ Aj : pj ▪ Qn=Dn+Dn-1