第１３卷第２期 西安文理学院学报：自然科学版 Ｖ０Ｉ．１３ Ｎｏ．２ ２０１０年４月 Ｊｏｕｒｎａｌ ｏｆ Ｘｉ’ａｌｌ Ｕｎｉｖｅｒｓｉｔｙ ｏｆ Ａｒｔｓ＆Ｓｃｉｅｎｃｅ（Ｎａｔ Ｓｃｉ Ｅａ） Ａｐｒ．２０１０ 文章编号：１００８－５５６４（２０１０）０２－００２５－０３ 容斥原理的应用 邬毅，于静静 （重庆科技学院数理系，重庆４０１３３１） 摘要：容斥原理是组合数学的一个基本的计数原理．通过给出容斥原理的两种等价形式，来探讨 容斥原理在排列组合、数论、图论以及代数中有关解决有限集合计数问题方面的应用． 关键词：容斥原理；有限集合计数；组合数 中图分类号：Ｏ１５７．１ 文献标识码：Ａ 首先给出容斥原理的两种等价形式，即下面的定理１和定理２． 定理１［】 （容斥原理的简单形式）：设Ｊｓ是有限集合，Ｐ ，Ｐ２，…，Ｐ 是同集合ｓ有关的ｍ个性质． 设Ａｉ表示Ｊｓ中具有性质Ｐ 的元素构成的集合（１≤ｉ≤ｍ），Ａ 是．ｓ中不具有性质Ｐ 的元素构成的集合 （Ｉ≤ ≤ｍ），则有： （Ｉ）Ｊｓ中不具有性质Ｐ，，Ｐ２，…，Ｐ 的元素数是 ＩＡ１ ｎＡ２…ＮＡ Ｉ＝ＩＳＩ—ＥＩＡ‘Ｉ＋ｆ：ｌ １ ｆ葛 ＩＡｉ ｎａｉ ｌ一１ ｌ录ｋ＂ＺｍＩＡｉ ｎＡｊ ｎＡ Ｉ＋…＋（一１） ＩＡｌ ＮＡ２ ｎ…ＮＡｍ Ｉ （Ⅱ）在Ｉｓ中至少具有一条性质的元素数是 ＩＡ１ ｕＡ２‘ ｕ…ｕＡ Ｉ＝∑Ｉ”’ Ａｉ Ｉ一 ∑ ＩＡｉ’ ＮＡｙ Ｉ＋ ｉ＝１ ‘ １＜ｉ＜ｊ＜－１ｓｉ＜，＜七 ｍ ．．；．．１Ａｌ。 ｎＡ，ＮＡ ｌ一…＋（一１）』 ‘ ＩＡ１‘ ＮＡ２‘ ｎ…ＮＡ ｌ”。 －ｍ （证明见文献［１］） 定理２… （容斥原理的一般形式）设集合Ｉｓ中具有性质集合Ｐ＝｛Ｐ ，Ｐ２，…，Ｐ ｝中恰好ｒ个性质 的元素个数为Ⅳ（ｒ），则 Ⅳ（ｒ） ＋１）＋（ （ｒ＋２）－．．．＋（－１广 （ （证明见文献［１］） ｌ容斥原理在错排问题中的应用 利用答斥原理司以轻而易举得地得出在依次给以标号１，２，…，ｎ的ｎ个兀素的全排列中，每个兀素 都不在自己原来位置上的排列数，其递推公式为： Ｄｎ＝ｎｌ（１一 １＋ １一·＋（一１） ）． （证明见文献［２］） 例１数１、２，３、…、９的全排列中，求偶数在原来位置上，其余都不在原来位置上的错排列数目． 解析 －￣＿ｋｇ Ｉ、３、５、７、９五个数的错排问题，由递推公式得其总数为：Ｄｓ＝５ １×（１一 １＋ １一 ＋者一 ）＝４４． 收稿日期：２００９－１１－２８ 作者简介：邬毅（１９８２一），男，重庆人，重庆科技学院数理系讲师，硕士．研究方向：组合数学 西安文理学院学报：自然科学版 第１３卷 此外，答斥原理在有条件的排列ｌ司越和有禁区的羽｝夕ＵＩ司越中都有厂泛的应用，举例详见有关文就 ２容斥原理在多重集的ｒ组合数中的应用 例２确定多重集Ｓ＝｛２·ｎ，２·ｂ，４·ｃ｝的４一组合数． 分析设有多重集Ｓ＝｛ ·ａ。，ｎ ·口 ，…， ·ａ ｝，要求它的ｒ一组合数，如果某个ｎ ＞ｒ，可用ｒ来 代替 得到多重集Ｓ ．不难看出Ｓ 的卜．组合数就是Ｓ的ｒ一组合数，所以不妨假设所有的 ≤ｒ，ｉ＝１， ２，…，ｋ． 解令ｓ ＝｛∞·口，∞·６，∞·ｃ｝，￣Ｊｌ Ｓ＇的组合数为（ｎ＋，ｒ－１）＝（４＋４３－１）＝ｌ５，设集合Ａ是 的 组合全体，则ＩＡｌ＝１５，现在要求在４一组合中ａ的个数≤２，ｂ的个数≤２，ｃ的个数≤４～的组合数，定义 性质集合Ｐ＝｛Ｐ。，Ｐ ，Ｐ，｝，其中Ｐ ，Ｐ ，Ｐ，分别表示４一组合数中ａ的个数＞１３，ｂ的个数＞１３，ｃ的个数 １＞５的集合．将满足性质Ｐ 的４一组合全体记为Ａｉ（ｉ＝１，２，３）．那么，Ａ，中的元素可以看作是由Ｓ 的４ —３＝１组合再拼上３个口构成的，所以有： ＝（４＿４３＿ ３一 ）＝３，一 ＝４－４３一＋３３－１）＝３，·Ａ。，＝４＿４ ３一 ）＝。， －故Ｉ ｌ ｎＡ２ Ｉ－４－３４一３＋３一３３一 ）＝ｏ，同理ｌ ｌ ｎ ３ Ｉ＝ｏ，Ｊ ２ ｎＡ３ Ｉ＿０，ＪＡ１ ｎＡ２／ｑＡ３ Ｉ＝０．而口的个数 ≤２，ｂ的个数≤２，ｃ的个数≤４组合全体为 ｎ ｎＡ一３，由容斥原理，它的元素个数为 ｌ ｎ ｎＡ一３ １＝ＩＡ Ｉ一（ＩＡｌ ｌ＋ＩＡ２ Ｉ＋ＩＡ３ Ｉ）＋（ＩＡｌ ｆ＇ＩＡ２ ｌ＋ＩＡ１ ＶＩＡ３ Ｉ＋ＩＡ２ ＣｌＡ３ Ｉ）一ＩＡ１ ＮＡ２ ＣｌＡ３ Ｉ＝９ 它们分别是（Ｏ，０，５），（Ｏ，１，４），（０，２，３），（１，０，４），（１，１，３），（１，２，２），（２，Ｏ，３），（２，１，２），（２，２，１）． ３容斥原理在数论中的应用 问题ｌ ｐｉ给定正整数ｎ∈Ｎ，确定欧拉函数 （ｎ），即求出小于ｎ且与ｎ互素的正整数个数．若几＝ ｉ２ｚ－…ｐ 是将ｎ分解为．ｉ｝个不同素因子的分解式，则ＩＡ Ｉ＝ｎ，ＩＡｉ Ｉ＝［ 】，ＩＡ ｎ Ｉ＝【 ］，…，ｌＡ ｎ …ｎＡ Ｉ＝【 】，再由容斥原理， （ｎ）＝ＩＡＩ一轰ＩＡ ｌ＋鬲’Ａｉ ｎ Ｉ…。＋（一１） ＩＡｔ ｎ…ＮＡ Ｉ： 一 ． 耋 ＋鬲［ 卜…＋（＿１） 【 ］· 类似地，对于任意的正整数 ，还可以应用容斥原理求出集合［１，乃］中不能够被ａｉ整除的正整数的 个数，其中ａ 为一组两两互素的正整数． 例３求不超过１ ０００的自然数中不能被３整除也不能被５整除的个数． 解Ｊｓ：Ｉ １，２，…，１ ｏｏｏ｝，Ａ＝｛３ ，１≤ ≤［ ］｝，Ｂ＝｝５ ，ｌ≤后≤【 ］｝，不难发现所求个数 为 ｆＳＩ—ｆＡ ｌ—Ｉ ｆ＋ＩＡ ｎ Ｉ＝ｌ ０Ｏ０—３３３—２００＋６０＝５３３． ４容斥原理在图论中的应用 给定一个有限的无向图Ｇ＝（ ，Ｅ），这里 是顶点集，Ｅ是边集，且完全子图定义为：它的顶点是 的子集，在这些顶点中任两点都有Ｅ中的边相连接．一个具有 个顶点的完全子图称为一个完全 一子 图．下面假定２≤尼≤ｎ，其中 是Ｇ的顶点数，顶点 ∈Ｖ的次数记为ｄ（ｖ），定义为以 作为一个端点的 边数．显然，若一个图Ｇ不包含完全 一子图，则存在关于它的顶点的次数和它的边数的某些，其中 有两个经典的结果：Ｚａｒａｎｋｉｅｗｉｃｚ与Ｔｕｒｄｎ．其中，Ｚａｒａｎｋｉｅｗｉｃｚ的证明采用了反证法，巧妙的应用了容斥 原理的对偶形式得到一个与题设矛盾的结论，而Ｔｕｒ６ｎ的证明采用了归纳法，应用容斥原理构造出一个 第２期 邬毅，等：容斥原理的应用 ２７ 在同构的意义下唯一的没有完全ｋ一子图的图．这两个结论的证明可以详见文献［４］． 此外，应用容斥原理可以求出图顶点染色的色多项式． ＝例４设有４个顶点的圈，顶点和边数依次记为Ｖ＝｛ａ，ｂ，Ｃ，ｄ｝，Ｅ＝｛（ｏ，ｂ），（６，ｃ），（ｃ，ｄ），（ｄ，ａ）｝ ｛ｅ ，ｅ：，ｅ。，ｅ ｝．记性质 ，Ａ２，Ａ３，Ａ 分别为ａ—ｂ ｙｂ—Ｃ，Ｃ—ｄ ｒｄ—ａ染色相同．现有 种色，图Ｇ的正常 …． 染色为每点染上一色且相邻接的顶点不同色，正常染色的方式数目记为Ｐ（Ｇ， ）（称为色多项式），则Ｐ ＩＥＩ ，．（Ｇ， ）＝Ｎ（Ａ１ ｎＡ２ ｎＡ３ ＮＡ４）＝ …一２Ｎ（Ａ‘）＋ Ｎ（Ａｉ ｎ ）一， ．＿Ⅳ（Ａｆ ｎＡｊ ｎＡ ）＋Ｎ（Ａｌ ｎＡ２ ｎＡ３ ｎ Ａ ）．Ｎ（Ａ ）表示ａ—ｂ染同色的Ｇ的染色方式数，Ｎ（Ａ ）＝ ，显然Ｎ（Ａ：）＝Ｎ（Ａ，）＝Ｎ（Ａ ）＝＝ ；Ｊ７ｖ （Ａ ＮＡ：）表示ａ—ｂ染同色且ｂ—ｃ染同色的染色方式数，显然Ｎ（Ａ ｎＡ２）＝Ｎ（Ａ ＮＡ ）＝Ｎ（Ａ：ＮＡ，）＝ Ｎ（Ａ２ ＮＡ ）＝ 。，同理Ｎ（Ａ１ ＮＡ２ ｆ３Ａ３）＝Ｎ（Ａ ｆ３Ａ２ ｆ３Ａ４）＝Ｎ（Ａ２ ｆ３Ａ３ ＡＡ ）＝ ，用容斥原理，则Ｐ（Ｇ， ） ４＝ —４ ０＋６ ２—４ ＋ ＝ ４—４ ０＋６ ２—３ ． ５容斥原理在代数中的应用 Ｈ．Ｊ．Ｒｙｓｅｒ应用容斥原理得到 阶方阵积和式的一个计算公式，这个公式部分地把“积之和”的计 算转化成了“和之积”的计算．减小了计算域Ｆ上ｍ×／ｔ＇矩阵中所有可能的ｍ个两两不共线元的乘积之 和的计算量．此外，容斥原理还可以应用于确定有限集之间的满射个数和组合恒等式的证明． 通过以上对有关容斥原理应用的介绍和举例，不难发现，容斥原理给出了用满足组中某些性质的 元素个数来表示不满足该组性质的元素个数的一个计数公式，在求解计数问题时，应用容斥原理往往比 直接计数来得容易，它通常都可以在要求计算某一集合Ｉｓ中不满足某些性质（或某些条件）的元素 的个数这类问题中加以应用． ［参考文献］ ［１］孙淑玲，许胤龙．组合数学引论［Ｍ］．合肥：中国科学技术大学出版社，１９９９．９８—１０６． ［２］ 屈婉玲．组合数学［Ｍ］．北京：北京大学出版社，１９８９．６５． ［３］杨骅飞，王朝瑞．组合数学及其应用［Ｍ］．北京：北京理工大学出版社，１９９２．９３—９６． ［４］ ［罗］ＴＯＭＥＳＣＵ Ｌ．清华大学应用数学系离散数学教研组译．组合数学引论［Ｍ］．北京：高等教育出版社，１９８５．４６， ５０—５１． ［５］邵嘉裕．组合数学［Ｍ］．上海：同济大学出版社，１９９１．７９． ［责任编辑王新奇］ Ｔｈｅ Ａｐｐｌｉｃａｔｉｏｎｓ ｏｆ ｔｈｅ Ｉｎｃｌｕｓｉｏｎ－Ｅｘｃｌｕｓｉｏｎ Ｐｒｉｎｃｉｐｌｅ ＷＵⅥ．ＹＵ Ｊｉｎｇ－ｊｉｎｇ （Ｄｅｐａｒｔｍｅｎｔ ｏｆ Ｍａｔｈｅｍａｔｉｃｓ ａｎｄ Ｐｈｙｓｉｃｓ，Ｃｈｏｎｇｑｉｎｇ Ｕｎｉｖｅｒｓｉｔｙ ｏｆ Ｓｃｉｅｎｃｅ＆Ｔｅｃｈｎｏｌｏｇｙ，Ｃｈｏｎｇｑｉｎｇ ４０１３３１，Ｃｈｉｎａ） Ａｂｓｔｒａｃｔ：Ｔｈｅ Ｉｎｃｌｕｓｉｏｎ—Ｅｘｃｌｕｓｉｏｎ Ｐｒｉｎｃｉｐｌｅ ｉｓ ａ ｂａｓｉｃ ｐｒｉｎｃｉｐｌｅ ｉｎ Ｉｎｔｒｏｄｕｃｔｏｒｙ Ｃｏｍｂｉｎａｔｏｒｉｃｓ．Ｔｈｉｓ ｔｅｘｔ ｗｉｌｌ ｄｉｓｃｕｓｓ ｔｈｅ ａｐｐｌｉｃａｔｉｏｎｓ ｏｆ ｔｈｅ Ｉｎｃｌｕｓｉｏｎ·－Ｅｘｃｌｕｓｉｏｎ Ｐｒｉｎｃｉｐｌｅ ｉｎ ｓｏｌｖｉｎｇ ｃｏｕｎｔｉｎｇ ｔｈｅ ｎｕｍｂｅｒ ｏｆ ｏｂｊｅｃｔｓ ｉｎ ａｓ·· ｐｅｃｔｓ ｓｕｃｈ ａｓ Ｐｅｒｍｕｔａｔｉｏｎｓ，Ｃｏｍｂｉｎａｔｉｏｎｓ，Ｎｕｍｂｅｒ ｈＴｅｏｒｙ，Ｇｒａｐｈ Ｔｈｅｏｒｙ ａｎｄ Ａｌｇｅｂｒａ ａｃｃｏｒｄｉｎｇ ｔｏ ｔｈｅ ｅｑｕａｌ ｆｏｒｍ ｏｆｔｈｅ ｐｒｉｎｃｉｐｌｅ． Ｋｅｙ ｗｏｒｄｓ：ｔｈｅ Ｉｎｃｌｕｓｉｏｎ—Ｅｘｃｌｕｓｉｏｎ Ｐｒｉｎｃｉｐｌｅ；ｆｉｎｉｔｅ ｓｅｔ ｃｏｕｎｔ；Ｃｏｍｂｉｎａｔｉｏｎｓ
