《組合數(shù)學(xué)》課件PPT

組合數(shù)學(xué)課件PPT,組合數(shù)學(xué),組合,數(shù)學(xué),課件,PPT 1第五章第五章 生成函數(shù)生成函數(shù)n5.1 生成函數(shù)的定義和性質(zhì)生成函數(shù)的定義和性質(zhì)n5.2 組合數(shù)的生成函數(shù)組合數(shù)的生成函數(shù)n5.5 分拆數(shù)的生成函數(shù)分拆數(shù)的生成函數(shù)n5.3 指數(shù)型生成函數(shù)與指數(shù)型生成函數(shù)與多重集的排列數(shù)多重集的排列數(shù)n5.4 Catalan數(shù)列數(shù)列與與Stirling數(shù)列的生成函數(shù)數(shù)列的生成函數(shù)5.3 指數(shù)型生成函數(shù)與指數(shù)型生成函數(shù)與多重集的排列數(shù)多重集的排列數(shù)n定義定義5.3.1 數(shù)列數(shù)列 的指數(shù)型生成函數(shù)定義的指數(shù)型生成函數(shù)定義為形式冪級(jí)數(shù)為形式冪級(jí)數(shù)記為記為 或者或者2定理定理 5.3.1 設(shè)設(shè) ,考慮考慮 M 的的k-排列排列若要求在若要求在k-排列中元素排列中元素 出現(xiàn)次數(shù)構(gòu)成的集合為出現(xiàn)次數(shù)構(gòu)成的集合為 (1in)，則，則 k-排列數(shù)排列數(shù) 對(duì)應(yīng)數(shù)列對(duì)應(yīng)數(shù)列 的生成函數(shù)為的生成函數(shù)為 3例例5.3.5 有有3個(gè)紅球，個(gè)紅球，2個(gè)黃球，個(gè)黃球，3個(gè)藍(lán)球，每次從中取出個(gè)藍(lán)球，每次從中取出4個(gè)排成一行，求排列方案數(shù)。個(gè)排成一行，求排列方案數(shù)。解解 設(shè)每次取出設(shè)每次取出k個(gè)球的排列數(shù)為個(gè)球的排列數(shù)為bk，數(shù)列，數(shù)列bk 的指數(shù)型的指數(shù)型生成函數(shù)為生成函數(shù)為Gebk，則有，則有而我們所求的即為而我們所求的即為 為為 的系數(shù)，則取出的系數(shù)，則取出4個(gè)球的排個(gè)球的排列方案有列方案有70種。種。4例例5.3.3 計(jì)算計(jì)算M=4r,5g,6b 中中r和和g均出現(xiàn)奇數(shù)次均出現(xiàn)奇數(shù)次 的的10-排列數(shù)。排列數(shù)。解解 顯然根據(jù)要求在所求的顯然根據(jù)要求在所求的10-排列中排列中r可能出現(xiàn)的次數(shù)為可能出現(xiàn)的次數(shù)為1或或3，g出現(xiàn)的次數(shù)為出現(xiàn)的次數(shù)為1或或3或或5。若設(shè)。若設(shè)M的的k-排列數(shù)為排列數(shù)為bk，數(shù)列，數(shù)列bk 的指數(shù)型生成函數(shù)為的指數(shù)型生成函數(shù)為Gebk，則有，則有我們要求的我們要求的 是是 的系數(shù)，為的系數(shù)，為9660.5例例5.3.4 用紅、白、藍(lán)三種顏色給用紅、白、藍(lán)三種顏色給1行行k列棋盤涂色，并要列棋盤涂色，并要求紅色方格的個(gè)數(shù)是偶數(shù)且至少有一個(gè)方格為白色，求紅色方格的個(gè)數(shù)是偶數(shù)且至少有一個(gè)方格為白色，求涂色方案數(shù)求涂色方案數(shù)bk，其中，其中k為正整數(shù)。為正整數(shù)。解解 設(shè)數(shù)列設(shè)數(shù)列bk 的指數(shù)型生成函數(shù)為的指數(shù)型生成函數(shù)為Gebk，則有，則有因此，因此，65.4 Catalan數(shù)列的生成函數(shù)數(shù)列的生成函數(shù)n5.4.1 Catalan數(shù)列的生成函數(shù)數(shù)列的生成函數(shù)nCatalan數(shù)首先是由數(shù)首先是由Euler在精確計(jì)算對(duì)凸在精確計(jì)算對(duì)凸n邊形的不邊形的不同的對(duì)角三角形剖分的個(gè)數(shù)問(wèn)題時(shí)得到的，它經(jīng)常同的對(duì)角三角形剖分的個(gè)數(shù)問(wèn)題時(shí)得到的，它經(jīng)常出現(xiàn)在組合計(jì)數(shù)問(wèn)題中。出現(xiàn)在組合計(jì)數(shù)問(wèn)題中。n定義定義:一個(gè)凸一個(gè)凸n+1 邊形，通過(guò)不相交于邊形，通過(guò)不相交于n+1邊形內(nèi)部邊形內(nèi)部的對(duì)角線把的對(duì)角線把n+1邊形拆分成的三角形個(gè)數(shù)，記作邊形拆分成的三角形個(gè)數(shù)，記作hn稱為稱為Catalan數(shù)數(shù).7例如五邊形有如下五種拆分方案，所以例如五邊形有如下五種拆分方案，所以h4=58例5.4.1 在一個(gè)凸n+1邊形中，可以用(n-2)條不在內(nèi)部相交的對(duì)角線將其剖分成(n-1)個(gè)三角形，問(wèn)有多少種不同的分法？解解 令令 表示將一個(gè)凸表示將一個(gè)凸(n+1)邊形剖為三角形的方法數(shù)，規(guī)定邊形剖為三角形的方法數(shù)，規(guī)定 。當(dāng)當(dāng)n=2時(shí)，時(shí)，(n+1)邊形就是三角形，不需剖分，故邊形就是三角形，不需剖分，故 當(dāng)當(dāng) 考慮一個(gè)凸考慮一個(gè)凸(n+1)邊形，它的頂點(diǎn)分別用邊形，它的頂點(diǎn)分別用 表示，如圖表示，如圖5.4.1所示。取邊所示。取邊 ，任取頂點(diǎn)，任取頂點(diǎn) 將將 分別與分別與 之間連線，得三角形之間連線，得三角形T，三角形，三角形T將凸將凸(n+1)邊形分成邊形分成 T，R 1和和R 2 三部分，其中，三部分，其中，R 1為為(k+1)邊形，邊形，R 2為為(n-k+1)邊形。因此，邊形。因此，R 1可以用可以用 種方法剖分，種方法剖分，R 2 可以用可以用 種方法剖分，所以種方法剖分，所以 這正是這正是Catalan數(shù)列的通項(xiàng)公式。數(shù)列的通項(xiàng)公式。910TR2R1A1An+1Ak+2AkAk+1那么如何求那么如何求 ,本節(jié)用本節(jié)用 的生成函數(shù)的生成函數(shù) 來(lái)計(jì)算。來(lái)計(jì)算。解解 得得11 利用牛頓二項(xiàng)式定理，有利用牛頓二項(xiàng)式定理，有因?yàn)橐驗(yàn)?，開(kāi)方應(yīng)該取負(fù)號(hào)，故舍去，開(kāi)方應(yīng)該取負(fù)號(hào)，故舍去顯然一個(gè)凸顯然一個(gè)凸n+1邊形中有邊形中有 種不同的剖分方法。種不同的剖分方法。12 一般地，我們把一般地，我們把 稱為第稱為第k個(gè)個(gè)Catalan數(shù)，用數(shù)，用Cn表示，有表示，有 對(duì)于對(duì)于Ck-1和和Ck的形式我們并不陌生，例的形式我們并不陌生，例3.4.6的結(jié)論是從（的結(jié)論是從（0，0）點(diǎn)到）點(diǎn)到（n,n）點(diǎn)的除端點(diǎn)外不接觸直線）點(diǎn)的除端點(diǎn)外不接觸直線y=x的路徑數(shù)為的路徑數(shù)為 ,從從(0,0)點(diǎn)到（點(diǎn)到（n,n）點(diǎn)的除端點(diǎn)外不穿過(guò)直線）點(diǎn)的除端點(diǎn)外不穿過(guò)直線y=x 的路徑數(shù)為的路徑數(shù)為 如果用如果用Catalan數(shù)表示就是，從（數(shù)表示就是，從（0，0）點(diǎn)到（）點(diǎn)到（n,n）點(diǎn)的除端點(diǎn)外不）點(diǎn)的除端點(diǎn)外不接觸直線接觸直線y=x的路徑數(shù)為的路徑數(shù)為 ，從（，從（0，0）點(diǎn)到（）點(diǎn)到（n,n）點(diǎn)的除端）點(diǎn)的除端點(diǎn)外不穿過(guò)直線點(diǎn)外不穿過(guò)直線y=x的路徑數(shù)為的路徑數(shù)為 。13Catalan數(shù)列的數(shù)列的應(yīng)用應(yīng)用1)不同構(gòu)的有不同構(gòu)的有n 條邊的種植樹(shù)條邊的種植樹(shù)(planted tree)的棵數(shù)是的棵數(shù)是Catalan 數(shù)數(shù)Cn 。2)有有n 片樹(shù)葉的有序三度根樹(shù)的個(gè)數(shù)是片樹(shù)葉的有序三度根樹(shù)的個(gè)數(shù)是Catalan 數(shù)數(shù)Cn-1。3)n 個(gè)頂點(diǎn)的不同二元樹(shù)的個(gè)數(shù)是個(gè)頂點(diǎn)的不同二元樹(shù)的個(gè)數(shù)是Catalan 數(shù)數(shù)Cn。二元樹(shù)的定義。二元樹(shù)的定義:空空集或一組有限個(gè)頂點(diǎn)集或一組有限個(gè)頂點(diǎn),滿足滿足:有一個(gè)特定的點(diǎn)稱作有一個(gè)特定的點(diǎn)稱作“根點(diǎn)根點(diǎn)”;去去掉這個(gè)根點(diǎn)后掉這個(gè)根點(diǎn)后,余下的頂點(diǎn)組成兩支子二元樹(shù)余下的頂點(diǎn)組成兩支子二元樹(shù):左子樹(shù)與右子樹(shù)。左子樹(shù)與右子樹(shù)。4)從點(diǎn)從點(diǎn)(0,0)到點(diǎn)到點(diǎn)(n+1,n+1),除端點(diǎn)外與對(duì)角線不相交的除端點(diǎn)外與對(duì)角線不相交的(在對(duì)角線在對(duì)角線一側(cè)的一側(cè)的)非降路徑數(shù)是非降路徑數(shù)是Catalan 數(shù)數(shù)Cn。5)2n 個(gè)均勻分布在一個(gè)圓周上個(gè)均勻分布在一個(gè)圓周上,用用n 條不相交的弦將這條不相交的弦將這2n 個(gè)點(diǎn)配成個(gè)點(diǎn)配成n 對(duì)對(duì),則不同的配對(duì)方式數(shù)是則不同的配對(duì)方式數(shù)是Catalan 數(shù)數(shù)Cn。6)n 個(gè)個(gè)1 和和n 個(gè)個(gè)0 組成一組成一2n 位的二進(jìn)制數(shù)位的二進(jìn)制數(shù),要求從左到右掃描要求從左到右掃描,1 的累計(jì)的累計(jì)數(shù)不小于數(shù)不小于0 的累計(jì)數(shù)的累計(jì)數(shù),滿足這一條件的滿足這一條件的2n 位的二進(jìn)制數(shù)的個(gè)數(shù)是位的二進(jìn)制數(shù)的個(gè)數(shù)是Cn14Catalan數(shù)列的數(shù)列的應(yīng)用應(yīng)用7)在兩個(gè)候選人在兩個(gè)候選人A 和和B 的投票選舉中的投票選舉中,共有共有2n 個(gè)人投票個(gè)人投票,最終結(jié)果是支持最終結(jié)果是支持A 和和B 票數(shù)都是票數(shù)都是n 票。在開(kāi)票過(guò)程中始終使票。在開(kāi)票過(guò)程中始終使A 的票數(shù)不少于的票數(shù)不少于B 的票數(shù)的投票的票數(shù)的投票方案數(shù)是方案數(shù)是Catalan 數(shù)數(shù)Cn。8)有有2n 個(gè)人在劇院票房門前準(zhǔn)備買票入場(chǎng)。每張票價(jià)是個(gè)人在劇院票房門前準(zhǔn)備買票入場(chǎng)。每張票價(jià)是50 美分美分,而且此時(shí)而且此時(shí)票房售票員沒(méi)有零錢。這票房售票員沒(méi)有零錢。這2n 個(gè)人恰好有個(gè)人恰好有n 個(gè)人有個(gè)人有50 美分的錢美分的錢,其余其余n 個(gè)人個(gè)人只有只有1 美元的錢。如果在任何時(shí)候售票員都能找開(kāi)零錢的美元的錢。如果在任何時(shí)候售票員都能找開(kāi)零錢的2n 個(gè)人的排列個(gè)人的排列方法數(shù)是方法數(shù)是Catalan 數(shù)數(shù)Cn。9)有有2n 個(gè)高低不同的人個(gè)高低不同的人,排成兩行排成兩行,使得第一排使得第一排n 個(gè)人都比第二排個(gè)人都比第二排n 個(gè)人高的個(gè)人高的排列方法數(shù)是排列方法數(shù)是Catalan 數(shù)數(shù)Cn。10)設(shè)設(shè)a1,a2,an 與與b1,b2,bn 是兩個(gè)完全不同的序列是兩個(gè)完全不同的序列,則把這兩個(gè)序列融合則把這兩個(gè)序列融合在一起組成一個(gè)新的序列在一起組成一個(gè)新的序列，使得后一個(gè)序列與前一個(gè)序列相對(duì)應(yīng)的數(shù)始使得后一個(gè)序列與前一個(gè)序列相對(duì)應(yīng)的數(shù)始終排在前一個(gè)序列數(shù)后面的排列的個(gè)數(shù)是終排在前一個(gè)序列數(shù)后面的排列的個(gè)數(shù)是Catalan 數(shù)數(shù)。15Catalan數(shù)列的數(shù)列的應(yīng)用應(yīng)用11)有有2n 個(gè)人圍著圓桌就坐個(gè)人圍著圓桌就坐,手臂不相交的握手的方法數(shù)是手臂不相交的握手的方法數(shù)是Catalan 數(shù)數(shù)Cn12)n 個(gè)數(shù)相乘個(gè)數(shù)相乘,不改變它們的位置不改變它們的位置,只用括號(hào)表示不同的相乘順序只用括號(hào)表示不同的相乘順序,則構(gòu)成不則構(gòu)成不同的乘積的方法數(shù)同的乘積的方法數(shù)Catalan 數(shù)數(shù)Cn-1。例如：例如：n=4，161718