棋盘多项式PPT课件

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