离散数学--9.1-2容斥原理

1第9章容斥原理2第9章容斥原理•9.1容斥原理•9.2对称筛公式及其应用39.1容斥原理•9.1.1容斥原理的基本形式–容斥原理–容斥原理的推论•9.1.2容斥原理的应用–计数多重集的r-组合数–计数限制条件的元素数–计算欧拉函数的值–证明组合恒等式4容斥原理的基本形式mkjimmkjimimjijiimAAAAAAAAASAAA1211121|...|)1(...|||||||||...|定理9.1设S为有穷集，P1,P2,…,Pm是m种性质，Ai是S中具有性质Pi的元素构成的子集，是Ai相对于S的补集，i=1,2,…,m.则S中不具有性质P1,P2,…,Pm的元素数为iA5mkjimmkjimimjijiiAAAAAAAAAS12111|...|)1(...||||||||右边证明证明方法：数学归纳法、组合分析证组合分析.若x不具有任何性质，则对等式右边贡献为：10+00+…+(1)m0=1若x具有n条性质，1nm,则对等式右边的贡献为：nkkmknmnnn001)1(...2116推论推论S中至少具有其中一条性质的元素数为mkjimmkjimimjijiimAAAAAAAAAAAA12111121|...|)1(...|||||||...||...|)1(...|||||||...||||...||||...|211111212121mmmkjikjimimjijiimmmAAAAAAAAAAAASAAASAAA证7应用——计数多重集的r-组合数例1求多重集B={3a,4b,5c}的10-组合数解：令S={x|x是a,b,c任意重复的10-组合}A1={x|xS，x中至少含4个a}={x|x是a,b,c的任意6-组合}A2={x|xS，x中至少含5个b}={x|x是a,b,c的任意5-组合}A3={x|xS，x中至少含6个c}={x|x是a,b,c的任意4-组合}8计数多重集的r-组合数（续）15264143||,21275153||28286163||,66212101103||321AAAS60)013()152128(66||0||||,10103||31113||321321323121AAAAAAAAAAAA注意：性质的设定与要求条件相反性质彼此独立，不同性质的元素计数互不影响9应用——计数限制条件的元素数278561411200)1124()35881220()17244060(120||4321AAAA例2求不超过120的素数个数解：112=121，不超过120的合数的素因子可能是2,3,5,7，S={x|xZ,1x120},|S|=120被2,3,5,7整除的集合分别为A1,A2,A3,A4：|A1|=60，|A2|=40，|A3|=24，|A4|=17|A1A2|=20,|A1A3|=12,|A1A4|=8,|A2A3|=8,|A2A4|=5,|A3A4|=3|A1A2A3|=4,|A1A2A4|=2,|A1A3A4|=1,|A2A3A4|=1，|A1A2A3A4|=0N=27+3.10应用——欧拉函数的值例3计算欧拉函数的值(n).欧拉函数：小于n且与n互素的自然数的个数解n的素因子分解式:Ai={x|0xn1，且pi整除x}，kkpppn...2121)11)...(11)(11(...)1(...)...()...(|...|)(2121131212121kkkkkkkpppnpppnppnppnppnpnpnpnnAAAn11应用——证明交错和的恒等式rmnmmrnmrnmrnAAArmnAAAmjirnAAmjrnAmmmjij)1(...2211|...||...|...,1,2||,1,1||2121证：S={1,2,…,n},A={1,2,…,m}，计数S中包含A的r-子集.Pj:在S的r-子集中不包含j,j=1,2,…,mnrmrinimmrmnmii,)1(0例4证明12•9.2.1对称筛公式及其应用–对称筛公式–错位排列计数•9.2.2棋盘多项式与有限制条件的排列–布棋方案与有限制条件排列的对应–棋盘多项式及其性质–布棋方案数的计数9.2对称筛公式及其应用13对称筛公式令,|S|=N,对称筛公式:(容斥原理的特殊情况)使用条件：不同性质对计数的影响对称.各性质计数是独立的.miiiAAANkiiikk...1|...|2121tmttmmNtmNNmmNmNmNN1210)1()1(...2114应用——错位排列计数]!1)1(...!21!111[!!0)1(...)!2(2)!1(1!!0)!(...)!2()!1(!21nnnnnnnnnDNknNnNnNnNnnnnk错位排列数记作Dn,设S为{1,2,…,n}的排列的集合，Pi是其中i在第i位的性质，i=1,2,…,n.15错位排列实例例18个字母A,B,C,D,E,F,G,H的全排列中，使得4个字母不在原来位置的排列数.6309)4,8(91412)241612111(24)!41!31!21!111(!44CND解：4个字母的错排数为16错位排列的性质0,0))(1(.10112DDDDnDnnn021...210!.2DnnDnDnDnnnnn3.Dn为偶数当且仅当n为奇数.4.当n充分大时，Dn/n!趋向于1/e.证明思路：1.使用组合分析，按照第1位是什么数分类计数.2.将n!个排列按照出现错位的个数分类计数3.归纳证明4.将Dn的值代入取极限17排列与布棋方案一个棋盘由大小相同的正方形方格构成，一个方格中允许放入一个棋子.在向棋盘布棋时，要求任何两个棋子既不能布在棋盘的同一行，也不能布在同一列上.排列i1i2…in表示:第一行的棋子放在第i1列第二行的棋子放在第i2列…第n行的棋子放在第in列步棋方案排列：251364⇕18排列与n个棋子在nn棋盘的布棋方案一一对应位置有限制的排列与有禁区的步棋方案一一对应布棋方案与棋盘多项式rk(C)表示k个棋子在棋盘C上的布棋方案数，则称nkkkxCrCR0)()(为棋盘多项式位置受限的排列：251364一般表示：i1i2…i6ijj,j=1,2,…,6⇕⇔19棋盘多项式的性质)()()()()()()()()()()()(210211CRCRCRCRCxRCRCrCrCrCrCrCrlikiikiklkikkCi：去掉某个给定方格所在的行和列之后剩余棋盘Cl：去掉某个给定方格之后剩余棋盘C1和C2表示两个分离的棋盘则不难证明：20简单棋盘多项式的结果21有禁区的排列限制某些数字不能出现在某些位置的排列，对应于有禁区的放棋方案.有下述计数定理.定理9.2C是nn的具有给定禁区的棋盘，禁区对应于{1,2,…,n}的元素在排列中不允许出现的位置，则这种有禁区的排列数为中ri是i个棋子布置到禁区的方案数使用条件：棋盘为nn,小禁区nnrnrnrn)1(...)!2()!1(!2122定理证明证不考虑禁区限制，不带编号棋子的布棋方案数:n!，考虑棋子编号，布棋方案数:n!n!Pj:第j个棋子落入禁区的性质，j=1,2,…,n给定的1个棋子落入禁区的方案数:N1=r1(n1)!(n1)!给定的2个棋子落入禁区的方案数:N2=2!r2(n2)!(n2)!…给定的k个棋子落入禁区的方案数:Nk=k!rk(nk)!(nk)!…n个棋子落入禁区的方案数：Nn=n!rn0!0!23定理证明（续）nnkknnkknnkkrknrnrnrnNnrknnrnnrnnrnnrnnnknknrkknnnrnnnrnnnN)1(...)!()1(...)!2()!1(!!)1(...)!(!)1(...)!2(!)!1(!!!!)1(...)!()!(!)1(...)!2()!2(!22)!1()!1(1!!2121210带编号的棋子不落入禁区的方案数:N0不带编号的棋子不落入禁区的方案数:N两者关系：N0=N·n!24应用实例——工作分配3241061xxxN=4!63!+102–4=24–36+20–4=4解：禁区的棋盘多项式为根据定理9.2得例2G,L,W,Y4位工作人员，A,B,C,D为4项工作.每个人不能从事的工作如图中棋盘的禁区所示.问有多少种分配方案？25应用实例——错排问题)!1)1(...!31!21!111(!!!1)1(...!!31!!21!!!0)1(...)!2(2)!1(1!nnnnnnnnnnnnnnnDnnnn例3错位排列的禁区是主对角线上的所有方格关于禁区的棋盘多项式如下：