南京大学：《离散数学》课程教学资源（PPT课件讲稿）Lecture 09 计数

选课的例子 口全班共有160个学生 口选数学课64人,选计算机课94人,选金融课58人 口选数学与金融的28人,选数学与计算机的26人,选 计算机与金融的22人 口三种课全选的14人。 口问:这三种课都没选的是多少?只选一门计算 机的有多少?

选课的例子  全班共有160个学生  选数学课64人，选计算机课94人，选金融课58人  选数学与金融的28人，选数学与计算机的26人，选 计算机与金融的22人  三种课全选的14人。  问：这三种课都没选的是多少？只选一门计算 机的有多少？

选课的例子 8 口M-数学、C计算机、F金融 口容斥原理 M 24 M∪C∪F|=|M|+|C|+|F M⌒F|-|MnC|-|C⌒F|+ M⌒C∩F 12 14 14 =64+94+58-2826-22+14 22 =154 因此,6人未选课。 只选了计算机课的60人

选课的例子 8  M-数学、C-计算机、F-金融  容斥原理 |MCF|=|M|+|C|+|F|- |MF|-|MC|-|CF|+ |MCF| =64+94+58-28-26-22+14 =154 因此, 6人未选课。 只选了计算机课的60人 M C F 14 12 14 8 24 60 22 6

容斥原理 Principle of Inclusion and Exclusion) 假设A,42,4,是n个有限集合,则它们的并集的元素个数是 ∪A=S-S2+S3…+(-S++(1)"S 其中,S=∑41∩A12∩∩A1|k=12…,n 1≤i1≤2≤.sik≤n 例如:4个子集的公式为: A1+A2|+1A31+A4 (A1A2|+|A1A3+A1A4|+|A2A3|+|A2A4|+|A3A4|) +(A, A31+JAnA2nA4+AnA3nA4l+ A2nAnA4D) IAnA2NA3QA4I

容斥原理 (Principle of Inclusion and Exclusion )      = =    = = + + − + + − i i i n k i i i n n k k n k k S A A A k n S S S S S A A A 1 ... -1 -1 1 2 3 n i 1 i 1 2 1 2 1 2 | ... | 1,2,..., A - -... ( 1) ... ( 1) , ,..., n 其中， 假设 是 个有限集合，则它们的并集的元素个数是：  例如：4个子集的公式为： |A1|+ |A2|+ |A3|+ |A4| - (|A1A2|+|A1A3|+|A1A4|+|A2A3|+|A2A4|+|A3A4|) + (|A1A2A3|+|A1A2A4|+|A1A3A4|+|A2A3A4|) - |A1A2A3A4|

容斥原理的证明 公式:∪A +S3-…+(-1Sk+…+(-1) 口我们证明并集中的元素在右边式子中恰好被计数1次 口设并集中对象a出现在m个集合A中 口则它在在S1中被计数m次,在S2中被计数C次 ■以n=4,m=3为例 S1:|A1+1A2+A3+A4 S2:-(A1^A2+4A3+A1∩A4|+A2A3+A2A4+A9A4D) +(|A1A2A3|+|A1A2A4|+A1A3A4|+|AA3A4|) A,nA2nA3nA4l

容斥原理的证明  公式：  我们证明并集中的元素在右边式子中恰好被计数1次  设并集中对象a出现在m个集合Ai中  则它在在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 |A1|+ |A2|+ |A3|+ |A4| - (|A1A2|+|A1A3|+|A1A4|+|A2A3|+|A2A4|+|A3A4|) + (|A1A2A3|+|A1A2A4|+|A1A3A4|+|A2A3A4|) - |A1A2A3A4| S1 ： S2 ： S3 ： S4 ：

容斥原理的证明 公式:∪A=S-S2+s-…+(-)S++(- n-1 口我们证明并集中的元素在右边式子中恰好被计数1次 口设并集中对象a出现在m个集合A中 口则它在在S1中被计数m次,在S中被计数C次 口将上述分析带入计数公式可得a在右式中计数次数 四-C2++(-1)Cm+…+(-1)Cm 该计算式值为1,因为当x=1时下式为0 (1-x)"=1-C1xC2x2+…+(-1)Ckx+…+(-1)“Cmx 口a恰好被计数1次

容斥原理的证明  公式：  我们证明并集中的元素在右边式子中恰好被计数1次  设并集中对象a出现在m个集合Ai中  则它在在S1中被计数m 次，在Sk中被计数 次  将上述分析带入计数公式可得a在右式中计数次数： ◼ 该计算式值为1，因为当x=1时下式为0：  a恰好被计数1次 n n k k S S S S S -1 -1 1 2 3 n i 1 i A = - + -...+ (−1) +...+ (−1) =  m Ck 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 + + − + + −