容斥原理 若干应用.ppt

《容斥原理 若干应用.ppt》由会员上传分享，免费在线阅读，更多相关内容在PPT专区-天天文库。

1、容斥原理若干应用09011203王瑶09011204张梦微09011206张雯露2021/9/261、欧拉公式2、棋盘多项式3、色多项式2021/9/26欧拉公式2021/9/26封面页（设计好之后可以删掉这个文本框哦）欧拉函数是求小于n且与n互素的数的个数。若n分解为素数的乘积设1到n的n个数中为倍数的集合为则有。。。。。。用容斥原理求欧拉函数2021/9/262021/9/26封面页（设计好之后可以删掉这个文本框哦）即比60小且与60无公因子的数有16个：7，11，13，17。19。23，29，31，37，41，43，47，49，53，59，此外尚有一个1。2021/9/26封面页（设

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

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

4、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=02021/9/26设Ci是棋盘C的某一指定格子所在的行与列都去掉后所得的棋盘；Ce是仅去掉该格子后的棋盘。例如：R()=1+x；R()=xR()+R()=x+(1+x)=1+2x；2021/9/26R()=xR()+R()=x(1+x)+1+x=1+2x+x2如果C由相互分离的C1，C2组成，即C1的任一格子所在的行和列中都没有C2的格子。则有：i=0krk(C)=∑ri(C1)rk-i(C2)R(C)=∑(∑ri(C1)rk-i(

5、C2))xk=(∑ri(C1)xi)(∑rj(C2)xj)j=0nnkni=0i=0k=0∴R(C)=R(C1)R(C2)2021/9/26R(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+5x+6x2+x3*2021/9/263色多项式2021/9/26Def1：用x种颜色对图G的顶

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

7、VG

8、=n

9、EG

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

11、A

12、=N=xn2021/9/26例图G如图所示，现用x种颜色涂染G的顶点，求2021/9/262021/9/26cc