acm-組合數學的藝術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,問題的導入,一道ACM試題 (offered b

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

3、呢？考慮構造母函數。如果用x的指數表示稱出的重量，則：1個1克的砝碼可以用函數1+x表示，1個2克的砝碼可以用函數1+x2表示，1個3克的砝碼可以用函數1+x3表示，1個4克的砝碼可以用函數1+x4表示，,2024/3/18,5,幾種砝碼的組合可以稱重的情況，可以用以上幾個函數的乘積表示：,(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,從上面的函數知道：可稱出從1克到10克，系數便是方案數。例如右端有2x5 項，即稱出5克的方案有2：5=3+2=4+1；同樣，6=1+2+3=4+2；10=1+2+3+4。故稱出6克的方案有2，稱出10克的方案有1,Why?,這是最簡單的方式嗎？,問題還在繼續(xù)？,x+2y=10的非負整數解的個數將這個思想表示為如下的公式：(1 + x + x^2 + x^3+...)(1 + x

5、^2 + x^4 + x^6 +...)求x^10的系數。,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(二項式定理)當n是一個正整數時對任何x和y，有

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

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

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

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

25、z，有 (1.17),  又在式(1.19)中，用-z代替z,就有 推論4 當｜z｜<1時，有(1.20) ,在式(1.18)中，令n=1,就有 =1， 于是又得到 推論3 當｜z｜<1時，有 (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., 母函數又稱發(fā)生函數或生成函數，它是解決計數問題的一個重要工具。 母函數的類型

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

31、普通母函數, 必須注意的是，在定義2.1中，普通母函數是一個無窮級數，沒有必要去討論它的收斂性，實質上它只是引進一個表示序列的記號而已。,此時變量x只是一種形式變元。對這種級數可以把它看成形式冪級數，我們可以按通常方式定義其加法、乘法、形式微分等運算，從而構成一個代數體系。,一個序列和它的普通母函數是一一對應的。給定了一個序列就可以得到這個序列的普通母函數。 反之，如果給定了普通母函數，則序列也隨之而定。 由此可見，普

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

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

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

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

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

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

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

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

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

41、 從這三個物體中選取一個，有三種方法 從這三個物體中選取兩個。有一種方法 這三個物體中選取三個。一般說來，考慮多項式,對于這個多項式可作上面n=3時的同樣的解釋。也就是說，從n個不同的物體中選其r個物體，其方法數為(1+x)n的冪級數展開式中xr的系數 。,以上討論的是從n個不同物體中選取r個物體(每個物體至多選取一次)的簡單情形。當從n個不同的物體中，允許重復選取

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

43、性地表示某一物體可以不選，或者只選一次。,下面，我們舉例加以說明。,例1 證明從n個不同的物體中允許重復地選取r個物體的方式數為 F(n,r)=,這個問題可以等價地敘述為：證明重集B=｛∞·b1,∞·b2,…,∞·bn｝的r-組合數為 。這就是定理第一講已經證明過的結論。,下面用母函數法證明：設ar表示從n個不同物體中允許重復選取r個物體的方式數，由上面的分析可知，序列

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

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

46、(x)展開式中xr的系數即為所求的方式數。當r=12,x12的系數為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).,指數母函數的應用,以上，我們討論了普通母函數在組合計數問題中的應用。下面說明指數母函數在排列計數問題中的一些應用。,我們已知道,是從n個不同的物體中選取r個物體的組合數ar所成的序列的普通母函數。利用式(1.7)將上式變形有,而(1+x)=(1+x1/1!)象征性地表示某一物體在 排列中可以不選取，或者選取一次。由此我們得到啟發(fā)，某一物體在排列中可以

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

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

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

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

52、一些無區(qū)別的盒子中的問題.,如5=3+2和5=2+3被認為是同樣的拆分法。顯然整數n的一個拆分等價于把n個無區(qū)別的球分放在一些無區(qū)別的盒子中的一種方法。,一個整數的拆分是把整數分拆為若干個正整數部分。而這些部分的次序是無關緊要的。,正整數n的拆分種數記作P(n)。例如，對于正整數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的系數等于n拆分為1，2，3的和的方法數。例如x3的系數是3，這表示整數3

54、拆分成1，2，3的和的方法數是3，即 3=3, 3=2+1, 3=1+1+1 又例如x4的系數是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,…,分別表示數 字1沒有被選，選一個1，選二個1，選三個1，……。同樣的，因子(1+x2+x4+x6+…)則表

55、示2沒有被選，或選一個2，或選二個2，或選三個2，……。因子(1+x3+x6+x9+…)則表示3沒有被選，或選一個3，或選二個3，或選三個3，……。這樣，上面三個因子的乘積的xn的系數就是n拆分為1，2，3的和的方法數。,這與上面的例子是吻合的。由此我們可以分析如下：,又如x6的系數是7，它表示6拆分為1，2，3的和的方法有7種。由此可見，函數1/(1-x)(1-x2)1-x3)的級數展開式中，xn的系數就等于把n拆分為1，2，3的和

56、的方法數P(n)。,的級數展開式中的xn的系數等于把正整數n拆分成a,b,c,…的和的方法數P(n)。,一般地，有下面的定理。,定理4.2,設a,b,c,…是大于0的正整數，則,如果項xn是由x3a，xb,x2c,…的乘積所組成，則,證明：如前所述，只需注意,于是每當n可以拆分為a,b,c的和時，xn就會出現。這就證明了定理的結論。,1.用Pk(n)表示n拆分成1,2,…，k的允許重 復的方法數。2.用Po(n)表示n拆

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

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

59、的方式數。,這正好是P0(n)的普通母函數(由推論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,,下面我們驗證當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) 對正整數n，有 Pt(n)=1,證明：我們知道，任何正整數都可唯一

63、地用一個二進制數來表示，而一個二進制數又可唯一地表成2的冪的和。由此即得結論。,如正整數39可以表成 39=100111=20+21+22+25,下面用另一種方法來證明定理4.5。,我們知道，序列(1，1，…，1)的普通母函數是,又,而上式右端是Pt(n)的普通母函數(由定理4.3的推論2),定理證畢。, 因此，這個恒等式表明，任何正整數都可唯一地拆分成形式為,例如，對于整數349有唯一的拆分：3

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

65、 第k行有ak個點，稱這圖為Ferrers圖。,整數的拆分可以用一個Ferrers圖來表示，例如16=6+5+3+1+1的Ferrers圖如圖4-1, 當給定Ferrers圖后，可以將它的行與列對換，這就得到另一個圖。顯然，這個圖也是一個Ferrers圖。也就是說，一個Ferrers圖的行與列對換所得的圖仍是一個Ferrers圖。,如圖4-1作行與列的對換就得到圖4-2。稱圖4-2為圖41的共軛圖。這個圖

66、表示整數16的另一個拆分： 16=5+3+3+2+2+1,由此可見，n的一個拆分對應唯一的一個Ferrers圖，反過來，一個Ferrers圖又對應  一個n的唯一拆分。 所以n的一個拆分同它的Ferrers圖之間是一一對應的。, 證明：只須考慮Ferrers圖和它的共軛圖之間的關系，本定理結論即可得證。例如，對n=24,如圖4-3(書75頁),定理4.7正

67、整數n拆分成m項的和的方式數等于n拆分成最大數為m的方式數,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) ?