acm-組合數(shù)學(xué)的藝術(shù)2

1、Lecture 2Generating Functions,By Yuhong Zhang (張玉宏) yhily@126.com, 186-2371-8860 （O）, 159-3629-0516（H）,ACM-Association for Computing Machinery ICPC-International Collegiate Programming Contest,問(wèn)題的導(dǎo)入,一道ACM試題 (offered b

2、y Weilong Zhang)求裝有蘋(píng)果、香蕉、橘子和梨的果籃的數(shù)量h[n]，其中在每個(gè)果籃中蘋(píng)果數(shù)是偶數(shù)，香蕉是5的倍數(shù)，橘子最多是4個(gè)，而梨的個(gè)數(shù)是0或1。比如h[1]=2,h[2]=3.,數(shù)學(xué)方法解決問(wèn)題,利用generate function的方法，,因此得到h[n]=n+1.,公式從何而來(lái)？,2024/3/18,4,問(wèn)題2： 若有1克、2克、3克、4克的砝碼各一 枚，能稱(chēng)出哪幾種重量？各有幾種可能方案？,如何解決這個(gè)問(wèn)題

3、呢？考慮構(gòu)造母函數(shù)。如果用x的指數(shù)表示稱(chēng)出的重量，則：1個(gè)1克的砝碼可以用函數(shù)1+x表示，1個(gè)2克的砝碼可以用函數(shù)1+x2表示，1個(gè)3克的砝碼可以用函數(shù)1+x3表示，1個(gè)4克的砝碼可以用函數(shù)1+x4表示，,2024/3/18,5,幾種砝碼的組合可以稱(chēng)重的情況，可以用以上幾個(gè)函數(shù)的乘積表示：,(1+x)(1+x2)(1+x3)(1+x4)=(1+x+x2+x3)(1+x3+x4+x7)=1+x+x2+2x3+2x4+

4、2x5+2x6+2x7+x8+x9+x10,從上面的函數(shù)知道：可稱(chēng)出從1克到10克，系數(shù)便是方案數(shù)。例如右端有2x5 項(xiàng)，即稱(chēng)出5克的方案有2：5=3+2=4+1；同樣，6=1+2+3=4+2；10=1+2+3+4。故稱(chēng)出6克的方案有2，稱(chēng)出10克的方案有1,Why?,這是最簡(jiǎn)單的方式嗎？,問(wèn)題還在繼續(xù)？,x+2y=10的非負(fù)整數(shù)解的個(gè)數(shù)將這個(gè)思想表示為如下的公式：(1 + x + x^2 + x^3+...)(1 + x

5、^2 + x^4 + x^6 +...)求x^10的系數(shù)。,Why?How？,Problem Description：HDU1028,"Well, it seems the first problem is too easy. I will let you know how foolish you are later." feng5166 says."The second problem is, g

6、iven an positive integer N, we define an equation like this:  N=a[1]+a[2]+a[3]+...+a[m];  a[i]>0,1<=m<=N;My question is how many different equations you can find for a given N.,Problem Des

7、cription：HDU1028,For example, assume N is 4, we can find:  4 = 4;  4 = 3 + 1;  4 = 2 + 2;  4 = 2 + 1 + 1;  4 = 1 + 1 + 1 + 1;so the result is 5 when N is 4. Note th

8、at "4 = 3 + 1" and "4 = 1 + 3" is the same in this problem. Now, you do it!",The Binomial Theorem,A binomial is a polynomial with two terms such as x + a. Often we need to raise a binomial to a

9、 power. In this section we'll explore a way to do just that without lengthy multiplication.,Can you see a pattern?Can you make a guess what the next one would be?,,,,,We can easily see the pattern on the x's an

10、d the a's. But what about the coefficients? Make a guess and then as we go we'll see how you did.,Let's list all of the coefficients on the x's and the a's and look for a pattern.,1 1 1

11、 1 2 1 1 3 3 11 4 6 4 1,Can you guess the next row?,1 5 10 10 5 1,,1 1 1 1 2 1 1 3 3 11 4 6 4 1,

12、1 5 10 10 5 1,This is called Pascal's Triangle and would give us the coefficients for a binomial expansion of any power if we extended it far enough.,This is good for lower powers but could get very

13、large. We will introduce some notation to help us and generalise the coefficients with a formula based on what was observed here.,,The x's start out to the nth power and decrease by 1 in power each term. The a'

14、s start out to the 0 power and increase by 1 in power each term. The binomial coefficients are found by computing the combination symbol. Also the sum of the powers on a and x is n.,Find the 5th term of (x + a)12,5th te

15、rm will have a4 (power on a is 1 less than term number),So we'll have x8 (sum of two powers is 12),,,1 less than term number,,Here is the expansion of (x + a)12,,…and the 5th term matches the term we obtained!,,I

16、n this expansion, observe the following:,Powers on a and x add up to power on binomial,a's increase in power as x's decrease in power from term to term.,Powers on a are one less than the term number,Symmetry of c

17、oefficients (i.e. 2nd term and 2nd to last term have same coefficients, 3rd & 3rd to last etc.) so once you've reached the middle, you can copy by symmetry rather than compute coefficients.,,,,,Let's use what

18、 we've learned to expand (2x - 3y)6,First let's write out the expansion of the general (x + a)6 and then we'll substitute.,these will be the same,these will be the same,Let's find the coefficient for the

19、second term.,Let's confirm that this is also the coefficient of the 2nd to last term.,6,6,,Let's find the coefficient for the third term.,15,This will also be the coefficient of the 3rd to last term.,15,,,,Now we

20、'll find the coefficient of the 4th term,20,Now we'll apply this formula to our specific binomial.,,,,,Instead of x we have 2x,,Instead of a we have -3y,,,,定理1.7(二項(xiàng)式定理)當(dāng)n是一個(gè)正整數(shù)時(shí)對(duì)任何x和y，有

21、  (1.12),二項(xiàng)式定理,在這n個(gè)因子中，項(xiàng) 是從n個(gè)因子(x+y)中選取k個(gè)因子(x+y),k=0,1,…,n。在這k個(gè)(x+y)里都取x，而從余下的n-k個(gè)因子(x+y)中選取y作乘積得到。因此 的系數(shù)為上述選法的個(gè)數(shù)，即為

22、 組合數(shù) 。故有,證明：,此定理也可用歸納法證明(略)。,,,推論1,當(dāng)n是正整數(shù)時(shí)，對(duì)任何x,y均有,在實(shí)際應(yīng)用中，y=1的情況經(jīng)常出現(xiàn)，于是有下列恒等式,推論2當(dāng)n是正整數(shù)時(shí)，對(duì)所有的x有(1.13),令x=1時(shí)，有推論3當(dāng)n是正整數(shù)時(shí)，都有 (1.14),推論2,在式(1.13)中，令x=-1時(shí)，有推論4當(dāng)n是正整數(shù)時(shí)，有 (1.15)

23、 注意，推論3表明，在具有n個(gè)元素的 集合中，所有子集的個(gè)數(shù)為2n。推 論4表明，在具有n(n≠0)個(gè)元素的集 合中，偶數(shù)子集的個(gè)數(shù)與奇數(shù)

24、子集的 個(gè)數(shù)相等。, 為了區(qū)別二項(xiàng)式系數(shù) ， 稱(chēng) 為廣義的二項(xiàng)式系數(shù)。,定義1.6,對(duì)于任何實(shí)數(shù)a和整數(shù)k，有,定理1.8 設(shè)α是一個(gè)任意實(shí)數(shù)，則對(duì)于滿(mǎn)足｜x/y｜<1的所有x和y有,式中,,在式(1.17)中，若令α=-n(n為正整數(shù))，則有推論2 對(duì)于｜z｜<1的任何z，有 (1.18),證明：略,在式(1.16)中，若令z=x/y，則有推論1 對(duì)于｜z｜<1的任何

25、z，有 (1.17),  又在式(1.19)中，用-z代替z,就有 推論4 當(dāng)｜z｜<1時(shí)，有(1.20) ,在式(1.18)中，令n=1,就有 =1， 于是又得到 推論3 當(dāng)｜z｜<1時(shí)，有 (1.19),Generating

26、functions,2.1. Introductory examples,Ex 2.1. 12 oranges for three children, Grace, Mary, and Frank.Grace gets at least four, and Mary and Frank gets at least two, but Frank gets no more than five.(x4+ x5+ x6+ x7+ x8)

27、(x2+ x3+x4+ x5+ x6)(x2+ x3+x4+ x5)The coefficient of x12 is the solution.,Ex 2.2,Four kinds of jelly beans, Red, Green, White, BlackIn how many ways can we select 24 jelly beans so that we have an even number of white

28、beans and at least six black ones?Red (green): 1+ x1+ x2+….+ x23+ x24White: 1+ x2+ x4+….+ x22+ x24Black: x6+ x7+….+ x23+ x24f(x)=(1+ x1+ x2+….+ x23+ x24)(1+ x2+ x4+….+ x22+ x24)(x6+ x7+….+ x23+ x24)The coefficient

29、 of x24 is the solution.,Ex 2.3.,How many nonnegative integer solutions are there for c1+c2+c3+c4=25? f(x)=(1+ x1+ x2+….+ x24+ x25)4The coefficient of x25 is the solution., 母函數(shù)又稱(chēng)發(fā)生函數(shù)或生成函數(shù)，它是解決計(jì)數(shù)問(wèn)題的一個(gè)重要工具。 母函數(shù)的類(lèi)型

30、較多，這里僅討論最常見(jiàn)的兩種類(lèi)型的母函數(shù)： 1. 普通母函數(shù) 2. 指數(shù)母函數(shù),2.1母函數(shù)的基本概念,下面，我們分別進(jìn)行討論。,稱(chēng)函數(shù)為序列(a0,a1,…,an,…)的普通母函數(shù)。,一、普通母函數(shù),定義2.1,給定一個(gè)無(wú)窮序列(a0,a1,…,an,…)(簡(jiǎn)記為｛an｝，下同)，,2.2. Definition and examples: calculational techniques,

31、普通母函數(shù), 必須注意的是，在定義2.1中，普通母函數(shù)是一個(gè)無(wú)窮級(jí)數(shù)，沒(méi)有必要去討論它的收斂性，實(shí)質(zhì)上它只是引進(jìn)一個(gè)表示序列的記號(hào)而已。,此時(shí)變量x只是一種形式變?cè)?。?duì)這種級(jí)數(shù)可以把它看成形式冪級(jí)數(shù)，我們可以按通常方式定義其加法、乘法、形式微分等運(yùn)算，從而構(gòu)成一個(gè)代數(shù)體系。,一個(gè)序列和它的普通母函數(shù)是一一對(duì)應(yīng)的。給定了一個(gè)序列就可以得到這個(gè)序列的普通母函數(shù)。 反之，如果給定了普通母函數(shù)，則序列也隨之而定。 由此可見(jiàn)，普

32、通母函數(shù)實(shí)質(zhì)上是序列的另一種表達(dá)形式。,由定義2.1可知,解：由定義2.1和式(1.13)有,求序列 的普通母函數(shù)。,例1,解：由式(1.20)有,求序列(0，1×2×3，2×3×4，…，n(n+1)(n+2),…)的普通母函數(shù)。,例2,將上式兩邊同時(shí)微分兩次得,再將上式兩邊同乘以x得,例2,將上式兩邊再微分有,由定義2.1知,f(x)=6x/(1-x)4是序列(0

33、，1×2×3，2×3×4，…，n(n+1)(n+2)，…)的普通母函數(shù)。, 由上面的例子可見(jiàn)，普通母函數(shù)特別適用于某些序列，尤其是包含組合數(shù)的序列，這是由于它具有牛頓二項(xiàng)式定理的形式。 但是，對(duì)于具有排列數(shù)的那些序列，我們考慮下列類(lèi)型的母函數(shù)(指數(shù)母函數(shù))更為合適。,二、指數(shù)母函數(shù),給定無(wú)窮序列(a0,a1,…,an,…),稱(chēng)函數(shù),之所以稱(chēng)為指數(shù)母函數(shù)是由于式(4.2)的右

34、邊很像指數(shù)函數(shù)e的冪級(jí)數(shù)展開(kāi)式。注意，指數(shù)母函數(shù)也是形式冪級(jí)數(shù)。,定義2.2,為序列(a0,a1,…,an,…)的指數(shù)母函數(shù)。,2.4. The exponential generating function,解：由定義2.2和式(1.7)以及例1的結(jié)論有,例3,設(shè)n是整數(shù)，求序列 (p(n,0),p(n,1),…,p(n,n))的指數(shù)母函數(shù)fe(x)。,例4 求序列｛1,a,a2,…an,…｝的指數(shù)母函數(shù)fe(x)。其中α是

35、實(shí)數(shù)。,解：由定義2.2知,若α=1，則序列(1，1，…，1)的指數(shù)母函數(shù)為ex。,例5 求序列(1，1×4，1×4×7，…，1×4×7×…×(3n+1),…)的 指數(shù)母函數(shù)。,解：由定義2.2和二項(xiàng)式定理式(1.16)有,由定義4.2易見(jiàn)，序列(a0,a1,…,an,…)的指數(shù)母函數(shù)也是序列(a0,a1,a2/2!,…,an/n!,…)的普通母函數(shù)。

36、,這說(shuō)明普通母函數(shù)與指數(shù)母函數(shù)之間有著密切的聯(lián)系，這種聯(lián)系可由下面的定理表出。,設(shè)f(x),fe(x)分別是序列(a0,a1,…,an,…)的普通母函數(shù)和指數(shù)母函數(shù)，則,定理2.1,證明：將上式兩邊同乘以e-s并從0到∞積分得,由分部積分法有,證畢,故,從這節(jié)開(kāi)始我們分別討論母函數(shù)在某些問(wèn)題中的應(yīng)用,母函數(shù)在排列、組合中的應(yīng)用,母函數(shù)的應(yīng)用,母函數(shù)有著廣泛的應(yīng)用，它不僅可以用來(lái)處理排列組合的計(jì)數(shù)問(wèn)題、整數(shù)分拆問(wèn)題，……而且還可以用來(lái)證

37、明(或推導(dǎo))各種有用的組合恒等式。, 同樣，從這三個(gè)不同的物體中選取兩個(gè)有三種方法，或者選取a和b，或者選取b和c，或者選取c和a。,首先，我們考慮下列事實(shí)。令a,b,c表示三個(gè)不同的物體。顯然有三種方法從這三個(gè)不同的物體中選取一個(gè)，或者選a，或者選b，或者選c,我們把這些可能的選取象征性地記為 a+b+c,我們把這些可能選取也象征性地記為 ab+bc+ca,而從這三個(gè)不同的物體中選取三個(gè)只有一種方法，把這種

38、可能的選取象征性地記為 abc ,考慮多項(xiàng)式 (1+ax)(1+bx)(1+cx) =1+(a+b+c)x1+(ab+bc+ca)x2+(abc)x3,從這個(gè)多項(xiàng)式可以看出，以上所有的可能選取方法都作為x的冪的系數(shù)被表示出來(lái)了。,下面，利用乘法規(guī)則和加法規(guī)則對(duì)上面的多項(xiàng)式予以解釋。,特別是，xi的系數(shù)就是從三個(gè)不同的物體中選取i個(gè)物體的方法的表示。這并不是偶然的巧合。,對(duì)物體a, 因子(1+a

39、x)象征性地表示有 兩種選取方法： 不選取a，或選取a。 其中x僅是一個(gè)形式變量。x0的系數(shù)表明不選取a, x1的系數(shù)表明a被選取。,對(duì)于(1+bx),(1+cx)可作類(lèi)似的解釋。這樣，(1+ax)(1+bx)(1+cx)就表明：對(duì)三個(gè)不同的物體a,b,c，其選擇方法是，不選取a或選取a；不選取b或選取b；不選取c或選取c。,于是這三個(gè)因子的乘積中x的冪指數(shù)就表示被選取的物體的個(gè)數(shù)，而對(duì)應(yīng)的系數(shù)則表明了所有

40、可能的選取方法。因此，由普通母函數(shù)的定義知，三個(gè)因子 的乘積(1+ax)(1+bx)(1+cx)就是選取物體a，b，c的所有不同方法的普通母函數(shù)。,如果由于某種實(shí)際的需要，我們只對(duì)可能的選取方法的個(gè)數(shù)感興趣，而不是對(duì)不同的選取方法感興趣，則可令a=b=c=1。,于是有 (1+x) (1+x) (1+x)=(1+x)3=1+3x+3x2+x3,該多項(xiàng)式表明只有一種方法 從三個(gè)物體中一個(gè)也不選取，有三種方法

41、 從這三個(gè)物體中選取一個(gè)，有三種方法 從這三個(gè)物體中選取兩個(gè)。有一種方法 這三個(gè)物體中選取三個(gè)。一般說(shuō)來(lái)，考慮多項(xiàng)式,對(duì)于這個(gè)多項(xiàng)式可作上面n=3時(shí)的同樣的解釋。也就是說(shuō)，從n個(gè)不同的物體中選其r個(gè)物體，其方法數(shù)為(1+x)n的冪級(jí)數(shù)展開(kāi)式中xr的系數(shù) 。,以上討論的是從n個(gè)不同物體中選取r個(gè)物體(每個(gè)物體至多選取一次)的簡(jiǎn)單情形。當(dāng)從n個(gè)不同的物體中，允許重復(fù)選取

42、r個(gè)物體時(shí)，上面的情況就可作如下的推廣。,那么，類(lèi)似地，我們可以用因子(1+x+x2)象征性地表示某一物體可以不選，或者選一次，或者選兩次。也就是說(shuō)某一物體至多選兩次。 同樣，用因子(1+x+x2+x3+…)象征性地表示某一物體可以不選，或者選一次，或者選兩次，或者選三次，……。 那么，(1+x+x2+x3+…)n的冪級(jí)數(shù)展開(kāi)式中，xr的系數(shù)ar就表示從n個(gè)不同的物體中允許重復(fù)地選取r個(gè)物體的方式數(shù)。,由于因子(1+x)象征

43、性地表示某一物體可以不選，或者只選一次。,下面，我們舉例加以說(shuō)明。,例1 證明從n個(gè)不同的物體中允許重復(fù)地選取r個(gè)物體的方式數(shù)為 F(n,r)=,這個(gè)問(wèn)題可以等價(jià)地?cái)⑹鰹椋鹤C明重集B=｛∞·b1,∞·b2,…,∞·bn｝的r-組合數(shù)為 。這就是定理第一講已經(jīng)證明過(guò)的結(jié)論。,下面用母函數(shù)法證明：設(shè)ar表示從n個(gè)不同物體中允許重復(fù)選取r個(gè)物體的方式數(shù)，由上面的分析可知，序列

44、(a0,a1,…,ar,…)的普通母函數(shù)為,例2 證明從n個(gè)不同的物體中允許重復(fù)地選取r個(gè)物體，但每個(gè)物體至少出現(xiàn)一次的方式數(shù)為,證明：設(shè)ar表示從n個(gè)不同物體中允許重復(fù)地選取r個(gè)物體，但每個(gè)物體至少出現(xiàn)一次的方式數(shù)，則序列(a0,a1,…,ar,…)的普通母函數(shù)為,故有, 解：設(shè)a2r為所求的方式數(shù)，由于每個(gè)物體出現(xiàn)偶數(shù)次。故可用因子(1+x2+x4+…)表示某一物體可以不選，或選取兩次，或選取4次，……。,例3 求從n個(gè)

45、不同的物體中允許重復(fù)地選取r個(gè)物體，但每個(gè)物體出現(xiàn)偶數(shù)次的方式數(shù)。,因此序列(a0,a1,…,ar,…)的普通母函數(shù)為,故有,例4 在一個(gè)書(shū)架上共有16本書(shū)，其中4本是高等數(shù)學(xué)，3本是普通物理，4本是數(shù)據(jù)結(jié)構(gòu)，5本是離散數(shù)學(xué)。求從中選取r本書(shū)的方式數(shù)，其中r=12。, 設(shè)ar是選取r本書(shū)的方式數(shù)。由于高等數(shù)學(xué)最多只能選4本， 普通物理最多只能選3本， 數(shù)據(jù)結(jié)構(gòu)最多只能選4本， 離散數(shù)學(xué)最多只能選5本。,取f

46、(x)展開(kāi)式中xr的系數(shù)即為所求的方式數(shù)。當(dāng)r=12,x12的系數(shù)為34，即 a12=34,Ex 2.3.,Determine the coefficient of x15 in f(x)=(x2+x3+x4+…)4.(x2+x3+x4+…)=x2(1+x+x2+…)=x2/(1-x)f(x)=(x2/(1-x))4=x8/(1-x)4Hence the solution is the coefficient of x7 in

47、(1-x)-4, which is C(-4, 7)(-1)7=C(10, 7).,指數(shù)母函數(shù)的應(yīng)用,以上，我們討論了普通母函數(shù)在組合計(jì)數(shù)問(wèn)題中的應(yīng)用。下面說(shuō)明指數(shù)母函數(shù)在排列計(jì)數(shù)問(wèn)題中的一些應(yīng)用。,我們已知道,是從n個(gè)不同的物體中選取r個(gè)物體的組合數(shù)ar所成的序列的普通母函數(shù)。利用式(1.7)將上式變形有,而(1+x)=(1+x1/1!)象征性地表示某一物體在 排列中可以不選取，或者選取一次。由此我們得到啟發(fā)，某一物體在排列中可以

48、不取，或取一次，或取兩次，……，或取r次可用如下形式表示：,這表明從n個(gè)不同的物體中選取r個(gè)物體的排列數(shù)恰好是xr/r!的系數(shù)。,特別是，如果某物體的重復(fù)次數(shù)是∞時(shí)，則上式的形式變?yōu)?同樣地，如果某一物體在排列中至少取兩次，至多取五次，則可用下面的形式表示, 證明：這個(gè)問(wèn)題實(shí)質(zhì)上是證明重集B=｛∞·b1,∞·b2,…,∞·bn｝的r排列數(shù)為nr。這就是第一講已經(jīng)證明過(guò)的結(jié)論。這里用母函數(shù)的方法證明。,

49、下面，我們舉例說(shuō)明。,例5 證明從n個(gè)不同的物體中允許重復(fù)地選取r個(gè)物體的排列數(shù)為nr,設(shè)ar為所求的排列數(shù)，由上面的分析知，序列(a0,a1,…,ar,…)的指數(shù)母函數(shù)為,故有,解：這個(gè)問(wèn)題等價(jià)于求重集B=｛∞·1,∞·3,∞·5，∞·7，∞·9)｝的r排列數(shù)。其中要求7，9出現(xiàn)偶數(shù)次。,例7 求1，3，5，7，9五個(gè)數(shù)字組成r位數(shù)的個(gè)數(shù)。其中要求7，9出現(xiàn)的次數(shù)為偶數(shù)。其余數(shù)字的

50、出現(xiàn)不加限制。,而,故,設(shè)所求的r-排列數(shù)為ar，則序列(a0,a1,…, ar,…)的指數(shù)母函數(shù)為,故,所以有, 解：設(shè)ar為所求的符合題意的個(gè)數(shù)。由于1出現(xiàn)次數(shù)與2出現(xiàn)的次數(shù)的和為偶數(shù)，這有兩種情況：(1) 1出現(xiàn)的次數(shù)與2出現(xiàn)的次數(shù)都為偶數(shù)。 (2) 1出現(xiàn)的次數(shù)與2出現(xiàn)的次數(shù)都為奇數(shù)。,例6 求1，2，3，4，5五個(gè)數(shù)字組成的r位數(shù)的個(gè)數(shù)，其中要求1出現(xiàn)的次數(shù)與2出現(xiàn)的次數(shù)的和必須是偶數(shù)。,故由加法規(guī)則知，序列

51、(a0,a1,…，ar)的指數(shù)母函數(shù)為,故有,Partition of integers, 把n個(gè)無(wú)區(qū)別的球分放在一些無(wú)區(qū)別的盒子中，究竟有多少種不同的放法?無(wú)區(qū)別的盒子意味著，如果有四個(gè)相同的球，則在第一個(gè)盒子中放入三個(gè)球， 第二個(gè)盒子中放入一個(gè)球與第一個(gè)盒子中放入一個(gè)球，第二個(gè)盒子中放入三個(gè)球的放法是一樣的。,§4.4整數(shù)的拆分與Ferrers圖, 作為母函數(shù)應(yīng)用的一個(gè)實(shí)例，下面討論把n個(gè)無(wú)區(qū)別的球放在

52、一些無(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的拆分是 n=1: 1=1 ∴P(1)=1 n=2:

53、 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

54、拆分成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,x,x2,x3,…,分別表示數(shù) 字1沒(méi)有被選，選一個(gè)1，選二個(gè)1，選三個(gè)1，……。同樣的，因子(1+x2+x4+x6+…)則表

55、示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)，函數(shù)1/(1-x)(1-x2)1-x3)的級(jí)數(shù)展開(kāi)式中，xn的系數(shù)就等于把n拆分為1，2，3的和

56、的方法數(shù)P(n)。,的級(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拆

57、分成奇整數(shù)的方法數(shù)。3.用Pd(n)表示n拆分成不同的整數(shù)的方法數(shù)。4.用Pt(n)表示n拆分成2的不同冪(即1，2，4，8，…)的方法數(shù)。,定義4.7,由上面的討論和定理4.2即可得,推論1｛P3(n)｝的普通母函數(shù)是,推論2｛Pk(n)｝的普通母函數(shù)是,推論3｛P(n)｝的普通母函數(shù)是,在定理4.2中，令a,b,c,…是奇整數(shù)，我們又有,推論4｛P0(n)｝的普通母函數(shù)是,的級(jí)數(shù)展開(kāi)式中xn項(xiàng)的系數(shù)就是把n拆分成a,b

58、,c,…的和，且a,b,c,…最多只出現(xiàn)一次的方法數(shù)。,定理4.3 設(shè)a,b,c,…都是大于0的正整數(shù)，則,由定理4.3即可得,推論1｛Pd(n)｝的普通母函數(shù)是,推論2｛Pi(n)｝的普通母函數(shù)是,定理4.4(Euler)對(duì)于正整數(shù)n都有,證明：,上式的左端正好是Pd(n)的普通母函數(shù)(由定理4.3的推論1)，而上式的右端，可將分子分母的所有偶次冪約去就得到,以上我們證明了把n拆分成奇整數(shù)的和的方式數(shù)等于把n拆分成不相同的整數(shù)的和

59、的方式數(shù)。,這正好是P0(n)的普通母函數(shù)(由推論4)。,∴Po(n)=Pd(n),2.3 Partition of integers,p(x) is the number of partitions for x. For n, the number of 1’s is 0 or 1 or 2 or 3…. The power series is 1+x+x2+x3+x4+….For n, the number of 2’s can

60、 be kept tracked by the power series 1+x2+x4+x6+x8+….For n, the number of 3’s can be kept tracked by the power series 1+x3+x6+x9+x12+….f(x)=(1+x+x2+x3+x4+…)(1+x2+x4+x6+x8+x10+…) (1+x3+x6+x9+…)…(1+x10+…) =1

61、/(1-x)?1/(1-x2)? 1/(1-x3) ?…? 1/(1-x10)At last, we have the following series for p(n) by the coefficient of xn,,下面我們驗(yàn)證當(dāng)n=7的情況。7=7 7=77=5+1+1 7=6+17=3+3+1

62、 7=5+27=3+1+1+1+1 7=4+37=1+1+1+1+1+1+1 7=4+2+1∴Po(7)=5 Pd(7)=5 于是Po(7)=Pd(7)。, 定理4.5(Sylvester) 對(duì)正整數(shù)n，有 Pt(n)=1,證明：我們知道，任何正整數(shù)都可唯一

63、地用一個(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，1，…，1)的普通母函數(shù)是,又,而上式右端是Pt(n)的普通母函數(shù)(由定理4.3的推論2),定理證畢。, 因此，這個(gè)恒等式表明，任何正整數(shù)都可唯一地拆分成形式為,例如，對(duì)于整數(shù)349有唯一的拆分：3

64、49=9·100+4·101+3·102,的不同部分。換句話(huà)說(shuō)，任何整數(shù)的十進(jìn)制表示是唯一的。,下面，我們討論與整數(shù)拆分有著密切關(guān)系的Ferrers圖。,設(shè)n的一個(gè)拆分為 n=a1+a2+…+ak并假設(shè)a1≥a2≥a3≥…≥ak≥1。,下面畫(huà)一個(gè)圖,這個(gè)圖由一行行的點(diǎn)所組成。 在第一行有a1個(gè)點(diǎn)， 第二行有a2個(gè)點(diǎn)， ……，

65、 第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è)圖

66、表示整數(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)的。, 證明：只須考慮Ferrers圖和它的共軛圖之間的關(guān)系，本定理結(jié)論即可得證。例如，對(duì)n=24,如圖4-3(書(shū)75頁(yè)),定理4.7正

67、整數(shù)n拆分成m項(xiàng)的和的方式數(shù)等于n拆分成最大數(shù)為m的方式數(shù),Ex 9.21,Find the number of ways an advertising agent can purchase n minutes if the time slots come in blocks of 30, 60, 120 seconds.Let 30 seconds represent one time unit.a+2b+4c=2nf(x)=

68、(1+x+x2+x3+x4+…) (1+x2+x4+x6+x8+…)( 1+x4+x8+x12+…) =1/(1-x) ? 1/(1-x2) ? 1/(1-x4).The coefficient of x2n is the answer to the problem.,Examples,Ex 9.22. pd(n) is the number of partitions of a positive integer n into

69、 distinct summands.Pd(x)=(1+x)(1+x2)(1+x3)..…Ex 9.23. po(n) is the number of partitions of a positive integer n into odd summands.Po(x)= (1+x+x2+x3+x4+…) (1+x3+x6+x9+x12+…)( 1+x5+x10+x15+…)…Po(x)=1/(1-x) ? 1/(1-x3) ?