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