容斥原理 若干应用 09011203王瑶 09011204张梦微 09011206张雯露 2019/1/11.

Presentation on theme: "容斥原理 若干应用 09011203王瑶 09011204张梦微 09011206张雯露 2019/1/11."— Presentation transcript:

1 容斥原理 若干应用 王瑶 张梦微 张雯露 2019/1/11

2 1、欧拉公式 2、棋盘多项式 3、色多项式 2019/1/11

3 欧拉公式 2019/1/11

4 用容斥原理求欧拉函数 欧拉函数 是求小于n且与n互素的数的个数。 封面页 若n分解为素数的乘积 设1到n的n个数中为 倍数的集合为 则有
（设计好之后可以删掉这个文本框哦） 用容斥原理求欧拉函数 欧拉函数 是求小于n且与n互素的数的个数。 若n分解为素数的乘积 设1到n的n个数中为 倍数的集合为 则有 。。。。。。 2019/1/11

5 2019/1/11

6 封面页 （设计好之后可以删掉这个文本框哦） 即比60小且与60无公因子的数有16个：7，11，13，17。19。23，29，31，37，41，43，47，49，53，59，此外尚有一个1。 2019/1/11

7 封面页 （设计好之后可以删掉这个文本框哦） 例.求不超过120的素数个数。 解：因 ，故不超过120的合数必然是2、3、5、7的倍数，而且不超过120的合数的因子不可能都超过11。 设 为不超过120的数 的倍数集， =2，3，5，7。 2019/1/11

8 2019/1/11

9 2019/1/11

10 2019/1/11

11 注意：27并非就是不超过120的素数个数，因为这里排除了2，3，5，7这四个数，又包含了1这个非素数。2，3，5，7本身是素数。故所求的不超过120的素数个数为：27+4-1=30。
2019/1/11

12 棋盘多项式 2019/1/11

13 n 个不同元素的一个全排列可看做n个相同的棋子在n×n 的棋盘上的一个布局。布局满足同一行（列）中有且仅有一个棋子
2.1 棋盘多项式（ 特殊的禁位问题） n 个不同元素的一个全排列可看做n个相同的棋子在n×n 的棋盘上的一个布局。布局满足同一行（列）中有且仅有一个棋子 x x 排列41352对应于如图所示的布局。 x x x 2019/1/11

14 可以把棋盘的形状推广到任意形状： 布子规定同上 令rk (C)表示k个棋子布到棋盘C上的方案数。 2019/1/11

15 r1( )=1 r1( )=2 r1( )=2 r2( )=0 r2( )=1 2019/1/11

16 rk(C)=rk-1(Ci)＋rk(Ce)
规定 r0(C)=1，包括C=Ф时。 设Ci是棋盘C的某一指定格子所在的行与列都去掉后所得的棋盘；Ce是仅去掉该格子后的棋盘。 在上面定义下，显然有　　 rk(C)=rk-1(Ci)＋rk(Ce) 2019/1/11

17 R(C) =∑ rk(C) xk 定义1 设C为一棋盘，称R(C)=∑ rk (C) x k 为C的棋盘多项式。
定义1 设C为一棋盘，称R(C)=∑ rk (C) x k 为C的棋盘多项式。 k=0 ∞ 　　R(C) =∑ rk(C) xk = 1+ ∑ [rk-1(Ci)+ rk(Ce)]xk = x∑ rk(Ci)xk + ∑ rk(Ce)xk　　　　　　 = xR(Ci) + R(C e) ∞ k=0 k=1 设Ci是棋盘C的某一指定格子所在的行与列都去掉后所得的棋盘；Ce是仅去掉该格子后的棋盘。 2019/1/11

18 R( )= xR( )+ R( )= x+ (1+ x)=1+2x；
例如： R( )=1+ x； R( )= xR( )+ R( )= x+ (1+ x)=1+2x； R( )= x R( ) + R( ) = x(1 + x )+1 + x =1+ 2x +x2 2019/1/11

19 R(C) = ∑ (∑ ri (C1) rk-i (C2) ) xk = (∑ ri (C1) xi)(∑ rj (C2) xj )
如果C由相互分离的C1，C2组成，即C1的任一格子所在的行和列中都没有C2的格子。则有： i=0 k rk(C) =∑ ri (C1) rk-i (C2) R(C) = ∑ (∑ ri (C1) rk-i (C2) ) xk = (∑ ri (C1) xi)(∑ rj (C2) xj ) j=0 n k i=0 k=0 ∴ R(C) = R(C1) R(C2) 2019/1/11

20 * = x(1+ x)2 +(1+2x)2 =1+ 5x +6x2 + x3 例: R ( ) = xR( )+R( )
R(C) = xR(Ci) + R(C e) （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 * 2019/1/11

21 3 色多项式 2019/1/11

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

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

24 例 图G如图所示，现用x 种颜色涂染G的顶点，求
例 图G如图所示，现用x 种颜色涂染G的顶点，求 2019/1/11

25 c c 2019/1/11