第四章容斥原理.doc

第四章 容斥原理4.1引论 在求解计数问题时，用间接计数的方法往往比直接计数来得容易，这一章将讨论计数时常用的间接计数方法容斥原理及其在几个问题上的应用。例1 求1到600之间不能被6整除的整数个数。解 先计算1到600之间能被6整除的整数的个数，然后从总数中去掉它。1到600之间共有600个数，因为每6个连续的整数中恰有1个能被6整除，所以1到600之间共100个整数能被6整除。因而，1到600之间共有600-100500个整数不能被6整除。例2 求的1不在第一个位置上的全排列的个数。解 设小是的一个全排列，因1不在第一个位置上，所以。下面我们分别用直接计数和间接计数两种方法来计算此类排列的个数。(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的倍数的数有6个，即3，6，9，12，15，18。但不超过20的正整数中是2的倍数或是3的倍数的数不是10616个，而是下列13个：2，3，4，6，8，9，lO，12，14，15，16，18，20。其中，6，12，18三个数既是2的倍数又是3的倍数，若把是2的倍数的数的数目和是3的倍数的数的数目相加，则6，l 2，18三个数各重复计算了一次。所以，是2的倍数或是3的倍数的数的数目等于是2的倍数的数的数目和是3的倍数的数的数目之和减去既是2的倍数又是3的倍数的数目，即为106313个。例3是例l和例2的推广，下面我们用集合论来讨论例3所代表的一类问题。设S是一有限集合，和是两个性质，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.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中不具有性质的元素为 (4.2.1)证明 可以利用等式(4.1.1)，通过对作归纳进行证明（留给读者）。特别地，当时，。当时，。一般情况下，(4.2.1)式的右端共有。推论4.2.1 设S是一有限集合，是同集合S有关的m个性质，设是S中具有性质的元素构成的集合，则S中至少具有一个性质的元素个数为 (4.2.2)证明：因为，又，将上面两个等式代入定理4.2.1中的等式(4.2.1)。很容易得出结论。例1 1与1000之间不能被5，6，8整除的整数有多少个?解 令，则。记分别为1与1000之间能被5，6，8整除的整数集合，则有，。于是，表示中能被5和6整除的数，即能被30整除的数，其个数为；表示中能被5和8整除的数，即能被40整除的数，其个数为；表示中能被6和8整除的数，即能被24整除的数，其个数为；表示中能被5，6和8整除的数，即能被120整除的数，其个数为。由容斥原理，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中的任一个，共有个。类似地，有， ， 0。 而A，G，C，T至少出现一次的寡聚核苷酸片断集合即为，于是 。例3 欧拉函数表示小于n且与n互素的整数的个数，求。解 将n分解成素因子的乘积形式：，设为不大于n 且为的倍数的自然数的集合()，则因与互素，所以与的最小公倍数为，因此， 。小于n并与n互素的自然数是集合那些不属于任何一个集合的数，由容斥原理知 欧拉函数常用于数论中，例如，若，则， 小于20并与20互素的正整数为l，3，7，9，11，13，17，19。例4 若图G有n个顶点，且不含有完全k子图()，则它的顶点的次数满足不等式 (4.2.3) ， 其中，为图G的顶点集。在证明该结论之前，首先给出几个与该题有关的图的概念。图：一个图G是指一个有序二元组(V(G)，E(G)，)，其中V(G)是非空的d顶点集，E(G)是不与V(G)相交的边集，而是关联函数，它使G的每条边对应于G的无序顶点对(不必相异)。若是一条边，而和，是使得的顶点，则称连接和；而顶点和称为的端点。一般把一个图简记为。度：G的顶点的度(或次)是指G中与关联的边的数目，每个环算作两条边。用和分别表示G的顶点的最小度和最大度。不至于混淆的情况下，通常把写作。导出子图：假设，是一个非空子集。以为顶点集，以两端点均在中的边的全体为边集所组成的子图，称为G的由导出的子图，记为；称为G的导出子图。 完全图：每一对不同的顶点都有一条边相连的简单图称为完全图。个顶点的完全图记为。是完全图，且，则称是G的完全k子图。证明 设 即不妨设。若不等式(4.2.3)不成立，则对任意的，均有。在图G中任取一个顶点，用表示在图G中与相邻的那些顶点构成的集合。再取另一个顶点均和相应的集合，由容斥原理得到。这是因为集合和中的每一个至少包含个元素，而中至多只有n个无素(G中全部顶点)。再任取一个顶点，同上，由容斥原理可得等等。这样，我们可由归纳法得到对于，取G中与相邻的顶点集，有。因此，至少有一个顶点，由的定义知，之间相互相邻，所以顶点集合构成的导出于图是图G的完全子图，这与题设矛盾。故不等式(4.2.3)成立。利用定理4.2.1和推论4.2.1，我们可以算出S中不具有性质的元素个数和S中具有中某个性质的元素个数。下面将其推广到更一般的情形。设S是一有限集合，是S上的性质集合。现在的问题是要求出集合S中恰好具有中r个性质的元素个数。现用表示S中具有性质的元素个数，规定，令。若S中某元素恰好具有中个性质，则从中取出个性质的方法数为，因而在中计算了次。而对于S中具有中少于个性质的元素，则不计算在内。定理4.2.2 设集合S中具有性质集合中恰好r个性质的元素个数为，则 （4.2.4） 证明 设是集合S中的一个元素, 则 (1)若具有少于个性质，则对, ,的贡献均为0，从而对（4.2.4）式左右端的贡献均为0 (2)若恰好具有个性质，则对的贡献为1，而对的贡献均为0，从而对（4.2.4）式左右端的贡献均为1。 (3)若恰好具有个性质，则它对（4.2.4）左端贡献为0。而对的贡献为，对的贡献为，对的贡献为。当时，它对对的贡献为0。从而，它对（4.2.4）式右端的贡献为。综上所述，（4.2.4）式成立。例5 在1与1000之间，求（1） 不能被5，6，8整除的整数有多少个。（2） 只能被5，6，8之一整除的整数个数。（3） 只能被5，6，8中的两个整除的整数个数。（4） 被5，6，8三个数都整除的整数个数。 解：定义上的性质集合，其中分别表示在1与1000之间能被5，6，8整除。由例1的计算可知：，。因此有，。（1）。（2）。（3）（4）。 由此可见，定理4.2.2是定理4.2.1的推广。 例5 某学校有12位教师，己知教数学课的教师有8位，教物理课的教师有6位，教化学课的教师有5位。其中，有5位教师既教数学又教物理，有4位教师兼教数学和化学，兼教物理和化学的有3位教师，还有3位教师兼教这三门课。试问： (1)教数、理、化以外的课的教师有几位?(2)只教数、理、化中一门课的教师有几位?(3)正好教数、理、化中两门课的教师有几位? 解：设表示12位教师分别教数学课、物理课、化学课这一性质。由题意可知：，。因此有，。（1）。（2）。（3）。4.3 容斥原理的应用4.3.1 具有有限重复数的多重集合的组合数在第3章里，介绍了n元集合的组合数为，多重集合的组合数为。在本节中将应用容斥原理来计算重复数为任意给定的正整数的多重集合的r组合数。 下面通过一个例子来看看怎样用容斥原理解决上述问题，然而例子中所用的方法却适用于一般的情况。 例1 求的10组合数。 解 令，则的10组合数为。设集合是的10组合全体，则，现在要求在10组合中的个数小于等于3，的个数小于等于4，的个数小于等于5的组合数。定义性质集合 ， ：10组合中的个数大于等于4； ：10组合中的个数大于等于5； ：10组合中的个数大于等于6。由题意可知： 可以看作是由的l046组合再拼上4个构成的，所以。同理，。因此有，。所以，的个数小于等于3，的个数小于等于4，的个数小于等于5的组合数。4.3.2 错排问题集合的一个错排是该集合的一个满足条件的全排列,即集合的一个没有一个数字在它的自然顺序位置上的全排列。时，没有错排。时，有唯一的错排21。时，有两个的错排，分别为231和312。时，有9个的错排，分别为2143，3142，4123，2341，3412，4321，2413，3421和4312。用记的全部错排个数，则，。定理4.3.1 对任意正整数n，有。证明 令S是集合的全排列的全体，则。定义上的性质集合，其中表示排列中在左数第个位置上，即在其自然顺序的位置上。因中的每一个排列形如， 而是的全排列，所以有 ，同理，有，一般地，有，且互不相等。因此有，。 而为S中不满足性质的元素个数，由容斥原理，有。下面通过建立一个递推公式来求解的全部错排个数。为此，首先将的所有错排按照的取值分成类，记为的错排的全体，则显然有。令，则。而集合中的错排又可以分为两类：(1) ：，则是的一个错排，所以；(2) ：，则相当于的一个错排，所以。从而，并且有递推关系。对此递推关系稍加变形，得。因此 。再次得到前面用容斥原理推导出的从公式。在第5章中，我们还将专门讨论递推关系在组合问题中的应用。 4.3.3 有禁止模式的排列问题 在4.3.2中讨论了错排问题（有禁止位置的排列问题），即不在第个位置上的排列问题。本小节中将讨论有禁止模式的排列问题，在此类问题中，要讨论某些元素之间的某种相对位置不能出现的一类排列。先看下面的问题： 设某班有8位学生排成一队出去散步，第二天再列队时，同学们都不希望他前面的同学与前一天的相同，问有多少种排法? 一种可能的方法就是将这8位学生排的队掉个头，也就是让最后一名学生变为第一名，倒数第二名变为第二名，如此等等，但这只是很多种可能中的一种。若我们分别用1，2，8代表第一天列队时的第一、第二、第八位同学，则第一天的排队顺序为12345678，如上掉头后的排列为87654321。我们的问题是求第二次列队时不出现12，23，78这些模式的排列的个数。例如，3l 542876就是一个符合要求的排列，而25834761则不是，因为其中出现了34。 用表示的不出现12，23，(n-1)n这些模式的全排列的个数，并规定。时，21是唯一的一个满足要求的排列，。 时，213，321，132是3个可能的排列，。 时，有下列11种可能的排列，：4132，3142，2143，1324，4213，3214，2413，1432，4321，3241，2431。定理4.3.2 对