棋盘多项式.ppt

容斥原理 若干应用09011203王瑶09011204张梦微09011206张雯露2024/5/21周二1-1、欧拉公式2、棋盘多项式3、色多项式2024/5/21 周二2-欧拉公式2024/5/21 周二3-封面页（设计好之后可以删掉这个文本框哦）欧拉函数 是求小于n且与n互素的数的个数。若n分解为素数的乘积设1到n的n个数中为 倍数的集合为则有。用容斥原理求欧拉函数用容斥原理求欧拉函数2024/5/21周二4-2024/5/21 周二5-封面页（设计好之后可以删掉这个文本框哦）即比即比60小且与小且与60无公因子的数有无公因子的数有16个：个：7，11，13，17。19。23，29，31，37，41，43，47，49，53，59，此外尚有一个，此外尚有一个1。2024/5/21周二6-封面页（设计好之后可以删掉这个文本框哦）例例.求不超求不超过120的素数个数。的素数个数。解：因 ，故不超过120的合数必然是2、3、5、7的倍数，而且不超过120的合数的因子不可能都超过11。设 为不超过120的数 的倍数集，=2，3，5，7。2024/5/21周二7-2024/5/21 周二8-2024/5/21 周二9-2024/5/21 周二10-注意：注意：27并非就是不超过120的素数个数，因为这里排除了2，3，5，7这四个数，又包含了1这个非素数。2，3，5，7本身是素数。故所求的不超过120的素数个数为：27+4-1=30。2024/5/21 周二11-棋盘多项式2024/5/21 周二12-2.1 棋棋盘多多项式式（特殊的禁位特殊的禁位问题）xxxxx n 个不同元素的一个全排列可看做n个相同的棋子在nn 的棋盘上的一个布局。布局满足同一行（列）中有且仅有一个棋子排列41352对应于如图所示的布局。2024/5/21 周二13-可以把棋盘的形状推广到任意形状：布子规定同上 令rk(C)表示k个棋子布到棋盘C上的方案数。2024/5/21 周二14-r2()=0r1()=2r2()=1r1()=1r1()=22024/5/21 周二15-规定 r0(C)=1，包括C=时。设Ci是棋盘C的某一指定格子所在的行与列都去掉后所得的棋盘；Ce是仅去掉该格子后的棋盘。在上面定义下，显然有rk(C)=rk-1(Ci)rk(Ce)2024/5/21 周二16-定定义1 设C为一棋盘，称R(C)=rk(C)x k为C的棋盘多项式。k=0R(C)=rk(C)xk =1+rk-1(Ci)+rk(Ce)xk =x rk(Ci)xk+rk(Ce)xk =xR(Ci)+R(C e)k=0k=1k=0k=0设Ci是棋是棋盘C的某一指定格子所在的行与列都去的某一指定格子所在的行与列都去掉后所得的棋掉后所得的棋盘；Ce是是仅去掉去掉该格子后的棋格子后的棋盘。2024/5/21 周二17-例如：R()=1+x；R()=xR()+R()=x+(1+x)=1+2x；R()=x R()+R()=x(1+x)+1+x =1+2x+x22024/5/21 周二18-如果C由相互分离的C1，C2组成，即C1的任一格子所在的行和列中都没有C2的格子。则有：i=0krk(C)=ri(C1)rk-i(C2)R(C)=(ri(C1)rk-i(C2)xk =(ri(C1)xi)(rj(C2)xj)j=0nnkni=0i=0k=0 R(C)=R(C1)R(C2)2024/5/21 周二19-R(C)=xR(Ci)+R(C e)（Ci是棋是棋盘C的某一指定格子所在的行与列都的某一指定格子所在的行与列都 去掉后所得的棋去掉后所得的棋盘；Ce是是仅去掉去掉该格子后的棋格子后的棋盘）R(C)=R(C1)R(C2)（相互分离的相互分离的C1、C2，即即C1的任一格子的任一格子 所在的行和列中都没有所在的行和列中都没有C2的格子的格子）可以把较复杂的棋盘逐步分解成相对比较简单的棋盘，从而得到其棋盘多项式。例例:R()=xR()+R()=x(1+x)2 +(1+2x)2 =1+5x+6x2+x3*2024/5/21 周二20-3色多项式2024/5/21 周二21-Def1：用x 种颜色对图G的顶点进行着色时，若图 G 的任意两个相邻顶点都分配到不同的颜色，则称此着色为图G的正常x顶点着色。Def2：图G的不同x 着色的数目称为图G的色多项式，记为 P(G,x)。利用容斥原理求色多项式设G是任意图，用x 种颜色涂染G的顶点，对于每条边i，设ai是边i 的端部顶点得到相同颜色的性质（|VG|=n|EG|=r）。2024/5/21 周二22-证明：有色多项式的定义可知，我们所求的色多项式就是不具有性质 的对象数量，再由容斥原理可得其中x 种颜色涂染 G 的顶点的所有着色的集合记为A，|A|=N=xn2024/5/21 周二23-例 图G如图所示，现用x 种颜色涂染G的顶点，求2024/5/21 周二24-cc2024/5/21 周二25-