例:100以内有多少质数 口100以内的任意合数必有不大于其平方根的质数为其因子。 这样的质数只有4个:{2,3,5,7} 口设A2A3,A5,A7分别是可被相应质数整除的100以内大于1的 自然数的集合。则100以内质数的数量为: 100100|100|100 N(A2434541)=99 2 5 7 1001100|1001001100100 why? 23L2.5」2.735°3.7L5.7 100 100 100 100 100 +4 2.352.3·72.5.73.5.723.5·7 =99-50-33-20-14+16+10+7+6+4+2-3-2-1-0+0+4 5
例：100以内有多少质数 100以内的任意合数必有不大于其平方根的质数为其因子。 这样的质数只有4个：{2, 3, 5, 7} 设A2 , A3 , A5 , A7 分别是可被相应质数整除的100以内大于1的 自然数的集合。则100以内质数的数量为： 25 99 50 33 20 14 16 10 7 6 4 2 3 2 1 0 0 4 4 2 3 5 7 100 3 5 7 100 2 5 7 100 2 3 7 100 2 3 5 100 5 7 100 3 7 100 3 5 100 2 7 100 2 5 100 2 3 100 7 100 5 100 3 100 2 100 ( 2 3 5 7 ) 99 = = − − − − + + + + + + − − − − + + + + − − − − + + + + + + − − − N A A A A = − why?
例:粗心的衣帽间管理员 口剧场的衣帽管理间新来了一个粗心的管理员,他忘了给 每个客人的帽子夹上号码牌。散场时他只好随意地将 帽子发还给客人。没有任何人拿到自己的帽子的概率 是多少? 口这可以看作一个排列问题:对标号为1,2,3,…,m的n个帽 子重新排列,新的序号为,2。上述间题即: 满足对任意k(1≤km,运≠的排列出现的概率是多少? 口这样的排列称为“错位排列”( derangement 口适当的集合模型使问题得到简化
例：粗心的衣帽间管理员 剧场的衣帽管理间新来了一个粗心的管理员,他忘了给 每个客人的帽子夹上号码牌。散场时他只好随意地将 帽子发还给客人。没有任何人拿到自己的帽子的概率 是多少？ 这可以看作一个排列问题：对标号为1,2,3,…,n的n个帽 子重新排列，新的序号为i1 , i 2 , i 3 ,…,in。上述问题即： 满足对任意k (1kn), i kk的排列出现的概率是多少？ 这样的排列称为“错位排列”(derangement)。 适当的集合模型使问题得到简化
错位排列的个数 口我们将=k称为“性质A"。满足性质A的排列构 成所有排列的一个子集A。 错位排列的个数为: N(41A2A1AL)=N-S1+S2-S3+…+(-1Sk+…+(-1)"Sn 其中:N=n! S如前面的定义,即∑A⌒A2∩…A1 1≤i≤i2…ik≤n 注意:保持项不变的置换,即其余n-k项可任意排列。 所以: (n-1) n-2)…,Sk=,(m-k) k
错位排列的个数 我们将ik=k称为“性质Ak ”。满足性质Ak的排列构 成所有排列的一个子集Ak。 ! ! ( 2)!;..., ( )! 2 ( 1)!; 1 | ... | ! ( ... ) ... ( 1) ... ( 1) 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 k n k S A A A N n N A A A A N S S S S S k i i i n k i i i n n k k n k k − = − = − = = − = = − + − + + − + + − 所以： 注意：保持 项不变的置换，即其余 项可任意排列。 如前面的定义，即 其中： 错位排列的个数为：
错位排列的个数 我们已经知道错位排列的个数为: N(A4424A1)=N-S1+S2-S3+…+(-1)S+…+(-1)"Sn 其中:N=n 将诸S=|(n-k)=n(k=123、,m代入上面的式子 N(AA244,)=n∑ (-1) 要求的概率是:∑ k=0 注意∑(=c,所以这概率值与e103687的差小于1 换句话说,除了较小的n,所求概率约为0.368,且与n无关
错位排列的个数 换句话说，除了较小的 所求概率约为 且与 无关。 注意： 所以这概率值与 的差小于 要求的概率是： 将诸 代入上面的式子 其中： 我们已经知道错位排列的个数为： n n n e e k k k N A A A A n k n k n n k k n S N n 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 , 0.368, ; ! 1 , 0.367879... ! ( 1) ! ( 1) ; ! ( 1) ( ... ) ! ( 1,2,3,..., ) : ! ! ( )! ! ( ... ) ... ( 1) ... ( 1) 1 1 1 1 1 1 2 3 1 2 3 1 2 3 = − − − = − = = = = = − + − + + − + + − − = − = = 0 0 0