南京大学：《计算机问题求解》课程教学资源（PPT课件讲稿）离散概率基础

包含排斥定律：否定形式 没有被包含在若干个子集的并集中的元素个数： N(AA,A)=N-S,+S2-S3+.+(-1)*Sk++(-1)Sn where,Sk=∑1A,nA,n.∩A|k=1,2,,n l≤i1≤i2≤≤ik≤n For an example:the formula for 4 subsets N-(IAH+A2H+A3H+A4) +(A1∩A2HlA1∩A2tlA1∩AtlA2∩A3t|A2∩AtlA3A4D -(A1∩A2∩A3+lA1OA2∩A4tlA1∩A3∩A4tlA2∩A3∩A4D +A1∩A2∩A3∩A4

包含-排斥定律: 否定形式       =    = = − + − + + − + + − i i i n k i i i n n k k n k k S A A A k n N A A A N S S S S S 1 ... 1 2 1 2 3 1 2 1 2 where | ... | 1,2,..., ( ... ) ... ( 1) ... ( 1) ， For an example：the formula for 4 subsets N - (|A1 |+ |A2 |+ |A3 |+ |A4 |) + (|A1A2 |+|A1A2 |+|A1A4 |+|A2A3 |+|A2A4 |+|A3A4 |) - (|A1A2A3 |+|A1A2A4 |+|A1A3A4 |+|A2A3A4 |) + |A1A2A3A4 | 没有被包含在若干个子集的并集中的元素个数:

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(1kn), ikk？ ◼ 这样的序列称为 derangement