组合数学讲义及答案 4章 容斥原理

《组合数学讲义及答案 4章 容斥原理》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、《组合数学》第四章容斥原理第四章容斥原理是组合学中的一个基本计数理论。也称“包容与排斥原理”、“入与出原理”、“包含排斥原理”或“交互分类原理”。加法法则的限制：要求将计数的集合划分为若干个互不相交的子集，且这些子集都比较容易计数。问题：实际中又有很多计数问题要找到容易计数而又两两不相交的子集并非易事。但往往能够知道某一集合的若干相交子集的计数，进而把所要求的集合中的元素个数计算出来。§4.1引言（一）研究内容（1）实例【例】求不超过20的正整数中是2的倍数或3的倍数的数的个数。20①不超过20的正整数中是2的倍数的数有＝10个，2

2、即A＝{2,4,6,8,10,12,14,16,18,20}；20②是3的倍数的数有＝6个，即B＝{3,6,9,12,15,318}；③二者相加为10＋6＝16个。④实际为13个：即2,3,4,6,8,9,10,12,14,15,16,18,20；⑤原因：把既是2的倍数，又是3的倍数的数重复算了一20次，这样的数恰好有＝3个，即6,12,18。23⑥正确的统计方法：10＋6－3＝13个。（2）内容研究若干个有限集合的交或并的计数问题。1/49《组合数学》第四章容斥原理（二）集合的表示用大写字母表示一个集合，如A、B、C、S等

3、，用小写字母表示集合的元素，如a、b、c、x、y、z等。元素a属于集合A，记为aA，不属于A，记为aA.空集记为。（三）集合的运算（1）并（和）：记为AB或A＋B；（2）交（积）：记为AB或AB；（3）差：记为A－B（4）对立集（非）：即A＝S－A显然有A－B＝AB＝A－AB（四）优先级先取非，次为交，再次为并或差。出现在同一算式中的同级运算，按从左向右的顺序进行。先括号内，后括号外。（五）运算定律（1）交换律：A＋B＝B＋A，AB＝BA；（2）结合律：(A＋B)＋C＝A＋(B＋C),(AB)C＝A(BC)；（3）分配律：A(B＋C)＝A

4、B＋AC,A＋BC＝(A＋B)(A＋C)；（4）De.Morgan定律（互反律）：AAA＝AAA，12n12nAAA＝AAA.12n12n（六）集合的势当集合A中的元素为有限个时，称A为有限集合，其元素个数记为A，亦称为A的势。关于A，有如下简单性质：（1）若集合A、B不相交，即AB＝，则AB＝A＋B；（2）若AB，则AB＝A－B。2/49《组合数学》第四章容斥原理（3）AB＝A－AB§4.2容斥原理（一）容斥原理【引理4.2.1】设A，B为有限集合，则有ABABAB（4.2.1）（证）对于A＋B中的元素a，在

5、等式左边恰被统计一次，而在等式右边被统计的次数，分为三种情形统计：（1）aA，但aB，则a也恰被统计一次；（2）aA，但aB，同样恰被统计一次；（3）aA且aB，那么必有aAB，从而a被统计1＋1－1＝1次。所以，a在等式两边被统计的次数是相同的。【定理4.2.1】（容斥原理）设A1，A2，…An为有限集合，则AAA＝12nnn1AiAiAjAiAjAk1A1A2Ani11ijn1ijkn(4.2.2)证用数学归纳法证明。(1)当n＝2时，由引理4.2.1知，结论成立。(2)设对n－1，

6、结论正确。即AAA12n1n1n2＝AiAiAjAiAjAk1A1A2An1(4.2.3)i11ijn11ijkn1(3)对于n，有3/49《组合数学》第四章容斥原理nn1n1n1AiAiAn＝AiAnAnAi(4.2.4)i1i1i1i1利用式(4.2.3)：n1n1n1AnAiAiAn＝AiAni1i1i1n1＝AiAnAiAjAnAiAjAkAni11ijn11ijkn1n2

7、1AAAA12n1n将上式与式(4.2.3)代入式(4.2.4)整理即得式(4.2.2).（二）逐步淘汰原理【定理4.2.2】（逐步淘汰原理）设A1，A2，…An为有限集合S的子集，则AAA12nnn＝SAiAiAjAiAjAk1A1A2Ani11ijn1ijkn(4.2.5)证【证法一】利用De.Morgan定律和集合求差运算性质，可得AAA＝AAA12n12n＝SAAA＝SAAA12n12nn＝S－AiAiAjAiAjAki11ij

8、n1ijknn1－…＋1A1A2An4/49《组合数学》第四章容斥原理nn＝SAi