特殊計(jì)數(shù)序列

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

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

3、結(jié)點(diǎn)，則右子樹個(gè)結(jié)點(diǎn)，則右子樹Tr有有n-1-k個(gè)結(jié)點(diǎn)，于是每個(gè)個(gè)結(jié)點(diǎn)，于是每個(gè)不同的左子樹有不同的左子樹有ck種時(shí)，右子樹有種時(shí)，右子樹有cn-1-k種，由種，由計(jì)數(shù)原理：計(jì)數(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ù)我們?cè)诘谑胖v中補(bǔ)充的關(guān)于生成函數(shù)有根據(jù)我們?cè)诘谑胖v中補(bǔ)充的關(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項(xiàng)的系數(shù)只相差一項(xiàng)項(xiàng)的系數(shù)只相差一項(xiàng)nknknk

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

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

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

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

10、，其余時(shí)就把這些掃描到的項(xiàng)全部取反號(hào)，其余,.,221naaa14項(xiàng)不變，結(jié)果又得到項(xiàng)不變，結(jié)果又得到n個(gè)個(gè)+1和和n個(gè)個(gè)-1構(gòu)成的不可接構(gòu)成的不可接 受序列。從而，易知不可接受序列的數(shù)目受序列。從而，易知不可接受序列的數(shù)目Un就與就與n+1個(gè)個(gè)+1和和n-1個(gè)個(gè)-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)點(diǎn)沿第一象限的格線到點(diǎn)沿第一象限的格線到(n, n)點(diǎn)的不穿越方格對(duì)角線的最短路徑數(shù)；點(diǎn)的不穿越方格對(duì)角線的最短路徑數(shù)； （2） 序列序列a1a2ak的元素順序保持不變，的元素順序保持不變， 按不同結(jié)合方式插入合法圓括號(hào)對(duì)的方案數(shù)；按不同結(jié)合方式插入合法圓括號(hào)對(duì)的方案數(shù)； （3） 用用n-1條互不交叉的對(duì)角線把條互不交叉的對(duì)角線把n+2條邊條邊(n1)的凸多邊形拆分三角形化的方法數(shù)；的凸多邊形拆分三角形化的方法數(shù)； 16（4） 2n個(gè)人排隊(duì)上車，車票費(fèi)為個(gè)人排隊(duì)上車，車票費(fèi)為5角，角，2n個(gè)人個(gè)人 中有一半

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

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

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

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

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

17、一點(diǎn)起，改上移為初位于對(duì)角線上方的第一點(diǎn)起，改上移為右移，改右移為上移，即可得到一條右移，改右移為上移，即可得到一條nn方方格上格上(從從(0,0)點(diǎn)到點(diǎn)到(n,n)點(diǎn)點(diǎn))的壞路線。亦即的壞路線。亦即, nn方格上的壞路線與方格上的壞路線與(n+1)(n-1)方格上的方格上的路線之間存在一一對(duì)應(yīng)。由于路線之間存在一一對(duì)應(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 注意，在求對(duì)角線下方的好路線數(shù)時(shí)，每條注意，在求對(duì)角線下方的好路線數(shù)時(shí)，每條走過對(duì)角線上方的路線都作為壞路線計(jì)入了走過對(duì)角線上方的路線都作為壞路線計(jì)入了bn。進(jìn)而，僅走對(duì)角線一側(cè)且不穿越對(duì)角線進(jìn)而，僅走對(duì)角線一側(cè)且不穿越對(duì)角線 的的總路徑數(shù)為總路徑數(shù)為Catalan數(shù)：數(shù)：nnnnnCn211),2(1124（3）用互不交叉的對(duì)角線把）用互不交叉的對(duì)角線把n+1條邊條邊(n2) 的的 凸多邊形三角形化分的方法數(shù)；凸多邊形三角形化分的方法數(shù)；vkvk 1vk 1F1v1eF2

19、vk 2vnvn 1余點(diǎn)依次相鄰標(biāo)記余點(diǎn)依次相鄰標(biāo)記25 令令hn表示將表示將n+1(n2)邊凸多邊形進(jìn)行三角邊凸多邊形進(jìn)行三角 形拆分的方案數(shù)，則當(dāng)形拆分的方案數(shù)，則當(dāng)n=1時(shí)，時(shí)，h1=1，當(dāng)，當(dāng)n3時(shí)，任取多邊形一邊為時(shí)，任取多邊形一邊為基邊基邊記作記作e，其兩端，其兩端點(diǎn)一端記為點(diǎn)一端記為v1，一端記為，一端記為vn+1，余點(diǎn)依次相鄰，余點(diǎn)依次相鄰標(biāo)記如圖所示?，F(xiàn)以標(biāo)記如圖所示?，F(xiàn)以v1，vn+1及任意頂點(diǎn)及任意頂點(diǎn)vk+1(k=1,2,n-1)構(gòu)作一個(gè)三角形，該三角形構(gòu)作一個(gè)三角形，該三角形將凸多邊形分為將凸多邊形分為F1, F2兩個(gè)區(qū)域。兩個(gè)區(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由乘法原理知由乘法原理知 易證易證 對(duì)于六邊形時(shí)對(duì)于六邊形時(shí),即當(dāng)即當(dāng)n=5時(shí)時(shí),可求得分拆三角形數(shù)可求得分拆三角形數(shù):11nkknknhhhnnnhnnnhnn2111221114485115252515h28 凸凸6邊形邊形(n=5)的的14個(gè)拆分方案個(gè)拆分

21、方案 其中從同一頂點(diǎn)引出其中從同一頂點(diǎn)引出3條對(duì)角線的有條對(duì)角線的有6種種；從；從兩個(gè)頂點(diǎn)各引出兩個(gè)頂點(diǎn)各引出2條對(duì)角線的又有條對(duì)角線的又有6種種；從；從3個(gè)互個(gè)互不相鄰點(diǎn)連接的有不相鄰點(diǎn)連接的有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 我們可義求出前幾項(xiàng)的我們可義求出前幾項(xiàng)的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)在我們定義一個(gè)新的數(shù)列：現(xiàn)在我們定義一個(gè)新的數(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 利用這個(gè)遞推關(guān)系，可以計(jì)算前幾個(gè)利用這個(gè)遞推關(guān)系，可以計(jì)算前幾個(gè) 擬擬-Catalan數(shù)：數(shù)：3024012168021201*4*3*4*2*4*1CCCCCC 我們還可以求出擬我們還可以求出擬-Catalan數(shù)的計(jì)算公式：數(shù)的計(jì)算公式：122)!1(1) 1( 21) 1(1!1*nnnnnnnCnCnn33例：設(shè)例：設(shè)a1,a2,an是是n個(gè)數(shù)個(gè)數(shù) 。定義這些數(shù)的一種。定義這些數(shù)的一種 乘法格式乘法格式是指是指a1,

24、a2,an任意兩個(gè)或者它們部任意兩個(gè)或者它們部分積之間的分積之間的n-1種乘法運(yùn)算的方案。計(jì)算種乘法運(yùn)算的方案。計(jì)算n個(gè)數(shù)個(gè)數(shù)的不同乘法格式的個(gè)數(shù)。的不同乘法格式的個(gè)數(shù)。分析：設(shè)分析：設(shè)hn是是n個(gè)數(shù)的不同乘法格式的個(gè)數(shù)。個(gè)數(shù)的不同乘法格式的個(gè)數(shù)。 那么那么: h1 = 1 , 一個(gè)數(shù)的乘法格式一個(gè)數(shù)的乘法格式; h2 = 2 , 兩個(gè)數(shù)的乘法格式兩個(gè)數(shù)的乘法格式; (a1a2) 和和(a2a1) 34 h3 = 12 , 三個(gè)數(shù)的乘法格式三個(gè)數(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) 看得出看得出, 三個(gè)數(shù)的乘法格式都需要兩次乘法三個(gè)數(shù)的乘法格式都需要兩次乘法,兩組括號(hào)因子兩組括號(hào)因子,每種格式的乘法就對(duì)應(yīng)一括號(hào)每種格式的乘法就對(duì)應(yīng)一括號(hào)35內(nèi)的因子內(nèi)的因子, ,一般說來每個(gè)乘法格式都可以通過以一般說來每個(gè)乘法格式都可以通過以 看成是由某種看成是由某種規(guī)定順序規(guī)定順序列出：列出：a1,a2,a3, .an而后插入而后插入 n-1對(duì)括號(hào)和對(duì)括號(hào)和n-1個(gè)個(gè)號(hào)使得每對(duì)括號(hào)號(hào)使得每對(duì)括號(hào)都指定兩個(gè)因子的乘積都指定兩個(gè)因子的乘積,例如其中就有例如其中就有: (a1(a

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

27、兩側(cè)的任一側(cè)。又有個(gè)表達(dá)式兩側(cè)的任一側(cè)。又有2倍種。倍種。37由由h3 = 12 ，分析任一中乘法格式，分析任一中乘法格式(a1(a2a3), 可以有可以有10個(gè)位置插入個(gè)位置插入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 上例中我們只考慮了對(duì)以上例中我們只考慮了對(duì)以規(guī)定順序規(guī)定順序a1,a2, a3,.an列列成的成的n個(gè)數(shù)的那些乘法格式進(jìn)行計(jì)數(shù)個(gè)數(shù)的那些乘法格式進(jìn)行計(jì)數(shù),例如統(tǒng)計(jì)了：例如統(tǒng)計(jì)了：