软件2010组合数学第四章容斥原理(二)

容斥原理（1）容斥原理（2）知识点-并集：A 和B 并集是有所有A 的元素和所有B 的元素，而没有其他元素的集合。

A 和B 的并集通常写作"A ∪B"。

在计数时，为了使重叠部分不被重复计算，人们研究出一种新的计数方法，这种方法的基本思想是：先不考虑重叠的情况，把包含于某内容中的所有对象的数目先计算出来，然后再把计数时重复计算的数目排斥出去，使得计算的结果既无遗漏又无重复，这种计数的方法称为容斥原理。

容斥原理是公务员考试行政职业能力测验数量关系中较难的一类题，一般的解题思路有两种：1、公式法，适用于“条件与问题”都可直接代入公式的题目；2、文氏图示意法，即当条件与问题不能直接代入公式时，需要利用该方法解决。

一般而言，能够直接代入公式的题较容易，而需要利用文氏图的题目相对灵活，容易给考生解题带来不便。

如果考生能够对公式中的各个要素以及文氏图上的各个部分所代表的含义有深入了解，则可以快速抓住解题关键。

例：某班有35个学生，每个学生至少参加英语小组、语文小组、数学小组中的—个课外活动小组。

现已知参加英语小组的有17人。

参加语文小组的有30人，参加数学小组的有13人。

如果有5个学生三个小组全参加了，问有多少个学生只参加了一个小组？A.15B.16C.17D.18对于这道题，一般思路为：将题目条件带入三集合文氏图，假设只参加两个小组的人数分别为x，y，z人，由加减关系可以得到只参加一个小组的人数的表示形式，根据总人数可以列出方程：（13-5-x-y）+（17-5-x-y）+（30-5-x-y）+x+y+z+5=35，从而得到x+y+z=15，即为所求。

该方法是利用文氏图和列方程的方法进行解题，方法简单易懂，但是实际操作起来消耗时间较多，下文将给出本题的另外两种解法：解法1：文氏图与三集合标准型公式相结合。

三集合标准型的公式如下：AUBUC=A+B+C-(AB+AC+BC)+ABC。

将语文小组的人数视为A，数学小组人数视为B，英语小组人数视为C，分别代入公式可以得到AB+AC+BC=30。

技术创新33组合数学申的容斥原理及其应用实例◊宝鸡文理学院数学与信息科学学院李海侠容斥原理是组合数学中的一个重要计数工具，在集合论、概率论和初等数论等学科中占有非常重要的地位。

本文讨论容斥原理的思想以及在计数问题中的若干应用，帮助大家更方便的利用容斥原理解决相关问题。

容斥原理冋是组合数学中的基本计数原理，是解决计数问题的一个重要工具。

掌握容斥原理的主要思想可以大大简化计数问题的计算，给解决相关问题带来方便，具有非常重要的研究意义。

但纵观容斥原理的已有研究成果，目前对容斥原理在圆排列（非夫妻围坐问题）、多重集排列和与棋盘多项式有关的禁区排列等方面的应用很少。

因此，本文在容斥原理相关定理的基础上探析容斥原理的主要思想以及若干应用,并通过举例进行详细说明，从而使大家更好地理解并灵活应用容斥原理。

1预备知识为了后面讨论的需要，下面给出容斥原理的相关定理和思想。

定理1（容斥原理）呦设有限集S,P=｛片，马,…，好｝是与S中元素有关的性质集合，4,&，…,4,是分别具有性质£，妁，…上的元素构成的s的子集，贝U：|4U4U-U^…|»,,,,（1）=ZW-Z|4-n^|+s l4.n4.nAl—■+（-ir1l4n^n-n4.li=l l<i<j<n l<i<j<k<n|4A4n-n4；|⑵=l^|-il4l+Z|4A4|-z|4n4n^|+-+（-ir|4n4n-n4.li=l l<i<j<k<n运用容斥原理和组合販易得定理2如果有限集s的子集4,4,…,4.具有对称性，即|4|=^（1<«<«）,|4-C1勺| =J R2（i<i</<»）,-）|4n4n-AA|=^,”则14u U•••U Al=ex-CX+•-+（-1）"_1CX=（3）冈n瓦n…n可=国-c：x+c江-…+（-i）”c：&=同-x（-i）/_I c火（4）利用容斥原理解题的思想和步骤：J（1）根据题意,找出全集s并构造出s中具有性质P t的元素组成的s的子集4（i= 1,2,•••,»）,这里4（21,2,…，”）的寻找非常关键，目标是既能用容斥原理又使得⑷，|4ri24y|,---,|4/容易求出。

浅谈容斥原理及其应用摘要:容斥原理是一个重要的计数公式。

关键词:容斥原理、R 组合、错排。

回忆加法原理在集合间不重叠的情况下，即在这些集合确定一个划分的情况下，给出了这些集合的并的成员的简单计数公式。

容斥原理则给出一个最一般情形下的一个公式，此时集合间可以重叠而没有限制。

这个公式应该更复杂，但是应用更广泛。

定理1.1(容斥原理) 设S 是一个有限集，m P P P ,,,21 是S 上的元素，可能具有的性质{}()m i A S A P x S x x A i i i ,,2,1, , i =-=∈=具有性质且，则()m m mj i k j i m j i j i m i i m A A A A A A A A A A A A 211111211+≤<≤≤<≤=-+-+-=∑∑∑原理一：给定两个集合A 和B ，要计算A ∪B 中元素的个数，可以分成两步进行：第一步：先求出∣A ∣+∣B ∣（或者说把A ，B 的一切元素都“包含”进来，加在一起）； 第二步：减去∣A ∩B ∣（即“排除”加了两次的元素）总结为公式：|A ∪B|=∣A ∣+∣B ∣-∣A ∩B ∣原理二：给定三个集合A ，B ，C 。

要计算A ∪B ∪C 中元素的个数，可以分三步进行： 第一步：先求∣A ∣+∣B ∣+∣C ∣；第二步：减去∣A ∩B ∣，∣B ∩C ∣，∣C ∩A ∣；第三步：再加上∣A ∩B ∩C ∣。

即有以下公式：∣A ∪B ∪C ∣=∣A ∣+∣B ∣+∣C ∣-∣A ∩B ∣-∣B ∩C ∣- |C ∩A|+|A ∩B ∩C ∣ 例1 求不超过20的正整数中是2的倍数或3的倍数的数共有多少个。

分析：设A={20以内2的倍数}，B={20以内3的倍数}，显然，要求计算2或3的倍数个数，即求∣A ∪B ∣。

解1：A={2，4，6，…20}，共有10个元素，即|A|=10B={3，6，9，…18}，共有6个元素，即|B|=6A ∩B={既是2的倍数又是3的倍数}={6，12，18}，共有3个元素，即|A ∩B|=3 所以∣A ∪B ∣=∣A ∣+∣B ∣-∣A ∩B ∣=10+6-3=13，即A ∪B 中共有13个元素。

容斥原理及其应用１ 序言数学知识是人类社会文明的一个重要组成部分．在当今世界，数学已不仅是一门单一的科学，而是一种普适性的技术，正广泛地渗透到物质世界的每一个领域内，对科学技术和社会的发展起着日益突出的作用，但随着社会的向前推进，时代的进步，数学科学的思想、方法与内容伴随着远古时期的结绳记事，屈指记数到现在的办公自动化而日趋完善．人类的现实生活需要数学，而国家的经济发展，科学技术的进步更与数学知识息息相关．具备一些必要的数学知识和一定数学思想方法，是现代人才基本素质的重要组成部分．早期的组合数学是带着数学趣味性和益智魅力的问题，逐渐与数论、概率统计，以及后来新兴的拓扑学、线性规划等学科相互交织在一起，在二十世纪下半叶与电子计算机相结合足以显示了数学的用途．容斥原理是组合数学中解决计数问题的一个重要工具，是离散数学的一个重要组成部分，容斥原理在排列、组合、概率计算中有着广泛的应用．随着近代科学技术的发展，特别是计算机科学的长足进步，给与计算机密切相关的组合数学和离散数学注入了新的活力和生机，使它们与其他基础数学学科的联系更加紧密，让应用数学的适用范围进一步扩大，在现代科学技术中发挥出极为重要的作用．２ 容斥原理定理2.1 设S 是有限集，P 表示某种性质，令A 表示S 中具有性质P 的元素的集合，则S 中不具有性质P 的元素的个数为： A S A =-．定理2.2 设S 是有限集，12,P P 表示某种性质，令,A B 表示S 中具有性质12,P P 的元素的集合，则S 中不具有性质12,P P 的元素的个数为：A B S A B A B =--+I I ．定理2.3 设S 是有限集，123,,P P P 表示某种性质，令,,A B C 表示S 中具有性质123,,P P P 的元素的集合，则S 中不具有性质123,,P P P 的元素的个数为：A B C S A B C A B A C B C A B C =---+++-I I I I I I I定理2.4 设S 是有限集，()1,2,,i P i n =L 表示某种性质，令()1,2,,i A i n =L 表示S 中具有性质()1,2,,i P i n =L 的元素的集合，则S 中至少具有某一性质()1,2,,i P i n =L 的元素的个数为 1121121211n i i i i ni i nA A A A A A ≤≤≤<≤=-++∑∑U UL U I L()()12121112111k k k n i i i n i i i nA A A A A A --≤<<<≤-++-∑L I I L I L I I L I()12121111k k n k i i i k i i i nA A A -=≤<<<≤=-∑∑L I I L I ．现给出这个公式的证明． 证明[]()145P 当2n =时， 121212A A A A A A =+-U I因为 12112A A A A A -=-I ，12A A A ⊆I ，所以 12112112A A A A A A A A -=-=-I I ，所以 当2n =时，结论成立．假设当()2n s s =≥时结论成立，则当1n s =+时，111111111n s n ss i i i s is i s i i i i i A A AA A A ++++=====⎛⎫⎛⎫A =A ==+- ⎪ ⎪⎝⎭⎝⎭U I U U U U U ()1111ssis i s i i AA A A ++===+-I U U()11212111211kk sk i i i i i s k i i i sA A A A -≤≤+=≤<<<≤=+-∑∑∑L I I L I ()()1212111211111k s ksi i s s s k i i i sA A A A A A A -++=≤<<<≤+-+-∑∑L I I L I I I L I I 111i i s A ≤≤+=∑()()1212112121111211111k k k k s s k k i i i i i i s k i i i s k i i i s A A A A A A A ----+=≤<<<≤=≤<<<≤⎡⎤+-+-⎢⎥⎣⎦∑∑∑∑L L I I L I I I L I I ()1211ss A A A ++-I I L I ()()1121211211121111k k sk si i i i s i s k i i i s A A A A A A A -+≤≤+=≤<<<≤+=+-+-∑∑∑L I I L I I I L I ()1212112111kk s k i i i k i i i s A A A +-=≤<<<≤+=-∑∑L I I L I()12121211k k nk i i i k i i i nA A A -=≤<<<≤=-∑∑L I I L I所以 当1n s =+时，结论成立．由数学归纳法可知，对任意的自然数()2n n ≥结论成立．S 中不具有性质()1,2,,i P i n =L 的元素的个数为： ()121212111k k nkn i i i k i i i nA A A S A A A =≤<<<≤=+-∑∑L I I L I I I L I ．３ 应用举例３.１ 容斥原理的一些简单应用例３.1.1 由1至300的整数中, 有多少个整数能被7整除且能被2或5整除?解 设所求为N , 令{}1,2,,300S =L , A ={能被7214⨯=整除的整数}，B ={能被7535⨯=整除的整数}，A B I ={能被72570⨯⨯=整除的整数}，则N A B A B A B ==+-U I 3003003007275725⎡⎤⎡⎤⎡⎤=+-⎢⎥⎢⎥⎢⎥⨯⨯⨯⨯⎣⎦⎣⎦⎣⎦218425=+-= 例 3.１.2 有2008盏亮着的电灯，各有一个拉线开关控制着，现将其顺序编号为1,2,3,,2008L ．将编号为2的倍数的灯线拉一下，再将编号为3的倍数的灯线拉一下，最后将编号为5的倍数的灯线拉一下，拉完后还有几盏灯是亮的？解 令A ={不大于2008的2的倍数},B ={不大于2008的3的倍数}, C ={不大于2008的5的倍数}, 则200810042A ⎡⎤==⎢⎥⎣⎦, 20086693B ⎡⎤==⎢⎥⎣⎦, 20084015C ⎡⎤==⎢⎥⎣⎦． 又 A B I ={不大于2008的236⨯=的倍数}，A C I ={不大于2008的2510⨯=的倍数}，BC I ={不大于2008的3515⨯=的倍数}, A B C I I ={不大于2008的23530⨯⨯=的倍数},200833423A B ⎡⎤==⎢⎥⨯⎣⎦I , 200820025A C ⎡⎤==⎢⎥⨯⎣⎦I , 200813335B C ⎡⎤==⎢⎥⨯⎣⎦I , 200866235A B C ⎡⎤==⎢⎥⨯⨯⎣⎦I I ,所以拉过开关的灯的只数为：A B C A B C A B A C B C A B C =++---+I I I I I I I 1004669401334200133661473=++---+= (只)所以没拉开关的灯的只数为：20081473535-=（只） 只拉两次的开关的灯的只数为：3A B A C B C A B C ++-I I I I I 334200133366469=++-⨯=（只）所以最后亮着的灯的只数为：5354691004+=（只）3.2 容斥原理在重排问题中的应用 例3.2.1[]()21P 4只小鸟飞入四个不同的笼子里，每只小鸟都有自己的一个笼子（不同的笼子，笼子也不同）,每个笼子只能飞进一只小鸟，若都不飞进自己的笼子，应有多少种不同的飞法？分析 设4只小鸟是甲、乙、丙、丁，相对应的笼子分别是1号、2号、3号、4号，由题意可推算出有9种不同的飞法，分别是乙甲丁丙；乙丙丁甲；乙丁甲丙；丙甲丁乙；丙甲丁乙；丙丁乙甲；丙丁甲乙；丁甲乙丙；丁丙甲乙；丁丙乙甲。

四元容斥原理四元容斥原理是组合数学中的一种计数方法，用于解决排列组合问题。

它通过使用容斥原理来计算多个集合的交集和并集，从而得到所需的计数结果。

容斥原理在介绍四元容斥原理之前，我们先来了解一下容斥原理。

容斥原理是组合数学中常用的计数方法，用于计算多个集合的交集和并集。

它可以帮助我们解决一些复杂的计数问题。

假设有n个集合A1, A2, …, An，我们想要计算它们的并集和交集。

容斥原理告诉我们，这两个值之间存在如下关系：|A1 ∪ A2 ∪ ... ∪ An| = |A1| + |A2| + ... + |An| - |A1 ∩ A2| - |A1 ∩ A3| - ... - (-1)^(n-1)|An-1 ∩ An| + (-1)^n|A1 ∩ A2 ∩ ... ∩ An|其中，||表示集合的大小（即元素个数），∪表示并集运算，∩表示交集运算。

这个公式的意思是：要计算多个集合的并集的大小，我们需要将每个单独的集合大小相加，并减去两两交集的大小，再加上三个集合的交集的大小，以此类推。

容斥原理的思想很简单，它通过逐个排除重复计数的情况，并补回漏计的情况，从而得到正确的计数结果。

四元容斥原理四元容斥原理是容斥原理在四个集合之间的应用。

它可以帮助我们解决一些更为复杂的计数问题。

假设有四个集合A, B, C, D，我们想要计算它们的交集和并集。

四元容斥原理告诉我们，这两个值之间存在如下关系：|A ∪ B ∪ C ∪ D| = |A| + |B| + |C| + |D| - |A ∩ B| - |A ∩ C| - |A ∩ D| - |B ∩ C| - |B ∩ D| - |C ∩ D|+ |A ∩ B ∩ C| + |A ∩ B ∩ D| + |A ∩ C ∩ D| + |B ∩ C ∩ D|- |A ∩ B ∩ C ∩ D|这个公式与容斥原理类似，不同之处在于多了一些交集项和并集项。

使用四元容斥原理时，需要将每个单独的集合大小相加，并减去两两交集的大小，再加上三个集合的交集的大小，以此类推。

容斥原理及其应用容斥原理是组合数学中一种重要的计数技巧，被广泛运用于排列组合、概率统计等领域。

它的核心思想是通过求出多个集合的交集和并集来计算所需的数量，从而避免重复计数，确保准确性和全面性。

本文将介绍容斥原理的基本概念、推导过程以及其在实际问题中的应用。

一、容斥原理的基本概念容斥原理是根据集合的性质和运算规则推导出的一种计数方法。

在给定一组集合时，容斥原理可以帮助我们计算这些集合的交集和并集的元素个数。

在具体运用中，我们将问题转化成求解几个集合的元素个数之和的问题。

容斥原理表达式如下：∣A1∪A2∪⋯∪An∣=∣A1∣+∣A2∣+⋯+∣An∣−∣A1∩A2∣−∣A1∩A3∣−⋯−∣An−1∩An∣+⋯+（−1）^n−1∣An−1∩An∣其中，∣A∣表示集合A的元素个数，∪表示集合的并集，∩表示集合的交集，n表示集合的数量。

二、容斥原理的推导过程容斥原理的推导过程可以通过数学归纳法来实现，下面简要介绍：首先，我们给定两个集合A和B，我们用∣A∣表示集合A的元素个数，用∣B∣表示集合B的元素个数。

如果我们要计算A和B的并集∣A∪B∣，那么可以采取如下步骤：1. 首先，我们直接将∣A∣和∣B∣相加，得到∣A∣+∣B∣。

2. 然后，我们需要减去重复计算的部分，即集合A和B的交集∣A∩B∣。

因为∣A∩B∣这部分元素已经在∣A∣和∣B∣中被计算了一次，所以需要减去∣A∩B∣。

通过以上步骤，我们得到了∣A∪B∣=∣A∣+∣B∣−∣A∩B∣。

这就是容斥原理的基本推导过程。

接下来，我们将容斥原理推广到更多集合的情况。

假设我们有三个集合A、B和C，我们想要计算它们的并集∣A∪B∪C∣，我们可以按照以下步骤进行：1. 首先，我们将∣A∣、∣B∣和∣C∣相加，得到∣A∣+∣B∣+∣C∣。

2. 然后，我们需要减去两两集合的交集部分，即∣A∩B∣、∣A∩C∣和∣B∩C∣。

这是因为这些部分元素在∣A∣、∣B∣和∣C∣中都被计算了一次，所以需要减去。