《广义容斥原理》由会员分享，可在线阅读，更多相关《广义容斥原理（16页珍藏版）》请在金锄头文库上搜索。
1、点算的奥秘：容斥原理基本公式容斥原理(Principle of Inclusion and Exclusion)(亦作排容原理)是点算组合学中的一条重要原理。但凡略为复杂、包含多种限制条件的点算 问题，都要用到这条原理。现在首先从一个点算问题说起。例题1：设某班每名学生都要选修至少一种外语，其中选修英语的学生人数为25， 选修法语的学生人数为18，选修德语的学生人数为20，同时选修英语和法语的 学生人数为8，同时选修英语和德语的学生人数为13 ，同时选修法语和德语的 学生人数为6，而同时选修上述三种外语的学生人数则为3，问该班共有多少名 学生？答1：我们可以把上述问题表达为下图：其中红色、绿色
2、和蓝色圆圈分别代表选修英语、法语和德语的学生。根据三个圆 圈之间的交叉关系，可把上图分为七个区域，分别标以A至G七个字母。如果我 们用这七个字母分别代表各字母所在区域的学生人数，那么根据题意，我们有以 下七条等式：(1) A+D+E+G = 25； (2) B+D+F+G = 18； (3) C+E+F+G = 20； (4) D+G =8；(5) E+G = 13； (6) F+G = 6； (7) G = 3。现在我们要求的是 A+B+C+D+E+F+G。如何利用以上数据求得答案？ 把头三条等式加起来，我们得到A+B+C+2D+2E+2F+3G = 63。可是这结果包含了 多余的D、E、F
3、和G,必须设法把多余的部分减去。由于等式(4) (6)各有一个 D、E和F,若从上述结果减去这三条等式，便可以把多余的D、E和F减去，得 A+B+C+D+E+F = 36。可是这么一来，本来重复重现的G却变被完全减去了，所以 最后还得把等式(7)加上去，得最终结果为A+B+C+D+E+F+G = 39,即该班共有39 名学生。口在以上例题中，给定的数据是三个集合的元素个数以及这些集合之间的交集的元 素个数。在该题的解答中，我们交替加上及减去这些给定的数据。如果我们用S、S和S分别代表选修英语、法语和德语学生的集合，那么我们要求的答案就123是|S U S U S |,而该题的解答则可以重新表达
4、为123Is u s u s | = (|s | + |s | + |s I) (|s n s | + |S n s | + |S n1 2 3 1 2 3 1 2 1 3 2sI) + Is n s n sI3 1 2 3我们可以把上式推广至集合个数为n的情况，便得到以下的容斥原理。设有 n个集合s、S . s，那么12nI=s1u s2u . snI(IsI + IsI + . IsI)=12n (Is n1+ (Is1 n n sI) 1nsI + Is n sI + .2 1 3s n sI + Is n s2 3 1 2. Is n sI)n 1nn sI + . Is4n 2sn(
5、IsI)s n s n sI +234Is n s n s nn 3n 2n 1s n sIn 1n(1)+ ( 1)n 1 Is n s n .12有必要对上式作一些解释。为易于理解，上式分数行列出，每一行都是一些集合 元素个数的总和，其中第1行包含全部n个集合SS2. S；第2行包含所有 由2个集合构成的交集，应共有C(n, 2)个项；第3行2包含所有由3个集合构成 的交集，应共有C(n, 3)个项.第n行包含由全部n个集合构成的交集，这样 的交集只有C(n, n) = 1个。每行的开首交替为一个加(相当于容纳) 和一个减(相当于排斥)号，第1行开首为加号，第2行为减号， 第3行为加号，第
6、4行为减号。由于当k为奇数时，(1)k = 1； 当k为偶数时，(1)k=1，我们可以把第1行开首的加号改写为+ (-1)。， 把第2行开首的减号改写为+ (-1)1.如此类推，我们可知第k行开首 应有一个+ (1)k 1。我们还可以把上式化简，方法是引入一个新的变项S来代表上式等号右边的第n,kk行。S是由C(n, k)个项加起来的总和，每个项都是由S、S . S这n个n, k12n集合中抽r个出来构成的交集的元素个数。举例说，当n二5，k = 3时，S5, 3是由C(5, 3) = 10个项加起来的总和，这10个项都是由S . S这5个集合 15中抽3个出来构成的交集的元素个数，其中一个是
7、|S n S n S |，其余类推。 利用S以及工求和符号，我们便可以把上面的容斥原理公式大大简化为： n,kIs u S u . S | =工(1)k- 1S(2)12n1 W k W nn, k接着让我们证明以上容斥原理公式(1)的正确性，为此我们必须证明，S1.S这n个集合中的每一个元素在公式中都只被加一次。我们逐一考虑各种集合元 素的情况。首先考虑那些只包含于一个集合中的元素，每个这类元素只出现于上 述公式的第1行n个集合的其中一个，因此只会被加一次。其次考虑那些包含于 两个集合的元素，每个这类元素都出现于上述公式的第1行n个集合的其中两个, 并且出现于第2行C(n, 2)个交集的其中
8、一个。由于每个这类元素在第1行中被 加两次并在第2行中被减一次，因此结果该元素在公式中被加一次。=工(1) r1 W r W k我们把上述推理推广至一般情况，即考虑那些包含于k个集合的元素。每个这类 元素都出现于第1行的其中C(k, l)=k个集合，并且出现于第2行的其中C(k, 2)个交集，并且出现于第3行的其中C(k, 3)个交集.并且出现于第k行的其 中C(k, k) = 1个交集(注1)。总括而言，每个这类元素在公式中被加的次数为C(k, 1) - C(k, 2) + C(k, 3)- C(k, 4) (-)k- 1 C(k, k)- 1 C(k, r)现在的问题是，如何证明上式等于1
9、?答案是借助点算的奥秘：二项式定理和多项式定理中介绍的二项式定理：(a + b)n =工C(n, r) ab0 W r W n为了应用二项式定理，我们首先把上式等号右边重写：工(-1)r - 1 C(k, r)=1 Wr W k工(-1)r C(k, r)1 W r W k工(-1) r C(k, r) (-1)0 C(k, 0)0 W r W k工C(k, r) (-1) r + 10 W r W k现在如果把二项式定理中的a、b和n分别设定为T、1和k,便得到工0WrC(k, r) (-1)r = (-1 + 1)k = 0。把这个结果代入上面最后一行，我们便得 到工(-1)r- 1 C(
10、k, r) = -0 + 1 = 1。至此我们证明了每一个元素在容1 W r W k 斥原理公式中都被加一次，因此该公式是正确的。在应用上述容斥原理公式(1)时，我们必须逐一找出所有集合以及各种交集 的元素个数，有时这是颇为繁琐的工作，会令上述公式失去价值，因此容斥原 理一般应用于可交换集合(Exchangeable Sets)。如果从n个集合S、S . S中任意抽取k个出来(1 W r W n)，所得交集的元素个数只跟k有关，而跟 抽取结果无关，则我们说这n个集合是可交换的。换句话说，不论是由哪k 个集合构成的交集，所得交集的元素个数都是同一个数字。上面容斥原理公式(1)的第k行的每一项都是
11、由k个集合构成的交集的元素 个数。如果S、S . S是可交换集合，那么该行的每一项都是同一个数 字，可不妨用符号斤来代表。由于该行共有C(n, k)个项，所以该行可简化为(-1)k k-1 C(n, k) n。因此，可交换集合的容斥原理公式便是k|S U S U . S | =工(-1)k- 1 C(n, k) n (3)12n1 W k W nk在某些应用中，所求的答案是不属任何指定集合的元素个数，因此我们需要找出 以上容斥原理公式的变化形式。设某论域U包含n个集合S、S . S，现12n在我们要求不属这n个集合的任何一个的元素个数，即|s n S n . s|(注12n2)。根据集合论的德
12、.摩根律(De Morgans Law)，S n S n . S 等12n于u u s u . s)，因此 Is】n s n . s| = |u| - |S u S2 u . S | = |U| + (-|s u s u . s |)2(注3)。应用上面的容斥原理2 公式(2)，我们便得到|S n s n . s | = |U| + 工(1)kS(4)12n1 W k W nn, k同理，如果S、S . S是可交换集合，那么上式便变成1 2 nIs n S n . S | = |U| + 工（l）k c（n, k） n （5）12n1 W k W nk现在让我们来看看容斥原理的一些简单应用例子
13、。有关该原理的其他应用， 以后还会谈到。例题2：从26个英文字母中（可重复地）抽取10个出来排成字符串（String）（无 需考虑这个字符串是否构成一个英文单词），其中不可包含全部5个元音字母（即 A、E、I、0、U）,问有多少种排法？答2：利用容斥原理解题的关键在于，把原题表达为适当的集合。就本题而言，如果我们用S来代表所有由10个字母组成但不含A的字符串集合.用S 来代表所有由10个字母组成但不含U的字符串集合，那么本题所要求的答案就 是|Sr US U U S US。由于5个元音字母具有平等的地位，从s、Se、S、S和S这5个集合中任意抽取k个出来所构成的交集的元素个数都是一样的，I O
14、 U 所以这5个集合是可交换的。因此我们可以用上面的公式（3）来解题，但须 先求得n （1 W k W 5）的值。k我们先求n的值，这个值相当于由10个字母组成但不含A、E、I、0、U中某一 个字母的字1符串的数目。由于撇除了一个字母，我们可以从余下的25个字母中 （可重复地）抽取10个出来排成字符串，这是一个无限重覆排列问题，应共 有2510个这样的字符串，即n二2510。1接着考虑n,这个值相当于由10个字母组成但不含A、E、I、0、U中某两个字 母的字符串2的数目。由于撇除了两个字母，我们可以从余下的24个字母中（可重 复地）抽取10个出来排成字符串，因此n =2410。读到这里，相信读者应能看到2n = （26 k）10。k工(1)k 1 C(5, k) (26 k)1 W k W 5X最后，运用上面公式（3），本题的答案是10 = 5 X 2510 10 X 2410 + 10 X 2310 5 2210 + 2110 由于具体数字太大，这里只列出其算式。事实上，点算组合学经常要和这样 的天文数字打交道。若非靠逻辑思维，实在难以想象人类有何方法求得这类 问题的答案，由此可见逻辑思维的巨大力量！ 口例题3：现要把一对可区别的火星人、一对可区别的木星人和一对可区别的土星 人安排坐在一排共6个座位上。如规定同一类外星人不得坐在相邻的位置上，问 有多少种不同坐法？答3：如果
