组合数学课件--棋盘多项式和有限制条件的排列.ppt

第3章 容斥原理与鸽巢原理3.1 De Morgan定理 13.2 容斥原理 13.3 容斥原理举例 13.4 棋盘多项式与有限制的排列 23.5 有禁区的排列 23.6 广义的容斥原理 33.7 广义容斥原理的应用 32.8 第二类Stirling数的展开式 12.9 欧拉函数(n) 12.10 n对夫妻问题 3*2.11 Mobius反演定理 ×2.12 鸽巢原理 42.13 鸽巢原理举例 42.14 鸽巢原理的推广 4*2.15 Ramsey数 ×13.4 棋盘多项式和有限制条件的排列一、有限制的排列对有重复的排列或无重复的排列，可以对一 个或多个元素的出现次数进行限制，也可以对某 些元素出现的位置进行限制，这两种情况统称为 有限制条件的排列。

1、解决这些问题的工具有：(1)、指数型母函数：(3)、递推关系：(2)、容斥原理：23.4 棋盘多项式和有限制条件的排列(1)指数型母函数主要解决限制元素出现次数的排列 问题例1 求1,3,5,7,9这5个数字组成的n位数 个数，要求其中3出现的次数为偶数，其它 数字出现的次数无限制 33.4 棋盘多项式和有限制条件的排列(2)、容斥原理：既可解决限制元素出现次数的问题，也能 解决元素出现位置的问题典型特征是：问题能够化为集合问题：例2 求a,b,c,d,e,f这6个字母的全 排列中不允许出现ab和de图像的排列数43.4 棋盘多项式和有限制条件的排列(3)递推关系既可解决限制元素出现次数的问题，也能解 决元素出现位置的问题典型特征是：写出递推关系53.4 棋盘多项式和有限制条件的排列(4)棋盘多项式解决无重复排列元素出现位置的问题例3:甲乙丙丁4个人,有4项工作1,2,3,4,甲 干不了1,2,3号工作,乙干不了2,3,4号工作,丙干 不了1、4号工作,丁干不了1,2,4号工作,求满足 各人工作要求的方案数6n个不同元素的某一排列可以看做是n个 相同的棋子在n×n的棋盘上的一种布局。

3.2 棋盘多项式和有限条件的排列41352512341、棋盘多项式的由来7x xxx x棋盘的每一个布局每行每列有且有一个棋子；3.4 棋盘多项式和有限条件的排列类似于象棋中的车无对攻原则8n个不同元素取r个的排列可以看做 是n个相同的棋子在r×n的棋盘上的一种 布局，例如:1,2,3,4,5中取3个的排列3.2 棋盘多项式和有限条件的排列4355129x xxx x令rk(c)表示k只棋子布到棋盘C的不同的方案 数，规则是当一只棋子布到棋盘的某一格时，则 这个格子所在的行和列上的其他格子不再允许布 上别的棋子3.4 棋盘多项式和有限条件的排列103.4 棋盘多项式和有限条件的排列例3:甲乙丙丁4个人住店,有4个房间 1,2,3,4,甲不住1,2,3号房间,乙不住2,3,4房间, 丙不住1、4号房间,丁不住1,2,4号房间,求满足 要求的方案数1 2 3 4甲 乙 丙 丁113.4 棋盘多项式和有限条件的排列例4:甲乙丙丁4个人住店,有5个房间1,2,3, 4,5,甲不住1,2,3号房间,乙不住2,3,4房间,丙不 住1、4号房间,丁不住1,2,4号房间,求满足要求 的方案数。

1 2 3 4 5甲 乙 丙 丁12可以把棋盘C推广到任意形状，例如：3.4 棋盘多项式和有限条件的排列13r1( )r1( )r2( )r2( )令rk(c)表示k只棋子布到棋盘C的不同的 方案数，规则是当一只棋子布到棋盘的某一 格时，则这个格子所在的行和列上的其他格 子不再允许布上别的棋子3.4 棋盘多项式和有限条件的排列=1r1( ) =2=0=2=1***14定义：设C为一棋盘，称： 为棋盘C的棋盘多项式3.4 棋盘多项式和有限条件的排列r2( )r1( ) =2=0R( ) =1+2x2、棋盘多项式的定义***求棋盘 的多项式15设C(I)是棋盘C的某一指定格子所在的行与列 都去掉后所得的棋盘；棋盘CC(I)C(e)C(e)是仅去掉该格子后的棋盘3.4 棋盘多项式和有限条件的排列3、棋盘多项式的化简16公式1、rk(C)=rk－1(C(I))＋rk(C(e))3.4 棋盘多项式和有限条件的排列棋盘CC(I)C(e)r2(C)= 6r1(C(i))= 2r2(C(e))= 4例如:17公式1、rk(C)=rk－1(C(I))＋rk(C(e))就某一格子而言，无非两种可能，一种是 对该格子布子，另一种则是不布子，所有的布局 依此可分成两类：1、右端第一项rk－1(C(I))表示对某格下了一个 棋子后，剩下k-1个棋子布到C(I)棋盘的方案数；2、右端第二项rk(C(e))表示某格子不布棋子， 则k个棋子布到棋盘C(e)上的方案数。

证明：3.4 棋盘多项式和有限条件的排列18规定 r0(C)=1，包括r0( )=13.4 棋盘多项式和有限条件的排列公式1、rk(C)=rk－1(C(I))＋rk(C(e))r0( )+r1( )=r1( )r1( )= r0( ) + r1( )193.4 棋盘多项式和有限条件的排列公式2、棋盘CC(I)C(e)R(C) =R(C(i)) =R(C(e)) =1+ 5x+6x2+2x31+ 2x+x21+ 4x+4x2+x320证明：3.4 棋盘多项式和有限条件的排列公式2、21R( )利用公式R( )=R( )=1+ x；xR( )+ R( )=x+(1+x)=1+2x；= x R( ) + R( )=x(1+x)+1+x=1+2x+x23.4 棋盘多项式和有限条件的排列化简棋盘多项式22R( ) = x R( ) +=x+1+2x+x2=1+3x+x23.4 棋盘多项式和有限条件的排列R( )23R( )= x R( ) +=x+(1+x)(1+2x)=1+4x+2x2。

3.4 棋盘多项式和有限条件的排列R( )24如果C由相互分离的C1，C2组成，相互分 离指的是同行或同列中没有同时属于C1和C2的 格子则有：证明：因为C1,C2分离，因此在C1上布子与C2上 布子互不影响;在C上布k个棋子可分为C1上布i个，C2上布k -i个,方案数是C1C2C1C23.4 棋盘多项式和有限条件的排列25在C上布k个棋子可分为C1上布i个，C2上布k -i个,方案数是3.4 棋盘多项式和有限条件的排列26例：= x(1+ x)2 +(1+2x)2= xR( )+R( ) R ( )=1+ 5x +6x2 + x33.4 棋盘多项式和有限条件的排列27例：=x(1+x)(1+2x)+(1+2x)(1+3x+x2)= xR( ) + R( )= 1+6x +10 x2 +4x3R( )3.4 棋盘多项式和有限条件的排列283.4 棋盘多项式和有限条件的排列例4:甲乙丙丁4个人住店,有4个房间 1,2,3,4,甲不住1,2,3号房间,乙不住2,3,4房间, 丙不住1、4号房间,丁不住1,2,4号房间,求满足 要求的方案数。

甲 乙 丙 丁1 2 3 44、棋盘多项式的应用293.4 棋盘多项式和有限条件的排列R(C)=(1+x)(1+x)(1+3x+x2) =1+5x+8x2+5x3+x4甲 乙 丙 丁1 2 3 430例3.5 一婚姻介绍所，登记有5名男性A，B， C，D，E和4名女性1，2，3，4，经了解：1不能与 B,C,D,E，2不能与A,D,E,3不能与A,B,C，4不能与 A,B,C,D求可能婚配的方案数解：A B C D E1 2 3 43.4 棋盘多项式和有限条件的排列31解：A B C D E1 2 3 43.4 棋盘多项式和有限条件的排列R(C)=(1+x)(1+2x)(1+3x+x2) =1+6x+12x2+9x3+2x4*** 32例6:设对于1,2,3,4的排列P=P1P2P3P4， 规定P1≠3，P２≠1，P３≠2，P4≠43.5 有禁区的排列P1 P2 P3 P433定理3.3 有禁区的排列数为n!-r1(n-1)!+r2(n-2)!-…+(-1)nrn 其中ri是有i个棋子布置到禁区部分的方案数。

证明：设Ai为第i个棋子布入禁区，其他棋子任意布 的方案集的集合，i =1 , 2 , 3, …,n3.5 有禁区的排列34布n个棋子无一落入禁区的方案数应为：两个棋子落入禁区的方案数设为r2,而其余n- 2个棋子为无限制条件的排列，方案数是(n-2)!3.5 有禁区的排列35例3.7 有G,L,W,Y4位工作人员，A,B,C,D为4 项任务，但G不能从事任务B;L不能从事B，C两项任 务；W不能做C,D工作；Y不能从事任务D若要求每 人从事各自力所能及的一项工作，问有多少种不同 方案？A B C DGLWY解：3.5 有禁区的排列36按照定理3.3，相当于r1=6,r2=10,r3=4,代入公式：=x(1+x)(1+2x)+(1+2x)(1+3x+x2)= xR( ) + R( )= 1+6x +10 x2 +4x3R( )3.5 有禁区的排列37例3.8 错排问题···对角线棋盘的棋盘多 项式为：将错排问题看做是有 禁区的排列，可看作禁区 是在对角线上的方格 xx x xx3.5 有禁区的排列383.2 棋盘多项式和有限条件的排列因此错排的方案数为：*** 39第3章 容斥原理与鸽巢原理3.1 De Morgan定理 13.2 容斥原理 13.3 容斥原理举例 13.4 棋盘多项式与有限制的排列 23.5 有禁区的排列 23.6 广义的容斥原理 33.7 广义容斥原理的应用 32.8 第二类Stirling数的展开式 12.9 欧拉函数(n) 12.10 n对夫妻问题 3*2.11 Mobius反演定理 ×2.12 鸽巢原理 42.13 鸽巢原理举例 42.14 鸽巢原理的推广 4*2.15 Ramsey数 ×40。