最新棋盘多项式ppt课件.ppt

《最新棋盘多项式ppt课件.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、进入夏天，少不了一个热字当头，电扇空调陆续登场，每逢此时，总会想起那一把蒲扇。蒲扇，是记忆中的农村，夏季经常用的一件物品。　　记忆中的故乡，每逢进入夏天，集市上最常见的便是蒲扇、凉席，不论男女老少，个个手持一把，忽闪忽闪个不停，嘴里叨叨着“怎么这么热”，于是三五成群，聚在大树下，或站着，或随即坐在石头上，手持那把扇子，边唠嗑边乘凉。孩子们却在周围跑跑跳跳，热得满头大汗，不时听到“强子，别跑了，快来我给你扇扇”。孩子们才不听这一套，跑个没完，直到累气喘吁吁，这才一跑一踮地围过了，这时母亲总是，好似生气的样子，边扇边训，“你看热的，跑什么？”此时这把蒲扇，是那么

2、凉快，那么的温馨幸福，有母亲的味道！　　蒲扇是中国传统工艺品，在我国已有三千年多年的历史。取材于棕榈树，制作简单，方便携带，且蒲扇的表面光滑，因而，古人常会在上面作画。古有棕扇、葵扇、蒲扇、蕉扇诸名，实即今日的蒲扇，江浙称之为芭蕉扇。六七十年代，人们最常用的就是这种，似圆非圆，轻巧又便宜的蒲扇。　　蒲扇流传至今，我的记忆中，它跨越了半个世纪，也走过了我们的半个人生的轨迹，携带着特有的念想，一年年，一天天，流向长长的时间隧道，袅棋盘多项式1、欧拉公式2、棋盘多项式3、色多项式2021/9/16欧拉公式2021/9/16封面页（设计好之后可以删掉这个文本框哦）例

3、.求不超过120的素数个数。解：因，故不超过120的合数必然是2、3、5、7的倍数，而且不超过120的合数的因子不可能都超过11。设为不超过120的数的倍数集，=2，3，5，7。2021/9/162021/9/162021/9/162021/9/16注意：27并非就是不超过120的素数个数，因为这里排除了2，3，5，7这四个数，又包含了1这个非素数。2，3，5，7本身是素数。故所求的不超过120的素数个数为：27+4-1=30。2021/9/16棋盘多项式2021/9/162.1棋盘多项式（特殊的禁位问题）xxxxxn个不同元素的一个全排列可看做n个相同的棋

4、子在n×n的棋盘上的一个布局。布局满足同一行（列）中有且仅有一个棋子排列41352对应于如图所示的布局。2021/9/16可以把棋盘的形状推广到任意形状：布子规定同上令rk(C)表示k个棋子布到棋盘C上的方案数。2021/9/16r2()=0r1()=2r2()=1r1()=1r1()=22021/9/16规定r0(C)=1，包括C=Ф时。设Ci是棋盘C的某一指定格子所在的行与列都去掉后所得的棋盘；Ce是仅去掉该格子后的棋盘。在上面定义下，显然有rk(C)=rk-1(Ci)＋rk(Ce)2021/9/16定义1设C为一棋盘，称R(C)=∑rk(C)xk为C的

5、棋盘多项式。k=0∞R(C)=∑rk(C)xk=1+∑[rk-1(Ci)+rk(Ce)]xk=x∑rk(Ci)xk+∑rk(Ce)xk=xR(Ci)+R(Ce)∞k=0∞k=1∞k=0∞k=0设Ci是棋盘C的某一指定格子所在的行与列都去掉后所得的棋盘；Ce是仅去掉该格子后的棋盘。2021/9/16例如：R()=1+x；R()=xR()+R()=x+(1+x)=1+2x；R()=xR()+R()=x(1+x)+1+x=1+2x+x22021/9/16如果C由相互分离的C1，C2组成，即C1的任一格子所在的行和列中都没有C2的格子。则有：i=0krk(C)=∑r

6、i(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)2021/9/16R(C)=xR(Ci)+R(Ce)（Ci是棋盘C的某一指定格子所在的行与列都去掉后所得的棋盘；Ce是仅去掉该格子后的棋盘）R(C)=R(C1)R(C2)（相互分离的C1、C2，即C1的任一格子所在的行和列中都没有C2的格子）可以把较复杂的棋盘逐步分解成相对比较简单的棋盘，从而得到其棋盘多项式。例:R()=xR()+R()=x(1+x)2+(1+2x)2=1+

7、5x+6x2+x3*2021/9/163色多项式2021/9/16Def1：用x种颜色对图G的顶点进行着色时，若图G的任意两个相邻顶点都分配到不同的颜色，则称此着色为图G的正常x顶点着色。Def2：图G的不同x着色的数目称为图G的色多项式，记为P(G,x)。利用容斥原理求色多项式设G是任意图，用x种颜色涂染G的顶点，对于每条边i，设ai是边i的端部顶点得到相同颜色的性质（

8、VG

9、=n

10、EG

11、=r）。2021/9/16证明：有色多项式的定义可知，我们所求的色多项式就是不具有性质的对象数量，再由容斥原理可得其中x种颜色涂染G的顶点的所有着色的集合记为A，

12、A

13、=

14、N=xn2021/9/16例图G如图所示，现用x种颜