簡介:LECTURE2GENERATINGFUNCTIONS,BYYUHONGZHANG張玉宏YHILY126COM,18623718860(O),15936290516(H),ACMASSOCIATIONFORCOMPUTINGMACHINERYICPCINTERNATIONALCOLLEGIATEPROGRAMMINGCONTEST,問題的導入,一道ACM試題OFFEREDBYWEILONGZHANG求裝有蘋果、香蕉、橘子和梨的果籃的數(shù)量HN,其中在每個果籃中蘋果數(shù)是偶數(shù),香蕉是5的倍數(shù),橘子最多是4個,而梨的個數(shù)是0或1。比如H12,H23,數(shù)學方法解決問題,利用GENERATEFUNCTION的方法,,因此得到HNN1,公式從何而來,2024/3/18,4,問題2若有1克、2克、3克、4克的砝碼各一枚,能稱出哪幾種重量各有幾種可能方案,如何解決這個問題呢考慮構(gòu)造母函數(shù)。如果用X的指數(shù)表示稱出的重量,則1個1克的砝碼可以用函數(shù)1X表示,1個2克的砝碼可以用函數(shù)1X2表示,1個3克的砝碼可以用函數(shù)1X3表示,1個4克的砝碼可以用函數(shù)1X4表示,,2024/3/18,5,幾種砝碼的組合可以稱重的情況,可以用以上幾個函數(shù)的乘積表示,1X1X21X31X41XX2X31X3X4X71XX22X32X42X52X62X7X8X9X10,從上面的函數(shù)知道可稱出從1克到10克,系數(shù)便是方案數(shù)。例如右端有2X5項,即稱出5克的方案有253241;同樣,612342;101234。故稱出6克的方案有2,稱出10克的方案有1,WHY,這是最簡單的方式嗎,問題還在繼續(xù),X2Y10的非負整數(shù)解的個數(shù)將這個思想表示為如下的公式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二項式定理當N是一個正整數(shù)時對任何X和Y,有112,二項式定理,在這N個因子中,項是從N個因子XY中選取K個因子XY,K0,1,,N。在這K個XY里都取X,而從余下的NK個因子XY中選取Y作乘積得到。因此的系數(shù)為上述選法的個數(shù),即為組合數(shù)。故有,證明,此定理也可用歸納法證明略。,,,推論1,當N是正整數(shù)時,對任何X,Y均有,在實際應用中,Y1的情況經(jīng)常出現(xiàn),于是有下列恒等式,推論2當N是正整數(shù)時,對所有的X有113,令X1時,有推論3當N是正整數(shù)時,都有114,推論2,在式113中,令X1時,有推論4當N是正整數(shù)時,有115注意,推論3表明,在具有N個元素的集合中,所有子集的個數(shù)為2N。推論4表明,在具有NN≠0個元素的集合中,偶數(shù)子集的個數(shù)與奇數(shù)子集的個數(shù)相等。,為了區(qū)別二項式系數(shù),稱為廣義的二項式系數(shù)。,定義16,對于任何實數(shù)A和整數(shù)K,有,定理18設(shè)Α是一個任意實數(shù),則對于滿足|X/Y|1的所有X和Y有,式中,,在式117中,若令ΑNN為正整數(shù),則有推論2對于|Z|1的任何Z,有118,證明略,在式116中,若令ZX/Y,則有推論1對于|Z|1的任何Z,有117,又在式119中,用Z代替Z,就有推論4當|Z|1時,有120,在式118中,令N1,就有1,于是又得到推論3當|Z|1時,有119,GENERATINGFUNCTIONS,21INTRODUCTORYEXAMPLES,EX2112ORANGESFORTHREECHILDREN,GRACE,MARY,ANDFRANKGRACEGETSATLEASTFOUR,ANDMARYANDFRANKGETSATLEASTTWO,BUTFRANKGETSNOMORETHANFIVEX4X5X6X7X8X2X3X4X5X6X2X3X4X5THECOEFFICIENTOFX12ISTHESOLUTION,EX22,FOURKINDSOFJELLYBEANS,RED,GREEN,WHITE,BLACKINHOWMANYWAYSCANWESELECT24JELLYBEANSSOTHATWEHAVEANEVENNUMBEROFWHITEBEANSANDATLEASTSIXBLACKONESREDGREEN1X1X2X23X24WHITE1X2X4X22X24BLACKX6X7X23X24FX1X1X2X23X241X2X4X22X24X6X7X23X24THECOEFFICIENTOFX24ISTHESOLUTION,EX23,HOWMANYNONNEGATIVEINTEGERSOLUTIONSARETHEREFORC1C2C3C425FX1X1X2X24X254THECOEFFICIENTOFX25ISTHESOLUTION,母函數(shù)又稱發(fā)生函數(shù)或生成函數(shù),它是解決計數(shù)問題的一個重要工具。母函數(shù)的類型較多,這里僅討論最常見的兩種類型的母函數(shù)1普通母函數(shù)2指數(shù)母函數(shù),21母函數(shù)的基本概念,下面,我們分別進行討論。,稱函數(shù)為序列A0,A1,,AN,的普通母函數(shù)。,一、普通母函數(shù),定義21,給定一個無窮序列A0,A1,,AN,簡記為{AN},下同,,22DEFINITIONANDEXAMPLESCALCULATIONALTECHNIQUES,普通母函數(shù),必須注意的是,在定義21中,普通母函數(shù)是一個無窮級數(shù),沒有必要去討論它的收斂性,實質(zhì)上它只是引進一個表示序列的記號而已。,此時變量X只是一種形式變元。對這種級數(shù)可以把它看成形式冪級數(shù),我們可以按通常方式定義其加法、乘法、形式微分等運算,從而構(gòu)成一個代數(shù)體系。,一個序列和它的普通母函數(shù)是一一對應的。給定了一個序列就可以得到這個序列的普通母函數(shù)。反之,如果給定了普通母函數(shù),則序列也隨之而定。由此可見,普通母函數(shù)實質(zhì)上是序列的另一種表達形式。,由定義21可知,解由定義21和式113有,求序列的普通母函數(shù)。,例1,解由式120有,求序列0,123,234,,NN1N2,的普通母函數(shù)。,例2,將上式兩邊同時微分兩次得,再將上式兩邊同乘以X得,例2,將上式兩邊再微分有,由定義21知,FX6X/1X4是序列0,123,234,,NN1N2,的普通母函數(shù)。,由上面的例子可見,普通母函數(shù)特別適用于某些序列,尤其是包含組合數(shù)的序列,這是由于它具有牛頓二項式定理的形式。但是,對于具有排列數(shù)的那些序列,我們考慮下列類型的母函數(shù)指數(shù)母函數(shù)更為合適。,二、指數(shù)母函數(shù),給定無窮序列A0,A1,,AN,,稱函數(shù),之所以稱為指數(shù)母函數(shù)是由于式42的右邊很像指數(shù)函數(shù)E的冪級數(shù)展開式。注意,指數(shù)母函數(shù)也是形式冪級數(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ù)。,解由定義22知,若Α1,則序列1,1,,1的指數(shù)母函數(shù)為EX。,例5求序列1,14,147,,1473N1,的指數(shù)母函數(shù)。,解由定義22和二項式定理式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ù)在某些問題中的應用,母函數(shù)在排列、組合中的應用,母函數(shù)的應用,母函數(shù)有著廣泛的應用,它不僅可以用來處理排列組合的計數(shù)問題、整數(shù)分拆問題,而且還可以用來證明或推導各種有用的組合恒等式。,同樣,從這三個不同的物體中選取兩個有三種方法,或者選取A和B,或者選取B和C,或者選取C和A。,首先,我們考慮下列事實。令A,B,C表示三個不同的物體。顯然有三種方法從這三個不同的物體中選取一個,或者選A,或者選B,或者選C,我們把這些可能的選取象征性地記為ABC,我們把這些可能選取也象征性地記為ABBCCA,而從這三個不同的物體中選取三個只有一種方法,把這種可能的選取象征性地記為ABC,考慮多項式1AX1BX1CX1ABCX1ABBCCAX2ABCX3,從這個多項式可以看出,以上所有的可能選取方法都作為X的冪的系數(shù)被表示出來了。,下面,利用乘法規(guī)則和加法規(guī)則對上面的多項式予以解釋。,特別是,XI的系數(shù)就是從三個不同的物體中選取I個物體的方法的表示。這并不是偶然的巧合。,對物體A,因子1AX象征性地表示有兩種選取方法不選取A,或選取A。其中X僅是一個形式變量。X0的系數(shù)表明不選取A,X1的系數(shù)表明A被選取。,對于1BX,1CX可作類似的解釋。這樣,1AX1BX1CX就表明對三個不同的物體A,B,C,其選擇方法是,不選取A或選取A;不選取B或選取B;不選取C或選取C。,于是這三個因子的乘積中X的冪指數(shù)就表示被選取的物體的個數(shù),而對應的系數(shù)則表明了所有可能的選取方法。因此,由普通母函數(shù)的定義知,三個因子的乘積1AX1BX1CX就是選取物體A,B,C的所有不同方法的普通母函數(shù)。,如果由于某種實際的需要,我們只對可能的選取方法的個數(shù)感興趣,而不是對不同的選取方法感興趣,則可令ABC1。,于是有1X1X1X1X313X3X2X3,該多項式表明只有一種方法從三個物體中一個也不選取,有三種方法從這三個物體中選取一個,有三種方法從這三個物體中選取兩個。有一種方法這三個物體中選取三個。一般說來,考慮多項式,對于這個多項式可作上面N3時的同樣的解釋。也就是說,從N個不同的物體中選其R個物體,其方法數(shù)為1XN的冪級數(shù)展開式中XR的系數(shù)。,以上討論的是從N個不同物體中選取R個物體每個物體至多選取一次的簡單情形。當從N個不同的物體中,允許重復選取R個物體時,上面的情況就可作如下的推廣。,那么,類似地,我們可以用因子1XX2象征性地表示某一物體可以不選,或者選一次,或者選兩次。也就是說某一物體至多選兩次。同樣,用因子1XX2X3象征性地表示某一物體可以不選,或者選一次,或者選兩次,或者選三次,。那么,1XX2X3N的冪級數(shù)展開式中,XR的系數(shù)AR就表示從N個不同的物體中允許重復地選取R個物體的方式數(shù)。,由于因子1X象征性地表示某一物體可以不選,或者只選一次。,下面,我們舉例加以說明。,例1證明從N個不同的物體中允許重復地選取R個物體的方式數(shù)為FN,R,這個問題可以等價地敘述為證明重集B{∞B1,∞B2,,∞BN}的R組合數(shù)為。這就是定理第一講已經(jīng)證明過的結(jié)論。,下面用母函數(shù)法證明設(shè)AR表示從N個不同物體中允許重復選取R個物體的方式數(shù),由上面的分析可知,序列A0,A1,,AR,的普通母函數(shù)為,例2證明從N個不同的物體中允許重復地選取R個物體,但每個物體至少出現(xiàn)一次的方式數(shù)為,證明設(shè)AR表示從N個不同物體中允許重復地選取R個物體,但每個物體至少出現(xiàn)一次的方式數(shù),則序列A0,A1,,AR,的普通母函數(shù)為,故有,解設(shè)A2R為所求的方式數(shù),由于每個物體出現(xiàn)偶數(shù)次。故可用因子1X2X4表示某一物體可以不選,或選取兩次,或選取4次,。,例3求從N個不同的物體中允許重復地選取R個物體,但每個物體出現(xiàn)偶數(shù)次的方式數(shù)。,因此序列A0,A1,,AR,的普通母函數(shù)為,故有,例4在一個書架上共有16本書,其中4本是高等數(shù)學,3本是普通物理,4本是數(shù)據(jù)結(jié)構(gòu),5本是離散數(shù)學。求從中選取R本書的方式數(shù),其中R12。,設(shè)AR是選取R本書的方式數(shù)。由于高等數(shù)學最多只能選4本,普通物理最多只能選3本,數(shù)據(jù)結(jié)構(gòu)最多只能選4本,離散數(shù)學最多只能選5本。,取FX展開式中XR的系數(shù)即為所求的方式數(shù)。當R12,X12的系數(shù)為34,即A1234,EX23,DETERMINETHECOEFFICIENTOFX15INFXX2X3X44X2X3X4X21XX2X2/1XFXX2/1X4X8/1X4HENCETHESOLUTIONISTHECOEFFICIENTOFX7IN1X4,WHICHISC4,717C10,7,指數(shù)母函數(shù)的應用,以上,我們討論了普通母函數(shù)在組合計數(shù)問題中的應用。下面說明指數(shù)母函數(shù)在排列計數(shù)問題中的一些應用。,我們已知道,是從N個不同的物體中選取R個物體的組合數(shù)AR所成的序列的普通母函數(shù)。利用式17將上式變形有,而1X1X1/1象征性地表示某一物體在排列中可以不選取,或者選取一次。由此我們得到啟發(fā),某一物體在排列中可以不取,或取一次,或取兩次,,或取R次可用如下形式表示,這表明從N個不同的物體中選取R個物體的排列數(shù)恰好是XR/R的系數(shù)。,特別是,如果某物體的重復次數(shù)是∞時,則上式的形式變?yōu)?同樣地,如果某一物體在排列中至少取兩次,至多取五次,則可用下面的形式表示,證明這個問題實質(zhì)上是證明重集B{∞B1,∞B2,,∞BN}的R排列數(shù)為NR。這就是第一講已經(jīng)證明過的結(jié)論。這里用母函數(shù)的方法證明。,下面,我們舉例說明。,例5證明從N個不同的物體中允許重復地選取R個物體的排列數(shù)為NR,設(shè)AR為所求的排列數(shù),由上面的分析知,序列A0,A1,,AR,的指數(shù)母函數(shù)為,故有,解這個問題等價于求重集B{∞1,∞3,∞5,∞7,∞9}的R排列數(shù)。其中要求7,9出現(xiàn)偶數(shù)次。,例7求1,3,5,7,9五個數(shù)字組成R位數(shù)的個數(shù)。其中要求7,9出現(xiàn)的次數(shù)為偶數(shù)。其余數(shù)字的出現(xiàn)不加限制。,而,故,設(shè)所求的R排列數(shù)為AR,則序列A0,A1,,AR,的指數(shù)母函數(shù)為,故,所以有,解設(shè)AR為所求的符合題意的個數(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五個數(shù)字組成的R位數(shù)的個數(shù),其中要求1出現(xiàn)的次數(shù)與2出現(xiàn)的次數(shù)的和必須是偶數(shù)。,故由加法規(guī)則知,序列A0,A1,,AR的指數(shù)母函數(shù)為,故有,PARTITIONOFINTEGERS,把N個無區(qū)別的球分放在一些無區(qū)別的盒子中,究竟有多少種不同的放法無區(qū)別的盒子意味著,如果有四個相同的球,則在第一個盒子中放入三個球,第二個盒子中放入一個球與第一個盒子中放入一個球,第二個盒子中放入三個球的放法是一樣的。,§44整數(shù)的拆分與FERRERS圖,作為母函數(shù)應用的一個實例,下面討論把N個無區(qū)別的球放在一些無區(qū)別的盒子中的問題,如532和523被認為是同樣的拆分法。顯然整數(shù)N的一個拆分等價于把N個無區(qū)別的球分放在一些無區(qū)別的盒子中的一種方法。,一個整數(shù)的拆分是把整數(shù)分拆為若干個正整數(shù)部分。而這些部分的次序是無關(guān)緊要的。,正整數(shù)N的拆分種數(shù)記作PN。例如,對于正整數(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沒有被選,選一個1,選二個1,選三個1,。同樣的,因子1X2X4X6則表示2沒有被選,或選一個2,或選二個2,或選三個2,。因子1X3X6X9則表示3沒有被選,或選一個3,或選二個3,或選三個3,。這樣,上面三個因子的乘積的XN的系數(shù)就是N拆分為1,2,3的和的方法數(shù)。,這與上面的例子是吻合的。由此我們可以分析如下,又如X6的系數(shù)是7,它表示6拆分為1,2,3的和的方法有7種。由此可見,函數(shù)1/1X1X21X3的級數(shù)展開式中,XN的系數(shù)就等于把N拆分為1,2,3的和的方法數(shù)PN。,的級數(shù)展開式中的XN的系數(shù)等于把正整數(shù)N拆分成A,B,C,的和的方法數(shù)PN。,一般地,有下面的定理。,定理42,設(shè)A,B,C,是大于0的正整數(shù),則,如果項XN是由X3A,XB,X2C,的乘積所組成,則,證明如前所述,只需注意,于是每當N可以拆分為A,B,C的和時,XN就會出現(xiàn)。這就證明了定理的結(jié)論。,1用PKN表示N拆分成1,2,,K的允許重復的方法數(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,B,C,是奇整數(shù),我們又有,推論4{P0N}的普通母函數(shù)是,的級數(shù)展開式中XN項的系數(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對于正整數(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,,下面我們驗證當N7的情況。777775117617331752731111743711111117421∴PO75PD75于是PO7PD7。,定理45SYLVESTER對正整數(shù)N,有PTN1,證明我們知道,任何正整數(shù)都可唯一地用一個二進制數(shù)來表示,而一個二進制數(shù)又可唯一地表成2
下載積分: 6 賞幣
上傳時間:2024-01-05
頁數(shù): 109
大小: 2.13(MB)
子文件數(shù):