NumberofDerangementDefine i=k as Property Ak, and Akis used for thesubset of all permutations satisfying property AkThenumberof derangementis:N(A A, A..A)= N - S +S, - S, +...+(-1)*S, +...+(-1)"Swhere N = n!whereS,isEIAOAO..OAISi≤i...i≤nNote:S, is the number of permutatio ns keeping exactly k elementsin their original positions, and the other n -k elements as anypossible permutatio n Sonn!(n-k)!St(n-1); S, =(n-2),.., Sk!k2
Number of Derangement ◼ Define ik=k as Property Ak , and Ak is used for the subset of all permutations satisfying property Ak . ! ! ( 2)!;., ( )! 2 ( 1)!; 1 possible permutatio n. So : in their original positions, and the other elements as any Note : is the number of permutatio ns keeping exactly elements where is | . | where ! ( . ) . ( 1) . ( 1) The number of derangemen t is 1 2 1 . 1 2 3 1 2 3 1 2 1 2 k n n k k n n S n n S n S n k S k S A A A N n N A A A A N S S S S S k k i i i n k i i i n n k k n k k − = − = − = = − = = − + − + + − + + − ：
The Probability of DerangementWehaveknownthat thenumber of derangemen t isN(A,A,A...A)=N- S, +S, - S, +...+(-I)S, +...+(-1)"S,n!where N = n!, and S,n-kl(k =1,2,3....n)k!(-1)k(-1)k..N(A A, A...A) = n!and the probabilit y:k!k!k=0k=02Since-1, the difference between the probabilit yk!k=01and e-~0.367879... is less thanwhich means that then!probabilit y is about 0.368, independen t of n, except for very small n
The Probability of Derangement probabilit y is about 0.368, independen t of , except for very small . , which means that the ! 1 and 0.367879.is less than , the difference between th e probabilit y ! ( 1) Since ! ( 1) ; and the probabilit y ! ( 1) ( . ) ! ( 1,2,3,., ) ! ! where !, and ( )! ( . ) . ( 1) . ( 1) We have known that the number of derangemen t is 1 1 0 0 0 1 2 3 1 2 3 1 2 3 n n n e e k k k N A A A A n k n k n n k k n N n S N A A A A N S S S S S k k n k n k k k n k n n k k n = − − − = − = = = = = − + − + + − + + − − − = = = ：