特殊計數(shù)序列81Catalan數(shù)

1、1,第八章 特殊計數(shù)序列8.1 Catalan數(shù),前面我們已經(jīng)討論過一些特殊計數(shù)序列的例子。如：斐波那契序列： f n = f n-1 + f n-2 (n 3) 翰若塔問題序列： hn = 2hn-1+ 1 (n 1) 錯位排列數(shù)序列：D0, D1, D2, D3, Dn, 等 本節(jié)我們將繼續(xù)研究4個著名的計數(shù)序列,2,8.1 Catalan數(shù) Catalan(卡特朗)序列其遞推關(guān)系是非線性的,許多有意義的計數(shù)問題都導(dǎo)致這樣的遞推關(guān)系。本次課將舉出一些,后面還將見到。 通過下面的例題我們來引入Catalan(卡特朗)序列。 例 ： 二叉樹（或二元樹）的計數(shù)問題。 如 3個結(jié)點可有5棵不同的二

2、叉樹, 如下圖所示。,3,一般地，設(shè)cn為n個結(jié)點的不同的二叉樹的個數(shù)，定義c0=1。在n0的情形下，二叉樹有一個根結(jié)點及n-1個非根結(jié)點，設(shè)左子樹Tl有k個結(jié)點，則右子樹Tr有n-1-k個結(jié)點，于是每個不同的左子樹有ck種時，右子樹有cn-1-k種，由計數(shù)原理：,4,令由序列cn構(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

3、 +c2 c1+c3 c0 )x3+,5,根據(jù)我們在第十九講中補充的關(guān)于生成函數(shù)有 關(guān)結(jié)論可知：,6,再由于序列cn構(gòu)成的生成函數(shù)可以表示為:,B(x)與B2(x)在第n項的系數(shù)只相差一項,7,由于它們的首項都是1,將B(x)減去常數(shù)1后使得和式的每個單項式的冪大于等于1.再除以x后就得到生成函數(shù)為： 與B2(x) 的序列的生成函數(shù)化成一致。 那么我們得到生成函數(shù)B(x)滿足的方程： 其中B(0) =c0 =1,8,解此二次方程，并應(yīng)用牛頓二項式定理(P95)得:,9,作換元,10,這個數(shù)Cn常稱為Catalan(卡特朗)數(shù),序列Cn常稱為Catalan(卡特朗)序列。常用第一個字母C表示，記

4、為：C0,C1,C2,C3,.Cn, 其中，通項：,11,定理8.1.1 n 個+1 和 n個 1 構(gòu)成的 2n 項數(shù)列 a1, a2, , a2n若其部分和滿足 a1a2 ak 0 k1,2,2n 的數(shù)列a1, a2. ak的個數(shù)等于第n個Catalan數(shù)，即 證明：n 個+1 和 n個 1 構(gòu)成的 2n 項數(shù)列若其部分和滿足 a1a2 ak 0,12,則稱該數(shù)列是可接受的數(shù)列，否則是不可接受的 數(shù)列。令Sn是由n個 +1 和 n個 1 構(gòu)成的2n項數(shù)列的全體，An是其中可接受的部分，Un是其中不可接受的部分.于是: |Sn|An|Un| 而: 可見，通過計算|Un|進而計算出|An|; 對

5、每個不可接受序列，總可以找到最小的正奇數(shù)k，使得ak=-1且ak之前的+1與-1的個數(shù)相等，即有a1+a2+ak-1=0, ak =-1。,13,例: -1+1-1+1-1+1-1+1-1+1.其中a7 = -1 現(xiàn)將這個不可接受序列中前k項的每一項取反號， 其余部分保持不變， 得到新序列變?yōu)閙+1個+1和m-1個-1構(gòu)成的序列。 例: 1-1+1-1+1-1+1+1-1+1.注意有兩個1連加 反之，對任一由n+1個+1和n-1個-1構(gòu)成的序列，從左到右掃描，當+1的個數(shù)第一次比-1的個數(shù)多1時就把這些掃描到的項全部取反號，其余,14,項不變，結(jié)果又得到n個+1和n個-1構(gòu)成的不可接 受序列。

6、從而，易知不可接受序列的數(shù)目Un就與n+1個+1和n-1個-1所成的序列的數(shù)目相等。由于后者的數(shù)目為：,15,Catalan數(shù)的組合學(xué)意義可羅列如下： （1）從(0，0)點沿第一象限的格線到(n, n)點的不穿越方格對角線的最短路徑數(shù)； （2） 序列a1a2ak的元素順序保持不變， 按不同結(jié)合方式插入合法圓括號對的方案數(shù)； （3） 用n-1條互不交叉的對角線把n+2條邊(n1)的凸多邊形拆分三角形化的方法數(shù)；,16,（4） 2n個人排隊上車，車票費為5角，2n個人 中有一半人持有一元面值鈔票，一半人持有5角鈔票，求不同的上車方案數(shù)，使得在這些方案中售票員總能用先上車的購票錢給后上車者找零； （

7、5） 甲、乙二人比賽乒乓球， 最后結(jié)果為nn，比賽過程中甲始終不落后于乙的計分種數(shù)；,17,（6） n個點的有序二叉樹的個數(shù)； （7） n個葉子的完全二叉數(shù)的個數(shù)； （8） 圓周上2n個點連接成的n條兩兩互不相交的弦分割圓的方案數(shù)。 以上8種類型的計數(shù)問題, 是典型的Catalan數(shù)組合問題，我們僅僅對其中的部分問題進行討論；,18,(1)從O(0,0)點沿第一象限的格線到N(n,n)點的 不穿越方格對角線ON的最短路徑數(shù)； 沿格線前進不穿越對角線(但可接觸對角線上的 格點)的路線分為走對角線上方或走對角線下方兩種情形，由對稱性，易知兩種路線數(shù)相等。 因此，只需計算走一方的路線數(shù)(不妨計算對角

8、線下方的路線數(shù))。 設(shè)符合題意的路線為好路線，其總數(shù)記為gn；,19,即:遇到對角線就向右; 穿越對角線的路線記為 壞路線，其總數(shù)記為bn。 (a)圖是44方格中的壞路線，(b)圖是44方格變?yōu)?3方格的后的路線。,O,N,N,O,20,易知nn方格上從左下角到右上角的每一條路 線可用一個包含n個R(右) 和n個U(上)的字符串來描述。例如下圖所示的路線可用字符串RUURRURU共8個字符來表示，可以看出，R和U的數(shù)量各占一半。這樣的字符串可以由在給定的2n個位置中為R 選擇n個位置而不考慮順序， 其余n個位置填入U。于是，,21,有C(2n,n)種可能的路線。且有g(shù)n+bn=C(2n, n)

9、， 即：gn=C(2n, n)-bn, 故只需計算壞路線數(shù)bn。 對任一壞路線，選定最初穿越對角線后的第一次移動，并將此移動之后的右行改為上行，上行改為右行，這樣的變化使得向上移動增加一個而向右移動減少一個,即可得到一條(n+1)(n-1)方格上從左下角走到右上角不加限制的路線；反之， 對任一(n+1)(n-1)方格,22,上從左下角走到右上角不加限制的路線，從最 初位于對角線上方的第一點起，改上移為右移，改右移為上移，即可得到一條nn方格上(從(0,0)點到(n,n)點)的壞路線。亦即, nn方格上的壞路線與(n+1)(n-1)方格上的路線之間存在一一對應(yīng)。由于(n+1)(n-1)方格的路線

10、為: C(2n, n+1)或C(2n, n-1)，兩者相等, 故取bn=C(2n, n-1)。從而有：,23,注意，在求對角線下方的好路線數(shù)時，每條走過對角線上方的路線都作為壞路線計入了bn。進而，僅走對角線一側(cè)且不穿越對角線 的總路徑數(shù)為Catalan數(shù)：,24,（3）用互不交叉的對角線把n+1條邊(n2) 的 凸多邊形三角形化分的方法數(shù)；,余點依次相鄰標記,25,令hn表示將n+1(n2)邊凸多邊形進行三角 形拆分的方案數(shù)，則當n=1時，h1=1，當n3時，任取多邊形一邊為基邊記作e，其兩端點一端記為v1，一端記為vn+1，余點依次相鄰標記如圖所示?，F(xiàn)以v1，vn+1及任意頂點vk+1(k

11、=1,2,n-1)構(gòu)作一個三角形，該三角形將凸多邊形分為F1, F2兩個區(qū)域。,26,其中，F(xiàn)1由k+1邊凸多邊形圍成，其三角形拆分 方案數(shù)為hk，F(xiàn)2由n-k+1邊凸多邊形圍成，其三角形剖分方案數(shù)為hn-k， F1與F2的邊數(shù)關(guān)系是: (k+1)+(n-k+1)+1-2 = n+1(總邊數(shù)),27,由乘法原理知 易證 對于六邊形時,即當n=5時,可求得分拆三角形數(shù):,28,凸6邊形(n=5)的14個拆分方案,其中從同一頂點引出3條對角線的有6種；從兩個頂點各引出2條對角線的又有6種；從3個互不相鄰點連接的有2種，共14種。,29,下面證明Catalan數(shù)滿足1階齊次遞推關(guān)系； 由于 所以有：

12、,30,我們可義求出前幾項的Catalan數(shù)的數(shù)值： C0 = 1 , C1 = 1 , C2 = 2 , C3 = 5 C4 = 14 , C5 =42 , C6 = 132, C7 =429 C8 =1430, C9 = 4862 ,. 現(xiàn)在我們定義一個新的數(shù)列： 為了方便給它取名叫做擬- Catalan數(shù)。令：,31,將Catalan數(shù)的遞推關(guān)系代入得到擬-Catalan數(shù)的遞推關(guān)系：,這樣，擬-Catalan數(shù)的遞推關(guān)系和初值如下：,32,利用這個遞推關(guān)系，可以計算前幾個 擬-Catalan數(shù)：,我們還可以求出擬-Catalan數(shù)的計算公式：,33,例：設(shè)a1,a2,an是n個數(shù) 。定

13、義這些數(shù)的一種 乘法格式是指a1,a2,an任意兩個或者它們部分積之間的n-1種乘法運算的方案。計算n個數(shù)的不同乘法格式的個數(shù)。 分析：設(shè)hn是n個數(shù)的不同乘法格式的個數(shù)。 那么: h1 = 1 , 一個數(shù)的乘法格式; h2 = 2 , 兩個數(shù)的乘法格式; (a1a2) 和(a2a1),34,h3 = 12 , 三個數(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) 看得出, 三個

14、數(shù)的乘法格式都需要兩次乘法,兩組括號因子,每種格式的乘法就對應(yīng)一括號,35,內(nèi)的因子,一般說來每個乘法格式都可以通過以 看成是由某種規(guī)定順序列出：a1,a2,a3, .an而后插入 n-1對括號和n-1個號使得每對括號都指定兩個因子的乘積,例如其中就有: (a1(a2(a3(a4(a5(a6 .).) 一種乘法格式。 我們利用歸納法來驗證遞推關(guān)系：,36,i) 取a1,a2, a3,.an-1的一種乘法格式(它有n-2次乘 法和n-2組括號), 將an插入到n-2個乘法運算中任一個號兩側(cè)的任一側(cè)，有：2(n-2)種；對于任一個乘法因子(括號)由分左右兩側(cè)，所以共有: 22(n-2)種 ii)取

15、a1,a2, a3,.an-1的一種乘法格式, 將an放到整個表達式兩側(cè)的任一側(cè)。又有2倍種。,37,由h3 = 12 ，分析任一中乘法格式(a1(a2a3), 可以有10個位置插入a4 故h4 = (4*46)*12=120 由此可見，序列 hn與擬-Catalan數(shù)有相同的遞推關(guān)系，故有：,則：hn=22 (n-2) hn-1+2hn-1 從而 hn= (4n-6) hn-1 n 2,38,上例中我們只考慮了對以規(guī)定順序a1,a2, a3,.an列成的n個數(shù)的那些乘法格式進行計數(shù),例如統(tǒng)計了： a1,a2, a3而沒有考慮 a2,a3, a1;令gn是表示帶有這種附加限制的乘法格式數(shù),將這n個數(shù)全排： hn= n! gn, 因此，我們有：,39,這個序列關(guān)系與凸(n+1)邊形區(qū)域通過在區(qū)域內(nèi)插 入n個不相交的對角線而分成三角形區(qū)域的方法數(shù)相同。,這是n=7的情況,因為構(gòu)造三角形的三個頂點沒有次序區(qū)分.,40,總 結(jié),本次課我們介紹了Catalan數(shù)序列和 擬-Catalan數(shù)序列等知識。由于它們的遞推關(guān)系是非線性的，生成函數(shù)和序列通項顯的比較特殊?？梢岳斡汣atalan數(shù)序列和擬-Catalan數(shù)序列的固定公式。