【大學(xué)課件】特殊計(jì)數(shù)序列81 Catalan數(shù)

1、1 第八章第八章 特殊計(jì)數(shù)序列特殊計(jì)數(shù)序列 8.1 Catalan數(shù)數(shù) 前面我們已經(jīng)討論過(guò)一些特殊計(jì)數(shù)序列的例子。前面我們已經(jīng)討論過(guò)一些特殊計(jì)數(shù)序列的例子。 如：斐波那契序列：如：斐波那契序列： f n = f n-1 + f n-2 (n 3) 翰假設(shè)塔問(wèn)題序列：翰假設(shè)塔問(wèn)題序列： 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ù)序列 2 8.1 Catalan數(shù)數(shù) Catalan(卡特朗卡特朗)序列其遞推關(guān)系是非線性序列其遞推關(guān)系是非線性 的的,許多有意義

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

3、非根結(jié)點(diǎn)，設(shè)左子樹(shù)Tl有有k 個(gè)結(jié)點(diǎn)，那么右子樹(shù)個(gè)結(jié)點(diǎn)，那么右子樹(shù)Tr有有n-1-k個(gè)結(jié)點(diǎn)，于是每個(gè)結(jié)點(diǎn)，于是每 個(gè)不同的左子樹(shù)有個(gè)不同的左子樹(shù)有ck種時(shí)，右子樹(shù)有種時(shí)，右子樹(shù)有cn-1-k種，種， 由計(jì)數(shù)原理：由計(jì)數(shù)原理： 4 )0(, 1 0 1 nccc n k knkn 令令由序列由序列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

4、 c0)x2+ (c0 c3+c1 c2 +c2 c1+c3 c0 )x3+ 5 n n k knk nk kk k kk k kk xccxcc xccxccccxB . )()( 00 3 3 0 3 2 2 0 2 1 0 100 2 根據(jù)我們?cè)诘谑胖v中補(bǔ)充的關(guān)于生成函數(shù)有根據(jù)我們?cè)诘谑胖v中補(bǔ)充的關(guān)于生成函數(shù)有 關(guān)結(jié)論可知：關(guān)結(jié)論可知： )0(. 0132 2110 1 0 1 ncccc ccccccc nn nn n k knkn 6 再由于序列再由于序列cn構(gòu)成的生成函數(shù)可以表示為構(gòu)成的生成函數(shù)可以表示為: 比較發(fā)現(xiàn)與 n n k knk n n nnnn n n n k kn

5、k nn n n xccxB xcccccccc xccxcxB )( . )( 00 2 01322110 0 1 0 1 10 B(x)與與B2(x)在第在第n項(xiàng)的系數(shù)只相差一項(xiàng)項(xiàng)的系數(shù)只相差一項(xiàng) n k n knk n n k n knk n xccxcc 00 1 0 1 0 與 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ù)那么我們得到生

6、成函數(shù)B(x)滿足的方程：滿足的方程： 其中其中B(0) =c0 =1 1)( 1 00 1 0 1 1 1 n k n knk n n k n knk n xccxcc x xB )( 1)( 2 xB x xB 8 解此二次方程，并應(yīng)用牛頓二項(xiàng)式定理解此二次方程，并應(yīng)用牛頓二項(xiàng)式定理(P95)得得: )4(2 1 1 (1 2 1 )4(2 1 )4( 0 2 1 (1 2 1 )4(2 1 1 2 1 2 )41 (1 2 411 )( 1 1 0 0 2 1 n nn n n n n x n x x n x x x n xx x x x xB 9 )(2)1( 1)1( 2)1(2 2

7、)1( )1( 2)1( 1 2 1 : 2)1( 1 2 1 2)1(2 1 )4(2 1 2 1 )( 95 12 1)1(2 1)1( 12 0 122 1 1121 1 P n n n n c x n x n x n x xB nn n n nn n n nnn n nnn n nn 見(jiàn) 因此 作換元作換元 10 n n nn n n c nn n n n 2 ) 1( 1 2) 1( 2 2) 1( ) 1( 12 12 這個(gè)數(shù)這個(gè)數(shù)Cn常稱為常稱為Catalan( (卡特朗卡特朗) )數(shù)數(shù), ,序列序列Cn 常稱為常稱為Catalan( (卡特朗卡特朗) )序列序列。常用第一個(gè)字母

8、常用第一個(gè)字母 C表示，記為：表示，記為：C0,C1,C2,C3,.Cn, 其中，其中， 通項(xiàng)：通項(xiàng)： .)2, 1 ,0( 2 1 1 n n n n C n 11 定理定理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假設(shè)其局部和滿足假設(shè)其局部和滿足 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ù)列假設(shè)項(xiàng)數(shù)列假設(shè) 其局部和滿足其局部和滿足 a1a2 ak 0 .)2, 1 ,0( 2

9、1 1 n n n n C n 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| 而而: 可見(jiàn)，通過(guò)計(jì)算可見(jiàn)，通過(guò)計(jì)算|Un|進(jìn)而計(jì)進(jìn)而計(jì) 算出算出|An|; 對(duì)每個(gè)不可接受序列，總可以找到對(duì)每個(gè)不可接受序列，總可以找到 最小的正奇數(shù)最小的正奇數(shù)k，使得，使得ak=-1且且ak之前的之前的+1與與-1 的個(gè)數(shù)相

10、等，即有的個(gè)數(shù)相等，即有a1+a2+ak-1=0, ak =-1。 n n S n 2 13 例例: -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)?m+1個(gè)個(gè)+1和和m-1個(gè)個(gè)-1構(gòu)成的序列。構(gòu)成的序列。 例例: 1-1+1-1+1-1+1+1-1+1.注意有兩個(gè)注意有兩個(gè)1連加連加 反之，對(duì)任一由反之，對(duì)任一由n+1個(gè)個(gè)+1和和n-1個(gè)個(gè)-1構(gòu)成的序列，構(gòu)成的序列， 從左到右掃描，當(dāng)從左到右掃描，當(dāng)+1的個(gè)數(shù)第一次比

11、的個(gè)數(shù)第一次比-1的個(gè)數(shù)的個(gè)數(shù) 多多1時(shí)就把這些掃描到的項(xiàng)全部取反號(hào)，其余時(shí)就把這些掃描到的項(xiàng)全部取反號(hào)，其余 ,., 221n aaa 14 項(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ù)目為： n n nnnn n nnnn n nnnn n nn n nn n nn n n n USA nn n U nnn n 2 1 1 1 1 ! )!2( ) )1(

12、1 ( )!1(! )!2( ) 1 11 ( )!1(! )!2( )!1()!1( )!2( ! )!2( )!1()!1( )!2( 2 )!1()!1( )!2( 那么 15 Catalan數(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

13、條邊條邊 (n1)的凸多邊形拆分三角形化的方法數(shù)；的凸多邊形拆分三角形化的方法數(shù)； 16 4 2n個(gè)人排隊(duì)上車，車票費(fèi)為個(gè)人排隊(duì)上車，車票費(fèi)為5角，角，2n個(gè)人個(gè)人 中有一半人持有一元面值鈔票，一半人持中有一半人持有一元面值鈔票，一半人持 有有5角鈔票，求不同的上車方案數(shù)，使得在這角鈔票，求不同的上車方案數(shù)，使得在這 些方案中售票員總能用先上車的購(gòu)票錢給后上些方案中售票員總能用先上車的購(gòu)票錢給后上 車者找零；車者找零； 5 甲、乙二人比賽乒乓球，甲、乙二人比賽乒乓球， 最后結(jié)果為最后結(jié)果為 n n，比賽過(guò)程中甲始終不落后于乙的計(jì)分，比賽過(guò)程中甲始終不落后于乙的計(jì)分 種數(shù)；種數(shù)； 17 6 n個(gè)

14、點(diǎn)的有序二叉樹(shù)的個(gè)數(shù)；個(gè)點(diǎn)的有序二叉樹(shù)的個(gè)數(shù)； 7 n個(gè)葉子的完全二叉數(shù)的個(gè)數(shù)；個(gè)葉子的完全二叉數(shù)的個(gè)數(shù)； 8 圓周上圓周上2n個(gè)點(diǎn)連接成的個(gè)點(diǎn)連接成的n條兩兩互不條兩兩互不 相交的弦分割圓的方案數(shù)。相交的弦分割圓的方案數(shù)。 以 上以 上 8種 類 型 的 計(jì) 數(shù) 問(wèn) 題種 類 型 的 計(jì) 數(shù) 問(wèn) 題 , 是 典 型 的是 典 型 的 Catalan數(shù)組合問(wèn)題，我們僅僅對(duì)其中的局部數(shù)組合問(wèn)題，我們僅僅對(duì)其中的局部 問(wèn)題進(jìn)行討論；問(wèn)題進(jìn)行討論； 18 (1)從從O(0,0)點(diǎn)沿第一象限的格線到點(diǎn)沿第一象限的格線到N(n,n)點(diǎn)的點(diǎn)的 不穿越方格對(duì)角線不穿越方格對(duì)角線ON的最短路徑數(shù)；的最短路徑數(shù)

15、； 沿格線前進(jìn)不穿越對(duì)角線沿格線前進(jìn)不穿越對(duì)角線(但可接觸對(duì)角線上的但可接觸對(duì)角線上的 格點(diǎn)格點(diǎn))的路線分為走對(duì)角線上方或走對(duì)角線下方的路線分為走對(duì)角線上方或走對(duì)角線下方 兩種情形，由對(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)圖是圖是

16、44方格方格 中的中的壞路線壞路線，(b)圖是圖是44方格變?yōu)榉礁褡優(yōu)?3方格的方格的 后的路線。后的路線。 (a)(b) O N N O 20 易知易知nn方格上從左下角到右上角的每一條路方格上從左下角到右上角的每一條路 線可用一個(gè)包含線可用一個(gè)包含n個(gè)個(gè)R(右右) 和和n個(gè)個(gè)U(上上)的字的字 符串來(lái)描述。例如以下圖所示的路線可用字符符串來(lái)描述。例如以下圖所示的路線可用字符 串串RUURRURU共共8個(gè)字符來(lái)表示，可以看出，個(gè)字符來(lái)表示，可以看出， R和和U的數(shù)量各占一半。這樣的字符串可以由的數(shù)量各占一半。這樣的字符串可以由 在給定的在給定的2n個(gè)位置中為個(gè)位置中為R 選擇選擇n個(gè)位置而不

17、考慮順序，個(gè)位置而不考慮順序， 其余其余n個(gè)位置填入個(gè)位置填入U(xiǎn)。于是，。于是， 21 有有C(2n,n)種可能的路線。且有種可能的路線。且有g(shù)n+bn=C(2n, n)， 即：即：gn=C(2n, n)-bn, 故只需計(jì)算壞路線數(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)方格上從

18、左下角走到右上角不加限方格上從左下角走到右上角不加限 制的路線；反之，制的路線；反之， 對(duì)任一對(duì)任一(n+1)(n-1)方格方格 22 上從左下角走到右上角不加限制的路線，從最上從左下角走到右上角不加限制的路線，從最 初位于對(duì)角線上方的第一點(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)方方 格

19、的路線為格的路線為: C(2n, n+1)或或C(2n, n-1)，兩者相，兩者相 等等, 故取故取bn=C(2n, n-1)。從而有：。從而有： 23 ),2( 1 1 1 1 ! )!2( ) 1( 1 )!1( ! )!2( 1 11 )!1( ! )!2( )!1()!1( )!2( ! )!2( ) 1,2(),2(),2( nnC nnnn n nnnn n nnnn n nn n nn n nnCnnCbnnCg nn 注意，在求對(duì)角線下方的好路線數(shù)時(shí)，每條注意，在求對(duì)角線下方的好路線數(shù)時(shí)，每條 走過(guò)對(duì)角線上方的路線都作為壞路線計(jì)入了走過(guò)對(duì)角線上方的路線都作為壞路線計(jì)入了bn。

20、進(jìn)而，僅走對(duì)角線一側(cè)且不穿越對(duì)角線進(jìn)而，僅走對(duì)角線一側(cè)且不穿越對(duì)角線 的的 總路徑數(shù)為總路徑數(shù)為Catalan數(shù)：數(shù)： n n n nnC n 2 1 1 ),2( 1 1 24 3用互不交叉的對(duì)角線把用互不交叉的對(duì)角線把n+1條邊條邊(n2) 的的 凸多邊形三角形化分的方法數(shù)；凸多邊形三角形化分的方法數(shù)； vk vk 1 vk 1 F 1 v1 e F 2 vk 2 vn v n 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í)，任取多邊形一邊為

21、基邊記作時(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邊凸多邊形圍成，其三角形拆分邊凸多邊形圍成，其三角形拆分 方案數(shù)為方案數(shù)為hk，F(xiàn)2由由n-k+1邊凸多邊形圍成，邊凸多邊形圍成， 其三角形剖分方案數(shù)為其三角形剖分方案數(shù)為hn-k， F1與與F2的邊數(shù)關(guān)的邊數(shù)關(guān) 系是系

22、是: (k+1)+(n-k+1)+1-2 = n+1(總邊數(shù)總邊數(shù)) vk vk 1 vk 1 F 1 v1 e F 2 vk 2 vn v n 1 27 由乘法原理知由乘法原理知 易證易證 對(duì)于六邊形時(shí)對(duì)于六邊形時(shí),即當(dāng)即當(dāng)n=5時(shí)時(shí),可求得分拆三角形數(shù)可求得分拆三角形數(shù): 1 1 n k knkn hhh n n n h n n n h nn 2 1 1 1 22 1 1 14 4 8 5 1 15 252 5 1 5 h 28 凸凸6邊形邊形(n=5)的的14個(gè)拆分方案?jìng)€(gè)拆分方案 其中從同一頂點(diǎn)引出其中從同一頂點(diǎn)引出3條對(duì)角線的有條對(duì)角線的有6種種；從；從 兩個(gè)頂點(diǎn)各引出兩個(gè)頂點(diǎn)各引出2

23、條對(duì)角線的又有條對(duì)角線的又有6種種；從；從3個(gè)互個(gè)互 不相鄰點(diǎn)連接的有不相鄰點(diǎn)連接的有2種種，共，共14種。種。 29 下面證明下面證明Catalan數(shù)滿足數(shù)滿足1階齊次遞推關(guān)系；階齊次遞推關(guān)系； 由于由于 所以有：所以有： 1)1( 1 24 1 24)12)(2( 1 1 )!1()!1( )!22(1 ! )!2( 1 1 01 1 CnC n n C n n n nn n nn n n nn n n C C nn n n 所以 1 22(1) 11 11 nn nn CC nnnn 30 我們可義求出前幾項(xiàng)的我們可義求出前幾項(xiàng)的Catalan數(shù)的數(shù)值：數(shù)的數(shù)值： C0 = 1 , C1

24、 = 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 * 1n CCCC ,.)3 , 2 , 1(! 1 * nCnC nn 31 將將Catalan數(shù)的遞推關(guān)系代入得到擬數(shù)的遞推關(guān)系代入得到擬- Catalan數(shù)的遞推關(guān)系：數(shù)的遞推關(guān)系： 111! 1: 0 * 1 CC我們有初值 * 12 221 * )64()!

25、1)(64( 64 ! 1)1( 2)1(4 ! nn nnnn CnCnn C n n nC n n nCnC 這樣，擬這樣，擬-Catalan數(shù)的遞推關(guān)系和初值如下：數(shù)的遞推關(guān)系和初值如下： 1 )2()64( * 1 * 1 * C nCnC nn 32 利用這個(gè)遞推關(guān)系，可以計(jì)算前幾個(gè)利用這個(gè)遞推關(guān)系，可以計(jì)算前幾個(gè) 擬擬-Catalan數(shù)：數(shù)： 3024012 16802 1201 * 4 * 3 * 4 * 2 * 4 * 1 CC CC CC 我們還可以求出擬我們還可以求出擬-Catalan數(shù)的計(jì)算公式：數(shù)的計(jì)算公式： 1 22 )!1( 1 ) 1( 2 1) 1( 1 ! 1

26、 * n n n n n n nCnC nn 33 例：設(shè)例：設(shè)a1,a2,an是是n個(gè)數(shù)個(gè)數(shù) 。定義這些數(shù)的一種。定義這些數(shù)的一種 乘法格式是指乘法格式是指a1,a2,an任意兩個(gè)或者它們?nèi)我鈨蓚€(gè)或者它們 局部積之間的局部積之間的n-1種乘法運(yùn)算的方案。計(jì)算種乘法運(yùn)算的方案。計(jì)算n個(gè)個(gè) 數(shù)的不同乘法格式的個(gè)數(shù)。數(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 , 三

27、個(gè)數(shù)的乘法格式三個(gè)數(shù)的乘法格式; (a1(a2a3), (a2(a1a3),(a3(a1a2) (a1(a3a2), (a2(a3a1),(a3(a2a1) (a2a3)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)的因子, ,一般說(shuō)來(lái)每個(gè)乘法格式都可以通過(guò)以一般說(shuō)來(lái)每個(gè)乘法格式都可以通過(guò)以 看成是由某種看成是由某種規(guī)定順序規(guī)定順序列出：列出：a1,a

28、2,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(a2(a3(a4(a5(a6 .).) 一種乘法格式。一種乘法格式。 我們利用歸納法來(lái)驗(yàn)證遞推關(guān)系：我們利用歸納法來(lái)驗(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è)乘法

29、因子(括號(hào)括號(hào))由分左右兩側(cè)，所由分左右兩側(cè)，所 以共有以共有: 22(n-2)種種 ii)取取a1,a2, a3,.an-1的一種乘法格式的一種乘法格式, 將將an放到整放到整 個(gè)表達(dá)式兩側(cè)的任一側(cè)。又有個(gè)表達(dá)式兩側(cè)的任一側(cè)。又有2倍種。倍種。 37 由由h3 = 12 ，分析任一中乘法格式，分析任一中乘法格式(a1(a2a3), 可以有可以有10個(gè)位置插入個(gè)位置插入a4 故故h4 = (4*46)*12=120 由此可見(jiàn)，序列由此可見(jiàn)，序列 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)!1 1 nn n hCnn n 38 上例中我們只考慮了對(duì)以上例中我們只考慮了對(duì)以規(guī)定順序規(guī)定順序a1,a2, a3,.an列列 成的成的n個(gè)數(shù)的那些乘法格式進(jìn)行計(jì)數(shù)個(gè)數(shù)的那些乘