第四章 容斥原理

第四章 容斥原理 第四章第四章 容斥原理容斥原理 4.1 引言引言 4.2 容斥原理容斥原理 4.3 应用应用4.4 限制排列与棋盘限制排列与棋盘多项式多项式4.5 反演公式反演公式 第四章 容斥原理 容斥原理又称为“入与出原理”、“包含排斥原理”或“交互分类原理”.它是组合学中的 一个基本计数理论.当用加法法则解决一些集合的计数问题时,一般要求将计数的集合划 分为若干个互不相交的子集,且这些子集都比较容易计数.然而,实际中又有很多计数问 题要找到容易计数且又两两不相交的子集并非易事.但往往能够知道某一集合的若干相交 子集的计数,进而把所要求的集合中的元素个数计算出来.这一计数方法就是下面所要介 绍的容斥原理.第四章 容斥原理 4.1 引引 言言第四章 容斥原理 关于集合的运算,有:第四章 容斥原理 集合的运算,满足下列运算定律:第四章 容斥原理 当集合A 中的元素为有限个时,称A 为有限集合,其元素个数记为|A|,亦称为A 的 势.关于|A|,有如下简单性质:(1)若集合A、B 不相交,即AB=,则|A+B|=|A|+|B|;(2)若AB,则|A-B|=|A|-|B|.第四章 容斥原理 4.2 容容 斥斥 原原 理理引理引理 4.2.1 设A,B 为有限集合,则有第四章 容斥原理 证证 显然,对于A+B 中的元素a,在等式左边恰被统计一次,而在等式右边被统计 的次数,可分为如下三种情形来考虑:(1)aA,但aB,则a 也恰被统计一次;(2)aA,但aB,同样恰被统计一次;(3)aA 且aB,那么必有aAB,从而a 被统计1+1-1=1次.所以,a 在等式两边被统计的次数是相同的,引理4.2.1得证.第四章 容斥原理 定理定理 4.2.1(容斥原理容斥原理)设A1,A2,An 为有限集合,则证证 用数学归纳法证明.(1)当n=2时,由引理4.2.1知,结论成立.(2)设对n-1,结论正确.即第四章 容斥原理(3)那么,对于n,有第四章 容斥原理 第四章 容斥原理 第四章 容斥原理 第四章 容斥原理 第四章 容斥原理 第四章 容斥原理 第四章 容斥原理 定理定理 4.2.3(一般公式一般公式)一般公式也称为约当(Jordan)公式.第四章 容斥原理 证证 类似于定理4.2.2的证法二,只要算出S 中每个恰好具有k 个性质的元素,在式(4.2.6)的右端被统计一次,而对性质少于k 或大于k 的元素,则统计了0次,就证明了一 般公式的正确性.设S 中元素a 具有j种性质,分三种情况予以讨论:(1)jk 时,a 在q-中同样不可能被统计;第四章 容斥原理 第四章 容斥原理 在所讨论的问题中,如果性质 P1,P2,Pn 是对称的,即具有k 个性质的事物的 个数不依赖于这k 个性质的选取,总是等于同一个数值,则称这个值为公共数,记作Rk,例如:第四章 容斥原理 第四章 容斥原理 容斥原理用法总结容斥原理用法总结 在应用容斥原理求解计数问题时,可按下列步骤进行:(1)根 据 问 题 的 实 际 情 况,构 造 一 个 有 限 集 S=e1,e2,et和 一 个 性 质 集 P=P1,P2,Pn,Ai 是S 中具有性质Pi 的所有元素组成的子集,问题的关键是构造 的性质集P,要使得|A1A2Ak|容易计算出来(k=1,2,n).(2)当统计S 中恰好具有k 种特征的元素的个数时,将问题转化为求S 中恰好具有P 中k 个性质的元素个数Nk(k=0,1,2,n),可利用逐步淘汰原理或一般公式,即 式(4.2.5)或(4.2.6).第四章 容斥原理(3)当统计S 中至少具有P 中一种性质的元素个数L1时,利用容斥原理,即式(4.2.2),或由L1=|S|-N0求得.(4)注意|S|=N0+N1+N2+Nn,故可由此式求得S 中至少具有k 种特征的元素个数Lk.如k=2时,有第四章 容斥原理 4.3 应应 用用4.3.1 排列组合问题排列组合问题第四章 容斥原理【例【例4.3.2】(错排问题错排问题)本问题在研究递推关系时已经讨论过,但若利用容斥原理,则 可很容易地得出同一结果.n 个元素依次给以标号1,2,n,进行全排列,求每个元素 都不在自己原来位置上的排列数.第四章 容斥原理 第四章 容斥原理【例【例4.3.3】保位问题】保位问题(亦称不动点问题或相遇问题亦称不动点问题或相遇问题)将原始自然排列1,2,n 重新 作成各种排列,求恰有m 个元素在其原来自身位置的排列数(记作Dnm).第四章 容斥原理 第四章 容斥原理 第四章 容斥原理 4.3.2 初等数论问题初等数论问题【例【例 4.3.4】求不超过120的素数个数.第四章 容斥原理 第四章 容斥原理 第四章 容斥原理 4.3.3 集合的划分集合的划分 将集合划分为若干个非空部分后,部分与部分之间可以毫无区分,也可以标上号以示 区别.前者称为无序划分,后者称为有序划分.【例【例 4.3.6】将一个n 元集划分成r 个非空子集,并且给每个子集分别标上号:1,2,r.试证由此得到的全部划分方案数为第四章 容斥原理 第四章 容斥原理 第四章 容斥原理 4.3.4 其它应用其它应用【例【例 4.3.7】求完全由n 个布尔变量确定的布尔函数的个数.解 分析:当n=2时,两个自变量x,y 共有22=4种状态:00,01,10,11.有24=16 种不同函数,其取值情况见表4.3.1.第四章 容斥原理 第四章 容斥原理 第四章 容斥原理【例【例 4.3.8】证明把n 分成各部分不能被d 所整除的剖分数等于把n 划分成每一部分 不出现d 次或d 次以上的剖分数.证证 以p(n)表示n 的所有剖分数,易知n 的含有数x 的剖分数等于数n-x 的剖分 数p(n-x).因为n 的任一含有x 的剖分,去掉x 之后,恰是n-x 的一个剖分.反之,n-x 的一个剖分加上x 之后,恰是n 的一个剖分.推广为一般情形,n 的含有x,y,z,的剖分数等于数n-x-y-z-的剖分数p(n-x-y-z-).第四章 容斥原理 第四章 容斥原理 所以,由逐步淘汰原理知第四章 容斥原理【例【例 4.3.9】试求多重集S=5a,5b,c的r=11的组合数,要求组合中至 少含有一个a.解解 可先从S 中取出一个a,然后再从a、b、c中选取10个元素,即得S 的满足条件 的组合方案.因此,问题等价于求多重集4a,5b,c的r=10的组合数.构造集合S=a,b,c.从S的r=10的组合中去掉那些有多于4个 a,或多于5个b 的组合,便得S 的10组合.第四章 容斥原理 第四章 容斥原理 第四章 容斥原理【例【例4.3.11】用容斥原理证明下列组合等式:第四章 容斥原理 第四章 容斥原理 第四章 容斥原理 4.4 限制排列与棋盘多项式限制排列与棋盘多项式4.4.1 有限制的排列有限制的排列 所谓有限制的排列,是指排列中对元素的排列位置加以限制.这样的限制分两种情形:(1)相对位置:即某些元素不能相互连在一起,如前边的例4.3.1及下边的例.(2)绝对位置(也称禁位排列):指相对于原始排列中的排列顺序,再次打乱顺序重排 时,某些元素不在其原来的位置,最典型的如错排.第四章 容斥原理【例【例 4.4.1】在4个x,3个y,2个z 的全排列中,求不出现xxxx、yyy、zz 图像的 排列数.解解 设A、B、C 分别为出现图像xxxx、yyy、zz 的全体排列的组成的集合,那么,按照要求,在A 中可以将xxxx 视为一个整体,即一个元素再与3个y 和2个z 进行排 列,所以第四章 容斥原理 第四章 容斥原理 第四章 容斥原理 第四章 容斥原理【例【例 4.4.3】举办一个8人参加的舞会,其中有4位先生和4位女士.每人都戴着面 具,且外观上两两不同.如果将面具集中后,再随意地分发给每人一个,试求:(1)每位先生都拿到自己的面具,而女士无一人拿到自己面具的方案数;(2)先生们没有一位拿到自己面具的方案数;(3)8人中,只有4位没有领到自己面具的方案数.第四章 容斥原理 解解 显见,本例是一个局部错排问题,也是禁位排列问题.设S 为所有分发方案集.(1)由条件易知是4个元素的错排问题,所求方案数为第四章 容斥原理(2)由于先生们的面具无一到位,而女士们的面具可能到位也可能错位,故不能简单 套用错位排列的计算公式.第四章 容斥原理 4.4.2 棋盘多项式棋盘多项式 n 个元素的某一全排列可以看作是n 个棋子在一个nn 棋盘上的一种特殊布局,其 特殊性在于当一个棋子放到棋盘的某一格子时,则这个格子所在的其它行和列便不能再布 放其它任何棋子.例如排列3241和图4.4.1的布局相对应.第四章 容斥原理 图 4.4.1 棋盘布局第四章 容斥原理 第四章 容斥原理 例如:图 4.4.2 棋盘举例第四章 容斥原理 定理定理 4.4.1第四章 容斥原理 证证(1)就某一格子而言,无非有两种可能,一是对该格子布有棋子,一是不布棋子,所有 的布局依此可分为两类.右端第一项rk-1(Ci)表示某格子放有棋子,而剩下的k-1个棋子 布到Ci 棋盘上的方案数.第二项rk(Ce)表示该格子不布棋子,所有k 个棋子布到棋盘Ce 上的方案数.两类布法,不能同时出现,由加法法则可知,式(4.4.3)成立.第四章 容斥原理(2)由R(C)的定义和式(4.4.3),有第四章 容斥原理 第四章 容斥原理 利用式(4.4.4)和(4.4.6),可以把一个较复杂的棋盘逐步分解为一批较简单的棋盘,从 而比较容易地得到原棋盘的多项式.例如:第四章 容斥原理 4.4.3 有禁区的排列有禁区的排列定理定理 4.4.2第四章 容斥原理 证证 设n 元排列a1a2an,其中ai 是第i号棋子落在第i行的位置,如2314657表示 第1号棋子放在第1行的2号位置(即第2列),棋子2在第2行的3号位(第3列),棋子3 在第3行的1号位(第1列),.令Pi 表示第i个棋子放入禁区的性质,集合Ai 表示具有性质Pi 的所有布局方案集.第四章 容斥原理【例【例 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).显见第四章 容斥原理 第四章 容斥原理 这样的实际问题很多,如工作安排(即匹配)问题:设有 A、B、C、D 四位工作人员,要完成x、y、z、w 四项任务,但A 不适合去做事情y,B 不适合做事情y、z,C 不适合 做z、w,D 不适合做w.读者可以试计算,若要求每人完成一项各自所适宜的任务,共有 多少种分配任务的方案?第四章 容斥原理 图 4.4.3 有禁区的排列第四章 容斥原理【例【例 4.4.5】(错排问题)即第i个棋子不能排在第i行的第i个位置,问题可以看作在 一个nn 的棋盘上,以对角线上的方格为禁区A 的布局问题,求布局方案数.解解 如图4.4.4所示,阴影部分为禁区构成的棋盘A,由式(4.4.6)知从而必有第四章 容斥原理 因此,由公式(4.4.8)可得错排的方案数为第四章 容斥原理 图 4.4.4 错排问题的棋盘布局第四章 容斥原理 4.5 反反 演演 公公 式式例如,前面已经用几种方法解决了错排的计数问题,现在,仍以此为例,给出另一种 新的解决方法.已知n 个相异元素的错排数为Dn,其中有k 个元素在其原来位置(保位),其余n-k 个元素都不在原来位置(错位)的“保位问题”的排列数为 Dnk=Ckn Dn-k(见例4.3.3).为了求解Dn,先建立关于Dk 的方程(k=1,2,n).第四章 容斥原理 n 个元素的全排列可分为以下情况:0个元素保位,n 个元素错位;1个元素保位,n-1个元素错位;2个元素保位,n-2个元素错位;n 个元素保位,0个元素错位.第四章 容斥原理 第四章 容斥原理 第四章 容斥原理 4.5.1 第一