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

般感 容斥原理的证明 。公式：UA,=S,-S2+S-+(-1)1S4++(-1)Sn 。我们证明在上述公式中： 。并集中的元素在右边式子中恰好被计数次 ●设并集中对象a出现在m个集合中 。则它在在S1中被计数m次，在S2中被计数C次 。以n=4,m=3为例： IS+IS2+IS3l+IS4l -(ISOS2l+ISOS3l+ISOS4l+IS20S3l+IS20S4l+IS3OS4l) +(IS1∩S2nS3+lS1∩S2nS4+lS1∩S3nS4+S2nS3∩S4) -IS]0S20S30S4l

容斥原理的证明  公式：  我们证明在上述公式中:  并集中的元素在右边式子中恰好被计数1次  设并集中对象a出现在m个集合中  则它在在S1中被计数m 次，在S2中被计数 次  以n=4，m=3为例： n n k k S S S S S -1 -1 1 2 3 n i 1 i A  -  -... (1) ... (1)   m C2 |S1 |+ |S2 |+ |S3 |+ |S4 | - (|S1S2 |+|S1S3 |+|S1S4 |+|S2S3 |+|S2S4 |+|S3S4 |) + (|S1S2S3 |+|S1S2S4 |+|S1S3S4 |+|S2S3S4 |) - |S1S2S3S4 |

毁扇 容斥原理的证明 。公式：UA=S-S2+S-+(-1)S4++(-I)mS ●我们证明并集中的元素在右边式子中恰好被计数1次 。设并集中对象a出现在m个集合中 ●则它在在S,中被计数m次，在S中被计数 CW次

容斥原理的证明  公式：  我们证明并集中的元素在右边式子中恰好被计数1次  设并集中对象a出现在m个集合中  则它在在S1中被计数m 次，在Sk中被计数 次 n n k k S S S S S -1 -1 1 2 3 n i 1 i A  -  -... (1) ... (1)   m Ck

容斥原理的证明 。计数公式：UA=S-S2+S-+(-1)S++(-1)mSn ·第二步：满足1个或多个性质的元素恰好被计数0次： ●设对象a出现在m个集合中 。a在S,中被计数C次，Sk中被计数恰好C次 ●将上述分析带入计数公式可得： C-C++(-1)1C+.+(-1)mCm 。该计算式值为1，因为当x=1时下式为0： (1-x)m=1-Cmx+C2mx2+.+(-1)Cx+.+(-1）"Cmxm ·a恰好被计数1次

容斥原理的证明  计数公式：  第二步：满足1个或多个性质的元素恰好被计数0次：  设对象a出现在m个集合中  a在S1中被计数 次，Sk中被计数恰好 次  将上述分析带入计数公式可得：  该计算式值为1，因为当x=1时下式为0：  a恰好被计数1次 m m m m k m m k C C C C 1 1 1 2 ... ( 1) ... ( 1)          m m m m k m k m m m k (1 x) 1 C x C x ... ( 1) C x ... ( 1) C x 2    1  2       m Ck m C1 n n k k S S S S S -1 -1 1 2 3 n i 1 i A  -  -... (1) ... (1)  

埃拉托色尼的筛子 1902 (Eratosthenes'Sieve) ●用筛法求质数（以25以内的为例） 2345678910111213141516171819202122232425 [2]2345678910111213141516171819202122232425 [3]2345678910111213141516171819202122232425 [5]2345678910111213141516171819202122232425

埃拉托色尼的筛子 (Eratosthenes’ Sieve)  用筛法求质数（以25以内的为例） 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 [2] 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 [3] 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 [5] 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25

100以内有多少质数 。100以内的任意合数必有不大于其平方根的质数为其因子。 这样的质数只有4个：{2,3,5,7] 设A2,A3,A5,A7分别是可被相应质数整除的100以内大于1 的自然数的集合。则100以内质数的数量为： N(AA AsA)=99 why? 100 =99-50-33-20-14+16+10+7+6+4+2-3-2-1-0+0+4 =25

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?