簡介:LECTURE2GENERATINGFUNCTIONS,BYYUHONGZHANG張玉宏YHILY126COM,18623718860(O),15936290516(H),ACMASSOCIATIONFORCOMPUTINGMACHINERYICPCINTERNATIONALCOLLEGIATEPROGRAMMINGCONTEST,問題的導(dǎo)入,一道ACM試題OFFEREDBYWEILONGZHANG求裝有蘋果、香蕉、橘子和梨的果籃的數(shù)量HN,其中在每個(gè)果籃中蘋果數(shù)是偶數(shù),香蕉是5的倍數(shù),橘子最多是4個(gè),而梨的個(gè)數(shù)是0或1。比如H12,H23,數(shù)學(xué)方法解決問題,利用GENERATEFUNCTION的方法,,因此得到HNN1,公式從何而來,2024/3/18,4,問題2若有1克、2克、3克、4克的砝碼各一枚,能稱出哪幾種重量各有幾種可能方案,如何解決這個(gè)問題呢考慮構(gòu)造母函數(shù)。如果用X的指數(shù)表示稱出的重量,則1個(gè)1克的砝碼可以用函數(shù)1X表示,1個(gè)2克的砝碼可以用函數(shù)1X2表示,1個(gè)3克的砝碼可以用函數(shù)1X3表示,1個(gè)4克的砝碼可以用函數(shù)1X4表示,,2024/3/18,5,幾種砝碼的組合可以稱重的情況,可以用以上幾個(gè)函數(shù)的乘積表示,1X1X21X31X41XX2X31X3X4X71XX22X32X42X52X62X7X8X9X10,從上面的函數(shù)知道可稱出從1克到10克,系數(shù)便是方案數(shù)。例如右端有2X5項(xiàng),即稱出5克的方案有253241;同樣,612342;101234。故稱出6克的方案有2,稱出10克的方案有1,WHY,這是最簡單的方式嗎,問題還在繼續(xù),X2Y10的非負(fù)整數(shù)解的個(gè)數(shù)將這個(gè)思想表示為如下的公式1XX2X31X2X4X6求X10的系數(shù)。,WHYHOW,PROBLEMDESCRIPTIONHDU1028,“WELL,ITSEEMSTHEFIRSTPROBLEMISTOOEASYIWILLLETYOUKNOWHOWFOOLISHYOUARELATER“FENG5166SAYS“THESECONDPROBLEMIS,GIVENANPOSITIVEINTEGERN,WEDEFINEANEQUATIONLIKETHISNA1A2A3AMAI0,1MNMYQUESTIONISHOWMANYDIFFERENTEQUATIONSYOUCANFINDFORAGIVENN,PROBLEMDESCRIPTIONHDU1028,FOREXAMPLE,ASSUMENIS4,WECANFIND44431422421141111SOTHERESULTIS5WHENNIS4NOTETHAT“431“AND“413“ISTHESAMEINTHISPROBLEMNOW,YOUDOIT“,THEBINOMIALTHEOREM,ABINOMIALISAPOLYNOMIALWITHTWOTERMSSUCHASXAOFTENWENEEDTORAISEABINOMIALTOAPOWERINTHISSECTIONWELLEXPLOREAWAYTODOJUSTTHATWITHOUTLENGTHYMULTIPLICATION,CANYOUSEEAPATTERNCANYOUMAKEAGUESSWHATTHENEXTONEWOULDBE,,,,,WECANEASILYSEETHEPATTERNONTHEXSANDTHEASBUTWHATABOUTTHECOEFFICIENTSMAKEAGUESSANDTHENASWEGOWELLSEEHOWYOUDID,LETSLISTALLOFTHECOEFFICIENTSONTHEXSANDTHEASANDLOOKFORAPATTERN,111121133114641,CANYOUGUESSTHENEXTROW,15101051,,111121133114641,15101051,THISISCALLEDPASCALSTRIANGLEANDWOULDGIVEUSTHECOEFFICIENTSFORABINOMIALEXPANSIONOFANYPOWERIFWEEXTENDEDITFARENOUGH,THISISGOODFORLOWERPOWERSBUTCOULDGETVERYLARGEWEWILLINTRODUCESOMENOTATIONTOHELPUSANDGENERALISETHECOEFFICIENTSWITHAFORMULABASEDONWHATWASOBSERVEDHERE,,THEXSSTARTOUTTOTHENTHPOWERANDDECREASEBY1INPOWEREACHTERMTHEASSTARTOUTTOTHE0POWERANDINCREASEBY1INPOWEREACHTERMTHEBINOMIALCOEFFICIENTSAREFOUNDBYCOMPUTINGTHECOMBINATIONSYMBOLALSOTHESUMOFTHEPOWERSONAANDXISN,FINDTHE5THTERMOFXA12,5THTERMWILLHAVEA4POWERONAIS1LESSTHANTERMNUMBER,SOWELLHAVEX8SUMOFTWOPOWERSIS12,,,1LESSTHANTERMNUMBER,,HEREISTHEEXPANSIONOFXA12,,ANDTHE5THTERMMATCHESTHETERMWEOBTAINED,,INTHISEXPANSION,OBSERVETHEFOLLOWING,POWERSONAANDXADDUPTOPOWERONBINOMIAL,ASINCREASEINPOWERASXSDECREASEINPOWERFROMTERMTOTERM,POWERSONAAREONELESSTHANTHETERMNUMBER,SYMMETRYOFCOEFFICIENTSIE2NDTERMAND2NDTOLASTTERMHAVESAMECOEFFICIENTS,3RD3RDTOLASTETCSOONCEYOUVEREACHEDTHEMIDDLE,YOUCANCOPYBYSYMMETRYRATHERTHANCOMPUTECOEFFICIENTS,,,,,LETSUSEWHATWEVELEARNEDTOEXPAND2X3Y6,FIRSTLETSWRITEOUTTHEEXPANSIONOFTHEGENERALXA6ANDTHENWELLSUBSTITUTE,THESEWILLBETHESAME,THESEWILLBETHESAME,LETSFINDTHECOEFFICIENTFORTHESECONDTERM,LETSCONFIRMTHATTHISISALSOTHECOEFFICIENTOFTHE2NDTOLASTTERM,6,6,,LETSFINDTHECOEFFICIENTFORTHETHIRDTERM,15,THISWILLALSOBETHECOEFFICIENTOFTHE3RDTOLASTTERM,15,,,,NOWWELLFINDTHECOEFFICIENTOFTHE4THTERM,20,NOWWELLAPPLYTHISFORMULATOOURSPECIFICBINOMIAL,,,,,INSTEADOFXWEHAVE2X,,INSTEADOFAWEHAVE3Y,,,,定理17二項(xiàng)式定理當(dāng)N是一個(gè)正整數(shù)時(shí)對(duì)任何X和Y,有112,二項(xiàng)式定理,在這N個(gè)因子中,項(xiàng)是從N個(gè)因子XY中選取K個(gè)因子XY,K0,1,,N。在這K個(gè)XY里都取X,而從余下的NK個(gè)因子XY中選取Y作乘積得到。因此的系數(shù)為上述選法的個(gè)數(shù),即為組合數(shù)。故有,證明,此定理也可用歸納法證明略。,,,推論1,當(dāng)N是正整數(shù)時(shí),對(duì)任何X,Y均有,在實(shí)際應(yīng)用中,Y1的情況經(jīng)常出現(xiàn),于是有下列恒等式,推論2當(dāng)N是正整數(shù)時(shí),對(duì)所有的X有113,令X1時(shí),有推論3當(dāng)N是正整數(shù)時(shí),都有114,推論2,在式113中,令X1時(shí),有推論4當(dāng)N是正整數(shù)時(shí),有115注意,推論3表明,在具有N個(gè)元素的集合中,所有子集的個(gè)數(shù)為2N。推論4表明,在具有NN≠0個(gè)元素的集合中,偶數(shù)子集的個(gè)數(shù)與奇數(shù)子集的個(gè)數(shù)相等。,為了區(qū)別二項(xiàng)式系數(shù),稱為廣義的二項(xiàng)式系數(shù)。,定義16,對(duì)于任何實(shí)數(shù)A和整數(shù)K,有,定理18設(shè)Α是一個(gè)任意實(shí)數(shù),則對(duì)于滿足|X/Y|1的所有X和Y有,式中,,在式117中,若令ΑNN為正整數(shù),則有推論2對(duì)于|Z|1的任何Z,有118,證明略,在式116中,若令ZX/Y,則有推論1對(duì)于|Z|1的任何Z,有117,又在式119中,用Z代替Z,就有推論4當(dāng)|Z|1時(shí),有120,在式118中,令N1,就有1,于是又得到推論3當(dāng)|Z|1時(shí),有119,GENERATINGFUNCTIONS,21INTRODUCTORYEXAMPLES,EX2112ORANGESFORTHREECHILDREN,GRACE,MARY,ANDFRANKGRACEGETSATLEASTFOUR,ANDMARYANDFRANKGETSATLEASTTWO,BUTFRANKGETSNOMORETHANFIVEX4X5X6X7X8X2X3X4X5X6X2X3X4X5THECOEFFICIENTOFX12ISTHESOLUTION,EX22,FOURKINDSOFJELLYBEANS,RED,GREEN,WHITE,BLACKINHOWMANYWAYSCANWESELECT24JELLYBEANSSOTHATWEHAVEANEVENNUMBEROFWHITEBEANSANDATLEASTSIXBLACKONESREDGREEN1X1X2X23X24WHITE1X2X4X22X24BLACKX6X7X23X24FX1X1X2X23X241X2X4X22X24X6X7X23X24THECOEFFICIENTOFX24ISTHESOLUTION,EX23,HOWMANYNONNEGATIVEINTEGERSOLUTIONSARETHEREFORC1C2C3C425FX1X1X2X24X254THECOEFFICIENTOFX25ISTHESOLUTION,母函數(shù)又稱發(fā)生函數(shù)或生成函數(shù),它是解決計(jì)數(shù)問題的一個(gè)重要工具。母函數(shù)的類型較多,這里僅討論最常見的兩種類型的母函數(shù)1普通母函數(shù)2指數(shù)母函數(shù),21母函數(shù)的基本概念,下面,我們分別進(jìn)行討論。,稱函數(shù)為序列A0,A1,,AN,的普通母函數(shù)。,一、普通母函數(shù),定義21,給定一個(gè)無窮序列A0,A1,,AN,簡記為{AN},下同,,22DEFINITIONANDEXAMPLESCALCULATIONALTECHNIQUES,普通母函數(shù),必須注意的是,在定義21中,普通母函數(shù)是一個(gè)無窮級(jí)數(shù),沒有必要去討論它的收斂性,實(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ù),則序列也隨之而定。由此可見,普通母函數(shù)實(shí)質(zhì)上是序列的另一種表達(dá)形式。,由定義21可知,解由定義21和式113有,求序列的普通母函數(shù)。,例1,解由式120有,求序列0,123,234,,NN1N2,的普通母函數(shù)。,例2,將上式兩邊同時(shí)微分兩次得,再將上式兩邊同乘以X得,例2,將上式兩邊再微分有,由定義21知,FX6X/1X4是序列0,123,234,,NN1N2,的普通母函數(shù)。,由上面的例子可見,普通母函數(shù)特別適用于某些序列,尤其是包含組合數(shù)的序列,這是由于它具有牛頓二項(xiàng)式定理的形式。但是,對(duì)于具有排列數(shù)的那些序列,我們考慮下列類型的母函數(shù)指數(shù)母函數(shù)更為合適。,二、指數(shù)母函數(shù),給定無窮序列A0,A1,,AN,,稱函數(shù),之所以稱為指數(shù)母函數(shù)是由于式42的右邊很像指數(shù)函數(shù)E的冪級(jí)數(shù)展開式。注意,指數(shù)母函數(shù)也是形式冪級(jí)數(shù)。,定義22,為序列A0,A1,,AN,的指數(shù)母函數(shù)。,24THEEXPONENTIALGENERATINGFUNCTION,解由定義22和式17以及例1的結(jié)論有,例3,設(shè)N是整數(shù),求序列PN,0,PN,1,,PN,N的指數(shù)母函數(shù)FEX。,例4求序列{1,A,A2,AN,}的指數(shù)母函數(shù)FEX。其中Α是實(shí)數(shù)。,解由定義22知,若Α1,則序列1,1,,1的指數(shù)母函數(shù)為EX。,例5求序列1,14,147,,1473N1,的指數(shù)母函數(shù)。,解由定義22和二項(xiàng)式定理式116有,由定義42易見,序列A0,A1,,AN,的指數(shù)母函數(shù)也是序列A0,A1,A2/2,,AN/N,的普通母函數(shù)。,這說明普通母函數(shù)與指數(shù)母函數(shù)之間有著密切的聯(lián)系,這種聯(lián)系可由下面的定理表出。,設(shè)FX,FEX分別是序列A0,A1,,AN,的普通母函數(shù)和指數(shù)母函數(shù),則,定理21,證明將上式兩邊同乘以ES并從0到∞積分得,由分部積分法有,證畢,故,從這節(jié)開始我們分別討論母函數(shù)在某些問題中的應(yīng)用,母函數(shù)在排列、組合中的應(yīng)用,母函數(shù)的應(yīng)用,母函數(shù)有著廣泛的應(yīng)用,它不僅可以用來處理排列組合的計(jì)數(shù)問題、整數(shù)分拆問題,而且還可以用來證明或推導(dǎo)各種有用的組合恒等式。,同樣,從這三個(gè)不同的物體中選取兩個(gè)有三種方法,或者選取A和B,或者選取B和C,或者選取C和A。,首先,我們考慮下列事實(shí)。令A(yù),B,C表示三個(gè)不同的物體。顯然有三種方法從這三個(gè)不同的物體中選取一個(gè),或者選A,或者選B,或者選C,我們把這些可能的選取象征性地記為ABC,我們把這些可能選取也象征性地記為ABBCCA,而從這三個(gè)不同的物體中選取三個(gè)只有一種方法,把這種可能的選取象征性地記為ABC,考慮多項(xiàng)式1AX1BX1CX1ABCX1ABBCCAX2ABCX3,從這個(gè)多項(xiàng)式可以看出,以上所有的可能選取方法都作為X的冪的系數(shù)被表示出來了。,下面,利用乘法規(guī)則和加法規(guī)則對(duì)上面的多項(xiàng)式予以解釋。,特別是,XI的系數(shù)就是從三個(gè)不同的物體中選取I個(gè)物體的方法的表示。這并不是偶然的巧合。,對(duì)物體A,因子1AX象征性地表示有兩種選取方法不選取A,或選取A。其中X僅是一個(gè)形式變量。X0的系數(shù)表明不選取A,X1的系數(shù)表明A被選取。,對(duì)于1BX,1CX可作類似的解釋。這樣,1AX1BX1CX就表明對(duì)三個(gè)不同的物體A,B,C,其選擇方法是,不選取A或選取A;不選取B或選取B;不選取C或選取C。,于是這三個(gè)因子的乘積中X的冪指數(shù)就表示被選取的物體的個(gè)數(shù),而對(duì)應(yīng)的系數(shù)則表明了所有可能的選取方法。因此,由普通母函數(shù)的定義知,三個(gè)因子的乘積1AX1BX1CX就是選取物體A,B,C的所有不同方法的普通母函數(shù)。,如果由于某種實(shí)際的需要,我們只對(duì)可能的選取方法的個(gè)數(shù)感興趣,而不是對(duì)不同的選取方法感興趣,則可令A(yù)BC1。,于是有1X1X1X1X313X3X2X3,該多項(xiàng)式表明只有一種方法從三個(gè)物體中一個(gè)也不選取,有三種方法從這三個(gè)物體中選取一個(gè),有三種方法從這三個(gè)物體中選取兩個(gè)。有一種方法這三個(gè)物體中選取三個(gè)。一般說來,考慮多項(xiàng)式,對(duì)于這個(gè)多項(xiàng)式可作上面N3時(shí)的同樣的解釋。也就是說,從N個(gè)不同的物體中選其R個(gè)物體,其方法數(shù)為1XN的冪級(jí)數(shù)展開式中XR的系數(shù)。,以上討論的是從N個(gè)不同物體中選取R個(gè)物體每個(gè)物體至多選取一次的簡單情形。當(dāng)從N個(gè)不同的物體中,允許重復(fù)選取R個(gè)物體時(shí),上面的情況就可作如下的推廣。,那么,類似地,我們可以用因子1XX2象征性地表示某一物體可以不選,或者選一次,或者選兩次。也就是說某一物體至多選兩次。同樣,用因子1XX2X3象征性地表示某一物體可以不選,或者選一次,或者選兩次,或者選三次,。那么,1XX2X3N的冪級(jí)數(shù)展開式中,XR的系數(shù)AR就表示從N個(gè)不同的物體中允許重復(fù)地選取R個(gè)物體的方式數(shù)。,由于因子1X象征性地表示某一物體可以不選,或者只選一次。,下面,我們舉例加以說明。,例1證明從N個(gè)不同的物體中允許重復(fù)地選取R個(gè)物體的方式數(shù)為FN,R,這個(gè)問題可以等價(jià)地?cái)⑹鰹樽C明重集B{∞B1,∞B2,,∞BN}的R組合數(shù)為。這就是定理第一講已經(jīng)證明過的結(jié)論。,下面用母函數(shù)法證明設(shè)AR表示從N個(gè)不同物體中允許重復(fù)選取R個(gè)物體的方式數(shù),由上面的分析可知,序列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ù)次。故可用因子1X2X4表示某一物體可以不選,或選取兩次,或選取4次,。,例3求從N個(gè)不同的物體中允許重復(fù)地選取R個(gè)物體,但每個(gè)物體出現(xiàn)偶數(shù)次的方式數(shù)。,因此序列A0,A1,,AR,的普通母函數(shù)為,故有,例4在一個(gè)書架上共有16本書,其中4本是高等數(shù)學(xué),3本是普通物理,4本是數(shù)據(jù)結(jié)構(gòu),5本是離散數(shù)學(xué)。求從中選取R本書的方式數(shù),其中R12。,設(shè)AR是選取R本書的方式數(shù)。由于高等數(shù)學(xué)最多只能選4本,普通物理最多只能選3本,數(shù)據(jù)結(jié)構(gòu)最多只能選4本,離散數(shù)學(xué)最多只能選5本。,取FX展開式中XR的系數(shù)即為所求的方式數(shù)。當(dāng)R12,X12的系數(shù)為34,即A1234,EX23,DETERMINETHECOEFFICIENTOFX15INFXX2X3X44X2X3X4X21XX2X2/1XFXX2/1X4X8/1X4HENCETHESOLUTIONISTHECOEFFICIENTOFX7IN1X4,WHICHISC4,717C10,7,指數(shù)母函數(shù)的應(yīng)用,以上,我們討論了普通母函數(shù)在組合計(jì)數(shù)問題中的應(yīng)用。下面說明指數(shù)母函數(shù)在排列計(jì)數(shù)問題中的一些應(yīng)用。,我們已知道,是從N個(gè)不同的物體中選取R個(gè)物體的組合數(shù)AR所成的序列的普通母函數(shù)。利用式17將上式變形有,而1X1X1/1象征性地表示某一物體在排列中可以不選取,或者選取一次。由此我們得到啟發(fā),某一物體在排列中可以不取,或取一次,或取兩次,,或取R次可用如下形式表示,這表明從N個(gè)不同的物體中選取R個(gè)物體的排列數(shù)恰好是XR/R的系數(shù)。,特別是,如果某物體的重復(fù)次數(shù)是∞時(shí),則上式的形式變?yōu)?同樣地,如果某一物體在排列中至少取兩次,至多取五次,則可用下面的形式表示,證明這個(gè)問題實(shí)質(zhì)上是證明重集B{∞B1,∞B2,,∞BN}的R排列數(shù)為NR。這就是第一講已經(jīng)證明過的結(jié)論。這里用母函數(shù)的方法證明。,下面,我們舉例說明。,例5證明從N個(gè)不同的物體中允許重復(fù)地選取R個(gè)物體的排列數(shù)為NR,設(shè)AR為所求的排列數(shù),由上面的分析知,序列A0,A1,,AR,的指數(shù)母函數(shù)為,故有,解這個(gè)問題等價(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ù)字的出現(xiàn)不加限制。,而,故,設(shè)所求的R排列數(shù)為AR,則序列A0,A1,,AR,的指數(shù)母函數(shù)為,故,所以有,解設(shè)AR為所求的符合題意的個(gè)數(shù)。由于1出現(xiàn)次數(shù)與2出現(xiàn)的次數(shù)的和為偶數(shù),這有兩種情況11出現(xiàn)的次數(shù)與2出現(xiàn)的次數(shù)都為偶數(shù)。21出現(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ī)則知,序列A0,A1,,AR的指數(shù)母函數(shù)為,故有,PARTITIONOFINTEGERS,把N個(gè)無區(qū)別的球分放在一些無區(qū)別的盒子中,究竟有多少種不同的放法無區(qū)別的盒子意味著,如果有四個(gè)相同的球,則在第一個(gè)盒子中放入三個(gè)球,第二個(gè)盒子中放入一個(gè)球與第一個(gè)盒子中放入一個(gè)球,第二個(gè)盒子中放入三個(gè)球的放法是一樣的。,§44整數(shù)的拆分與FERRERS圖,作為母函數(shù)應(yīng)用的一個(gè)實(shí)例,下面討論把N個(gè)無區(qū)別的球放在一些無區(qū)別的盒子中的問題,如532和523被認(rèn)為是同樣的拆分法。顯然整數(shù)N的一個(gè)拆分等價(jià)于把N個(gè)無區(qū)別的球分放在一些無區(qū)別的盒子中的一種方法。,一個(gè)整數(shù)的拆分是把整數(shù)分拆為若干個(gè)正整數(shù)部分。而這些部分的次序是無關(guān)緊要的。,正整數(shù)N的拆分種數(shù)記作PN。例如,對(duì)于正整數(shù)N1,2,3,4的拆分是N111∴P11N222,211∴P22N333,321,3111∴P33N444,431,422,4211,41111∴P45,首先考慮恒等式,于是有,在上式中可以看出XN的系數(shù)等于N拆分為1,2,3的和的方法數(shù)。例如X3的系數(shù)是3,這表示整數(shù)3拆分成1,2,3的和的方法數(shù)是3,即33,321,3111又例如X4的系數(shù)是4,它表明有4種方法將4拆分為1,2,3的和。即431,422,4211,41111,在因子1XX2X3中的1,X,X2,X3,,分別表示數(shù)字1沒有被選,選一個(gè)1,選二個(gè)1,選三個(gè)1,。同樣的,因子1X2X4X6則表示2沒有被選,或選一個(gè)2,或選二個(gè)2,或選三個(gè)2,。因子1X3X6X9則表示3沒有被選,或選一個(gè)3,或選二個(gè)3,或選三個(gè)3,。這樣,上面三個(gè)因子的乘積的XN的系數(shù)就是N拆分為1,2,3的和的方法數(shù)。,這與上面的例子是吻合的。由此我們可以分析如下,又如X6的系數(shù)是7,它表示6拆分為1,2,3的和的方法有7種。由此可見,函數(shù)1/1X1X21X3的級(jí)數(shù)展開式中,XN的系數(shù)就等于把N拆分為1,2,3的和的方法數(shù)PN。,的級(jí)數(shù)展開式中的XN的系數(shù)等于把正整數(shù)N拆分成A,B,C,的和的方法數(shù)PN。,一般地,有下面的定理。,定理42,設(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用PKN表示N拆分成1,2,,K的允許重復(fù)的方法數(shù)。2用PON表示N拆分成奇整數(shù)的方法數(shù)。3用PDN表示N拆分成不同的整數(shù)的方法數(shù)。4用PTN表示N拆分成2的不同冪即1,2,4,8,的方法數(shù)。,定義47,由上面的討論和定理42即可得,推論1{P3N}的普通母函數(shù)是,推論2{PKN}的普通母函數(shù)是,推論3{PN}的普通母函數(shù)是,在定理42中,令A(yù),B,C,是奇整數(shù),我們又有,推論4{P0N}的普通母函數(shù)是,的級(jí)數(shù)展開式中XN項(xiàng)的系數(shù)就是把N拆分成A,B,C,的和,且A,B,C,最多只出現(xiàn)一次的方法數(shù)。,定理43設(shè)A,B,C,都是大于0的正整數(shù),則,由定理43即可得,推論1{PDN}的普通母函數(shù)是,推論2{PIN}的普通母函數(shù)是,定理44EULER對(duì)于正整數(shù)N都有,證明,上式的左端正好是PDN的普通母函數(shù)由定理43的推論1,而上式的右端,可將分子分母的所有偶次冪約去就得到,以上我們證明了把N拆分成奇整數(shù)的和的方式數(shù)等于把N拆分成不相同的整數(shù)的和的方式數(shù)。,這正好是P0N的普通母函數(shù)由推論4。,∴PONPDN,23PARTITIONOFINTEGERS,PXISTHENUMBEROFPARTITIONSFORXFORN,THENUMBEROF1’SIS0OR1OR2OR3THEPOWERSERIESIS1XX2X3X4FORN,THENUMBEROF2’SCANBEKEPTTRACKEDBYTHEPOWERSERIES1X2X4X6X8FORN,THENUMBEROF3’SCANBEKEPTTRACKEDBYTHEPOWERSERIES1X3X6X9X12FX1XX2X3X41X2X4X6X8X101X3X6X91X101/1X?1/1X2?1/1X3??1/1X10ATLAST,WEHAVETHEFOLLOWINGSERIESFORPNBYTHECOEFFICIENTOFXN,,下面我們驗(yàn)證當(dāng)N7的情況。777775117617331752731111743711111117421∴PO75PD75于是PO7PD7。,定理45SYLVESTER對(duì)正整數(shù)N,有PTN1,證明我們知道,任何正整數(shù)都可唯一地用一個(gè)二進(jìn)制數(shù)來表示,而一個(gè)二進(jìn)制數(shù)又可唯一地表成2
下載積分: 6 賞幣
上傳時(shí)間:2024-01-05
頁數(shù): 109
大?。?2.13(MB)
子文件數(shù):