請在此處填寫作品信息（此頁非設(shè)計模板）

1、,容斥原理 若干應(yīng)用,09011203王瑤09011204張夢微09011206張雯露,2024/3/10,,,1、歐拉公式2、棋盤多項式3、色多項式,2024/3/10,,歐拉公式,2024/3/10,封面頁 （設(shè)計好之后可以刪掉這個文本框哦）,,歐拉函數(shù) 是求小于n且與n互素的數(shù)的個數(shù)。,若n分解為素數(shù)的乘積設(shè)1到n的n個數(shù)中為 倍數(shù)的集合為則有,,,。。。。。。,用容斥原

2、理求歐拉函數(shù),2024/3/10,,2024/3/10,封面頁 （設(shè)計好之后可以刪掉這個文本框哦）,,即比60小且與60無公因子的數(shù)有16個：7，11，13，17。19。23，29，31，37，41，43，47，49，53，59，此外尚有一個1。,2024/3/10,封面頁 （設(shè)計好之后可以刪掉這個文本框哦）,,例.求不超過120的素數(shù)個數(shù)。,解：因 ，故不超過120的合數(shù)必然是2、3、5、7

3、的倍數(shù)，而且不超過120的合數(shù)的因子不可能都超過11。,設(shè) 為不超過120的數(shù) 的倍數(shù)集， =2，3，5，7。,2024/3/10,,2024/3/10,,2024/3/10,,2024/3/10,,注意：27并非就是不超過120的素數(shù)個數(shù)，因為這里排除了2，3，5，7這四個數(shù)，又包含了1這個非素數(shù)。2，3，5，7本身是素數(shù)。故所求的不超過120的素數(shù)個數(shù)為：27+4-1=30。,2024/3/10,,,棋盤多項式,

4、2024/3/10,,2.1 棋盤多項式（ 特殊的禁位問題）,x,x,x,x,x,n 個不同元素的一個全排列可看做n個相同的棋子在n×n 的棋盤上的一個布局。布局滿足同一行（列）中有且僅有一個棋子,排列41352對應(yīng)于如圖所示的布局。,2024/3/10,,可以把棋盤的形狀推廣到任意形狀：,布子規(guī)定同上,令rk (C)表示k個棋子布到棋盤C上的方案數(shù)。,2024/3/10,,2024/3/10,,規(guī)定 r0(C)=1，包括

5、C=Ф時。設(shè)Ci是棋盤C的某一指定格子所在的行與列都去掉后所得的棋盤；Ce是僅去掉該格子后的棋盤。在上面定義下，顯然有,rk(C)=rk-1(Ci)＋rk(Ce),2024/3/10,,2024/3/10,設(shè)Ci是棋盤C的某一指定格子所在的行與列都去掉后所得的棋盤；Ce是僅去掉該格子后的棋盤。,,例如：,2024/3/10,,如果C由相互分離的C1，C2組成，即C1的任一格子所在的行和列中都沒有C2的格子。則有：,∴ R(C)

6、 = R(C1) R(C2),2024/3/10,,R(C) = xR(Ci) + R(C e) （Ci是棋盤C的某一指定格子所在的行與列都 去掉后所得的棋盤；Ce是僅去掉該格子后的棋盤） R(C) = R(C1) R(C2) （相互分離的C1、C2，即C1的任一格子 所在的行和列中都沒有C2的格子） 可以把較復(fù)雜的棋盤逐步分解成相對比較簡單

7、的棋盤，從而得到其棋盤多項式。,2024/3/10,,,,3,,,,色多項式,2024/3/10,,Def1：用x 種顏色對圖G的頂點進(jìn)行著色時，若圖 G 的任意兩個相鄰頂點都分配到不同的顏色，則稱此著色為圖G的正常x頂點著色。 Def2：圖G的不同x 著色的數(shù)目稱為圖G的色多項式，記為 P (G , x )。利用容斥原理求色多項式設(shè)G是任意圖，用x 種顏色涂染G的頂點，對于每條邊i ，設(shè)ai是邊i 的端部頂點得到相同顏色的