南京大学：《离散数学 Discrete Mathmatics》课程教学资源（课件讲稿，2018）计数与离散概率——第10章 基本计数技术

粗心的衣帽间管理员 ·剧场的衣帽管理间新来了一个粗心的管理员，他忘了给 每个客人的帽子夹上号码牌。散场时他只好随意地将 帽子发还给客人。没有任何人拿到自己的帽子的概率 是多少？ 。这可以看作一个排列问题：对标号为1,2,3，..，n的n个 帽子重新排列，新的序号为i1,2,3…,n。上述问题即： 满足对任意k(1≤ks),k≠k的排列出现的概率是多少？ 这样的排列称为“错位排列”(derangement)。 。适当的集合模型使问题得到简化

粗心的衣帽间管理员  剧场的衣帽管理间新来了一个粗心的管理员,他忘了给 每个客人的帽子夹上号码牌。散场时他只好随意地将 帽子发还给客人。没有任何人拿到自己的帽子的概率 是多少？  这可以看作一个排列问题：对标号为1,2,3,…,n的n个 帽子重新排列，新的序号为i1 , i2 , i3 ,…,in。上述问题即： 满足对任意k (1kn), ikk的排列出现的概率是多少？  这样的排列称为“错位排列”(derangement)。  适当的集合模型使问题得到简化

错位排列的个数-推导 我们将=k称为“性质Ak”。满足性质A的排列构成 所有排列的一个子集Ak。 错位排列的个数为： N(AA,2AAn)=N-S1+S2-S3+.+(-1)Sk+.+(-1)”Sm 其中：N=nl S如前面的定义即∑|A∩4，.∩A 1≤i1≤i2≤ik≤n 注意：保持k项不变的置换，即其余一k项可任意排列。 所以： s0加9加-21s-a-=月

错位排列的个数 – 推导  我们将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                                                   所以： 注意：保 持 项不变的置换，即其余 项可任意排列。 如前面的定义，即 其中： 错位排列的个数为：