組合數(shù)學(xué)幻燈片44整數(shù)的拆分課件

1、 把n個(gè)無(wú)區(qū)別的球分放在一些無(wú)區(qū)別的盒子中，究竟有多少種不同的放法?無(wú)區(qū)別的盒子意味著，如果有四個(gè)相同的球，則在第一個(gè)盒子中放入三個(gè)球， 第二個(gè)盒子中放入一個(gè)球與第一個(gè)盒子中放入一個(gè)球，第二個(gè)盒子中放入三個(gè)球的放法是一樣的。4.4整數(shù)的拆分 作為母函數(shù)應(yīng)用的一個(gè)實(shí)例，下面討論把n個(gè)無(wú)區(qū)別的球放在一些無(wú)區(qū)別的盒子中的問(wèn)題. 如5=3+2和5=2+3被認(rèn)為是同樣的拆分法。顯然整數(shù)n的一個(gè)拆分等價(jià)于把n個(gè)無(wú)區(qū)別的球分放在一些無(wú)區(qū)別的盒子中的一種方法。一個(gè)整數(shù)的拆分是把整數(shù)分拆為若干個(gè)正整數(shù)部分。而這些部分的次序是無(wú)關(guān)緊要的。 正整數(shù)n的拆分種數(shù)記作P(n)。例如，對(duì)于正整數(shù)n =1,2,3,4的拆分

2、是 n=1: 1=1 P(1)=1 n=2: 2=2, 2=1+1 P(2)=2 n=3: 3=3, 3=2+1,3=1+1+1 P(3)=3 n=4: 4=4, 4=3+1,4=2+2, 4=2+1+1, 4=1+1+1+1 P(4)=5首先考慮恒等式于是有 在上式中可以看出xn的系數(shù)等于n拆分為1，2，3的和的方法數(shù)。例如x3的系數(shù)是3，這表示整數(shù)3拆分成1，2，3的和的方法數(shù)是3，即 3=3, 3=2+1, 3=1+1+1 又例如x4的系數(shù)是4，它表明有4種方法將4拆分為1，2，3的和。即4=3+1, 4=2+2, 4=2+1+1， 4=1+1+1+1在因子(1+x+x2+x3+)中的1

3、,x,x2,x3,分別表示數(shù) 字1沒(méi)有被選，選一個(gè)1，選二個(gè)1，選三個(gè)1，。同樣的，因子(1+x2+x4+x6+)則表示2沒(méi)有被選，或選一個(gè)2，或選二個(gè)2，或選三個(gè)2，。因子(1+x3+x6+x9+)則表示3沒(méi)有被選，或選一個(gè)3，或選二個(gè)3，或選三個(gè)3，。這樣，上面三個(gè)因子的乘積的xn的系數(shù)就是n拆分為1，2，3的和的方法數(shù)。 這與上面的例子是吻合的。由此我們可以分析如下： 又如x6的系數(shù)是7，它表示6拆分為1，2，3的和的方法有7種，見(jiàn)表4-1。由此可見(jiàn)，函數(shù)1/(1-x)(1-x2)1-x3)的級(jí)數(shù)展開(kāi)式中，xn的系數(shù)就等于把n拆分為1，2，3的和的方法數(shù)P(n)。注：表41見(jiàn)書(shū)69頁(yè)。的

4、級(jí)數(shù)展開(kāi)式中的xn的系數(shù)等于把正整數(shù)n拆分成a,b,c,的和的方法數(shù)P(n)。一般地，有下面的定理。定理4.2 設(shè)a,b,c,是大于0的正整數(shù)，則如果項(xiàng)xn是由x3a，xb, x2c, 的乘積所組成，則證明：如前所述，只需注意于是每當(dāng)n可以拆分為a,b,c的和時(shí)，xn就會(huì)出現(xiàn)。這就證明了定理的結(jié)論。 1.用Pk(n)表示n拆分成1,2,，k的允許重 復(fù)的方法數(shù)。 2.用Po(n)表示n拆分成奇整數(shù)的方法數(shù)。 3.用Pd(n)表示n拆分成不同的整數(shù)的方法數(shù)。 4.用Pt(n)表示n拆分成2的不同冪(即1，2，4，8，)的方法數(shù)。定義4.7由上面的討論和定理4.2即可得推論1P3(n)的普通母函數(shù)

5、是推論2Pk(n)的普通母函數(shù)是推論3P(n)的普通母函數(shù)是在定理4.2中，令a,b,c,是奇整數(shù)，我們又有推論4P0(n)的普通母函數(shù)是的級(jí)數(shù)展開(kāi)式中xn項(xiàng)的系數(shù)就是把n拆分成a,b,c,的和，且a,b,c,最多只出現(xiàn)一次的方法數(shù)。定理4.3 設(shè)a,b,c,都是大于0的正整數(shù)，則由定理4.3即可得推論1Pd(n)的普通母函數(shù)是推論2Pt(n)的普通母函數(shù)是定理4.4 (Euler)對(duì)于正整數(shù)n都有證明：上式的左端正好是Pd(n)的普通母函數(shù)(由定理4.3的推論1)，而上式的右端，可將分子分母的所有偶次冪約去就得到以上我們證明了把n拆分成奇整數(shù)的和的方式數(shù)等于把n拆分成不相同的整數(shù)的和的方式數(shù)

6、。這正好是P0(n)的普通母函數(shù)(由推論4)。Po(n)=Pd(n)下面我們驗(yàn)證當(dāng)n=7的情況。7=7 7=77=5+1+1 7=6+17=3+3+1 7=5+27=3+1+1+1+1 7=4+37=1+1+1+1+1+1+1 7=4+2+1Po(7)=5 Pd(7)=5 于是Po(7)=Pd(7)。定理4.5 (Sylvester) 對(duì)正整數(shù)n，有 Pt(n)=1 證明：我們知道，任何正整數(shù)都可唯一地用一個(gè)二進(jìn)制數(shù)來(lái)表示，而一個(gè)二進(jìn)制數(shù)又可唯一地表成2的冪的和。由此即得結(jié)論。如正整數(shù)39可以表成 39=100111=20+21+22+25下面用另一種方法來(lái)證明定理4.5。我們知道，序列(1，

7、1，1)的普通母函數(shù)是又 而上式右端是Pt(n)的普通母函數(shù)(由定理4.3的推論2)定理證畢。 并用整數(shù)拆分的說(shuō)法，這個(gè)恒等式的組合意義是什么?例1證明恒等式證明：而 左端 因此，這個(gè)恒等式表明，任何正整數(shù)都可唯一地拆分成形式為例如，對(duì)于整數(shù)349有唯一的拆分： 349=9100+4101+3102的不同部分。換句話說(shuō)，任何整數(shù)的十進(jìn)制表示是唯一的。 通常，對(duì)于大的n，要求出將n拆分成某些整數(shù)的和的方式數(shù)P(n)是很困難的，但在有些問(wèn)題中并不需要P(n)的精確值，只需P(n)的估計(jì)式就夠了。下面的定理就給出了P(n)的估計(jì)式。證明：由推論3知P(n)的普通母函數(shù)為定理4.6 對(duì)于任何正整數(shù)n,

8、有將上式兩邊取對(duì)數(shù)得由對(duì)數(shù)的泰勒展開(kāi)式知于是有即故有 對(duì)于 ，設(shè) ，則有將上面的不等式代入（A）式有而而對(duì)于w1時(shí)，有于是有將以上結(jié)果代入（B）式得在上式中，令 ，則有所以有證畢。 下面，我們討論與整數(shù)拆分有著密切關(guān)系的Ferrers圖。 這個(gè)定理的估計(jì)式還可以進(jìn)一步加以改進(jìn)?，F(xiàn)在，已經(jīng)有人證明了近似式： 設(shè) n的一個(gè)拆分為 n=a1+a2+ak 并假設(shè)a1a2a3ak1。 下面畫(huà)一個(gè)圖,這個(gè)圖由一行行的點(diǎn)所組成。 在第一行有a1個(gè)點(diǎn)， 第二行有a2個(gè)點(diǎn)， ， 第k行有ak個(gè)點(diǎn)，稱(chēng)這圖為Ferrers圖。 整數(shù)的拆分可以用一個(gè)Ferrers圖來(lái)表示，例如16=6+5+3+1+1的Ferrers圖如圖4-1 當(dāng)給定Ferrers圖后，可以將它的行與列對(duì)換，這就得到另一個(gè)圖。 顯然，這個(gè)圖也是一個(gè)Ferrers圖。也就是說(shuō)，一個(gè)Ferrers圖的行與列對(duì)換所得的圖仍是一個(gè)Ferrers圖。 如圖4-1作行與列的對(duì)換就得到圖4-2。稱(chēng)圖4-2為圖4-1的共軛圖。這個(gè)圖表示整數(shù)16的另一個(gè)拆分： 16=5+3+3+2+2+1 由此可見(jiàn)，n的一個(gè)拆分對(duì)應(yīng)唯一的一個(gè)Ferrers圖，反過(guò)來(lái)，一個(gè)Ferrers圖又對(duì)應(yīng) 一個(gè)n的唯一拆分。 所以n的一個(gè)拆分同它的Ferrers圖之間是一一對(duì)應(yīng)的。 證明：只須考慮Fer