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