组合数学-第九节：容斥原理.doc

3.2 容斥原理将3.1节讨论的原理进一步推广，总结成一般性规律，就得到定理3.2.1所描述的容斥原理定理3.2.1 设S是有限集合，是同集合S有关的m个性质，设是S中具有性质的元素构成的集合，是S中不具有性质的元素构成的集合，则S中不具有性质的元素个数为 （3.2.1）证明 可以利用等式（3.1.1），通过对m作归纳进行证明下面通过其组合意义来证明等式（3.2.1）的左端表示的是S中不具有性质的元素的个数下面我们来证明：对于S中每个元素，若不具有性质，则对等式（3.2.1）的右端贡献1；否则，若x具有某个性质，则对等式（3.2.1）的右端贡献0，从而证（3.2.1）式任给，则（1）若x不具有性质，即，则x在集合S中，但不在（3.2.1）式右端的任一其他集合中所以，x对（3.2.1）式右端的贡献为 （2）若x恰具有中的个性质，则x对的贡献为 因x恰具有n个性质，所以x恰属于集合，共n个于是，x对的贡献为 从中选出两个性质，共有种，所以x恰在个形如的集合中，x对的贡献为；……；同理，x对的贡献为而当时，所以x对（3.2.1）式右端的贡献为 综上所述，（3.2.1）式的右端是集合S中不具有性质的元素的个数。

证毕若，则（3.2.1）式变成 上面等式的右端共有 项若，则（3.2.1）式变成 例2 求由四个字符构成的n位符号串中，至少出现一次的符号串的数目解 设分别为不出现的n位符号串的集合由于n位符号串的每一位都可取四个符号中的任一个，所以共有个其中，不出现的符号串的每一位都可取中的任一个，共有个类似地，有 而至少出现一次的符号串集合即为，于是 例3 欧拉函数表示小于n且与n互素的整数的个数解 将n分解成素因子的乘积形式：设为不大于n且为的倍数的自然数的集合，则：因与互素，所以与的最小公倍数为，所以 ……小于n并与n互素的自然数是集合中那些不属任何一个集合的数，由容斥原理知 上面的和式正好是下列乘积的展开式：欧拉函数常用于数论中例如，若，则 小于12并与12互素的正整数为1，5，7和11例4 若图G有n个顶点，且不含有完全k子图，则它的顶点的次数满足不等式 （3.2.3）其中，X为图G的顶点集证明 设 若不等式（3.2.3）不成立，则对任意的，均有在图G中任取一个顶点，用和相应的集合，由容斥原理得到 这是因为集合和中的每一个至少包含个元素，而中至多只有n个元素（G中全部顶点）再任取一个顶点，同上，由容斥原理可得 等等。

这样，我们可由归纳法得到对于，取G中与相邻的顶点集，有 因此，至少有一个顶点由的定义知之间相互相邻，所以顶点集合构成的导出子图是图G的完全k子图，这与题设矛盾故不等式（3.2.3）成立利用定理3.2.1和推论3.2.1，我们可以算出S中不具有性质的元素个数和S中具有中某个性质的元素个数下面我们将其推广到更一般的情形设S是一有限集合，是S上的性质集合现在的问题是要求出集合S中恰好具有P中r个性质的元素个数现用表示S中具有性质的元素个数，规定，令 若S中某元素x恰好具有P中个性质，则从中取出k个性质的方法数为，因而x在中计算了次而对于SK 具有P中少于k个性质的元素，则不计算在内例如，在本节的例1中，有 于是 在中，对具有3个性质的元素，在和中各计算了一次，共3次例如，120能被5，6，8整除，所以，，即120在中共计算了3次定理3.2.2 设集合S中具有性质集合恰好r个性质的元素个数为，则 （3.2.4）证明 设x是集合S的一个元素，则（1）若x具有少于r个性质，则x对的贡献均为0，从而对（3.2.4）式右端的贡献为02）若x恰好具有r个性质，则x对的贡献为1，而对的贡献均为0，从而对（3.2.4）式右端的贡献为1。

3）若x恰好具有个性质，则它对的贡献为，对的贡献为对的贡献为；当时，它对的贡献为0从而，它对（3.2.4）式右端的贡献为 综上所述，（3.2.4）式的右端是S中恰好具有r个性质的元素个数在例1中，有 它是S中不能被5，6，8整除的整数个数，这正是容斥原理所反映的事实 它是S中只能被5，6，8之一整除的整数个数 它是S中只能被5，6，8中的两个整数的整数个数 由此可见了，定理3.2.2是定理3.2.1的推广例5 某学校有12位教师，已知教数学课的教师有8位，教物理课的教师有6位，教化学课的教师有5位其中，有5位教师既教数学又教物理，有4位教师兼教数学和化学，兼教物理和化学的有3位教师，还有3位教师兼教这三门课试问：（1）教数、理、化以外的课的教师有几位？（2）只教数、理、化中一门课的教师有几位？（3）正好教数、理、化中两门课的教师有几位？解 令12位教师中教数学课的教师属于集合，教物理课的教师属于集合，教化学的教师属于集合，则有 （1）不教数学、物理、化学课的教师数目为 （2）只教数、理、化中一门课的教师数目为 （3）正好教数、理、化中两门课的教师数目为 3.3 容斥原理的应用：3.3.1 具有有限重复数的多重集合的r组合数在第2章里，我们介绍了n元集合的r组合数为，多重集合的r组合数为。

在本节中，我们将应用容斥原理来计算重复数为任意给定的正整数的多重集合的r组合数下面通过一下例子来看看怎样用容斥原理解决上述问题，然而例子中所用的方法却适用于一般的情况例1 求的10组合数解 令，则的10组合数为：设集合A是的10组合全体，则，现在要求在10组合中的个数小于等于3，b的个数小于等于4，c的个数小于等于5的组合数定义性质集合 其中：组合中的的个数大于等于4；组合中b的个数大于等于5；组合中c的个数大于等于6将满足性质的10组合体记为那么，的元素可以看作是由的组合再拼上4个构成的，所以 类似地，有 而的个数小于等于3，b的个数小于等于4，c的个数小于等于5的10组合全体为 3.3.2 错排问题：集合的一个错排是该集合的一个满足条件：的全排列即集合的一个没有一个数字在它的自然顺序位置上的全排列时，没有错排时，有唯一一个错排，为21时有两个错排，分别为231和312时，共有下面所列的9个错排： 用记的全部错排个数，则定理3.3.1 对任意正整数n，有：证明 令S是的全排的全体，则定义S上的性质集合：其中，表示排列中i在左数第i个位置上，即在其自然顺序的位置上令为S中满足性质的全排列的全体。

因中的每一个全排列形如：而是的全排列，所以有：同理，有：一般地，有：其中，且互不相等而为S中不满足性质的元素个数，由容斥原理，有 我们还可以从另外一个角度来计算设：是的一个错排，我们将的所有错排按照的取值分成类，记为的错排的全体，则显然有：令，则：而集合中的错排又可以分为两类：（i），则是的一个错排，所以；（ii），则相当于的一个错排，所以从而：并且有递推关系：对此递推关系稍加变形，得 因此： 再次得到前面用容斥原理推导出的公式在第4章中，我们还将专门讨论递推关系在组合问题中的应用3.3.3 有禁止模式的排列问题在3.3.2小节中我们讨论了禁止位置的排列问题，即i不在第i个位置上的排列问题本小节我们来讨论有禁止模式的排列问题，在此类问题中，要讨论某些元素之间的某种相对位置不能出现的一些排列先看下面的问题：设某班有8位学生排成一队出去散步，第二天再列队时，同学们都不希望他前面的同学与前一天的相同，问有多少种排法？一种可能的方法就是将这8位学生排的队掉个头，也就是让最后一名学生变为第一名，倒数第二名变为第二名，如此等等，但这只是很多种可能中的一种若我们分别用1，2，……8代表第一天列队时的第一、第二、……第八位同学，则第一天的排队顺序为12345678，如上掉头后的排列为87654321。

我们的问题是求第二次列队时不出现12，23，……78这些模式的排列的个数例如，31542876就是一个符合要求的排列，而25834761则不是，因为其中出现了34用表示的不出现12，23，……，这些模式的全排列的个数，并规定时，21是唯一的一个满足要求的排列，时，213，321，132是3个可能的排列，时，有如下11种可能的排列， 定理3.3.2 对任意正整数n，有 证明 令S为的所有全排列，则定义性质集合 其中，表示全排列中出现模式，设为S中满足性质的全排列在全体，则中的每一个排列都可看作元集合的一个全排列，所以 同理 一般地，有 其中互不相等，且而为S中不满足性质的元素个数，由容斥原理，有 从和的显式表达式可以看出： 例2 多重集合的全排列中不出现模式的排列有多少种？解 令S为M的全排列全体，则有 定义性质集合 其中： 全排列中出现模式； 全排列中出现模式； 全排列中出现模式用分别表示S中具有性质的全排列全体中的全排列出现模式，我们将看作一个字符，则中的全排列就是多重集合的全排列，所以 同理，有 由容斥原理知，满足条件的排列个数为 例3（menage 问题） n对夫妇参加宴会围桌就座，要坟男女相间并且每对夫妇两人不得相邻，问有多少种就座方式？解 易知时这样的坐法是不存在的，今设。

设想先让n位女士围桌入座，其方法有种选定n位女士的一种入座方法，从某一位开始对这n位女士按环形顺序编号为1，2，……，n，并将编号的i的女士的丈夫也编号为i第i位女士与第位女士之间的位置称为第i号位置，第n位女士与第1位女士之间的位置称为n那么，第1位男士除第n号和第1位位置外，可以在其他个座位中的任何一个就座；第i位男士除了第号和第i号位置外，可以在其他个座位中的任何一个就座假定n位男士已全部入座，在第i号位置就座的男士编号为，则为的一个全排列根据题意，必须满足因而，符合题意的坐法对应的排列应当使得 （3.3.1）中的任一列都无相同的数我们称为的一个二重错排的二重错排的个数称为ménage数记为，求ménage数的问题称为既化的ménage问题这样，原问题就变成求ménage数的，而围桌入座的方法数等于为求，定义n个性质如下： 或 或1则是不具有性质的全排列的数目，由定理3.2.2知令S是的全排列全体，由的定义，有：而：我们先求设排列：满足性质，则或，而：为集合的全排列，所以：从而：一般地，有：但由于计算有困难，这里我们直接计算，假定的一个排列中有k个数分别满足性质，即 再将这个元素补上，就构成的一个满足性质的全排列。

因而，对于一组，能构造出个满足性质的全排列下面的问题是有多少个k元组满足中的k个性质满足k个性质的k序列也就是在序列（3.3.1）中分别为第列，第列，……第列的前两行中取出k个不同的数，换个说法也就是从： （3.3.2）的第个，第个，……第个括号中取出k个彼此不同的数将序列（3.3.2）中的括号去掉，变成 （3.3.3）则从序列（3.3.2）的k个不同的括号中取出k个彼此不同的数等价于从序列（3.3.3）中取出满足下列条件的k序列：（i）任何两数皆不相邻；（ii）头尾两数不能同时为1序列（3.3。