Hatcheck Problem 大剧院衣帽间的员工太粗心，将个客人的帽子上的 标签搞乱了。他将顶帽子随意地递交给每个客人。 口问题：“每个客人都拿错了帽子”的概率是多少？ ▣数学模型：随机地排列自然数1,2,3，..，n,生成 一个序列：1,2,3，…，n。出现下述情况的概率 是多少：对任意的k1≤k≤m),k≠k? ■这样的序列称为derangement
Hatcheck Problem ◼ 大剧院衣帽间的员工太粗心，将n个客人的帽子上的 标签搞乱了。他将n顶帽子随意地递交给每个客人。 ❑ 问题：“每个客人都拿错了帽子”的概率是多少？ ◼ 数学模型：随机地排列自然数 1,2,3,…,n，生成 一个序列：i1 , i2 , i3 ,…,in。出现下述情况的概率 是多少 ： 对任意的 k(1kn), ikk？ ◼ 这样的序列称为 derangement
Number of Derangement Define i=k as Property Ak,and Ak is used for the subset of all permutations satisfying property Ak. The number of derangement is: N(AAAA)=N-S1+S2-S,+.+(-1)*Sk+.+(-1)”Sm where N=n! where S is >440.. lsi≤2≤ik≤n Note:S is the number of permutatio ns keeping exactly k elements in their original positions,and the other n-k elements as any possible permutatio n.So: 8-0-%-[9}a-28=a-=
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 − = − = − = = − = = − + − + + − + + − ：