請(qǐng)?jiān)诖颂幪顚?xiě)作品信息（此頁(yè)非設(shè)計(jì)模板）

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

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

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

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

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

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

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