組合數(shù)學教學課件44整數(shù)的拆分課件

把n個無區(qū)別的球分放在一些無區(qū)別的盒子中，究竟有多少種不同的放法?無區(qū)別的盒子意味著，如果有四個相同的球，則在第一個盒子中放入三個球，第二個盒子中放入一個球與第一個盒子中放入一個球，第二個盒子中放入三個球的放法是一樣的?！?.4整數(shù)的拆分

作為母函數(shù)應用的一個實例，下面討論把n個無區(qū)別的球放在一些無區(qū)別的盒子中的問題.§4.4整數(shù)的拆分作為母函數(shù)應用的一個實例，下面討論把n如5=3+2和5=2+3被認為是同樣的拆分法。顯然整數(shù)n的一個拆分等價于把n個無區(qū)別的球分放在一些無區(qū)別的盒子中的一種方法。一個整數(shù)的拆分是把整數(shù)分拆為若干個正整數(shù)部分。而這些部分的次序是無關(guān)緊要的。一個整數(shù)的拆分是把整數(shù)分拆為若干個正整數(shù)

正整數(shù)n的拆分種數(shù)記作P(n)。例如，對于正整數(shù)n=1,2,3,4的拆分是n=1:1=1∴P(1)=1n=2:2=2,2=1+1∴P(2)=2n=3:3=3,3=2+1,3=1+1+1∴P(3)=3n=4:4=4,4=3+1,4=2+2,4=2+1+1,4=1+1+1+1∴P(4)=5正整數(shù)n的拆分種數(shù)記作P(n)。首先考慮恒等式于是有首先考慮恒等式于是有

在上式中可以看出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在上式中可以看出xn的系數(shù)等于n拆分為1，2，3的和在因子(1+x+x2+x3+…)中的1,x,x2,x3,…,分別表示數(shù)字1沒有被選，選一個1，選二個1，選三個1，……。同樣的，因子(1+x2+x4+x6+…)則表示2沒有被選，或選一個2，或選二個2，或選三個2，……。因子(1+x3+x6+x9+…)則表示3沒有被選，或選一個3，或選二個3，或選三個3，……。這樣，上面三個因子的乘積的xn的系數(shù)就是n拆分為1，2，3的和的方法數(shù)。

這與上面的例子是吻合的。由此我們可以分析如下：在因子(1+x+x2+x3+…)中的1,x,x2,x3,…,

又如x6的系數(shù)是7，它表示6拆分為1，2，3的和的方法有7種，見表4-1。由此可見，函數(shù)1/(1-x)(1-x2)1-x3)的級數(shù)展開式中，xn的系數(shù)就等于把n拆分為1，2，3的和的方法數(shù)P(n)。注：表4－1見書69頁。又如x6的系數(shù)是7，它表示6拆分為1，2，3的的級數(shù)展開式中的xn的系數(shù)等于把正整數(shù)n拆分成a,b,c,…的和的方法數(shù)P(n)。一般地，有下面的定理。定理4.2設(shè)a,b,c,…是大于0的正整數(shù)，則一般地，有下面的定理。定理4.2設(shè)a,b,c,…是大于0如果項xn是由x3a，xb,x2c,…的乘積所組成，則證明：如前所述，只需注意于是每當n可以拆分為a,b,c的和時，xn就會出現(xiàn)。這就證明了定理的結(jié)論。如果項xn是由x3a，xb,x2c,…的乘積所組成，則證

1.用Pk(n)表示n拆分成1,2,…，k的允許重復的方法數(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即可得1.用Pk(n)表示n拆分成1,2,…，k的允許重推論1｛P3(n)｝的普通母函數(shù)是推論2｛Pk(n)｝的普通母函數(shù)是推論3｛P(n)｝的普通母函數(shù)是推論1｛P3(n)｝的普通母函數(shù)是推論2｛Pk(n)｝的普通在定理4.2中，令a,b,c,…是奇整數(shù)，我們又有推論4｛P0(n)｝的普通母函數(shù)是的級數(shù)展開式中xn項的系數(shù)就是把n拆分成a,b,c,…的和，且a,b,c,…最多只出現(xiàn)一次的方法數(shù)。定理4.3設(shè)a,b,c,…都是大于0的正整數(shù)，則在定理4.2中，令a,b,c,…是奇整數(shù)，我們又有推論4｛P由定理4.3即可得推論1｛Pd(n)｝的普通母函數(shù)是推論2｛Pt(n)｝的普通母函數(shù)是定理4.4(Euler)對于正整數(shù)n都有由定理4.3即可得推論1｛Pd(n)｝的普通母函數(shù)是推論2｛證明：上式的左端正好是Pd(n)的普通母函數(shù)(由定理4.3的推論1)，而上式的右端，可將分子分母的所有偶次冪約去就得到證明：上式的左端正好是Pd(n)的普通母函數(shù)(由定理4.3的以上我們證明了把n拆分成奇整數(shù)的和的方式數(shù)等于把n拆分成不相同的整數(shù)的和的方式數(shù)。這正好是P0(n)的普通母函數(shù)(由推論4)?！郟o(n)=Pd(n)這正好是P0(n)的普通母函數(shù)(由推論4)。∴Po(n)=P下面我們驗證當n=7的情況。7=77=77=5+1+17=6+17=3+3+17=5+27=3+1+1+1+17=4+37=1+1+1+1+1+1+17=4+2+1∴Po(7)=5Pd(7)=5

于是Po(7)=Pd(7)。下面我們驗證當n=7的情況。定理4.5(Sylvester)

對正整數(shù)n，有Pt(n)=1證明：我們知道，任何正整數(shù)都可唯一地用一個二進制數(shù)來表示，而一個二進制數(shù)又可唯一地表成2的冪的和。由此即得結(jié)論。定理4.5(Sylvester)證明：我們知道，任何正如正整數(shù)39可以表成

39=100111=20+21+22+25下面用另一種方法來證明定理4.5。如正整數(shù)39可以表成下面用另一種方法來證明定理4.5。我們知道，序列(1，1，…，1)的普通母函數(shù)是又我們知道，序列(1，1，…，1)的普通母函數(shù)是又

而上式右端是Pt(n)的普通母函數(shù)(由定理4.3的推論2)定理證畢。而上式右端是Pt(n)的普通母函數(shù)(由

并用整數(shù)拆分的說法，這個恒等式的組合意義是什么?例1證明恒等式例1證明恒等式證明：而左端證明：而左端因此，這個恒等式表明，任何正整數(shù)都可唯一地拆分成形式為例如，對于整數(shù)349有唯一的拆分：349=9·100+4·101+3·102的不同部分。換句話說，任何整數(shù)的十進制表示是唯一的。因此，這個恒等式表明，任何正整數(shù)都可唯一地拆分成形式

通常，對于大的n，要求出將n拆分成某些整數(shù)的和的方式數(shù)P(n)是很困難的，但在有些問題中并不需要P(n)的精確值，只需P(n)的估計式就夠了。下面的定理就給出了P(n)的估計式。通常，對于大的n，要求出將n拆分成某些整數(shù)的和證明：由推論3知｛P(n)｝的普通母函數(shù)為定理4.6對于任何正整數(shù)n,有將上式兩邊取對數(shù)得由對數(shù)的泰勒展開式知證明：由推論3知｛P(n)｝的普通母函數(shù)為定理4.6對于任于是有即故有

對于，設(shè)，則有于是有即故有對于，設(shè)將上面的不等式代入（A）式有而將上面的不等式代入（A）式有而而對于w>1時，有而對于w>1時，有于是有將以上結(jié)果代入（B）式得在上式中，令，則有所以有證畢。于是有

下面，我們討論與整數(shù)拆分有著密切關(guān)系的Ferrers圖。

這個定理的估計式還可以進一步加以改進?，F(xiàn)在，已經(jīng)有人證明了近似式：

設(shè)n的一個拆分為

n=a1+a2+…+ak

并假設(shè)a1≥a2≥a3≥…≥ak≥1。這個定理的估計式還可以進一步加以改進?，F(xiàn)在，已

下面畫一個圖,這個圖由一行行的點所組成。在第一行有a1個點，第二行有a2個點，

……，第k行有ak個點，稱這圖為Ferrers圖。

整數(shù)的拆分可以用一個Ferrers圖來表示，例如16=6+5+3+1+1的Ferrers圖如圖4-1下面畫一個圖,這個圖由一行行的點所組成。

當給定Ferrers圖后，可以將它的行與列對換，這就得到另一個圖。顯然，這個圖也是一個Ferrers圖。也就是說，一個Ferrers圖的行與列對換所得的圖仍是一個Ferrers圖。

如圖4-1作行與列的對換就得到圖4-2。稱圖4-2為圖4-1的共軛圖。這個圖表示整數(shù)16的另一個拆分：16=5+3+3+2+2+1當給定Ferrers圖后，可以將它的行與列對換，

由此可見，n的一個拆分對應唯一的一個Ferrers圖，反過來，一個Ferrers圖又對應

一個n的唯一拆分。所以n的一個拆分同它的Ferrers圖之間是一一對應的。由此可見，n的一個拆分對應唯一的一個F

證明：只須考慮Ferrers圖和它的共軛圖之間的關(guān)系，本定理結(jié)論即可得證。例如，對n=24,如圖4-3(書75頁)定理4.7正整數(shù)n拆分成m項的和的方式數(shù)等于n拆分成最大數(shù)為m的方式數(shù)。定理4.7正整數(shù)n拆分成m項的和的方式數(shù)等于n拆

定理4.8正整數(shù)n拆分成最多不超過m個項的和的方式數(shù)等于n拆分成最大的數(shù)不超過m的方式數(shù)。證明：留作練習。定理4.8正整數(shù)n拆分成最多不超過m個項的和的方式數(shù)等

把n個無區(qū)別的球分放在一些無區(qū)別的盒子中，究竟有多少種不同的放法?無區(qū)別的盒子意味著，如果有四個相同的球，則在第一個盒子中放入三個球，第二個盒子中放入一個球與第一個盒子中放入一個球，第二個盒子中放入三個球的放法是一樣的。§4.4整數(shù)的拆分

作為母函數(shù)應用的一個實例，下面討論把n個無區(qū)別的球放在一些無區(qū)別的盒子中的問題.§4.4整數(shù)的拆分作為母函數(shù)應用的一個實例，下面討論把n如5=3+2和5=2+3被認為是同樣的拆分法。顯然整數(shù)n的一個拆分等價于把n個無區(qū)別的球分放在一些無區(qū)別的盒子中的一種方法。一個整數(shù)的拆分是把整數(shù)分拆為若干個正整數(shù)部分。而這些部分的次序是無關(guān)緊要的。一個整數(shù)的拆分是把整數(shù)分拆為若干個正整數(shù)

正整數(shù)n的拆分種數(shù)記作P(n)。例如，對于正整數(shù)n=1,2,3,4的拆分是n=1:1=1∴P(1)=1n=2:2=2,2=1+1∴P(2)=2n=3:3=3,3=2+1,3=1+1+1∴P(3)=3n=4:4=4,4=3+1,4=2+2,4=2+1+1,4=1+1+1+1∴P(4)=5正整數(shù)n的拆分種數(shù)記作P(n)。首先考慮恒等式于是有首先考慮恒等式于是有

在上式中可以看出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在上式中可以看出xn的系數(shù)等于n拆分為1，2，3的和在因子(1+x+x2+x3+…)中的1,x,x2,x3,…,分別表示數(shù)字1沒有被選，選一個1，選二個1，選三個1，……。同樣的，因子(1+x2+x4+x6+…)則表示2沒有被選，或選一個2，或選二個2，或選三個2，……。因子(1+x3+x6+x9+…)則表示3沒有被選，或選一個3，或選二個3，或選三個3，……。這樣，上面三個因子的乘積的xn的系數(shù)就是n拆分為1，2，3的和的方法數(shù)。

這與上面的例子是吻合的。由此我們可以分析如下：在因子(1+x+x2+x3+…)中的1,x,x2,x3,…,

又如x6的系數(shù)是7，它表示6拆分為1，2，3的和的方法有7種，見表4-1。由此可見，函數(shù)1/(1-x)(1-x2)1-x3)的級數(shù)展開式中，xn的系數(shù)就等于把n拆分為1，2，3的和的方法數(shù)P(n)。注：表4－1見書69頁。又如x6的系數(shù)是7，它表示6拆分為1，2，3的的級數(shù)展開式中的xn的系數(shù)等于把正整數(shù)n拆分成a,b,c,…的和的方法數(shù)P(n)。一般地，有下面的定理。定理4.2設(shè)a,b,c,…是大于0的正整數(shù)，則一般地，有下面的定理。定理4.2設(shè)a,b,c,…是大于0如果項xn是由x3a，xb,x2c,…的乘積所組成，則證明：如前所述，只需注意于是每當n可以拆分為a,b,c的和時，xn就會出現(xiàn)。這就證明了定理的結(jié)論。如果項xn是由x3a，xb,x2c,…的乘積所組成，則證

1.用Pk(n)表示n拆分成1,2,…，k的允許重復的方法數(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即可得1.用Pk(n)表示n拆分成1,2,…，k的允許重推論1｛P3(n)｝的普通母函數(shù)是推論2｛Pk(n)｝的普通母函數(shù)是推論3｛P(n)｝的普通母函數(shù)是推論1｛P3(n)｝的普通母函數(shù)是推論2｛Pk(n)｝的普通在定理4.2中，令a,b,c,…是奇整數(shù)，我們又有推論4｛P0(n)｝的普通母函數(shù)是的級數(shù)展開式中xn項的系數(shù)就是把n拆分成a,b,c,…的和，且a,b,c,…最多只出現(xiàn)一次的方法數(shù)。定理4.3設(shè)a,b,c,…都是大于0的正整數(shù)，則在定理4.2中，令a,b,c,…是奇整數(shù)，我們又有推論4｛P由定理4.3即可得推論1｛Pd(n)｝的普通母函數(shù)是推論2｛Pt(n)｝的普通母函數(shù)是定理4.4(Euler)對于正整數(shù)n都有由定理4.3即可得推論1｛Pd(n)｝的普通母函數(shù)是推論2｛證明：上式的左端正好是Pd(n)的普通母函數(shù)(由定理4.3的推論1)，而上式的右端，可將分子分母的所有偶次冪約去就得到證明：上式的左端正好是Pd(n)的普通母函數(shù)(由定理4.3的以上我們證明了把n拆分成奇整數(shù)的和的方式數(shù)等于把n拆分成不相同的整數(shù)的和的方式數(shù)。這正好是P0(n)的普通母函數(shù)(由推論4)?！郟o(n)=Pd(n)這正好是P0(n)的普通母函數(shù)(由推論4)?！郟o(n)=P下面我們驗證當n=7的情況。7=77=77=5+1+17=6+17=3+3+17=5+27=3+1+1+1+17=4+37=1+1+1+1+1+1+17=4+2+1∴Po(7)=5Pd(7)=5

于是Po(7)=Pd(7)。下面我們驗證當n=7的情況。定理4.5(Sylvester)

對正整數(shù)n，有Pt(n)=1證明：我們知道，任何正整數(shù)都可唯一地用一個二進制數(shù)來表示，而一個二進制數(shù)又可唯一地表成2的冪的和。由此即得結(jié)論。定理4.5(Sylvester)證明：我們知道，任何正如正整數(shù)39可以表成

39=100111=20+21+22+25下面用另一種方法來證明定理4.5。如正整數(shù)39可以表成下面用另一種方法來證明定理4.5。我們知道，序列(1，1，…，1)的普通母函數(shù)是又我們知道，序列(1，1，…，1)的普通母函數(shù)是又

而上式右端是Pt(n)的普通母函數(shù)(由定理4.3的推論2)定理證畢。而上式右端是Pt(n)的普通母函數(shù)(由

并用整數(shù)拆分的說法，這個恒等式的組合意義是什么?例1證明恒等式例1證明恒等式證明：而左端證明：而左端因此，這個恒等式表明，任何正整數(shù)都可唯一地拆分成形式為例如，對于整數(shù)349有唯一的拆分：349=9·100+4·101+3·102的不同部分。換句話說，任何整數(shù)的十進制表示是唯一的。因此，這個恒等式表明，任何正整數(shù)都可唯一地拆分成形式

通常，對于大的n，要求出將n拆分成某些整數(shù)的和的方式數(shù)P(n)是很困難的，但在有些問題中并不需要P(n)的精確值，只需P(n)的估計式就夠了。下面的定理就給出了P(n)的估計式。通常，對于大的n，要求出將n拆分成某些整數(shù)的和證明：由推論3知｛P(n)｝的普通母函數(shù)為定理4.6對于任何正整數(shù)n,有將上式兩邊取對數(shù)得由對數(shù)的泰勒展開式知證明：由推論3知｛P(n)｝的普通母函數(shù)為定理4.6對于任于是有即故有

對于，設(shè)，則有于是有即故有對于，設(shè)將上面的不等式代入（A）式有而將上面的不等式代入（A）式有而而對于w>1時，有而對于w>1時，有于是有將以上結(jié)果代入（B）式得在上式中，令，則有所以有證畢。于是有

下面，我們討論與整數(shù)拆分有著密切關(guān)系的Ferrers圖。

這個定理的估計式還可以進一步加以改進?，F(xiàn)在，已經(jīng)有人證明了近似式：