组合数学棋盘多项式和有限制条件的排列实用教案

《组合数学棋盘多项式和有限制条件的排列实用教案》由会员分享，可在线阅读，更多相关《组合数学棋盘多项式和有限制条件的排列实用教案（40页珍藏版）》请在装配图网上搜索。

1、会计学1组合数学组合数学(shxu)棋盘多项式和有限制条棋盘多项式和有限制条件的排列件的排列第一页，共40页。2 3.4 棋盘多项式和有限制条件棋盘多项式和有限制条件(tiojin)的排列的排列一、有限制一、有限制(xinzh)(xinzh)的排的排列列 对有重复的排列或无重复的排列，可以对一个或对有重复的排列或无重复的排列，可以对一个或多个元素的出现次数进行限制，也可以对某些元素出多个元素的出现次数进行限制，也可以对某些元素出现的位置进行限制，这两种情况现的位置进行限制，这两种情况(qngkung)(qngkung)统称为统称为有限制条件的排列。有限制条件的排列。1 1、解决这些问题的工具有

2、：、解决这些问题的工具有：(1)(1)、指数型母函数：、指数型母函数：(3)(3)、递推关系：、递推关系：(2)(2)、容斥原理：、容斥原理：第1页/共40页第二页，共40页。3 3.4 棋盘棋盘(qpn)多项式和有限制条件的多项式和有限制条件的排列排列(1)(1)指数指数(zhsh)(zhsh)型母型母函数函数 主要主要(zhyo)(zhyo)解决限制元素出现解决限制元素出现次数的排列问题次数的排列问题 例例1 求求1,3,5,7,9这这5个数字组成的个数字组成的n位数个位数个数，要求其中数，要求其中3出现的次数为偶数，其它数字出现的次数为偶数，其它数字出现的次数无限制。出现的次数无限制。

3、第2页/共40页第三页，共40页。4 3.4 棋盘多项式和有限制棋盘多项式和有限制(xinzh)条件的排条件的排列列(2)(2)、容斥原理、容斥原理(yunl)(yunl)： 既可解决限制元素既可解决限制元素(yun s)(yun s)出现次数的出现次数的问题，也能解决元素问题，也能解决元素(yun s)(yun s)出现位置的问出现位置的问题题 典型特征是：问题能够化为集合问题：典型特征是：问题能够化为集合问题：nA.AA21nAAA.21 例例2 2 求求a,b,c,d,e,fa,b,c,d,e,f这这6 6个字母的全排列个字母的全排列中不允许出现中不允许出现abab和和dede图像的排列

4、数。图像的排列数。第3页/共40页第四页，共40页。5 3.4 棋盘多项式和有限制条件棋盘多项式和有限制条件(tiojin)的的排列排列(3)(3)递推关系递推关系(gun x)(gun x) 既可解决限制元素既可解决限制元素(yun s)(yun s)出现次数的问题，也出现次数的问题，也能解决元素能解决元素(yun s)(yun s)出现位置的问题出现位置的问题 典型特征是：写出递推关系典型特征是：写出递推关系第4页/共40页第五页，共40页。6 3.4 棋盘棋盘(qpn)多项式和有限制条件的多项式和有限制条件的排列排列(4)(4)棋盘棋盘(qpn)(qpn)多项式多项式解决解决(jiju)

5、(jiju)无重复排列元素出现位无重复排列元素出现位置的问题置的问题 例例3:3:甲乙丙丁甲乙丙丁4 4个人个人, ,有有4 4项工作项工作1,2,3,4,1,2,3,4,甲干不甲干不了了1,2,31,2,3号工作号工作, ,乙干不了乙干不了2,3,42,3,4号工作号工作, ,丙干不了丙干不了1 1、4 4号工作号工作, ,丁干不了丁干不了1,2,41,2,4号工作号工作, ,求满足各人工求满足各人工作要求的方案数。作要求的方案数。第5页/共40页第六页，共40页。7 n n个不同元素的某一排列可以看做是个不同元素的某一排列可以看做是n n个相个相同的棋子在同的棋子在n nn n的棋盘的棋盘

6、(qpn)(qpn)上的一种布局上的一种布局。 3.2 棋盘多项式和有限棋盘多项式和有限(yuxin)条件的排条件的排列列41352512341 1、棋盘、棋盘(qpn)(qpn)多项式的由来多项式的由来第6页/共40页第七页，共40页。8xxxxx棋盘的每一个布局棋盘的每一个布局(bj)(bj)每行每列有且有一个每行每列有且有一个棋子；棋子； 3.4 棋盘棋盘(qpn)多项式和有限条件的排多项式和有限条件的排列列类似于象棋中的车无对攻类似于象棋中的车无对攻(du (du n)n)原则。原则。第7页/共40页第八页，共40页。9 n n个不同元素取个不同元素取r r个的排列可以看做是个的排列可

7、以看做是n n个相同个相同(xin tn)(xin tn)的棋子在的棋子在r rn n的棋盘的棋盘上的一种布局，上的一种布局， 例如例如:1,2,3,4,5:1,2,3,4,5中取中取3 3个的排列个的排列 3.2 棋盘多项式和有限棋盘多项式和有限(yuxin)条件条件的排列的排列435512第8页/共40页第九页，共40页。10 xxxxx 令令rk(c)rk(c)表示表示k k只棋子布到棋盘只棋子布到棋盘C C的不同的方的不同的方案数，规则是当一只棋子布到棋盘的某一格时，案数，规则是当一只棋子布到棋盘的某一格时，则这个格子所在则这个格子所在(suzi)(suzi)的行和列上的其他格子的行和

8、列上的其他格子不再允许布上别的棋子。不再允许布上别的棋子。 3.4 棋盘多项式和有限棋盘多项式和有限(yuxin)条件条件的排列的排列第9页/共40页第十页，共40页。11 3.4 棋盘多项式和有限条件棋盘多项式和有限条件(tiojin)的排的排列列 例例3:3:甲乙丙丁甲乙丙丁4 4个人住店个人住店, ,有有4 4个房间个房间(fngjin)1,2,3,4,(fngjin)1,2,3,4,甲不住甲不住1,2,31,2,3号房间号房间(fngjin),(fngjin),乙不住乙不住2,3,42,3,4房间房间(fngjin),(fngjin),丙不住丙不住1 1、4 4号房间号房间(fngji

9、n),(fngjin),丁不住丁不住1,2,41,2,4号房间号房间(fngjin),(fngjin),求满足要求的方案数。求满足要求的方案数。1 2 3 41 2 3 4甲甲乙乙丙丙丁丁第10页/共40页第十一页，共40页。12 3.4 棋盘多项式和有限条件棋盘多项式和有限条件(tiojin)的排的排列列 例例4:4:甲乙丙丁甲乙丙丁(ji y bn dn)4(ji y bn dn)4个人住个人住店店, ,有有5 5个房间个房间1,2,3,1,2,3,4,5,4,5,甲不住甲不住1,2,31,2,3号房间号房间, ,乙不住乙不住2,3,42,3,4房间房间, ,丙丙不住不住1 1、4 4号房

10、间号房间, ,丁不住丁不住1,2,41,2,4号房间号房间, ,求满足要求满足要求的方案数。求的方案数。1 2 3 4 51 2 3 4 5甲甲乙乙丙丙丁丁第11页/共40页第十二页，共40页。13可以把棋盘可以把棋盘C C推广到任意推广到任意(rny)(rny)形状，例如：形状，例如： 3.4 棋盘多项式和有限条件棋盘多项式和有限条件(tiojin)的排的排列列第12页/共40页第十三页，共40页。14r1( )r1( )r2( )r2( ) 令令rk(c)rk(c)表示表示(biosh)k(biosh)k只棋子布到棋盘只棋子布到棋盘C C的不同的方案数，规则是当一只棋子布到棋的不同的方案数

11、，规则是当一只棋子布到棋盘的某一格时，则这个格子所在的行和列上盘的某一格时，则这个格子所在的行和列上的其他格子不再允许布上别的棋子。的其他格子不再允许布上别的棋子。 3.4 棋盘多项式和有限棋盘多项式和有限(yuxin)条件的排条件的排列列=1r1( )=2=0=2=1*第13页/共40页第十四页，共40页。15 定义定义(dngy)(dngy)：设：设C C为一棋盘，称：为一棋盘，称：为棋盘为棋盘C C的棋盘多项式。的棋盘多项式。0)()(kkkxCrCR 3.4 棋盘多项式和有限棋盘多项式和有限(yuxin)条件的排条件的排列列r2( )r1( )=2=0R( )=1+2x2 2、棋盘、棋

12、盘(qpn)(qpn)多项式的定义多项式的定义*求棋盘求棋盘 的多项式的多项式第14页/共40页第十五页，共40页。16 设设C(I)C(I)是棋盘是棋盘C C的某一指定格子的某一指定格子(g zi)(g zi)所在的行与列都去掉后所得的棋盘；所在的行与列都去掉后所得的棋盘；棋盘棋盘C CC C(I)(I)C C(e)(e)C(e)C(e)是仅去掉是仅去掉(q dio)(q dio)该格子后的该格子后的棋盘。棋盘。 3.4 棋盘棋盘(qpn)多项式和有限条件的排多项式和有限条件的排列列3 3、棋盘多项式的化简、棋盘多项式的化简第15页/共40页第十六页，共40页。17公式公式(gngsh)1(

13、gngsh)1、rk(C)=rkrk(C)=rk1(C(I)1(C(I)rk(C(e)rk(C(e) 3.4 棋盘多项式和有限条件棋盘多项式和有限条件(tiojin)的的排列排列棋盘棋盘C CC C(I)(I)C C(e)(e)r2(C)=6r1(C(i)=2r2(C(e)=4例如例如(lr):(lr):第16页/共40页第十七页，共40页。18公式公式(gngsh)1(gngsh)1、rk(C)=rkrk(C)=rk1(C(I)1(C(I)rk(C(e)rk(C(e) 就某一格子而言，无非两种可能，一种是对该格子布子，另一种则是不布子，所有的布局就某一格子而言，无非两种可能，一种是对该格子布

14、子，另一种则是不布子，所有的布局(bj)(bj)依此可分成两类：依此可分成两类： 1 1、右端第一项、右端第一项rkrk1(C(I)1(C(I)表示表示(biosh)(biosh)对某格下了一个棋子后，剩下对某格下了一个棋子后，剩下k-1k-1个棋子布到个棋子布到C(I)C(I)棋盘的方案数；棋盘的方案数； 2 2、右端第二项、右端第二项rk(C C(e)(e)表示某格子不布棋子，则表示某格子不布棋子，则k个个棋子布到棋盘棋子布到棋盘C C(e)(e)上的方案数。上的方案数。证明：证明： 3.4 棋盘多项式和有限条件的排列棋盘多项式和有限条件的排列第17页/共40页第十八页，共40页。19规定

15、规定(gudng) r0(C)=1(gudng) r0(C)=1，包括，包括r0( r0( )=1)=1。 3.4 棋盘多项式和有限棋盘多项式和有限(yuxin)条件的排条件的排列列公式公式(gngsh)1(gngsh)1、rk(C)=rkrk(C)=rk1(C(I)1(C(I)rk(C(e)rk(C(e)r0( )+r1( )=r1( )r1( )= r0( ) +r1( )第18页/共40页第十九页，共40页。20)()()()()(eiCRCxRCR 3.4 棋盘多项式和有限条件棋盘多项式和有限条件(tiojin)的排的排列列公式公式(gngsh(gngsh)2)2、棋盘棋盘C CC C

16、(I)(I)C C(e)(e)R(C) =R(C(i) =R(C(e) =1+ 5x+6x2+2x31+ 2x+x21+ 4x+4x2+x3第19页/共40页第二十页，共40页。210)()(kkkxCrCR)()()()()(eiCRCxRCR1)(1kkkxCr证明证明(zhngmng)(zhngmng)：1)()(1)()(1kkekikxCrCr1)(11)(1)(1)(kkekkkikxCrxCrx0)(0)()()(kkekhhihxCrxCrx)()()()(eiCRCxR1)(1)(1)()(1kkekkkikxCrxCr 3.4 棋盘多项式和有限棋盘多项式和有限(yuxin)

17、条件的条件的排列排列公式公式(gngsh(gngsh)2)2、第20页/共40页第二十一页，共40页。22R( )利用利用(lyng)(lyng)公式公式R( )=R( )=1+ x；xR( )+ R( )=x+(1+x)=1+2x=x+(1+x)=1+2x；= x R( ) + R( )=x(1+x)+1+x=x(1+x)+1+x=1+2x+x=1+2x+x2 2。 3.4 棋盘多项式和有限棋盘多项式和有限(yuxin)条件的排条件的排列列)()()()()(eiCRCxRCR化简棋盘化简棋盘(qpn)(qpn)多项式多项式第21页/共40页第二十二页，共40页。23R( )= x R( )

18、 += =x+1+2x+xx+1+2x+x2 2=1+=1+3 3x+xx+x2 2。 3.4 棋盘多项式和有限条件棋盘多项式和有限条件(tiojin)的排的排列列R( )第22页/共40页第二十三页，共40页。24R( )= x R( ) += =x+(1+x)(1+2x)x+(1+x)(1+2x)= =1+41+4x+x+2 2x x2 2。 3.4 棋盘棋盘(qpn)多项式和有限条件的多项式和有限条件的排列排列R( )第23页/共40页第二十四页，共40页。25 如果如果C由相互分离的由相互分离的C1，C2组成，相互分离指组成，相互分离指的是同行或同列中没有同时的是同行或同列中没有同时(

19、tngsh)属于属于C1和和C2的的格子。则有：格子。则有：0)()(kkkxCrCR)()()(21CRCRCR证明证明(zhngmn(zhngmng)g)： 因为因为C1,C2分离分离(fnl)，因此在，因此在C1上布子上布子与与C2上布子互不影响上布子互不影响; 在在C上布上布k个棋子可分为个棋子可分为C1上布上布i个，个，C2上布上布k-i个个,方案数是方案数是)()(21CrCrikiC C1 1C C2 2C C1 1C C2 2 3.4 棋盘多项式和有限条件的排列棋盘多项式和有限条件的排列第24页/共40页第二十五页，共40页。26 0021) )()()(kkkiikixCrC

20、rCRjijjiixCrxCr0021)()()()(21CRCR 在在C上布上布k个棋子可分为个棋子可分为(fn wi)C1上布上布i个，个，C2上布上布k-i个个,方案数是方案数是)()(21CrCriki0)()(kkkxCrCR 3.4 棋盘多项式和有限条件棋盘多项式和有限条件(tiojin)的排的排列列第25页/共40页第二十六页，共40页。27例：例：= x(1+ x)2 +(1+2x)2= xR( )+R( ) R ( )=1+ 5x +6x2 + x3 3.4 棋盘多项式和有限棋盘多项式和有限(yuxin)条件的排条件的排列列第26页/共40页第二十七页，共40页。28例：例：

21、=x(1+x)(1+2x)+(1+2x)(1+3x+x2)= xR( ) + R( )= 1+6x +10 x2 +4x3R( ) 3.4 棋盘棋盘(qpn)多项式和有限条件的多项式和有限条件的排列排列第27页/共40页第二十八页，共40页。29 3.4 棋盘多项式和有限条件棋盘多项式和有限条件(tiojin)的排列的排列 例例4:4:甲乙丙丁甲乙丙丁4 4个人住店个人住店, ,有有4 4个房间个房间1,2,3,4,1,2,3,4,甲不住甲不住(b zh)1,2,3(b zh)1,2,3号房间号房间, ,乙不住乙不住(b zh)2,3,4(b zh)2,3,4房间房间, ,丙不住丙不住(b z

22、h)1(b zh)1、4 4号房号房间间, ,丁不住丁不住(b zh)1,2,4(b zh)1,2,4号房间号房间, ,求满足要求的求满足要求的方案数。方案数。甲甲 乙乙 丙丙 丁丁1 12 23 34 44 4、棋盘、棋盘(qpn)(qpn)多项式的多项式的应用应用第28页/共40页第二十九页，共40页。30 3.4 棋盘多项式和有限棋盘多项式和有限(yuxin)条件的条件的排列排列R(C)R(C)=(1+x)(1+x)(1+3x+x=(1+x)(1+x)(1+3x+x2 2) )=1+5x+8x=1+5x+8x2 2+5x+5x3 3+x+x4 4甲甲 乙乙 丙丙 丁丁1 12 23 34

23、 4第29页/共40页第三十页，共40页。31 例例3.5 3.5 一婚姻介绍所，登记一婚姻介绍所，登记(dngj)(dngj)有有5 5名男性名男性A A，B B，C C，D D，E E和和4 4名女性名女性1 1，2 2，3 3，4 4，经了解：，经了解：1 1不能与不能与B,C,D,EB,C,D,E，2 2不能与不能与A,D,E,3A,D,E,3不能与不能与A,B,CA,B,C，4 4不能与不能与A,B,C,DA,B,C,D求可能婚配的方案数。求可能婚配的方案数。 解：解： A B C D E1234 3.4 棋盘多项式和有限棋盘多项式和有限(yuxin)条件条件的排列的排列第30页/共

24、40页第三十一页，共40页。32 解：解： A B C D E1234 3.4 棋盘棋盘(qpn)多项式和有限条件的多项式和有限条件的排列排列R(C)R(C)=(1+x)(1+2x)(1+3x+x=(1+x)(1+2x)(1+3x+x2 2) )=1+6x+12x=1+6x+12x2 2+9x+9x3 3+2x+2x4 4*第31页/共40页第三十二页，共40页。33 例例6:6:设对于设对于(duy)1,2,3,4(duy)1,2,3,4的排列的排列P=P1P2P3P4P=P1P2P3P4，规定，规定P13P13，P P11，P P22，P44P44。 3.5 有禁区有禁区(jnq)的的排列

25、排列P1P2P3P4第32页/共40页第三十三页，共40页。34 定理定理3.3 3.3 有禁区的排列数为有禁区的排列数为 n!-r1(n-1)!+r2(n-2)!-+(-1)nrn n!-r1(n-1)!+r2(n-2)!-+(-1)nrn 其中其中(qzhng)ri(qzhng)ri是有是有i i个棋子布置到禁区部分的方个棋子布置到禁区部分的方案数。案数。 证明证明(zhngm(zhngmng)ng)： 设设Ai为第为第i个棋子布入禁区，其他个棋子布入禁区，其他(qt)棋子任意布的棋子任意布的方案集的集合，方案集的集合，i =1 , 2 , 3, ,n。)!1(11nrAnii 3.5 有

26、禁区的排列有禁区的排列第33页/共40页第三十四页，共40页。35布布n n个棋子个棋子(qz)(qz)无一落入禁区的方案数应为无一落入禁区的方案数应为： 两个棋子落入禁区的方案数设为两个棋子落入禁区的方案数设为r2,而其余而其余(qy)n-2个棋子为无限制条件的排列，方案数是个棋子为无限制条件的排列，方案数是(n-2)!。)!2(21nrAAniijji 3.5 有禁区有禁区(jnq)的的排列排列nAAA. 21nnniijjhhjiniijjiniiAAAAAAAAAN.)1( . 21111nnr.)!(nr)(nrn!) 1(2!121第34页/共40页第三十五页，共40页。36 例例

27、3.7 3.7 有有G,L,W,Y4G,L,W,Y4位工作人员，位工作人员，A,B,C,DA,B,C,D为为4 4项项任务，但任务，但G G不能从事任务不能从事任务B;LB;L不能从事不能从事B B，C C两项任务；两项任务；W W不能做不能做C,DC,D工作；工作；Y Y不能从事任务不能从事任务D D。若要求。若要求(yoqi)(yoqi)每人从事各自力所能及的一项工作，问有多少种不同每人从事各自力所能及的一项工作，问有多少种不同方案？方案？A B C D G L W Y 解：解： 3.5 有禁区有禁区(jnq)的的排列排列第35页/共40页第三十六页，共40页。37 按照定理按照定理(dn

28、gl)3.3(dngl)3.3，相当于，相当于r1=6,r2=10,r3=4,r1=6,r2=10,r3=4,代入代入公式：公式：nr.)!(nr)(nrn!2!1N21442036244! 210! 36! 4=x(1+x)(1+2x)+(1+2x)(1+3x+x2)= xR( ) + R( )= 1+6x +10 x2 +4x3R( ) 3.5 有禁区有禁区(jnq)的排列的排列第36页/共40页第三十七页，共40页。38 例例3.8 3.8 错排问题错排问题(wnt)(wnt) 对角线棋盘对角线棋盘(qpn)(qpn)的棋盘的棋盘(qpn)(qpn)多多项式为：项式为：nxCR)1()(

29、 将错排问题看做是有禁将错排问题看做是有禁区的排列，可看作区的排列，可看作(kn zu)(kn zu)禁区是在对角线上的方格。禁区是在对角线上的方格。 xxxxxnxnnCxnCxnC),(.)2,()1 ,(12 3.5 有禁区的排列有禁区的排列第37页/共40页第三十八页，共40页。39 3.2 棋盘棋盘(qpn)多项式和有限条件的排列多项式和有限条件的排列),(.),.2 ,(),1 ,(21nnCrnCrnCrn因此因此(ync)(ync)错排的方案错排的方案数为：数为：),() 1.()!2)(2 ,()!1)(1 ,(nnCnnCnnCn!nnnxnnCxnCxnCxCR),(.)

30、2 ,() 1 ,(1 )1 ()(2)!1)1(.!31!21! 111( !nnn*第38页/共40页第三十九页，共40页。40第第3章章 容斥原理容斥原理(yunl)与鸽与鸽巢原理巢原理(yunl) 3.1 De Morgan 3.1 De Morgan定理定理 1 1 3.2 3.2 容斥原理容斥原理 1 1 3.3 3.3 容斥原理举例容斥原理举例 1 1 3.4 3.4 棋盘多项式与有限制的排列棋盘多项式与有限制的排列 2 2 3.5 3.5 有禁区的排列有禁区的排列 2 2 3.6 3.6 广义的容斥原理广义的容斥原理 3 3 3.7 3.7 广义容斥原理的应用广义容斥原理的应用 3 3 2.8 2.8 第二类第二类StirlingStirling数的展开式数的展开式 1 1 2.9 2.9 欧拉函数欧拉函数(n) 1(n) 1 2.10 n 2.10 n对夫妻问题对夫妻问题(wnt) (wnt) 3 3 * *2.11 Mobius2.11 Mobius反演定理反演定理 2.12 2.12 鸽巢原理鸽巢原理 4 4 2.13 2.13 鸽巢原理举例鸽巢原理举例 4 4 2.14 2.14 鸽巢原理的推广鸽巢原理的推广 4 4 * *2.15 Ramsey2.15 Ramsey数数 第39页/共40页第四十页，共40页。