4章 容斥原理

94 第4章 容斥原理 · 是组合学中的一个基本计数理论，也称 “包容与排斥原理”、“入与出原理”、“包含排斥原理”或“交互分类原理”。 · 加法法则的限制：要求将计数的集合划分为若干个互不相交的子集，且这些子集都比较容易计数。 · 问 题 快递公司问题件快递公司问题件货款处理关于圆的周长面积重点题型关于解方程组的题及答案关于南海问题 ：实际中又有很多计数问题要找到容易计数而又两两不相交的子集并非易事。但往往能够知道某一集合的若干相交子集的计数，进而把所要求的集合中的元素个数计算出来。 §4.1 引 言 （1） 研究内容 （1） 实例 【例】求不超过20的正整数中是2的倍数或3的倍数的数的个数。 ①不超过20 的正整数中是2的倍数的数有 ＝10个，即A={2,4,6,8,10,12,14,16,18,20}； ②是3的倍数的数有 ＝6个，即B={3,6,9,12.15,18}； ③二者相加为16个。但实际上满足条件的数只有13个：即2,3,4,6,8,9,10,12,14,15,16,18,20；原因在于把既是2的倍数，又是3的倍数的数重复算了一次，这样的数恰好有 ＝3个，即6,12,18。 ④正确的统计方法应为：16＋6－3＝13个。 （2） 内容 容斥原理所要研究的就是若干个有限集合的交或并的计数问题。 （2） 集合的表示 用大写字母表示一个集合，如A、B、C、S等，用小写字母表示集合的元素，如a、b、c、x、y、z等。元素a属于集合A，记为 ，不属于A，记为 . 空集记为 。 （3） 集合的运算 （1） 并（和）：记为 或A＋B； （2） 交（积）：记为 或AB； （3） 差：记为A－B （4） 对立集（非）：即 ＝S－A 显然有 A－B＝ ＝A－AB （4） 优先级 类似于数字的四则运算，我们这里规定在混合算式中的优先级为：先取非，次为交，再次为并或差。对于出现在同一算式中的同级运算，按从左向右的顺序进行。若算式中含有括号，则先括号内，后括号外。 （5） 运算定律 （1） 交换律： A＋B＝B＋A， AB＝BA； （2） 结合律： (A＋B)＋C＝A＋(B＋C), (AB)C＝A(BC)； （3） 分配律： A(B＋C)＝AB＋AC, A＋BC＝(A＋B)(A＋C)； （4） De.Morgan定律（互反律）： ＝ ， ＝ . （6） 集合的势 当集合A中的元素为有限个时，称A为有限集合，其元素个数记为 ，亦称为A的势。关于 ，有如下简单性质： （1） 若集合A、B不相交，即AB＝ ，则 ＝ ＋ ； （2） 若 ，则 ＝ － 。 （3） ＝ － §4.2 容 斥 原 理 （1） 容斥原理 引理4.2.1 设A，B为有限集合，则有 （4.2.1） 证 显然，对于A＋B中的元素a，在等式左边恰被统计一次，而在等式右边被统计的次数，可分为如下三种情形来考虑： （1） ，但 ，则a也恰被统计一次； （2） ，但 ，同样恰被统计一次； （3） 且 ，那么必有 ，从而a被统计1＋1－1＝1次。 所以，a在等式两边被统计的次数是相同的，引理4.2.1得证。 定理4.2.1（容斥原理） 设A1，A2，…An为有限集合，则 (4.2.2) 证 用数学归纳法证明。 (1) 当n＝2时，由引理4.2.1知，结论成立。 (2) 设对n－1，结论正确。即 ＝ (4.2.3) (3) 那么，对于n，有 ＝ (4.2.4) 其中利用式(4.2.3),有 EMBED Equation.3 ＝ 将上式与式(4.2.3)代入式(4.2.4)整理即得式(4.2.2) . （2） 逐步淘汰原理 定理4.2.2（逐步淘汰原理） 设A1，A2，…An为有限集合S的子集，则 (4.2.5) 证 证法一 利用De.Morgan定律和集合求差运算性质，可得 ＝ ＝ ＝ 再将式(4.2.2)代入上式即得式(4.2.5) . 证法二 （为了较容易地证明下面的一般 公式 小学单位换算公式大全免费下载公式下载行测公式大全下载excel公式下载逻辑回归公式下载 (4.2.6)）。 设有限集合S和与S中的元素有关的性质集合P＝{ P1，P2，…，Pn}，令Ai为S中具有性质Pi的所有元素构成的子集，那么，S－Ai即为S中不具有性质Pi的所有元素，Ai Aj Ak表示S中同时具有性质Pi、Pj、Pk的元素的子集合， 是S中不具有P中任何性质的元素之集合。 式(4.2.5)左边是S中不具有性质集合P中任何一种性质的元素个数。因此要证明式(4.2.5)成立，只要证明对S中的任何一个元素a，如果a不具备P中任何一个性质，则a在等式右边被统计一次。否则，a被统计0次。 首先，设元素 且a不具有任何性质，则a不属于任何一个Ai或若干个Ai的交集，因此，a在右边被统计的次数为 其次，若 ，且b同时具有P中的k种性质，那么，子集A1、A2、…、An中必有某k个都含有元素b，从而b在 中被统计一次，在 中被统计k次，在 中被统计 次，… . 因此，按照式（4.2.5），统计的总次数为 其中规定：r>k时， 。证毕。 （3） 一般问题 （1） 问题 到目前为止，我们已经解决了如何计算集合S中具有某些性质的元素个数，以及不具备这些性质的元素个数。一个自然而然的问题是：如何计算S里恰好具有P中k个性质的元素个数。即容斥原理的更一般情形。 （2） 例子 设某单位共有 ＝11人，其中有 ＝7人会英语， ＝5人会德语， ＝2人同时会英、德两种语言，那么，由式(4.2.5)，立即可知会0种语言（即不具有任何性质）的人数为 ＝ －( ＋ )＋ ＝11－(7＋5)＋2＝1（人） 而恰好会两种语言（即具有两种性质）的人数，条件已经给出， ＝2。现在的问题是恰好会一种语言的人数如何计算。从集合的角度，可以分别计算： （1）会英语而不会德语的人数为 ＝ ＝ － ＝7－2＝5 （2）会德语而不会英语的人数为 ＝ － ＝3 所以，恰好会英、德语中一种语言的人数为 ＝ ＋ ＝ ＋ －2 ＝8 注意， ＝ ＋ － ＝10≠8，原因在于 表示至少会一种语言的人数，其中自然含有同时会两种语言的人。 通过本例，初步接触到了当n＝11时，计算集合S中恰好具有k种性质的元素个数的方法（k＝0,1,2）。特别地，当k＝0时的计算公式就是逐步淘汰原理。 （3） 符号 设S为一个集合，A i是S上具有性质P i的元素集，令 ＝ ＝ q2 ＝ ＝( ＋ ＋…＋ )＋( ＋…＋ )＋…＋ q3 ＝ ＝[( ＋ ＋…＋ )＋( ＋ ＋…＋ )＋…＋ ]＋[（ ＋ ＋…＋ ）＋…＋ ]＋…＋ qn ＝ 再令 表示S中恰好具有k种性质的元素个数（k＝0,1, …,n）。例如 （4） 结论 定理4.2.3（一般公式） N[k]＝ ＝ (4.2.6) 一般公式也称为Jordan公式。 证 类似于定理4.2.2的证法二，只要算出S中每个恰好具有k个性质的元素，在式(4.2.6)的右端被统计一次，而对性质少于k或大于k的元素，则统计了0次。设S中元素a具有j种性质，分三种情况予以讨论： (1) jk时，a在qi中同样不可能被统计； （3）j>k，那么，在qk中，a被统计了 次，在qk＋1中，a被统计了 次，……，在 中被统计了 ＝1次，在qj＋1，qj＋2，…，qn中被统计了0次。即qk＋r＝ （r＝0，1，…，n－k）。所以，a在式(4.2.6)右端总共被统计的次数为 ＝ ＝ ＝ ＝0 定理得证。 （4） 对称原理 在所讨论的问题中，如果性质 是对称的，即具有k个性质的事物的个数不依赖于这k个性质的选取，总是等于同一个数值，则称这个值为公共数，记作 ，例如： 另外，记 。并称子集 具有对称性质，那么，有 定理4.2.4（对称原理、对称筛） 若子集 具有对称性质，则有 (4.2.7) (4.2.8) N[k]＝ ＝ EMBED Equation.3 (4.2.9) 或 N[k]＝ (4.2.10) （5） 总结 初级经济法重点总结下载党员个人总结TXt高中句型全总结.doc高中句型全总结.doc理论力学知识点总结pdf 容斥原理用法总结 在应用容斥原理求解计数问题时，可按下列步骤进行： （1）根据问题的实际情况，构造一个有限集S＝ 和一个性质集P＝ ， 是S中具有性质 的所有元素组成的子集，问题的关键是构造的性质集P，要使得 容易计算出来 。 （2）统计S中恰好具有k种特征的元素的个数时，将问题转化为求S中恰好具有P中k个性质的元素个数N[k]（k＝0,1,2,…,n），可利用逐步淘汰原理或一般公式，即式(4.2.5)或(4.2.6)。 （3）当统计S中至少具有P中一种性质的元素个数L[1]时，利用容斥原理，即式(4.2.2)，或由L[1]＝ 求得。 （4）注意 ，故可由此式求得S中至少具有k种特征的元素个数L[k]。如k＝2时，有 L[2]＝ §4.3 应 用 4.3.1 排列组合问题 例4.3.1 求a,b,c,d,e,f六个字母的全排列中不允许出现ace和df图像的排列数。 解 令A表示ace作为一个元素出现的排列集合，B为df作为一个元素出现的排列集合，那么，AB为ace、df同时出现的排列集合。因此 ＝4！， ＝5！， ＝3！ 由容斥原理，所求的排列数为 ＝6！－(5！＋4！)＋3！＝582 例4.3.2 错排问题：本问题在研究递推关系时已经讨论过，但若利用容斥原理，则可很容易地得出同一结果。n个元素依次给以标号1,2,…,n，进行全排列，求每个元素都不在自己原来位置上的排列数。 解 令Ai表示数i排在第i个位置上的所有排列，则公共数 ＝ ＝（n－1）！， i＝1,2, …,n . 同理 ＝ ＝（n－2）！, i,j＝1,2, …,n , i≠j ＝ ＝（n－3）！, i,j,k＝1,2, …,n ； i，j,k两两不等 一般 ＝ ＝（n－k）！， k＝1,2, …,n 所求排列数为 Dn ＝ ＝n!－ (n－1)!＋ (n－2)!－…＋ ＝ ＝ 例4.3.3 保位问题（亦称不动点问题或相遇问题）：将原始自然排列1,2,…,n重新作成各种排列，求恰有m个元素在其原来自身位置的排列数（记作 ）。 解 设性质 ：数 排在第 个位置；集合 ：具有性质 的全体排列。那么 ＝ ；k＝1,2, …,n 所以 ，……， ， 由定理4.2.3知， ＝ ＝ ＝ ＝ ＝ ＝ 另法，从n个元素中取m个，有 种取法，且这m 个元素保持不动，其余n－m个元素互相错排，有Dn－m种，故共有 种排法。 特例，当m＝0时，即为错排问题， 就是错排数Dn ． 4.3.2 初等数论问题 例4.3.4 求不超过120的素数个数。 解 （1）因112＝121，故不超过120的和数既是2、3、5、7的倍数，而且其因子不可能都大于11。即若 且 为和数，则a和b中必有一个小于11。例如 55＝5×11， 194＝2×97 （2）设 为数 的倍数集（ ＝2,3,5,7），那么 ， ， ， ，…， （3）利用逐步淘汰原理计算 ＝ － ＋ ＝120－(60＋40＋24＋17)＋(20＋12＋8＋8＋5＋3) －(4＋2＋1＋1)＋0 ＝27 （4）但是，这27个数未包含2,3,5,7本身，却将非素数1含在其中，故所求素数个数为 27＋4－1＝30 例4.3.5 （Euler问题） 求1～n中与n互质的数的个数 (n)（称作Euler函数）。这是数论中一个著名的函数。例如： (1)＝1， (2)＝1， (3)＝2， (4)＝2， (5)＝4， (6)＝2 . 特别是当n是一个素数p时， (p)＝p－1 . 解 分解n为素数幂的乘积 （Pi为素数），并设数集N＝{1，2，…，n}，Ai为N中能被Pi整除的那些数的全体，显然 ，i＝1,2, …,k ， 1≤i＜j≤k 于是 (n)＝ ＝ ＝ ＝ 4.3.3 集合的划分 将集合划分为若干个非空部分后，部分与部分之间可以毫无区分，也可以标上号以示区别。前者称为无序划分，后者称为有序划分。 例4.3.6 将一个n元集划分成r个非空子集，并且给每个子集分别标上号：1，2，…，r。试证由此得到的全部划分 方案 气瓶 现场处置方案 .pdf气瓶 现场处置方案 .doc见习基地管理方案.doc关于群访事件的化解方案建筑工地扬尘治理专项方案下载 数为 D(n, r)＝ ＝ 证 设S为将n元集划分成有序r部分的全部划分方案集（每一部分可空），Ai表示第i部分为空的全部方案集，那么 ，1≤i＜j≤r 所以 D(n，r)＝ ＝ ＝ 当r＝n时，将n元集划分成有序的n部分，且每部分不空的每一种划分方案实质上对应n个元素的一个排列，故应有n！种划分方案。由此可得关于n！的一个恒等表达式： 如果将问题改为无序划分，则方案数就是第二类Stirling数 由此即得关于S2（n，r）的计算公式（见3.4.2节） 此类模型还对映以下问题：将n个人分为r组的分法数（无序划分），或将n个小学生分为r个班，班号为1，2，…，r，每班至少一人，求分法数（有序划分）。类似的还有n元集A到r元集B的满射共有D(n，r)种。所谓满射就是指B中每个元素至少有一个原像。 4.3.4 其它应用 例4.3.7 求完全由n个布尔变量确定的布尔函数的个数。 解 分析：当n＝2时，两个自变量x，y共有22＝4种状态：00,01,10,11 。 有24＝16种不同函数，其取值情况见表4.3.1 。 表4.3.1 n＝2时的布尔函数表 自变量 x 0 0 1 1 y 0 1 0 1 函 数 f0 0 0 0 0 0 f1 x∧y 0 0 0 1 f2 x∧ 0 0 1 0 f3 x 0 0 1 1 f4 ∧y 0 1 0 0 f5 y 0 1 0 1 f6 (x∨y) ∧( ∨ ) 0 1 1 0 f7 x∨y 0 1 1 1 f8 ∧ 1 0 0 0 f9 ( ∨y) ∧(x∨ ) 1 0 0 1 f10 1 0 1 0 f11 x∨ 1 0 1 1 f12 1 1 0 0 f13 ∨y 1 1 0 1 f14 ∨ 1 1 1 0 f15 1 1 1 1 1 从表中可以看出，f(x,y)的取值情况与22＝4的二进制数相对应。但其中有的可能与某一变量无关。如f 3实际上是x的函数，与y无关，f 5则只是y的函数，与x无关。f 10＝ ，f 12＝ ，f 15＝1，f 16＝0，均与x，y都无直接关系。故完全由x、y确定的函数应为10个。那么，对于n个变量，情况又如何呢？ 设n个布尔变量x1, x2, … xn的布尔函数为f（x1, x2, … xn）,S是由所有f组成的函数的集合，并令Ai为S中xi不出现的函数类（i＝1,2, … , n）。由于k个布尔变量x1, x2, … xk 的不同的布尔函数数目与2k位二进制数数目相同，即 个。所以 ，1≤i＜j≤n 所以 ＝ － ＋ －…＋ 例如， n＝2时， ＝ － ＋ ＝16－8＋2＝10 n＝3时， ＝ ＝256－48＋12－2＝218 例4.3.8 证明把n分成各部分不能被d所整除的剖分数等于把n划分成每一部分不出现d次或d次以上的剖分数。 证 以 表示n的所有剖分数，易知n的含有数x的剖分数等于数n－x的剖分数 。因为n的任一含有x的剖分，去掉x之后，恰是n－x的一个剖分。反之n－x的一个剖分加上x之后，恰是n的一个剖分。推广为一般情形，n的含有x，y，z，…的剖分数等于数n－x－y－z－…的剖分数p(n－x－y－z－…)。 以 表示每一部分都不能被d所整除的n的剖分数， 表示每一部分出现的次数都不能超过d－1的剖分数。因此从 中减去含有d，2d，3d，…的剖分个数即得 ，从 中减去含有d个1，d个2，d个3，…的剖分个数就得到 。 设 为n的满足如下条件的所有分拆方案构成的集合：该方案中有一项为d的 倍 ，那么 ，1≤i＜j≤n 所以，由逐步淘汰原理知 ＝ = 同理，有 比较两式得 ＝ 。 例4.3.9 试求多重集 的r＝11的组合数，要求组合中至少含有一个a。 解 可先从S中取出一个a，然后再从a、b、c中选取10个元素，即得S的满足条件的组合方案。因此，问题等价于求多重集 的r＝10的组合数。 构造集合 。从 的r＝10的组合中去掉那些有多于4个a，或多于5个b的组合，便得S的10组合。 令 为 的所有r组合构成的集合， 分别为 中那些含有多于4个a，5个b的元素组成的子集，则 为了求 ，可设想先从 中取5个a，而后再任取10－5＝5个元素，以构成 的10组合。所以 类似地，有 由逐步淘汰原理，所求组合数为 ＝66－（21＋15）＋0＝30 例4.3.10 求方程 ＝20的整数解的个数，其中 ， ， 。 解 令 ， ， ，则原方程转化为等价方程 ＝20 即 ＝15 其中 ， ， 。而关于y的方程的解的个数等于多重集 的r＝15的组合数，即 ＋ －0 ＝ ＝136－（28＋36＋55）＋（0＋1＋0）＝18 因为两个方程是等价的，所以原方程解的个数也是18。 §4.4 限制排列与棋盘多项式 4.4.1 有限制的排列 所谓有限制的排列，是指排列中对元素的排列位置加以限制。这样的限制分两种情形： （1）相对位置：即某些元素不能相互连在一起，如前边的例4.3.1及下边的例。 （2）绝对位置（也称禁位排列）：指相对于原始排列中的排列顺序，再次打乱顺序重排时，某些元素不在其原来的位置，最典型的如错排。 例4.4.1 在4个x，3个y，2个z的全排列中，求不出现xxxx、yyy、zz图像的排列数。 解 设A为出现xxxx图像的全体排列，B为出现yyy的全体排列，C为出现zz的全体排列。那么，按照要求，在A中可以将xxxx视为一个整体，即一个元素再与3个y和2个z进行排列，所以 类似地,有 ， ， ， ， ， 由容斥原理，所求排列数为 ＝ －（ ＋ ＋ ）＋（ ＋ ＋ ）－ ＝ －（ ＋ ＋ ）＋（ ＋ ＋ ）－ 例4.4.2 相邻禁位排列问题：在整数1,2, …,n的无重全排列a1 a2… an中，要求 (k＝1,2, …,n－1)。试求全体排列数Qn . 解 问题等价于在排列中，数i不能排在数i＋1之前。即不允许出现12，23，34，…， (n－1) n中任何一种形式。 用S表示所有无重全排列的集合，并设性质Pi表示在全排列中具有i (i＋1)的形式这一性质，令 视i (i＋1)为一个整体，立即可得 ，i ＝1,2, …,n－1 . 现在计算 ( i≠j)。 这种排列里同时含有i (i＋1)和j (j＋1)两种形式，不失一般性，设i < j，下面分两种情况进行讨论： （1）j ≠ i＋1，例如23，45等，可把i (i＋1)和j (j＋1)分别看作一个元素，于是成为n－2个元素的排列，其个数为(n－2)! ； （2）j ＝ i＋1，例如23，34等，这时排列中出现i (i＋1) (i＋2)，可将其视为一个元素，于是这样的排列个数也是(n－2)! . 注意，两种情况不能同时存在，故 ＝(n－2)! 同理可得 ＝(n－3)!，……， ＝[n－(n－1)]!＝1. 所以 Qn＝ ＝ ＝ 整理，得 Qn＝ ＋ ＝ Dn－1＋ Dn ，Dn为错排数 （4.4.1） 本例的实际应用就是有若干人经常按身高大小排着队出外散步，除第一人之外，其他的人总是看到某一个人在自己之前，时间久了，难免感到乏味，故决定变换他们的相对位置，使得每个人的前面都不是原来的那个人，问有多少种变换方式？ 例4.4.3 举办一个8人参加的舞会，其中有4位先生和4位女士。每人都戴着面具，且外观上两两不同。如果将面具集中后，再随意地分发给每人一个，试求： （1）每位先生都拿到自己的面具，而女士无一人拿到自己面具的方案数； （2）先生们没有一位拿到自己面具的方案数； （3）8人中，只有4位没有领到自己面具的方案数。 解 显见，本例是一个局部错排问题，也是禁位排列问题。设S为所有分发方案集。 （1）由条件易知是4个元素的错排问题，所求方案数为 D4＝ ＝9 （2）由于先生们的面具无一到位，而女士们的面具可能到位也可能错位，故不能简单套用错位排列的计算公式。 设Ai表示第i个先生拿到自己面具的分发方案集(i＝1,2,3,4)，那么 ＝（8－k）！， k＝1,2,3,4 所求方案数为 ＝ ＝ ＝24024 （3）这是一个保位问题，由例4.3.3和本例(1)可求得方案数为 ＝70×9＝630 4.4.2 棋盘多项式 （1） n元排列与棋盘布局 n个元素的某一全排列可以看作是n个棋子在一个n×n棋盘上的一种特殊布局，其特殊性在于当一个棋子放到棋盘的某一格子时，则这格子所在的其它行和列便不能再布放其它任何棋子。例如排列3241和图4.4.1的布局相对应。4132 所以，n元排列与n个棋子在n×n棋盘上的布局，是一一对应的，而布局的规则则是棋子间不共行、不共列。 〇 〇 〇 〇 图4.4.1 棋盘布局 （2） 符号 把棋盘记作C，它可以是由小方格拼起来的任意形状的棋盘（如图4.4.2所示）。这里，先给出如下记号： rk(C)：将k个棋子布到棋盘C的不同方案数，规定r0(C) ＝1； R(C)：数列{ rk }的母函数，称为C的棋盘多项式，即 R(C)＝ (4.4.2) 规定R( )＝1，其中φ表示一个格子也没有的空棋盘。 Ci：在C中去掉某一方格所在的行和列后所剩的棋盘，如图4.4.2（a）中去掉*所在的行与列后即为图4.4.2（b）； Ce：在C中去掉某一方格后所剩的棋盘，如图4.4.2（c）就是在图4.4.2（a）中去掉*所在的格子后剩下的棋盘； 若棋盘C可分为两个小棋盘C1和C2，且C中任一行（或列）要么属于C1，要么属于C2，即同行（或列）中没有属于C1和C2的两种格子，则称棋盘C是可分离的，如图4.4.2中的(d)。 (a) (b) (c) (d) 图4.4.2 棋盘举例 例如： C1 C2 C3 r1(C1)＝1，r1(C2)＝2，r1(C3)＝2，r2(C2)＝0，r2(C3)＝1。 对简单的棋盘C，通过观察可直接写出R（C）： R(C1)＝ ， R(C3)＝ ， R(C2)＝ ， 又如 C4 C5 C6 C7 C8 R(C4)＝ ，R(C5)＝ ， R(C6)＝ ，R(C7)＝ ， R(C8)＝ ＝ . 显然，多项式R(C)与棋盘C不是一一对应的。 （3） rk(C)和R(C)的计算 定理4.4.1 （1） rk(C)＝ rk－1(Ci)＋ rk(Ce) (4.4.3) （2） R(C)＝x R(Ci)＋ R(Ce) (4.4.4) （3）若C可分离为C1和C2，则有 rk(C)＝ (4.4.5) R(C)＝ R(C1) R(C2) (4.4.6) 证 （1）就某一格子而言，无非有两种可能，一是对该格子布下了棋子，一是不布棋子，所有的布局依此可分为两类。右端第一项rk－1(Ci)表示某格子放有棋子，而剩下的k－1个棋子布到Ci棋盘上的方案数。第二项rk(Ce)表示该格子不布棋子，所有k个棋子布到棋盘Ce上的方案数。两类布法，不能同时出现，由加法法则，式（4.4.3）成立。 （2）由R(C)的定义和式（4.4.3），有 R(C)＝ ＝ ＝x R(Ci)＋ R(Ce) （3）由于C1与C2是分离的，故可以将k个棋子布到棋盘C上的方案分为k＋1类，即C1上布j个棋子，C2上布k－j个棋子，j＝0,1,…,k . 每一类有 种方案，再对所有j求和，即得布k个棋子的总方案数为 。 其次，由R(C)的定义和式(4.4.5)，有 R(C)＝ ＝ ＝ R(C1) R(C2) 其中当r>n时，xr之前的系数肯定是0 . 利用式(4.4.4)和(4.4.6)，可以把一个较复杂的棋盘逐步分解为一批较简单的棋盘，从而比较容易地得到原棋盘的多项式。例如 ＝xR(□)＋ ＝ ＝ , ＝ EMBED Equation.3 ＝ EMBED Equation.3 ＝ ＝ . 4.4.3 有禁区的排列 若在4个元素a1，a2，a3，a4进行排列的过程中，限制a1不能排在第一个位置，a2不能在1、4号位置，a3不在2号,a4不在3号。前面已经提到，可以将4元素的排列对应一个4×4的棋盘，对于某个具体排列，对应到棋盘上如图4.4.1所示，棋盘上的第i行对应第i个棋子（即ai），第j列对应该棋子所布放的位置。现在用带阴影线的格子表示限制，称为禁区。所以，有限制的n元排列与n个棋子在带有禁区的n×n棋盘C上的布局又一一对应起来。求有限制的排列数就等价于求有禁区的棋盘的布局方案数。 另一方面，可以将禁区视为一个随意形状的棋盘A，棋盘C去掉A后余下的部分夜视仪个形状不规则的棋盘，叫做B。显然，将棋子布入B的方案数就是在C上符合条件的方案数。所以，只要计算出n个棋子在A上的布局方案数N[A]，再用总的n元排列数n!减去N[A]，即得在B上的布局方案数N[B]。 定理4.4.2 N[A]＝ (4.4.7) 或 N[B]＝ (4.4.8) 证 设n元排列a1 a2…an，其中ai是第i号棋子落在第i行的位置，如2314657表示第1号棋子放在第1行的2号位置（即第2列），棋子2在第2行的3号位（第3列），棋子3在第3行的1号位（第1列），…。令Pi表示第i个棋子放入禁区的性质，集合Ai表示具有性质Pi的所有布局方案集。 一个棋子落入禁区A的方案数显然为r1(A)，而剩下的n－1个棋子为无限制条件的排列，故至少有一个棋子落在A上的方案数为 。同理，两个棋子落入禁区A的方案数显然为r2(A)，而剩下的n－2个棋子为无限制条件的排列，故至少有两个棋子落在A上的方案数为 ，……总的排列方案数共n!个，所以由容斥原理和逐步淘汰原理，即知式(4.4.7)和(4.4.8)成立。 例4.4.4 设有4个元素的排列，其中要求第1个元素不能排在第1个位置，第2个元素不能在1、4号位置，元素3不能在2号、元素4不能在3号位置。问共有多少排列方案数？ 解 所提排列问题对应有禁区的棋盘C（见图4.4.3 (a)），其禁区A（见图4.4.3 (b)）可分离为两个小棋盘A1和A2（见图4.4.3 (c)）。 显见 R(A1)＝1＋3x＋x2， R(A2) ＝1＋2x＋x2 图4.4.3 有禁区的排列 由公式(4.4.7)可得到 R(A)＝( 1＋3x＋x2)( 1＋2x＋x2)＝1＋5x＋8 x2＋5x3＋x4 由定理4.4.2，所求排列数应为 N[B]＝4!－r1(A) 3!＋r2(A)2!－r3(A)1!＋r4(A)0! ＝4!－5×3!＋8×2!－5×1!＋1×0! ＝6 这6个满足条件的排列是 2314 2341 3214 3241 4231 4312 这样的实际问题如工作安排（即匹配）问题：设有A、B、C、D四位工作人员，要完成x﹑y﹑z﹑w四项任务，但A不适合去做事情y，B不适合做事情y﹑z，C不适合做z﹑w，D不适合做w。读者可以试计算，若要求每人完成一项各自所适宜的任务，共有多少种分配任务的方案？ 例4.4.5 （错排问题） 即第i个棋子不能排在第i横行的第i个位置，问题可以看作在一个n×n的棋盘上，以对角线上的方格为禁区A的布局问题，求布局方案数。 解 如图4.4.4所示，阴影部分为禁区构成的棋盘A，由式（4.4.6）知 R(A)＝ R(□) …R(□)＝ …… …… …… …… 图4.4.4 错排问题的棋盘布局 从而必有 rk (A)＝ ， k＝1,2, …,n 因此，由公式(4.4.8)可得错排的方案数为 Dn＝N[B] ＝ ＝ §4.5 反演公式 （1） 问题 在某些组合（计数）问题中，很多组合数都不易直接得出明显的计算公式。但能从实际问题出发，得到未知量所满足的一组方程，然后通过解方程得出这些未知量的解。 （2） 实例 例如，前面已经用几种方法解决了错排的计数问题，现在，仍以此为例，给出另一种新的解决方法。 已知n个相异元素的错排数为Dn，其中有k个元素在其原来位置（保位），其余 个元素都不在原来位置（错位）的“保位问题”排列数为 （见例4.3.3）。为了求解Dn，先建立关于Dk的方程（k＝1，2，…，n）。 n个元素的全排列可分为以下情况： 0个元素保位，n个元素错位； 1个元素保位，n－1个元素错位； 2个元素保位，n－2个元素错位； n个元素保位，0个元素错位。 因此有 n！＝ 或 ，n＝1，2，… 解之得 Dn＝ ＝ 其解法见后。 （3） 一般情形 归纳起来，就是已知fk是某个计数问题的解，以及fk所满足的关系式 （4.5.1） （cnk为常数，gn已知），然后针对式（4.5.1）解隐式方程，得到 （4.5.2） （dni为常数）。这类问题就称为反演问题，通常把式（4.5.1）和（4.5.2）这对等式称为反演公式或互逆公式。常数cnk和dni称为连结系数。 反演也可以看作求逆变换。即已知序列f0，f1，f2，…，fn到序列g0，g1，g2，…，gn的变换式（4.5.1），求g0，g1，g2，…，gn到f0，f1，f2，…，fn的逆变换式（4.5.2）。 本节的任务就是针对某些典型的反演问题，给出具体的求解结果。 （4） 矩阵表示 将式（4.5.1）和（4.5.2）用矩阵表示，有 ， 其中， ， 均为下三角方阵； ， 。 不难看出，反演公式（4.5.1）和（4.5.2）等价于相应的变换矩阵 和 是互逆的。因此，只要能构造出两个互逆的下三角矩阵，便能得到相应的反演公式。 4.5.1 第一反演公式 （一）结论 定理4.5.1 设有两个（实系数）的多项式序列{ Pk (x)} 和{ Qk (x)}（均为k次多项式，k＝0,1,2, …,n），满足 ， （4.5.3） 则对于两组实数序列{ak} 和{ bk}，有 ，k＝0，1，…，n （4.5.4） 证 令 ， ， ， ， 则式（4.5.3）可用矩阵表示为 P(x)＝CQ(x) 和Q(x)＝DP(x) 式（4.5.4）的矩阵表示形式为 A＝CB， B＝DA 那么，从矩阵运算角度，有 P(x)＝CQ(x)＝（CD）P(x) 由x的任意性且P0(x)，P1(x)，…，Pn(x)是不同次数的多项式，因此必有 CD＝In＋1 即有n＋1阶单位矩阵。所以，C、D为互逆矩阵，即 于是 证毕。 本定理表明，由于用连结系数所构成的两个（左下三角矩阵）是互逆的，从而由此导出了用相应连结系数所确定的一对反演公式。 （二）反演公式 推论4.5.1 二项式反演公式： ，k＝0，1，…，n （4.5.5） 证 取Pk(x)＝xk ，Qk(x)＝(x－1) k，由二项式定理知 xk ＝{(x－1)＋1}k＝ (x－1)k＝ ＝ 可见两个多项式族{ xk }和{(x－1) k }满足关系（4.5.3），由定理即得式（4.5.5）。 二项式反演公式也可以写成如下的对称形式： EMBED Equation.3 ，k＝0，1，…，n （4.5.6） 推论4.5.2 Stirling反演公式： EMBED Equation.3 ，k＝0，1，…，n （4.5.7） 其中， 、 分别为第一类和第二类Stirling数。 证 取Pk(x)＝xk ，Qk(x)＝[x] k＝x(x－1)(x－2) …(x－k＋1)（即下阶乘函数，见 3.4.2节），那么，由Stirling数的定义即知式（4.5.7）成立。 推论4.5.3 Lah反演公式： EMBED Equation.3 ，k＝0，1，…，n （4.5.8） 其中，L(k,i)为Lah数，它是由等式[－x]k ＝ 来定义的，即L(k,i)是函数 按下阶乘函数[x]i展开的系数。 证 取Pk(x)＝ [－x] k ，Qk(x)＝[x] k 。由下阶乘函数[x] k和Lah数L(k,i)的定义知 [－x] k ＝(－x) (－x－1) (－x－2) …(－x－k＋1) ＝(－1)k x(x＋1)(x＋2) …(x＋k－1) 是x的多项式，故可以按[x] k展开成 [－x]k ＝ 再在上式中以－x代替x，可得 [x]k ＝ 按照定理，即得式（4.5.8）。 （三）应用 例4.5.1 （错排问题） 已知 ，令ak＝ Ek＝k!，则由式（4.5.5），有 Dk＝bk＝ ＝ ＝ 4.5.2 反演公式 反演公式是初等数论中一个古典的反演公式，它在组合数学、信息论以及应用物理几类逆问题的研究中都有重要应用。 （一）墨比乌斯函数 定义4.5.1 函数 (n)定义为 . 例如， (2)＝(－1)1＝－1， (9)＝ (32)＝0， (10)＝ (2×5)＝(－1)2＝1， (126)＝ (2×32×7)＝0， (54)＝ (2×33)＝0. 定理4.5.2 对任意正整数n,有 其中 表示让d取遍n的所有正因子而对 (d)求和，包括因子1和n . 证 当n＝1时，由定义知 (n)＝1 . 当n>1时，设n的 标准 excel标准偏差excel标准偏差函数exl标准差函数国标检验抽样标准表免费下载红头文件格式标准下载 素因子分解式为 并令 显见，若d能整除n*，则d必能整除n；若d能整除n，但d不能整除n*，则d 必含平方素因子，从而 (d)＝0 。 于是，在求和式 中只要考虑 的因子就够了。对于那些是n的因子而又不是n*的因子的数d，由于 (d)＝0，就不用考虑了。所以，问题化简为 ＝ ＝ ＝ ＝(1－1)k＝0 证毕。 例 n＝2， (1)+ (2)＝1+(－1)＝0， n＝6， (1)+ (2) + (3) + (6)＝1+(－1) +(－1) +(－1) 2＝0 例4.5.2 关于Euler函数 (n)的一个公式如下： （4.5.9） 证 如果n＝1，等式显然成立。 若n>1，设 ，并令 ，则 ＝ ＝ ＝ ＝ ＝ (n) （二）墨比乌斯反演公式 反演公式是初等数论中一个古典的反演公式，它在组合数学、信息论以及应用物理几类逆问题的研究中都有重要应用。 （一）墨比乌斯函数 定义4.5.1 函数 (n)定义为 . 例如， (2)＝(－1)1＝－1， (9)＝ (32)＝0， (10)＝ (2×5)＝(－1)2＝1， (54)＝ (2×33)＝0， (126)＝ (2×32×7)＝0. 定理4.5.2 对任意正整数n,有 其中 表示让d取遍n的所有正因子而对 (d)求和，包括因子1和n . 证 当n＝1时，由定义知 (n)＝1 . 当n>1时，设n的标准素因子分解式为 并令 显见，若d能整除n*，则d必能整除n；若d能整除n，但d不能整除n*，则d 必含平方素因子，从而 (d)＝0 。 于是，在求和式 中只要考虑 的因子就够了。对于那些是n的因子而又不是n*的因子的数d，由于 (d)＝0，就不用考虑了。所以，问题化简为 ＝ ＝ ＝ ＝(1－1)k＝0 证毕。 例 n＝2， (1)+ (2)＝1+(－1)＝0， n＝6， (1)+ (2) + (3) + (6)＝1+(－1) +(－1) +(－1) 2＝0 例4.5.2 关于Euler函数 (n)的一个公式如下： （4.5.9） 证 如果n＝1，等式显然成立。 若n>1，设 ，并令 ，则 ＝ ＝ ＝ ＝ ＝ (n) （二）墨比乌斯反演公式 定理4.5.3 古典 反演公式：设f(n)、g(n)是自然数集上的两个函数，则 f(n)＝ g(n)＝ (4.5.10) 证 先证必夭性。若式(4.5.10)左端的等式对自然数n成立，那么它对自然数 也应该成立，即将式f(n)＝ 中的n换为 ，有 ＝ ，从而有 ＝ ＝ （例如n=6， =μ(1)[ g(1)+ g(2)+ g(3)+ g(6)]+μ(2)[ g(1) + g(3)] +μ(3)[ g(1)+ g(2)] +μ(6)[ g(1)] = g(1)[μ(1) +μ(2) +μ(3) +μ(6)]+ g(2)[μ(1) +μ(3)] g(3)[μ(1) +μ(2)]+ g(6) [μ(1)] = ） 由定理4.5.1知 故 ＝ g(n) 同理可证充分性成立。 （三）应用 例4.5.3 利用 反演公式，将n用Euler函数 (d)表示。 因为 (n)＝ ＝ 在式(4.5.10)中，令g(n)＝ (n)， （即函数f取值为f(n)＝n），那么，由定理4.5.3知 n＝f(n)＝ ＝ 故 n ＝ (4.5.11) 式（4.5.9）和（4.5.11）构成了n与 (n)之间的互为逆变换的关系，或者说二者满足 反演。 例4.5.4 （可重圆排列问题）我们已经知道m个相异元素的不重圆排列数为 个，但这m个相异元素的可重圆排列数是多少，问题将复杂得多。首先是将某个给定的m元不重圆排列在某两个元素的中间断开，就对应一个线排列，断开的位置不同，对应的线排列也不同。因此，同一个圆排列对应m个不同的线排列，从而m个相异元素的不重圆排列数为 。但对可重圆排列，上述规律未必成立，即从m个相异元素中可重复地取n个构成的圆排列的个数并不能简单地直接推广为 。例如，设集合 有m个相异元素，当 时取其不同的部分元素a1,a2,…, ad重复n/d次构成的（n个元素的）圆排列 ⊙ 只能形成d个不同的线排列（⊙表示上述n个元素是首尾相接形成一个圆排列的）。 例如，m=8， ，n=6，则圆排列与线排列的对应关系有： 圆排列 线排列 比例 出现的字符数 ⊙222222 222222 1:1 1 ⊙121212 121212，212121 1:2 2 ⊙655655 655655，556556，565565 1:3 2 ⊙222226 222226，222262，222622，226222，262222， 622222 1:6 2 ⊙362362 362362，623623，236236 1:3 3 ⊙362236 362236，622363，223636， 236362，363622， 636223 1:6 3 ⊙142255 142255，422551，225514， 255142，551422， 514225 1:6 4 ⊙143516 143516，435161，351614， 516143，161435， 614351 1:6 5 ⊙135462 135462，135462，135462，135462，135462， 135462 1:6 6 一个圆排列中所含元素的个数称为该圆排列的长度（重复出现的元素按其重复出现次数统计）。长度为 n的圆排列简称为n圆排列。一个圆排列如果可由某个长度为k的线排列在圆周上重复若干次而产生，则把这种k中的最小者称为该圆排列的（最小）周期。因此，任何一个圆排列必有一个周期，而且周期必是圆排列长度的因子。不重的m圆排列只是长度和周期都等于m的特殊可重圆排列而已。 将周期为d的n可重圆排列的个数记为M(d)，则周期是d的全部n可重圆排列所对应的n可重线排列的个数是d·M(d)。对所有的周期进行求和，便得到 (4.5.12) 其中 是集合A所有元素的n可重线排列的个数，和式遍取n的所有因子（包括1与n本身）。 令f(n)＝ ，g(n)＝ n·M(n)，利用古典 反演公式(4.5.10)可得 n·M(n)＝g(n)＝ ， 即M(n)＝ 它表示以n为周期的n可重圆排列的个数。 若用T(n)表示长度为n的所有n可重圆排列的个数，那么 T(n)＝ 可以证明 T(n)＝ ＝ 其中 (d)为Euler函数。 作业 2，3，4，5，6，9，10，12 习 题 四 1. 试求不超过200的正整数中素数的个数。 2. 问由1到2000的整数中： （1） 至少能被2，3，5之一整除的数有多少个？ （2） 至少能被2，3，5中两个数同时整除的数有多少个？ （3） 能且只能被2，3，5中1个数整除的数有多少个？ 3. 求从1到500的整数中能被3和5整除但不能被7整除的数的个数。 4. 某人参加一种会议，会上有6位朋友，他和其中每一人在会上各相遇12次，每二人各相遇6次，每三人各相遇4次，每四人各相遇3次，每五人各相遇2次，与六人都相遇1次，一人也没遇见的有5次，问该人共参加几次会议？ 5. n位的四进制数中，数字1，2，3各自至少出现一次的数有多少个？ 6. 某照相馆给n个人分别照相后，装入每人的纸袋里，问出现以下情况有多少种可能： （1） 没有任何一个人得到自己的相片； （2） 至少有一人得到自己的相片； （3） 至少有两人得到自己的相片。 7. 把{a,a,a,b,b,b,c,c,c}排成相同字母互不相邻的排列，有多少种排法？ 8. 把1,2,…,n排成一圈，令f(n)表示没有相邻数字恰好是自然顺序的排列数 （1） 求f(n)； （2） 证明 f(n)＋ f(n＋1)＝Dn . 9. n个单位各派两名代表出席一个会议，2n 位代表围圆桌而坐，试问 （1） 同一单位的代表相邻而坐的方案有多少？ （2） 同一单位的代表互不相邻的方案又有多少？ 10. 一书架有m层，分别放置m类不同种类的书，每层n册，现将书架上的图书全部取出整理，整理过程中要求同一类的书仍然放在同一层，但可以打乱顺序，试问 （1） m类书全不在各自原来层次上的方案数有多少？ （2） 每层的n本书都不在原来位置上的方案数是多少？ （3） M层书都不在原来层次，每层n本书也不在原来位置上的方案数又是多少？ 11. 证明错排数的下列性质 （1） Dn＝(n－1)( Dn－2＋ Dn－1) （2） Dn＝n Dn－1＋(－1)n 12. n个人参加一晚会，每人寄存一顶帽子和一把雨伞，会后各人也是任取一顶帽子和一把雨伞，问 （1） 有多少种可能使得没有人能拿到他原来的任一件物品？ （2） 有多少种可能使得没有人能同时拿到他原来的两件物品？ _1161114967.unknown _1161270452.unknown _1225108701.unknown _1242295215.unknown _1242295415.unknown _1242295548.unknown _1243604152.unknown _1243604200.unknown _1243604262.unknown _1245819983.unknown _1245826731.unknown _1243604389.unknown _1243604910.unknown _1243604205.unknown _1243604184.unknown _1243604196.unknown _1243604188.unknown _1243604156.unknown _1242296393.unknown _1243603937.unknown _1243604101.unknown _1243604147.unknown _1243604107.unknown