第四章容斥原理

《第四章容斥原理》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、第四章容斥原理4.1引论在求解计数问题时，用间接计数的方法往往比直接计数来得容易，这一章将讨论计数时常用的间接计数方法－容斥原理及其在几个问题上的应用。例1求1到600之间不能被6整除的整数个数。解先计算1到600之间能被6整除的整数的个数，然后从总数中去掉它。1到600之间共有600个数，因为每6个连续的整数中恰有1个能被6整除，所以1到600之间共＝100个整数能被6整除。因而，1到600之间共有600-100＝500个整数不能被6整除。例2求的1不在第一个位置上的全排列的个数。解设小是的一个全排列，因1不在第一个位置上，所以。下面我们分别用直接计数和间接计数两种方法来计算此类排列的个数

2、。(1)直接计数。因，所以有种取值，即可取。当确定以后，的全排列数为，由乘法原则知的全排列数为。(2)间接计数。的全排列的个数为。若，则是的全排列，所以的第一个位置为1的全排列共有。因而，1不在第一个位置上的全排列共有个。在上面的例子中，我们使用间接计数的方法解决了题设的计数问题，它基于的原理可以用集合论的语言叙述如下；设A是有限集合S的一个子集，则A中元素的个数等于S中元素的个数减去S中不在A内的元素的个数。若记，则可写成。例3求不超过20的正整数中，是2的倍数或是3的倍数的数的个数。解不超过20的正整数中，是2的倍数的数有10个，即2，4，6，8，10，12，14，16，18，20；是3

3、的倍数的数有6个，即3，6，9，12，15，18。但不超过20的正整数中是2的倍数或是3的倍数的数不是10＋6＝16个，而是下列13个：2，3，4，6，8，9，lO，12，14，15，16，18，20。其中，6，12，18三个数既是2的倍数又是3的倍数，若把是2的倍数的数的数目和是3的倍数的数的数目相加，则6，l2，18三个数各重复计算了一次。所以，是2的倍数或是3的倍数的数的数目等于是2的倍数的数的数目和是3的倍数的数的数目之和减去既是2的倍数又是3的倍数的数目，即为10＋6－3＝13个。例3是例l和例2的推广，下面我们用集合论来讨论例3所代表的一类问题。12设S是一有限集合，和是两个性质

4、，S中的每个元素具有或者不具有性质或，现在要计算S中既不具有性质也不具有性质的元素的个数。为此，我们从中去掉具有性质的元素个数，再去掉具有性质的元素个数，这样就将既具有性质又具有性质的元素个数从中去除了两次，所以要补一次。设分别是S中具有性质，的元素构成的集合，则就是S中既不具有性质性质也不具有性质的元素构成的集合，且有(4.1.1)我们可以如下形式地证明等式(4.1.1)：对S中任一元素，若既不具有性质也不具有性质，则对(4.1.1)式的右端贡献1；否则对(4.1.1)式的右端贡献0，从而(4.1.1)式的右端就是S中同时不具有性质和的元素个数。任给，则(1)若，则，，且。所以对(4.1.

5、1)式左右端的贡献为(2)若，则或，以下分情况讨论：(a)但，则，则对(4.1.1)式左右端的贡献为；(b)但，则，则对(4.1.1)式左右端的贡献为；(c)且，则，则对(4.1.1)式左右端的贡献为。综合上述分析，等式(4.1.1)成立。4.2容斥原理将4.1节讨论的原理进一步推广，总结成一般性规律，就得如下定理。定理4.2.1设S是有限集合，是同集合S有关的m个性质，设是S中具有性质的元素构成的集合，是S中不具有性质的元素构成的集合，则S中不具有性质的元素为12(4.2.1)证明可以利用等式(4.1.1)，通过对作归纳进行证明（留给读者）。特别地，当时，。当时，。一般情况下，(4.2.1

6、)式的右端共有。推论4.2.1设S是一有限集合，是同集合S有关的m个性质，设是S中具有性质的元素构成的集合，则S中至少具有一个性质的元素个数为(4.2.2)证明：因为，又，将上面两个等式代入定理4.2.1中的等式(4.2.1)。很容易得出结论。例11与1000之间不能被5，6，8整除的整数有多少个?解令，则。记分别为1与1000之间能被5，6，8整除的整数集合，则有，，。于是，表示中能被5和6整除的数，即能被3012整除的数，其个数为；表示中能被5和8整除的数，即能被40整除的数，其个数为；表示中能被6和8整除的数，即能被24整除的数，其个数为；表示中能被5，6和8整除的数，即能被120整除

7、的数，其个数为。由容斥原理，1与1000之间不能被5，6，8整除的数的个数为。例2求由A，G，C，T四个碱基构成的长为n的寡聚核苷酸片断（DNA链）中A，G，C，T至少出现一次的寡聚核苷酸片断的数目。解设分别为不出现A，G，C，T的长为n的寡聚核苷酸片断的集合。由于长为n的寡聚核苷酸片断的每一位都可取A，G，C，T四个碱基中的任一个，所以共有个。其中，不出现A的寡聚核苷酸片断的每一位都可取G，C，T中的任一个