§32容斥原理 令:M为修数学的学生集合 P为修物理的学生集合; C为修化学的学生集合; M=170P=130.c1=120,MP=45 M∩C=20PnC=2MnP∩C=3
令：M为修数学的学生集合； P 为修物理的学生集合； C 为修化学的学生集合； 170, 130, 120, 45 20, 22, 3 P C M P M C P C M P C = = = = = = = M §3.2 容斥原理
§32容斥原理 MUPUC=M+P+(c+M∩PM M∩c||P∩c+M∩P∩c 170+130+120-45-20-22+3 336 即学校学生数为336人
170 130 120 45 20 22 3 336 M P C P C M P M M C P C M P C − − = = + + − − − + = + + − + M 即学校学生数为336人。 §3.2 容斥原理
§32容斥原理 同理可推出 AUBUCUDEA+B+C+D-An B A∩C+|Bc-|AD+A∩BC +|A∩BD+BCD|-ABCD 利用数学归纳法可得一般的定理:
同理可推出： A B C D A B C D A B B C A D A B C A B D B C D A B C D − − − − − + + + = + + + A C 利用数学归纳法可得一般的定理： §3.2 容斥原理
§3.2容斥原理 定理设￠(nk)是[1,n]的所有k 子集的集合,则 A|=21)2c(40合 证对n用归纳法。n=2时,等式成立 假设对n-1,等式成立。对于n有
定理 设￠(n,k)是［1,n］的所有k- 子集的集合, 则 |∪Ai | = ∑ (－1)k-1 ∑ | ∩ Ai | 证 对n用归纳法。n=2时，等式成立。 假设对n - 1，等式成立。对于n有 §3.2 容斥原理 n i=1 k=1 n I∈￠(n,k) i∈I
§3.2容斥原理 UA=UAUA 14|+14-4n4 U4+14|-4n4) ∑(-1)∑n4+4-2()∑∩(4∩4 I∈￠(n1l)y I∈c(n-1l)e
§3.2 容斥原理 1 i 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 A ( ) ( 1) ( 1) ( ) n n i n i i n n i n i n i i n n i n i n i i n n k k i n i n k k i I A A A A A A A A A A A A A A − = = − − = = − = = − − − − = = = = + − = + − = − + − − I∈￠(n-1,k) I∈￠(n-1,k) i∈I