组合数学第九节容斥原理

《组合数学第九节容斥原理》由会员分享，可在线阅读，更多相关《组合数学第九节容斥原理（22页珍藏版）》请在金锄头文库上搜索。

1、3.2 容斥原理将 3.1 节讨论的原理进一步推广，总结成一般性规律，就得到定理 3.2.1 所描述的容斥原理。定理 3.2.1 设 S 是有限集合， 是同集合 S 有关的 m 个性质，设 是 S 中具有性质 的元素12,mP iAiP构成的集合 ， 是 S 中不具有性质 的元素构成的集合 ，则 S 中不具有性质1imiAi 1的元素个数为12,P（3.2.1）121,21,22mi ijiijikmmASAA 不不证明 可以利用等式（3.1.1） ，通过对 m 作归纳进行证明。下面通过其组合意义来证明。等式（3.2.1）的左端表示的是 S 中不具有性质 的元素的个数。下面我们来证明：对于 S

2、 中每12,P个元素 ，若 不具有性质 ，则对等式（3.2.1 ）的右端贡献 1；否则，若 x 具有某个性质x12,mP，则对等式（3.2.1）的右端贡献 0，从而证（3.2.1）式。1iPm任给 ，则xS（1）若 x 不具有性质 ，即 ，则 x 在集合 S 中，但不在（3.2.1）式右12,mP 12,mxAA端的任一其他集合中。所以，x 对（3.2.1）式右端的贡献为 001（2）若 x 恰具有 中的 个性质 ，则 x 对 的贡献为12,mP 1n12,iinP S0因 x 恰具有 n 个性质 ，所以 x 恰属于集合 ，共 n 个。于是，x 对 的贡献12,iinP 12,niiA iA为

3、 1n从 中选出两个性质，共有 种，所以 x 恰在 个形如 的集合中，x 对12,iinP 22kliiA的贡献为 ；同理，x 对 的贡献为 。而当 时，ijA2n12niiiA kn。所以 x 对（3.2.1）式右端的贡献为0nk 110230mnnxnn 综上所述， （3.2.1）式的右端是集合 S 中不具有性质 的元素的个数。证毕。12,mP若 ，则（ 3.2.1）式变成3m123231123123ASAA上面等式的右端共有 8项。若 ，则（3.2.1）式变成4m12342341112323106535486ASAA例 2 求由 四个字符构成的 n 位符号串中， 至少出现一次的符号串的数

4、目。,abcd,abcd解 设 分别为不出现 的 n 位符号串的集合。由于 n 位符号串的每一位都可取1234,A,四个符号中的任一个，所以共有 个。其中，不出现 的符号串的每一位都可取 中的任,c4n ,bcd一个，共有 个。类似地，有n123431,24,3;,12,340niijijkAijijk不而 至少出现一次的符号串集合即为 ，于是,abcd1234A123423411123243411234341246nnnAA例 3 欧拉函数 表示小于 n 且与 n 互素的整数的个数。求 。解 将 n 分解成素因子的乘积形式： 12qiip设 为不大于 n 且为 的倍数的自然数的集合 ，则：i

5、Aipi1,2iinAqp因 与 互素 ，所以 与 的最小公倍数为 ，所以ipjijij ijp;,12,ijijnAq。小于 n 并与 n 互素的自然数是集合 中那些不属任何一个集合 的1,2 1,2iAq数，由容斥原理知12411121112qiijiijqijkijqqiijqijqijijkqnAAnnpp 上面的和式正好是下列乘积的展开式： 121qnpp欧拉函数常用于数论中。例如，若 ，则21314小于 12 并与 12 互素的正整数为 1，5，7 和 11例 4 若图 G 有 n 个顶点，且不含有完全 k 子图 ，则它的顶点的次数 满足不等式2dx（3.2.3）min1xXknd

6、其中，X 为图 G 的顶点集。证明 设 2102knpkrk若不等式（3.2.3）不成立，则对任意的 ，均有 。xX在图 G 中任取一个顶点 ，用 和相应的集合 ，由容斥原理得到1x1A221120Apn这是因为集合 和 中的每一个至少包含 个元素，而 中至多只有 n 个元素（G 中全部顶点）1A2 12。再任取一个顶点 ，同上，由容斥原理可得312x1230Apn等等。这样，我们可由归纳法得到对于 ，取 G 中与 相邻的顶点集 ，有21kjxA1kx1kA1211221130kkjjkkkj jAAppnkkr因此，至少有一个顶点 。由 的定义知 之间相互相邻，所以顶点集合21kjxAj12

7、,kx构成的导出子图是图 G 的完全 k 子图，这与题设矛盾。故不等式（3.2.3）成立。12,kx利用定理 3.2.1 和推论 3.2.1，我们可以算出 S 中不具有性质 的元素个数和 S 中具有12,mP中某个性质的元素个数。下面我们将其推广到更一般的情形。12,mP设 S 是一有限集合， 是 S 上的性质集合。现在的问题是要求出集合 S 中恰好具有 P 中12,mPr 个性质的元素个数 。Nr现用 表示 S 中具有性质 的元素个数，规定 ，令12,iik 12,kiiP 0w1212,kkiiiimwkNP 若 S 中某元素 x 恰好具有 P 中 个性质 ，则从 中取出 k 个性质的0r

8、12,krii 12,kriiP方法数为 ，因而 x 在 中计算了 次。而对于 SK 具有 P 中少于 k 个性质的元素，则krkkr不计算在内。例如，在本节的例 1 中，有 1231232130,65,48,NPPN于是 01,265491,38.w在 中，对具有 3 个性质 的元素，在 和 中各计算了一次，共2w123,P1213,NP23,NP3 次。例如，120 能被 5，6，8 整除，所以， ，即 120 在000AA中共计算了 3 次。定理 3.2.2 设集合 S 中具有性质集合 恰好 r 个性质的元素个数为 ，则12,mP Nr（3.2.4）21.mrNrww证明 设 x 是集合

9、 S 的一个元素，则（1）若 x 具有少于 r 个性质，则 x 对 的贡献均为 0，从而对（3.2.4）式右端的,1,wrw贡献为 0。（2）若 x 恰好具有 r 个性质，则 x 对 的贡献为 1，而对 的贡献均为r1,2,rwm0，从而对（3.2.4）式右端的贡献为 1。（3）若 x 恰好具有 个性质，则它对 的贡献为 ，对 的贡献为 对krwrkrr,1kr的贡献为 ；当 时，它对 的贡献为 0。从而，它对（3.2.4）式右端的贡献为wklml11210lrklrlrklrlrkllrklxkkrkrl综上所述， （3.2.4）式的右端是 S 中恰好具有 r 个性质的元素个数。在例 1 中

10、，有 01236Nww它是 S 中不能被 5，6，8 整除的整数个数，这正是容斥原理所反映的事实。 231137它是 S 中只能被 5，6，8 之一整除的整数个数。 3275Nw它是 S 中只能被 5，6，8 中的两个整数的整数个数。 38由此可见了，定理 3.2.2 是定理 3.2.1 的推广。例 5 某学校有 12 位教师，已知教数学课的教师有 8 位，教物理课的教师有 6 位，教化学课的教师有 5位。其中，有 5 位教师既教数学又教物理，有 4 位教师兼教数学和化学，兼教物理和化学的有 3 位教师，还有 3 位教师兼教这三门课。试问：（1）教数、理、化以外的课的教师有几位？（2）只教数、

11、理、化中一门课的教师有几位？（3）正好教数、理、化中两门课的教师有几位？解 令 12 位教师中教数学课的教师属于集合 ，教物理课的教师属于集合 ，教化学的教师属于集合1A2A，则有3A1231232138,65,4,AA（1）不教数学、物理、化学课的教师数目为 123123231238654AA（2）只教数、理、化中一门课的教师数目为 12312312386544.NAA（3）正好教数、理、化中两门课的教师数目为 121323354.NAA3.3 容斥原理的应用：3.3.1 具有有限重复数的多重集合的 r 组合数在第 2 章里，我们介绍了 n 元集合 的 r 组合数为 ，多重集合12,nx n

12、r的 r 组合数为 。在本节中，我们将应用容斥原理来计算重复数为12,nMx 1r任意给定的正整数的多重集合的 r 组合数。下面通过一下例子来看看怎样用容斥原理解决上述问题，然而例子中所用的方法却适用于一般的情况。例 1 求 的 10 组合数。3,45Sabc解 令 ，则 的 10 组合数为：,SabcS103126设集合 A 是 的 10 组合全体，则 ，现在要求在 10 组合中 的个数小于等于 3，b 的个数小于6Aa等于 4，c 的个数小于等于 5 的组合数。定义性质集合 123,P其中： 组合中的 的个数大于等于 4； 组合中 b 的个数大于等于 5； 组合中 c 的个数1:0Pa2:

13、03:10P大于等于 6。将满足性质 的 10 组合体记为 。那么， 的元素可以看作是由 的iPiA1AS组合再拼上 4 个 构成的，所以4210537类似地，有 10431826A3105412031A130463122310,A而 的个数小于等于 3，b 的个数小于等于 4，c 的个数小于等于 5 的 10 组合全体为a123123231236850AA3.3.2 错排问题：集合 的一个错排是该集合的一个满足条件：1,2n 1jijn的全排列。即集合 的一个没有一个数字在它的自然顺序位置上的全排列。时， 没有错排。1n时， 有唯一一个错排，为 21。2,时 有两个错排，分别为 231 和 3123时， 共有下面所列的 9 个错排：4n1, 2143,2,341,用 记 的全部错排个数，则nD1,2 12340,9DD定理 3.3.1 对任意正整数 n，有： 11!nn证明 令 S 是 的全排的全体，则 。定义 S 上的性质集合：1,2 S12,nP其中， 表示排列中 i 在左数第 i 个位置上，即在其自然顺序的位置上 。令 为 S 中满足性质iP iiA的全排列的全体。i因 中的每一个全排列形如：iA11injj 而 是 的全排列