容斥原理

2024-10-17

容斥原理（通用4篇）

容斥原理篇1

容斥原理, 又称包含——排斥原理或取舍原理, 它是组合数学中解决计数问题的一个重要原理和工具, 若将这一原理应用到排列问题中, 则对解决错位排列、有禁区排列和圆形排列等问题都会起到很大作用.

1. 容斥原理简述

(2) 一般形式:设S, P同上, F为一域, 对每一a∈S, 有唯一w (a) ∈F与a对应, 称w (a) 为a的权, W (pi1, pi2, …, pir) 为S中同时具有r这个性质pi1, pi2, …, pir的所有元素的权和, W (r) =∑W (pi1, p i2, …, pir) , 其中和式取遍P的r元子集, 当r=0时, 规定W (0) 等于S中所有元素的权的和, 令E (k) 表示中恰好具有P中k个性质的元素的权和, E (0) 表示S中不具有P中任何性质的元素的权和, 则有:

若对一切a∈S, 都有w (a) =1, 并以N (m) 记W (m) , 则有

2. 容斥原理在错排问题中的应用

错位排列, 又称为更列, 是一种带限制条件的全排列。若Z={1, 2, …, n}, 则Z的一个错位排列是指这样的全排列a1a2…an, 使ai≠i (i=1, 2, …, n) .利用容斥原理可以推导的所有错位排列的个数Dn.

定义性质Pi:对排列a1a2…an, 有ai=i (i=1, 2, …, n) , 设Ai为具有性质Pi的全体排列, 则Z的所有错位排列所构成的集合为.

因数字i不动, 故

同理

由容斥原理得:

例1:数1, 2, 3, …, 9的全排列中, 求偶数在原来的位置上, 其余都不在原来的位置上的错排数目.

解:此问题实际上是1, 3, 5, 7, 9五个数的错排问题, 总数是

3. 容斥原理在有禁区排列中的应用

n个元素的某一排列可以看做是n个棋子在n×n的棋盘上的一种布局。当一个棋子置于棋盘的某一格子时, 则这一格子所在的行和列都不能再布任何棋子, 即棋盘的每一个布局每行每列有且只有一个棋子.有禁区排列是指每个棋子在棋盘上都有一定的禁区的布局.

利用容斥原理可以导出有禁区的排列数为

其中ri是有i个棋子布置到禁区部分的方案数.

令P1P2…Pn为n个棋子布入n×n棋盘所得到的排列, 其中Pi为第i个棋子落在棋盘的第i行的位置.Ai为第i个棋子放入禁区, 即Pi在禁区内事件.

一个棋子落入禁区方案数为r1, 剩下的n-1个棋子为无限制条件的排列, 故至少有一个棋子进入禁区的方案数为r1 (n-1) !.两个棋子落入禁区方案数为r2, 而其余n-2个棋子为无限制条件的排列, 故至少有两个棋子进入禁区的方案数为r2 (n-2) !, 依此类推.

依据容斥原理, 布个棋子无一落入禁区的方案数应为:

例2:有甲, 乙, 丙, 丁四个人, A, B, C, D为四项任务, 甲不能从事任务B;乙不能从事B, C两项任务;丙不能从事C, D任务;丁不能从事任务D.若要求每人从事各自力所能及的一项任务, 试问有多少种不同方案?

分析:每一种分配方案相当于图1的关于A, B, C, D的有禁区排列 (阴影表示禁区) .问题也相当于求在如图1所示的有禁区的棋盘上, 用四个棋子进行布局的方案数, 因此需用到棋盘多项式.

解:图1的禁区的棋盘多项式为1+6x+10x2+4x3,

即r1=6, r2=10, r3=4

所求方案数为:

4. 容斥原理在圆形排列中的应用

问题:将1, 1′, 2, 2′, …, n, n′排成一个圆圈, 当i, i′ (i=1, 2, …, n) 相邻时, 则将i, i′看作一个整体而不考虑它们之间的顺序, 求这种圆形排列的个数Rn.

应用容斥原理的一般形式, 我们可以得到Rn的公式.

设S为1, 1′, 2, 2′, …, n, n′的所有圆形排列的集合, Pi表示性质“排列中i, i′相邻” (i=1, 2, …, n) , 则:

易知, (m=0, 1, …, n) , 由容斥原理知

故

以上仅是容斥原理被应用到排列中的几个方面, 而它在排列问题中的应用远不止这些, 在其他类型的排列求解中也经常被使用.

参考文献

[1]陈敬华.容斥原理及其应用[J].高等函授学报 (自然科学版) , 2000, 13, (2) :17.

[2]柯召, 魏万迪.组合论[M].北京:科学出版社, 1981.

[3]卢开澄.组合数学[M].北京:清华大学出版社, 1991.

[4]卢青林, 刘光乾.一类排列问题的计数[J].徐州师范大学学报 (自然科学版) , 1998, 16, (2) :17.

容斥原理篇2

Co-prime

Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)

Total Submission(s): 1798 Accepted Submission(s): 685

Problem Description Given a number N, you are asked to count the number of integers between A and B inclusive which are relatively prime to N.

Two integers are said to be co-prime or relatively prime if they have no common positive divisors other than 1 or, equivalently, if their greatest common divisor is 1. The number 1 is relatively prime to every integer.

Input The first line on input contains T (0 < T <= 100) the number of test cases, each of the next T lines contains three integers A, B, N where (1 <= A <= B <= 1015) and (1 <=N <= 109).

Output For each test case, print the number of integers between A and B inclusive which are relatively prime to N. Follow the output format below.

Sample Input

21 10 23 15 5

Sample Output

Case #1: 5Case #2: 10HintIn the first test case, the five integers in range [1,10] which are relatively prime to 2 are {1,3,5,7,9}.

容斥原理篇3

一、预备知识

1. 容斥原理的概念

当A1, A2, …, An是有限集合A的一个分划, 即:

(1) A1∪A2∪…∪An=A

(2) A1∩Aj=准, 这时我们有A=A1+A2+…+An

这实际上是组合计数中的加法法则。

在讨论容斥原理的过程中, 要用到以下集合论的基本性质。

引理1 (德摩根〈De Morgan〉定理) :若A和B是集合U的子集, 则:

德摩根定理还可以推广为:

推论 (1) 设A1, A2, …, An是U子集, 则

一般当n=2, 3, 4时的情形况下, 应用容斥原理, 即:

引理2 (容斥原理) :设A1, A2, …, An是有限集合, 则:

又其中N为集合U的元素个数, 即不属于A的元素数目等于集合的全体减去属于A的元素个数。

容斥原理是记数中常用的一种方法, 先举例阐明应用容斥原理求解计数问题的思想。

例1.求1到600之间不能被6整除的整数的个数。

解:先计算1到600之间能被6整除的整数的个数, 然后从总数中去掉它。1到600之间共有600个数, 因为每6个连续的整数中恰有一个能被6整除, 所以1到600之间共有=100个整数能被6整除。因而, 1到600之间共有600-100=500个整数不能被6整除。

2. 逐步淘汰原理

引理3 (逐步淘汰原理) :设A1, A2, …, An是有限集合A1, A2, …, An是S的子集, 则

所谓容斥原理就由上面两个原理构成。

例2.求a, b, c, d, e, f这6个字母的全排列中不允许出现ace和df的图像的排列数。

解:设A1为ace作为一个元素出现的排列集, A2为df作为一个元素出现的排列集, A1∩A2为同时出现ace和df的排列集, 则

根据容斥原理, 不允许出现ace和df的排列集为

二、容斥原理组合计数问题中的应用

线状限位排列问题 (相邻禁位排列问题)

限位排列问题又称为不含连续数对的排列问题, 就是如果π=a1a2…an是由1, 2, …, n组成的一个全排列, 其中ai+1-ai=1 (1≤i≤n-1) , 则称π含有连续数对 (ai, ai+1) , 例如评论1243567含有3个连续数对 (1, 2) , (5, 6) , (6, 7) 这就是连续数对。

引理4:由数字1, 2, 3, …, n组成的n级排列中不出现12, 23, …, (n-1) n的排列称为线状限位排列, 其排列数用Qn表示, 则

例3.以Qn为由字母a1, a2, …, an作成的aiaj (i=j-1) 不相邻的全排列的个数, 求Qn

分析:可以将a1, a2, …, an看成是1, 2, …, n而aiaj (i=j-1) 可以看成数字中的i, j, 故这个问题可以用引理4来解决。

解:可以将a1, a2, …, an做成的aiaj (i=j-1) 不相邻的排列, 看成是由数字1, 2, …, n组成的数字中的i, j (j=i+1) , 不相邻的排列。则由引理4:

三、容斥原理在组合计数中应用的推广

1. 限位排列问题的推广

定理1:以f (2n) 表示由两个a1两个a2, …, 两个an组成的任何两个ai (i=1, 2, …, n) 均不相邻的排列, 排列的个数为

分析:该题中两个a1两个a2, …, 两个an做成的任何两个ai (i==1, 2, …, n) 均不相邻, 我们在考虑时应该用逐步淘汰原理, 排除所有相邻的情况。

证:令S表示由字母a1, a1, a2, a2, …, an, an组成的全排列的集合, 则

如果在S的排列里有aiai出现, 则称该排列具有性质Pj (j==1, 2, …, n) , 令Aj是S中具有性质Pj的排列的集合。则Aj的排就是由a1, a1, a2, a2, …, aj, aj, …, an, an组成的全排列, 故

Ai∩Aj的排列就是由a1, a1, …, ai, ai, …, aj, aj, …, an, an组成的全排列, 故。

由上述分析相类似地可得, 对任意的自然数k (1≤k≤n) 都有

2. 环状限位排列问题

定理2:有n个人围圆桌而坐, 如果让他们交换座位, 使得每一个人前边都不是原来在他前面的那个人, 不同的坐法数为

证:这是一个限位环状排列问题。

令S表示由n个人组成的所有环状排列的集合, 则

如果在S的排列里有j (j+1) 出现, 则称该排列具有性质Pj (j=1, 2, …, n-1) 。

当j=n时, 令Pn表示n1出现在S的排列里。

令Aj是S中具有性质Pj的排列的集合, 则

由上述分析相类似地可得, 对任意的自然数k (1≤k<n) , 都有

其中, i1, i2, …, ik为1, 2, …, n中的k个数字的一个集合, 且

本文利用容斥原理探讨了夫妻问题, 错位排列问题以及相邻禁位排列问题等一系列典型的组合计数问题, 并且将夫妻围坐问题推广到夫妻沿长凳而坐, 把直线型限位排列问推广到圆形限位排列问题, 说明了容斥原理在组合计数中的作用。利用容斥原理得出一系列求解组合计数问题的计数公式, 为解决一类组合计数问题提供了较为新颖、快捷的求解方法, 当然对容斥原理的其他应用还有待进一步的探索。

摘要：计数问题是组合数学的重要内容, 而容斥原理是求解计数问题的一个重要方法。利用容斥原理可以使复杂且难于计算的问题变得简单且更加容易计算。介绍了容斥原理的基本概念和一些应用, 重点讨论了容斥原理组合计数问题中的应用和限位排列等内容。

关键词：容斥原理,组合计数,限位排列

参考文献

[1]卢开澄, 卢华明.组合数学.3版.北京:清华大学出版社, 2002:207-212.

[2]曹汝成.组合数学.广州:华南理工大学出版社, 2001:54-61.

[3]陈传理, 张同君.竞赛数学教程.2版.北京:高等教育出版社, 2004:231-239.

[4]掌家柜.容斥原理与排列.连云港教育学院学报, 1995 (2) :13-16.