《組合數(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.2 組合數(shù)的生成函數(shù)組合數(shù)的生成函數(shù)我們在前面幾章中討論過三種不同類型的組合問題：我們在前面幾章中討論過三種不同類型的組合問題：n求求 的的r組合數(shù)；組合數(shù)；n求求 的的r組合數(shù)；組合數(shù)；n求求 的的10組合數(shù)。組合數(shù)。n其中其中:n問題（問題（1）是普通集合的組合問題；）是普通集合的組合問題；n問題（問題（2）轉(zhuǎn)化為不定方程）轉(zhuǎn)化為不定方程 的非負(fù)整數(shù)解的個(gè)數(shù)的非負(fù)整數(shù)解的個(gè)數(shù)問題；問題；n問題（問題（3）是第四章的例子，利用容斥原理來計(jì)數(shù)。它們在解）是第四章的例子，利用容斥原理來計(jì)數(shù)。它們在解題方法上各不相同。題方法上各不相同。n下面我們將看到，引入生成函數(shù)的概念后，上述三類組合問下面我們將看到，引入生成函數(shù)的概念后，上述三類組合問題可以統(tǒng)一地處理題可以統(tǒng)一地處理2n定理定理 5.3.1 設(shè)多重集設(shè)多重集 ，則則M的的k-組合數(shù)組合數(shù) ck 對應(yīng)序列對應(yīng)序列 的生成函數(shù)為的生成函數(shù)為 n其中，其中，ck 為為 展開式中展開式中 的系數(shù)。的系數(shù)。3證明證明:令令 中各中各 的項(xiàng)分別對應(yīng)的項(xiàng)分別對應(yīng)各個(gè)各個(gè)元素的元素的可能取法。例如可能取法。例如，對，對 時(shí)時(shí)x2表示元素表示元素a2 選取了選取了 2次次，其中，其中依次類推。依次類推。展開式中的項(xiàng)展開式中的項(xiàng) xk 具有一般形式具有一般形式 其中其中 對此方程的一非負(fù)整數(shù)解對此方程的一非負(fù)整數(shù)解 (滿足條件滿足條件 下下)，相應(yīng)的相應(yīng)的 就對應(yīng)了就對應(yīng)了M的的一個(gè)一個(gè)k-組合組合因此因此合并同類項(xiàng)后，合并同類項(xiàng)后，xk的系數(shù)就表示了的系數(shù)就表示了M的的k-組合數(shù)組合數(shù)。4n例例5.2.1 利用生成函數(shù)方法求利用生成函數(shù)方法求 的的k-組合數(shù)。組合數(shù)。5解解 設(shè)設(shè) 的的k-組合數(shù)為組合數(shù)為 ，則，則數(shù)列數(shù)列 的生成函數(shù)為：的生成函數(shù)為：其中其中 的系數(shù)就是的系數(shù)就是 M 的的k-組合數(shù)組合數(shù) ，這個(gè)結(jié)果顯然與第三章中定理這個(gè)結(jié)果顯然與第三章中定理3.3.3是一致的。是一致的。6n推論推論5.2.1 設(shè)設(shè) ，若限定在，若限定在k-組合中元素組合中元素 出現(xiàn)的次數(shù)集合為出現(xiàn)的次數(shù)集合為 ，則從，則從M的的k-組合數(shù)組合數(shù) 對應(yīng)序列對應(yīng)序列 的生成函數(shù)為的生成函數(shù)為7n例例5.2.2 用生成函數(shù)方法求多重集合用生成函數(shù)方法求多重集合 的的10-組合數(shù)。組合數(shù)。解解 將將 的的k-組合數(shù)記為組合數(shù)記為 ，的生的生成函數(shù)是成函數(shù)是所以，所以，的系數(shù)的系數(shù) 為為與第與第4章中用容斥原理得到的結(jié)果相同。章中用容斥原理得到的結(jié)果相同。8n在普通集合在普通集合 的的k-組合中，組合中，或出現(xiàn)或不出現(xiàn)，故其或出現(xiàn)或不出現(xiàn)，故其k-組合數(shù)數(shù)列組合數(shù)數(shù)列 的生成函數(shù)為的生成函數(shù)為 從而從而例例5.2.3 求求 的每個(gè)元素至少的每個(gè)元素至少取一次的取一次的k-組合數(shù)。組合數(shù)。9n解解 設(shè)設(shè) 的每個(gè)元素至少取一的每個(gè)元素至少取一次的次的k-組合數(shù)組合數(shù) 對應(yīng)數(shù)列對應(yīng)數(shù)列 的生成函數(shù)為的生成函數(shù)為 為為 的系數(shù)的系數(shù) 。10n例例5.2.4 求方程求方程 的整數(shù)解的個(gè)數(shù)。的整數(shù)解的個(gè)數(shù)。解：解：設(shè)方程的設(shè)方程的 整數(shù)解數(shù)為整數(shù)解數(shù)為 ，數(shù)列，數(shù)列 對應(yīng)的生成函數(shù)為對應(yīng)的生成函數(shù)為我們所求的是我們所求的是 為為 展開式中展開式中 的系數(shù)的系數(shù)11n例例5.2.5 求方程求方程 x1+2x2=15 的非負(fù)整數(shù)解的個(gè)數(shù)。的非負(fù)整數(shù)解的個(gè)數(shù)。n解解 設(shè)方程設(shè)方程 x1+2x2=k 的非負(fù)整數(shù)解的個(gè)數(shù)為的非負(fù)整數(shù)解的個(gè)數(shù)為 ak ,ak的生成函數(shù)為的生成函數(shù)為 因此，因此，a15=8.12n例例5.2.6 假定有足夠多的蘋果、香蕉、橘子和梨，用這假定有足夠多的蘋果、香蕉、橘子和梨，用這4種水果裝成由種水果裝成由k個(gè)水果的構(gòu)成水果袋，要求水果袋中個(gè)水果的構(gòu)成水果袋，要求水果袋中蘋果數(shù)為偶數(shù)，香蕉數(shù)是蘋果數(shù)為偶數(shù)，香蕉數(shù)是5的倍數(shù)，橘子最多有的倍數(shù)，橘子最多有4個(gè)，個(gè)，梨的個(gè)數(shù)是梨的個(gè)數(shù)是0或者或者1，求可以有多少種不同的裝法？，求可以有多少種不同的裝法？n解解 設(shè)有設(shè)有ck種裝法，則數(shù)列種裝法，則數(shù)列ck對應(yīng)的生成函數(shù)對應(yīng)的生成函數(shù)n因此，有因此，有k+1種不同的裝法。種不同的裝法。135.5.1 有序分拆有序分拆定理定理5.5.1 對于對于n的的k有序分拆有序分拆其其k有序分拆數(shù)數(shù)列有序分拆數(shù)數(shù)列 的生成函數(shù)是的生成函數(shù)是這個(gè)定理等價(jià)于如下分配模型：即把這個(gè)定理等價(jià)于如下分配模型：即把n個(gè)相同的球放入個(gè)相同的球放入k個(gè)不同的盒子里，第個(gè)不同的盒子里，第i個(gè)盒的容量為個(gè)盒的容量為 ，且使每盒非空，且使每盒非空的方案數(shù)為的方案數(shù)為14n推論推論5.5.1 若對若對n的的k有序分拆的各分量有序分拆的各分量()沒有沒有限制，則其限制，則其k有序分拆數(shù)數(shù)列有序分拆數(shù)數(shù)列 的生成函數(shù)是的生成函數(shù)是 ，且且 155.5.2 無序分拆無序分拆n在在3.6節(jié)中可知無序分拆和有序分拆的區(qū)別在于是否考節(jié)中可知無序分拆和有序分拆的區(qū)別在于是否考慮分拆后的各分量的順序，慮分拆后的各分量的順序，n將將n分拆為分拆為k個(gè)分部（每一分部的大小不受限制）的分個(gè)分部（每一分部的大小不受限制）的分拆數(shù)等于將拆數(shù)等于將n分拆為最大分部為分拆為最大分部為k（分部個(gè)數(shù)不限）的（分部個(gè)數(shù)不限）的分拆數(shù)，該分拆數(shù)也記為分拆數(shù)，該分拆數(shù)也記為 16定理定理5.5.2 令令B(n)表示正整數(shù)表示正整數(shù) 的所有分拆數(shù)，的所有分拆數(shù)，Bk(n)表示表示 n的各分部量都不超過的各分部量都不超過 k的分拆數(shù)，則它們相應(yīng)的生成的分拆數(shù)，則它們相應(yīng)的生成函數(shù)分別為函數(shù)分別為(1)(2)(3)17（1）等于不定方程等于不定方程 的非負(fù)整數(shù)解的個(gè)數(shù)。因此其分拆數(shù)列的生成函數(shù)為的非負(fù)整數(shù)解的個(gè)數(shù)。因此其分拆數(shù)列的生成函數(shù)為 其中展開式中其中展開式中 的系數(shù)即為的系數(shù)即為n的最大分項(xiàng)不超過的最大分項(xiàng)不超過k的分拆個(gè)的分拆個(gè)數(shù)。數(shù)。18（2）根據(jù)定理根據(jù)定理 3.6.3知，將知，將n分拆為分拆為k個(gè)分部（每一分部的大個(gè)分部（每一分部的大小不受限制）的分拆數(shù)等于將小不受限制）的分拆數(shù)等于將n分拆為最大分部為分拆為最大分部為k（分部（分部個(gè)數(shù)不限）的分拆數(shù)，其分拆數(shù)相當(dāng)于求方程個(gè)數(shù)不限）的分拆數(shù)，其分拆數(shù)相當(dāng)于求方程的整數(shù)解的個(gè)數(shù)，其生成函數(shù)為的整數(shù)解的個(gè)數(shù)，其生成函數(shù)為19其中展開式中其中展開式中 的系數(shù)即為的系數(shù)即為n的最大分項(xiàng)等于的最大分項(xiàng)等于k的分拆個(gè)數(shù)的分拆個(gè)數(shù)若若 ，則，則 ，因此當(dāng)，因此當(dāng) ，它，它們對應(yīng)的生成函數(shù)的系數(shù)為零，所以們對應(yīng)的生成函數(shù)的系數(shù)為零，所以20容易證明：容易證明：，因此，因此21（3）等于不定方程等于不定方程 的非負(fù)整數(shù)解的個(gè)數(shù)。因此其分拆數(shù)列的生成函數(shù)為的非負(fù)整數(shù)解的個(gè)數(shù)。因此其分拆數(shù)列的生成函數(shù)為 22推論推論5.5.2 n 的各分部量兩兩互不相同的分拆數(shù)等于的各分部量兩兩互不相同的分拆數(shù)等于 n的的各分部量是奇數(shù)的分拆數(shù)。各分部量是奇數(shù)的分拆數(shù)。證明證明 n的各分部量兩兩互不相同的分拆數(shù)的生成函數(shù)為的各分部量兩兩互不相同的分拆數(shù)的生成函數(shù)為 而而 顯然是顯然是n的各分部量是奇數(shù)的分拆的各分部量是奇數(shù)的分拆 數(shù)數(shù)列的生成函數(shù)，因此結(jié)論成立數(shù)數(shù)列的生成函數(shù)，因此結(jié)論成立.23例例 5.5.1 用用1角、角、2角、角、3角的郵票貼出面值角的郵票貼出面值6角，求有多少種不角，求有多少種不同的方案？同的方案？解解 這是可重復(fù)的無序分拆，相應(yīng)的生成函數(shù)為這是可重復(fù)的無序分拆，相應(yīng)的生成函數(shù)為顯然所求為顯然所求為 的系數(shù)，為的系數(shù)，為7，說明貼出，說明貼出6角面值的方案有角面值的方案有7種。具體為：種。具體為：6=1+1+1+1，6=2+2+2，6=2+2+1+1，6=2+1+1+1+1，6=3+3，6=3+2+1，6=3+1+1+1.例例5.5.1中，若考慮不同面值貼的順序，則有多少種方案。此問題留作習(xí)題中，若考慮不同面值貼的順序，則有多少種方案。此問題留作習(xí)題245.3 指數(shù)型生成函數(shù)與指數(shù)型生成函數(shù)與多重集的排列數(shù)多重集的排列數(shù)25n當(dāng)涉及到與排列有關(guān)的問題時(shí)，需要引入指數(shù)型生成當(dāng)涉及到與排列有關(guān)的問題時(shí)，需要引入指數(shù)型生成函數(shù)。函數(shù)。n例如例如n 元集合的元集合的k 排列數(shù)為排列數(shù)為 ，n 其對應(yīng)的組合型生成函數(shù)其對應(yīng)的組合型生成函數(shù)為：為：n 沒有簡單的解析表達(dá)式，但如果把基底函數(shù)沒有簡單的解析表達(dá)式，但如果把基底函數(shù) 改換成改換成 n ，則，則n這啟發(fā)人們引入指數(shù)型生成函數(shù)的概念。這啟發(fā)人們引入指數(shù)型生成函數(shù)的概念。5.3 指數(shù)型生成函數(shù)與指數(shù)型生成函數(shù)與多重集的排列數(shù)多重集的排列數(shù)n定義定義5.3.1 數(shù)列數(shù)列 的指數(shù)型生成函數(shù)定義的指數(shù)型生成函數(shù)定義為形式冪級數(shù)為形式冪級數(shù)記為記為 或者或者26n例如，考慮前面多次提到的數(shù)列例如，考慮前面多次提到的數(shù)列1,1,1，根據(jù)定義，根據(jù)定義5.3.1有有 ，而根據(jù)高等數(shù)學(xué)的知識，而根據(jù)高等數(shù)學(xué)的知識，因此因此n特別地，數(shù)列特別地，數(shù)列 的指數(shù)型生成函數(shù)的指數(shù)型生成函數(shù) 具有與指數(shù)函數(shù)相似具有與指數(shù)函數(shù)相似的性質(zhì)：的性質(zhì)：2728例例5.3.1 求排列數(shù)數(shù)列求排列數(shù)數(shù)列 的指數(shù)型生成函數(shù)的指數(shù)型生成函數(shù)，其其中中 解：解：設(shè)要求的生成函數(shù)為設(shè)要求的生成函數(shù)為Ge(x)，根據(jù)定義，根據(jù)定義5.1.129例例5.3.2 求多重集合求多重集合 的的k-排列數(shù)排列數(shù)bk.解解 設(shè)數(shù)列設(shè)數(shù)列bk 的指數(shù)型生成函數(shù)為的指數(shù)型生成函數(shù)為Gebk，根據(jù)定理，根據(jù)定理5.3.1有，有，從而從而 ，與第，與第3章中的結(jié)果是一致的。章中的結(jié)果是一致的。30定理定理 5.3.1 設(shè)設(shè) ,考慮考慮 M 的的k-排列排列若要求在若要求在k-排列中元素排列中元素 出現(xiàn)次數(shù)構(gòu)成的集合為出現(xiàn)次數(shù)構(gòu)成的集合為 (1in)，則，則 k-排列數(shù)排列數(shù) 對應(yīng)數(shù)列對應(yīng)數(shù)列 的生成函數(shù)為的生成函數(shù)為 31證明證明根據(jù)和式的性質(zhì)，上式右端等于根據(jù)和式的性質(zhì)，上式右端等于由多項(xiàng)式系數(shù)的組合學(xué)意義知，由多項(xiàng)式系數(shù)的組合學(xué)意義知，正是元素正是元素 出現(xiàn)出現(xiàn) 次，元素次，元素 出現(xiàn)出現(xiàn) 次次，元素，元素 出現(xiàn)出現(xiàn) 次的次的 k-排列數(shù)。故按所有可能的排列數(shù)。故按所有可能的 求和，即得總的求和，即得總的k-排列數(shù)排列數(shù) 。有了定理定理有了定理定理 5.3.1，我們就可以方便的計(jì)算多重集的排列數(shù)，我們就可以方便的計(jì)算多重集的排列數(shù)32例例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種。種。33例例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.34例例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，則有，則有因此，因此，355.4 Catalan數(shù)列的生成函數(shù)數(shù)列的生成函數(shù)n5.4.1 Catalan數(shù)列的生成函數(shù)數(shù)列的生成函數(shù)nCatalan數(shù)首先是由數(shù)首先是由Euler在精確計(jì)算對凸在精確計(jì)算對凸n邊形的不邊形的不同的對角三角形剖分的個(gè)數(shù)問題時(shí)得到的，它經(jīng)常同的對角三角形剖分的個(gè)數(shù)問題時(shí)得到的，它經(jīng)常出現(xiàn)在組合計(jì)數(shù)問題中。出現(xiàn)在組合計(jì)數(shù)問題中。n定義定義:一個(gè)凸一個(gè)凸n+1 邊形，通過不相交于邊形，通過不相交于n+1邊形內(nèi)部邊形內(nèi)部的對角線把的對角線把n+1邊形拆分成的三角形個(gè)數(shù)，記作邊形拆分成的三角形個(gè)數(shù)，記作hn稱為稱為Catalan數(shù)數(shù).365.4 Catalan數(shù)列的生成函數(shù)數(shù)列的生成函數(shù)n5.4.1 Catalan數(shù)列的生成函數(shù)數(shù)列的生成函數(shù)nCatalan數(shù)首先是由數(shù)首先是由Euler在精確計(jì)算對凸在精確計(jì)算對凸n邊形的不邊形的不同的對角三角形剖分的個(gè)數(shù)問題時(shí)得到的，它經(jīng)常同的對角三角形剖分的個(gè)數(shù)問題時(shí)得到的，它經(jīng)常出現(xiàn)在組合計(jì)數(shù)問題中。出現(xiàn)在組合計(jì)數(shù)問題中。n定義定義:一個(gè)凸一個(gè)凸n+1 邊形，通過不相交于邊形，通過不相交于n+1邊形內(nèi)部邊形內(nèi)部的對角線把的對角線把n+1邊形拆分成的三角形個(gè)數(shù)，記作邊形拆分成的三角形個(gè)數(shù)，記作hn稱為稱為Catalan數(shù)數(shù).37例如五邊形有如下五種拆分方案，所以例如五邊形有如下五種拆分方案，所以h4=538例5.4.1 在一個(gè)凸n+1邊形中，可以用(n-2)條不在內(nèi)部相交的對角線將其剖分成(n-1)個(gè)三角形，問有多少種不同的分法？解解 令令 表示將一個(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)公式。3940TR2R1A1An+1Ak+2AkAk+1那么如何求那么如何求 ,本節(jié)用本節(jié)用 的生成函數(shù)的生成函數(shù) 來計(jì)算。來計(jì)算。解解 得得41 利用牛頓二項(xiàng)式定理，有利用牛頓二項(xiàng)式定理，有因?yàn)橐驗(yàn)?，開方應(yīng)該取負(fù)號，故舍去，開方應(yīng)該取負(fù)號，故舍去顯然一個(gè)凸顯然一個(gè)凸n+1邊形中有邊形中有 種不同的剖分方法。種不同的剖分方法。42 一般地，我們把一般地，我們把 稱為第稱為第k個(gè)個(gè)Catalan數(shù)，用數(shù)，用Cn表示，有表示，有 對于對于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)外不穿過直線）點(diǎn)的除端點(diǎn)外不穿過直線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)外不穿過直線點(diǎn)外不穿過直線y=x的路徑數(shù)為的路徑數(shù)為 。43Catalan數(shù)列的數(shù)列的應(yīng)用應(yīng)用1)不同構(gòu)的有不同構(gòu)的有n 條邊的種植樹條邊的種植樹(planted tree)的棵數(shù)是的棵數(shù)是Catalan 數(shù)數(shù)Cn 。2)有有n 片樹葉的有序三度根樹的個(gè)數(shù)是片樹葉的有序三度根樹的個(gè)數(shù)是Catalan 數(shù)數(shù)Cn-1。3)n 個(gè)頂點(diǎn)的不同二元樹的個(gè)數(shù)是個(gè)頂點(diǎn)的不同二元樹的個(gè)數(shù)是Catalan 數(shù)數(shù)Cn。二元樹的定義。二元樹的定義:空空集或一組有限個(gè)頂點(diǎn)集或一組有限個(gè)頂點(diǎn),滿足滿足:有一個(gè)特定的點(diǎn)稱作有一個(gè)特定的點(diǎn)稱作“根點(diǎn)根點(diǎn)”;去去掉這個(gè)根點(diǎn)后掉這個(gè)根點(diǎn)后,余下的頂點(diǎn)組成兩支子二元樹余下的頂點(diǎn)組成兩支子二元樹:左子樹與右子樹。左子樹與右子樹。4)從點(diǎn)從點(diǎn)(0,0)到點(diǎn)到點(diǎn)(n+1,n+1),除端點(diǎn)外與對角線不相交的除端點(diǎn)外與對角線不相交的(在對角線在對角線一側(cè)的一側(cè)的)非降路徑數(shù)是非降路徑數(shù)是Catalan 數(shù)數(shù)Cn。5)2n 個(gè)均勻分布在一個(gè)圓周上個(gè)均勻分布在一個(gè)圓周上,用用n 條不相交的弦將這條不相交的弦將這2n 個(gè)點(diǎn)配成個(gè)點(diǎn)配成n 對對,則不同的配對方式數(shù)是則不同的配對方式數(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ù)是Cn44Catalan數(shù)列的數(shù)列的應(yīng)用應(yīng)用7)在兩個(gè)候選人在兩個(gè)候選人A 和和B 的投票選舉中的投票選舉中,共有共有2n 個(gè)人投票個(gè)人投票,最終結(jié)果是支持最終結(jié)果是支持A 和和B 票數(shù)都是票數(shù)都是n 票。在開票過程中始終使票。在開票過程中始終使A 的票數(shù)不少于的票數(shù)不少于B 的票數(shù)的投票的票數(shù)的投票方案數(shù)是方案數(shù)是Catalan 數(shù)數(shù)Cn。8)有有2n 個(gè)人在劇院票房門前準(zhǔn)備買票入場。每張票價(jià)是個(gè)人在劇院票房門前準(zhǔn)備買票入場。每張票價(jià)是50 美分美分,而且此時(shí)而且此時(shí)票房售票員沒有零錢。這票房售票員沒有零錢。這2n 個(gè)人恰好有個(gè)人恰好有n 個(gè)人有個(gè)人有50 美分的錢美分的錢,其余其余n 個(gè)人個(gè)人只有只有1 美元的錢。如果在任何時(shí)候售票員都能找開零錢的美元的錢。如果在任何時(shí)候售票員都能找開零錢的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è)序列相對應(yīng)的數(shù)始使得后一個(gè)序列與前一個(gè)序列相對應(yīng)的數(shù)始終排在前一個(gè)序列數(shù)后面的排列的個(gè)數(shù)是終排在前一個(gè)序列數(shù)后面的排列的個(gè)數(shù)是Catalan 數(shù)數(shù)。45Catalan數(shù)列的數(shù)列的應(yīng)用應(yīng)用11)有有2n 個(gè)人圍著圓桌就坐個(gè)人圍著圓桌就坐,手臂不相交的握手的方法數(shù)是手臂不相交的握手的方法數(shù)是Catalan 數(shù)數(shù)Cn12)n 個(gè)數(shù)相乘個(gè)數(shù)相乘,不改變它們的位置不改變它們的位置,只用括號表示不同的相乘順序只用括號表示不同的相乘順序,則構(gòu)成不則構(gòu)成不同的乘積的方法數(shù)同的乘積的方法數(shù)Catalan 數(shù)數(shù)Cn-1。例如：例如：n=4，464748