特殊計數(shù)序列

1、1第八章第八章 特殊計數(shù)序列特殊計數(shù)序列8.1 Catalan數(shù)數(shù)前面我們已經(jīng)討論過一些特殊計數(shù)序列的例子。前面我們已經(jīng)討論過一些特殊計數(shù)序列的例子。如：斐波那契序列如：斐波那契序列： f n = f n-1 + f n-2 (n 3) 翰若塔問題序列：翰若塔問題序列： hn = 2hn-1+ 1 (n 1) 錯位排列數(shù)序列：錯位排列數(shù)序列：D0, D1, D2, D3, Dn, 等等 本節(jié)我們將繼續(xù)研究本節(jié)我們將繼續(xù)研究4個著名的計數(shù)序列個著名的計數(shù)序列28.1 Catalan數(shù)數(shù) Catalan(卡特朗卡特朗)序列其遞推關(guān)系是序列其遞推關(guān)系是非線性非線性的的,許多有意義的計數(shù)問題都導(dǎo)致這樣

2、的遞推許多有意義的計數(shù)問題都導(dǎo)致這樣的遞推關(guān)系。本次課將舉出一些關(guān)系。本次課將舉出一些,后面還將見到。后面還將見到。 通過下面的例題我們來引入通過下面的例題我們來引入Catalan(卡特卡特朗朗)序列。序列。例例 ： 二叉樹（或二元樹）的計數(shù)問題。二叉樹（或二元樹）的計數(shù)問題。如如 3個結(jié)點可有個結(jié)點可有5棵不同的二叉樹棵不同的二叉樹, 如下圖所示。如下圖所示。3 一般地，設(shè)一般地，設(shè)cn為為n個結(jié)點的不同的二叉樹的個結(jié)點的不同的二叉樹的個數(shù)，定義個數(shù)，定義c0=1。在。在n0的情形下，二叉樹有的情形下，二叉樹有一個根結(jié)點及一個根結(jié)點及n-1個非根結(jié)點，設(shè)左子樹個非根結(jié)點，設(shè)左子樹Tl有有k個

3、結(jié)點，則右子樹個結(jié)點，則右子樹Tr有有n-1-k個結(jié)點，于是每個個結(jié)點，于是每個不同的左子樹有不同的左子樹有ck種時，右子樹有種時，右子樹有cn-1-k種，由種，由計數(shù)原理：計數(shù)原理：4)0(,101ncccnkknkn令令由序列由序列cn構(gòu)成的生成函數(shù)為：構(gòu)成的生成函數(shù)為： B(x) = c0 + c1x + c2x2+ c3x3+cnxn+那么那么B(x)B(x) = (c0 + c1x + ) (c0 + c1x +c2x2+ ) B2(x) = (c0)2+ (c0 c1+c1c0) x + (c0 c2+c1 c1 +c2 c0)x2+ (c0 c3+c1 c2 +c2 c1+c3

4、c0 )x3+5nnkknknkkkkkkkkkxccxccxccxccccxB.)()(0033032202101002根據(jù)我們在第十九講中補充的關(guān)于生成函數(shù)有根據(jù)我們在第十九講中補充的關(guān)于生成函數(shù)有 關(guān)結(jié)論可知：關(guān)結(jié)論可知：)0(.01322110101ncccccccccccnnnnnkknkn6再由于序列再由于序列cn構(gòu)成的生成函數(shù)可以表示為構(gòu)成的生成函數(shù)可以表示為:比較發(fā)現(xiàn)與nnkknknnnnnnnnnkknknnnnxccxBxccccccccxccxcxB)(.)(00201322110010110B(x)與與B2(x)在第在第n項的系數(shù)只相差一項項的系數(shù)只相差一項nknknk

5、nnknknknxccxcc001010與7由于它們的首項都是由于它們的首項都是1,將將B(x)減去常數(shù)減去常數(shù)1后使得后使得和式的每個單項式的冪大于等于和式的每個單項式的冪大于等于1.再除以再除以x后后就得到生成函數(shù)為：就得到生成函數(shù)為： 與與B2(x) 的序列的生成函數(shù)化成一致。的序列的生成函數(shù)化成一致。 那么我們得到生成函數(shù)那么我們得到生成函數(shù)B(x)滿足的方程：滿足的方程： 其中其中B(0) =c0 =1 1)(10010111nknknknnknknknxccxccxxB)(1)(2xBxxB8解此二次方程，并應(yīng)用牛頓二項式定理解此二次方程，并應(yīng)用牛頓二項式定理(P95)得得: )4

6、(211 (1 21)4(21)4(021(1 21)4(211 212)41 (12411)(110021nnnnnnnxnxxnxxxnxxxxxxB9)(2)1(1)1(2)1(22)1()1(2)1(121:2)1(1212)1(21)4(2121)(95121)1(21)1(120122111211PnnnncxnxnxnxxBnnnnnnnnnnnnnnnnnn見因此作換元作換元10nnnnnncnnnnn2) 1(12) 1(22) 1() 1(1212這個數(shù)這個數(shù)Cn常稱為常稱為Catalan( (卡特朗卡特朗) )數(shù)數(shù), ,序列序列Cn常稱為常稱為Catalan( (卡特朗卡

7、特朗) )序列序列。常用第一個字母常用第一個字母C表示，記為：表示，記為：C0,C1,C2,C3,.Cn, 其中，其中，通項：通項：.)2, 1 ,0(211nnnnCn11定理定理8.1.1 n 個個+1 和和 n個個 1 構(gòu)成的構(gòu)成的 2n 項數(shù)列項數(shù)列 a1, a2, , a2n若其部分和滿足若其部分和滿足 a1a2 ak 0 k1,2,2n的數(shù)列的數(shù)列a1, a2. ak的個數(shù)等于第的個數(shù)等于第n個個Catalan數(shù)，即數(shù)，即證明：證明：n 個個+1 和和 n個個 1 構(gòu)成的構(gòu)成的 2n 項數(shù)列若其項數(shù)列若其部分和滿足部分和滿足 a1a2 ak 0.)2, 1 ,0(211nnnnCn

8、12則稱該數(shù)列是則稱該數(shù)列是可接受可接受的數(shù)列，否則是的數(shù)列，否則是不可接受不可接受的的 數(shù)列。令數(shù)列。令Sn是由是由n個個 +1 和和 n個個 1 構(gòu)成的構(gòu)成的2n項數(shù)列的全體，項數(shù)列的全體，An是其中可接受的部分，是其中可接受的部分，Un是其中不可接受的部分是其中不可接受的部分.于是于是: |Sn|An|Un| 而而: 可見，通過計算可見，通過計算|Un|進而計進而計算出算出|An|; 對每個不可接受序列，總可以找到對每個不可接受序列，總可以找到最小的最小的正奇數(shù)正奇數(shù)k，使得，使得ak=-1且且ak之前的之前的+1與與-1的個數(shù)相等，即有的個數(shù)相等，即有a1+a2+ak-1=0, ak

9、=-1。nnSn213例例: -1+1-1+1-1+1-1+1-1+1.其中其中a7 = -1 現(xiàn)將這個不可接受序列中前現(xiàn)將這個不可接受序列中前k項的每一項取項的每一項取反號，反號， 其余部分保持不變，其余部分保持不變， 得到新序列變?yōu)榈玫叫滦蛄凶優(yōu)閙+1個個+1和和m-1個個-1構(gòu)成的序列。構(gòu)成的序列。 例例: 1-1+1-1+1-1+1 1+1+1-1+1.注意有注意有兩個兩個1 1連連加加 反之，對任一由反之，對任一由n+1個個+1和和n-1個個-1構(gòu)成的序列，構(gòu)成的序列，從左到右掃描，當(dāng)從左到右掃描，當(dāng)+1的個數(shù)第一次比的個數(shù)第一次比-1的個數(shù)的個數(shù)多多1時就把這些掃描到的項全部取反號

10、，其余時就把這些掃描到的項全部取反號，其余,.,221naaa14項不變，結(jié)果又得到項不變，結(jié)果又得到n個個+1和和n個個-1構(gòu)成的不可接構(gòu)成的不可接 受序列。從而，易知不可接受序列的數(shù)目受序列。從而，易知不可接受序列的數(shù)目Un就與就與n+1個個+1和和n-1個個-1所成的序列的數(shù)目相等。所成的序列的數(shù)目相等。由于后者的數(shù)目為：由于后者的數(shù)目為： nnnnnnnnnnnnnnnnnnnnnnnnnnnnUSAnnnUnnnn21111!)!2()1(1()!1(!)!2()111()!1(!)!2()!1()!1()!2(!)!2()!1()!1()!2(2)!1()!1()!2(那么15 C

11、atalan數(shù)的組合學(xué)意義可羅列如下：數(shù)的組合學(xué)意義可羅列如下： （1）從）從(0，0)點沿第一象限的格線到點沿第一象限的格線到(n, n)點的不穿越方格對角線的最短路徑數(shù)；點的不穿越方格對角線的最短路徑數(shù)； （2） 序列序列a1a2ak的元素順序保持不變，的元素順序保持不變， 按不同結(jié)合方式插入合法圓括號對的方案數(shù)；按不同結(jié)合方式插入合法圓括號對的方案數(shù)； （3） 用用n-1條互不交叉的對角線把條互不交叉的對角線把n+2條邊條邊(n1)的凸多邊形拆分三角形化的方法數(shù)；的凸多邊形拆分三角形化的方法數(shù)； 16（4） 2n個人排隊上車，車票費為個人排隊上車，車票費為5角，角，2n個人個人 中有一半

12、人持有一元面值鈔票，一半人持中有一半人持有一元面值鈔票，一半人持有有5角鈔票，求不同的上車方案數(shù)，使得在這角鈔票，求不同的上車方案數(shù)，使得在這些方案中售票員總能用先上車的購票錢給后上些方案中售票員總能用先上車的購票錢給后上車者找零；車者找零； （5） 甲、乙二人比賽乒乓球，甲、乙二人比賽乒乓球， 最后結(jié)果為最后結(jié)果為n n，比賽過程中甲始終不落后于乙的計分，比賽過程中甲始終不落后于乙的計分種數(shù)；種數(shù)；17 （6） n個點的有序二叉樹的個數(shù)；個點的有序二叉樹的個數(shù)； （7） n個葉子的完全二叉數(shù)的個數(shù)；個葉子的完全二叉數(shù)的個數(shù)； （8） 圓周上圓周上2n個點連接成的個點連接成的n條兩兩互不條兩兩

13、互不相交的弦分割圓的方案數(shù)。相交的弦分割圓的方案數(shù)。 以 上以 上 8種 類 型 的 計 數(shù) 問 題種 類 型 的 計 數(shù) 問 題 , 是 典 型 的是 典 型 的Catalan數(shù)組合問題，我們僅僅對其中的部分?jǐn)?shù)組合問題，我們僅僅對其中的部分問題進行討論；問題進行討論；18 (1)從從O(0,0)點沿第一象限的格線到點沿第一象限的格線到N(n,n)點的點的 不穿越方格對角線不穿越方格對角線ON的最短路徑數(shù)；的最短路徑數(shù)； 沿格線前進不穿越對角線沿格線前進不穿越對角線(但可接觸對角線上的但可接觸對角線上的 格點格點)的路線分為走對角線上方或走對角線下方的路線分為走對角線上方或走對角線下方兩種情形

14、，由對稱性，易知兩種路線數(shù)相等。兩種情形，由對稱性，易知兩種路線數(shù)相等。 因此，只需計算走一方的路線數(shù)因此，只需計算走一方的路線數(shù)(不妨計算對角不妨計算對角線下方的路線數(shù)線下方的路線數(shù))。 設(shè)符合題意的路線為設(shè)符合題意的路線為好路線好路線，其總數(shù)記為，其總數(shù)記為gn；19即即:遇到對角線就向右遇到對角線就向右; 穿越對角線的路線記為穿越對角線的路線記為 壞路線壞路線，其總數(shù)記為，其總數(shù)記為bn。 (a)圖是圖是44方格方格中的中的壞路線壞路線，(b)圖是圖是44方格變?yōu)榉礁褡優(yōu)?3方格的方格的后的路線。后的路線。(a)(b)ONNO20易知易知nn方格上從左下角到右上角的每一條路方格上從左下角

15、到右上角的每一條路 線可用一個包含線可用一個包含n個個R(右右) 和和n個個U(上上)的字的字符串來描述。例如下圖所示的路線可用字符串符串來描述。例如下圖所示的路線可用字符串RUURRURU共共8個字符來表示，可以看出，個字符來表示，可以看出，R和和U的數(shù)量各占一半。這樣的字符串可以由在的數(shù)量各占一半。這樣的字符串可以由在給定的給定的2n個位置中為個位置中為R選擇選擇n個位置而不考慮順序，個位置而不考慮順序，其余其余n個位置填入個位置填入U。于是，。于是，21有有C(2n,n)種可能的路線。且有種可能的路線。且有g(shù)n+bn=C(2n, n)， 即：即：gn=C(2n, n)-bn, 故只需計算

16、壞路線數(shù)故只需計算壞路線數(shù)bn。 對任一壞路線，選定最初穿越對角線后的第對任一壞路線，選定最初穿越對角線后的第一次移動，并將此一次移動，并將此移動之后移動之后的右行改為上行，的右行改為上行，上行改為右行，這樣的變化使得向上移動增加上行改為右行，這樣的變化使得向上移動增加一個而向右移動減少一個一個而向右移動減少一個,即可得到一條即可得到一條(n+1)(n-1)方格上從左下角走到右上角不加限方格上從左下角走到右上角不加限制的路線；反之，制的路線；反之， 對任一對任一(n+1)(n-1)方格方格22上從左下角走到右上角不加限制的路線，從最上從左下角走到右上角不加限制的路線，從最 初位于對角線上方的第

17、一點起，改上移為初位于對角線上方的第一點起，改上移為右移，改右移為上移，即可得到一條右移，改右移為上移，即可得到一條nn方方格上格上(從從(0,0)點到點到(n,n)點點)的壞路線。亦即的壞路線。亦即, nn方格上的壞路線與方格上的壞路線與(n+1)(n-1)方格上的方格上的路線之間存在一一對應(yīng)。由于路線之間存在一一對應(yīng)。由于(n+1)(n-1)方方格的路線為格的路線為: C(2n, n+1)或或C(2n, n-1)，兩者相，兩者相等等, 故取故取bn=C(2n, n-1)。從而有：。從而有：23),2(1111!)!2() 1(1)!1( !)!2(111)!1( !)!2()!1()!1(

18、)!2(!)!2() 1,2(),2(),2(nnCnnnnnnnnnnnnnnnnnnnnnnnCnnCbnnCgnn 注意，在求對角線下方的好路線數(shù)時，每條注意，在求對角線下方的好路線數(shù)時，每條走過對角線上方的路線都作為壞路線計入了走過對角線上方的路線都作為壞路線計入了bn。進而，僅走對角線一側(cè)且不穿越對角線進而，僅走對角線一側(cè)且不穿越對角線 的的總路徑數(shù)為總路徑數(shù)為Catalan數(shù)：數(shù)：nnnnnCn211),2(1124（3）用互不交叉的對角線把）用互不交叉的對角線把n+1條邊條邊(n2) 的的 凸多邊形三角形化分的方法數(shù)；凸多邊形三角形化分的方法數(shù)；vkvk 1vk 1F1v1eF2

19、vk 2vnvn 1余點依次相鄰標(biāo)記余點依次相鄰標(biāo)記25 令令hn表示將表示將n+1(n2)邊凸多邊形進行三角邊凸多邊形進行三角 形拆分的方案數(shù)，則當(dāng)形拆分的方案數(shù)，則當(dāng)n=1時，時，h1=1，當(dāng)，當(dāng)n3時，任取多邊形一邊為時，任取多邊形一邊為基邊基邊記作記作e，其兩端，其兩端點一端記為點一端記為v1，一端記為，一端記為vn+1，余點依次相鄰，余點依次相鄰標(biāo)記如圖所示?，F(xiàn)以標(biāo)記如圖所示。現(xiàn)以v1，vn+1及任意頂點及任意頂點vk+1(k=1,2,n-1)構(gòu)作一個三角形，該三角形構(gòu)作一個三角形，該三角形將凸多邊形分為將凸多邊形分為F1, F2兩個區(qū)域。兩個區(qū)域。26其中，其中，F(xiàn)1由由k+1邊凸

20、多邊形圍成，其三角形拆分邊凸多邊形圍成，其三角形拆分 方案數(shù)為方案數(shù)為hk，F(xiàn)2由由n-k+1邊凸多邊形圍成，邊凸多邊形圍成，其三角形剖分方案數(shù)為其三角形剖分方案數(shù)為hn-k， F1與與F2的邊數(shù)關(guān)的邊數(shù)關(guān)系是系是: (k+1)+(n-k+1)+1-2 = n+1(總邊數(shù)總邊數(shù))vkvk 1vk 1F1v1eF2vk 2vnvn 127由乘法原理知由乘法原理知 易證易證 對于六邊形時對于六邊形時,即當(dāng)即當(dāng)n=5時時,可求得分拆三角形數(shù)可求得分拆三角形數(shù):11nkknknhhhnnnhnnnhnn2111221114485115252515h28 凸凸6邊形邊形(n=5)的的14個拆分方案個拆分

21、方案 其中從同一頂點引出其中從同一頂點引出3條對角線的有條對角線的有6種種；從；從兩個頂點各引出兩個頂點各引出2條對角線的又有條對角線的又有6種種；從；從3個互個互不相鄰點連接的有不相鄰點連接的有2種種，共，共14種。種。29 下面證明下面證明Catalan數(shù)滿足數(shù)滿足1階齊次遞推關(guān)系；階齊次遞推關(guān)系； 由于由于 所以有：所以有：1)1(124124)12)(2(11)!1()!1()!22(1!)!2(11011CnCnnCnnnnnnnnnnnnnnCCnnnn所以122(1)1111nnnnCCnnnn30 我們可義求出前幾項的我們可義求出前幾項的Catalan數(shù)的數(shù)值：數(shù)的數(shù)值： C0

22、 = 1 , C1 = 1 , C2 = 2 , C3 = 5 C4 = 14 , C5 =42 , C6 = 132, C7 =429 C8 =1430, C9 = 4862 ,. 現(xiàn)在我們定義一個新的數(shù)列：現(xiàn)在我們定義一個新的數(shù)列：為了方便給它取名叫做為了方便給它取名叫做擬擬- - Catalan數(shù)數(shù)。令：。令：,.,.,*3*2*1nCCCC,.)3 , 2 , 1(!1*nCnCnn31 將將Catalan數(shù)的遞推關(guān)系代入得到擬數(shù)的遞推關(guān)系代入得到擬-Catalan數(shù)的遞推關(guān)系：數(shù)的遞推關(guān)系：111! 1:0*1CC我們有初值*12221*)64()!1)(64(64!1)1(2)1(

23、4!nnnnnnCnCnnCnnnCnnnCnC這樣，擬這樣，擬-Catalan數(shù)的遞推關(guān)系和初值如下：數(shù)的遞推關(guān)系和初值如下：1)2()64(*1*1*CnCnCnn32 利用這個遞推關(guān)系，可以計算前幾個利用這個遞推關(guān)系，可以計算前幾個 擬擬-Catalan數(shù)：數(shù)：3024012168021201*4*3*4*2*4*1CCCCCC 我們還可以求出擬我們還可以求出擬-Catalan數(shù)的計算公式：數(shù)的計算公式：122)!1(1) 1( 21) 1(1!1*nnnnnnnCnCnn33例：設(shè)例：設(shè)a1,a2,an是是n個數(shù)個數(shù) 。定義這些數(shù)的一種。定義這些數(shù)的一種 乘法格式乘法格式是指是指a1,

24、a2,an任意兩個或者它們部任意兩個或者它們部分積之間的分積之間的n-1種乘法運算的方案。計算種乘法運算的方案。計算n個數(shù)個數(shù)的不同乘法格式的個數(shù)。的不同乘法格式的個數(shù)。分析：設(shè)分析：設(shè)hn是是n個數(shù)的不同乘法格式的個數(shù)。個數(shù)的不同乘法格式的個數(shù)。 那么那么: h1 = 1 , 一個數(shù)的乘法格式一個數(shù)的乘法格式; h2 = 2 , 兩個數(shù)的乘法格式兩個數(shù)的乘法格式; (a1a2) 和和(a2a1) 34 h3 = 12 , 三個數(shù)的乘法格式三個數(shù)的乘法格式; (a1(a2a3), (a2(a1a3),(a3(a1a2) (a1(a3a2), (a2(a3a1),(a3(a2a1) (a2a3)

25、a1), (a1a3)a2), (a1a2)a3) (a3a2)a1), (a3a1)a2), (a2a1)a3) 看得出看得出, 三個數(shù)的乘法格式都需要兩次乘法三個數(shù)的乘法格式都需要兩次乘法,兩組括號因子兩組括號因子,每種格式的乘法就對應(yīng)一括號每種格式的乘法就對應(yīng)一括號35內(nèi)的因子內(nèi)的因子, ,一般說來每個乘法格式都可以通過以一般說來每個乘法格式都可以通過以 看成是由某種看成是由某種規(guī)定順序規(guī)定順序列出：列出：a1,a2,a3, .an而后插入而后插入 n-1對括號和對括號和n-1個個號使得每對括號號使得每對括號都指定兩個因子的乘積都指定兩個因子的乘積,例如其中就有例如其中就有: (a1(a

26、2(a3(a4(a5(a6 .).) 一種乘法格式。一種乘法格式。 我們利用歸納法來驗證遞推關(guān)系：我們利用歸納法來驗證遞推關(guān)系： 36 i) 取取a1,a2, a3,.an-1的一種乘法格式的一種乘法格式(它有它有n-2次乘次乘 法和法和n-2組括號組括號), 將將an插入到插入到n-2個乘法運算個乘法運算中任一個中任一個號兩側(cè)的任一側(cè)，有：號兩側(cè)的任一側(cè)，有：2(n-2)種；種；對于任一個乘法因子對于任一個乘法因子(括號括號)由分左右兩側(cè)，所由分左右兩側(cè)，所以共有以共有: 22(n-2)種種 ii)取取a1,a2, a3,.an-1的一種乘法格式的一種乘法格式, 將將an放到整放到整個表達式

27、兩側(cè)的任一側(cè)。又有個表達式兩側(cè)的任一側(cè)。又有2倍種。倍種。37由由h3 = 12 ，分析任一中乘法格式，分析任一中乘法格式(a1(a2a3), 可以有可以有10個位置插入個位置插入a4 故故h4 = (4*46)*12=120由此可見，序列由此可見，序列 hn與擬與擬-Catalan數(shù)有相同的數(shù)有相同的遞推關(guān)系，故有：遞推關(guān)系，故有：則：則：hn=22 (n-2) hn-1+2hn-1 從而從而 hn= (4n-6) hn-1 n 2 22(1)!11nnnhCnnn38 上例中我們只考慮了對以上例中我們只考慮了對以規(guī)定順序規(guī)定順序a1,a2, a3,.an列列成的成的n個數(shù)的那些乘法格式進行計數(shù)個數(shù)的那些乘法格式進行計數(shù),例如統(tǒng)計了：例如統(tǒng)計了：