卡塔蘭數及其在競賽中的應用*

●

(紹興市第一中學,浙江 紹興 312000)

1 卡塔蘭數的介紹

卡塔蘭數列是組合數學中一個重要的數列，這個數由比利時的數學家卡塔蘭命名，它常常出現在各種計數問題中,并在競賽數學中有著廣泛的應用.它的一般項為

(1)

它的前幾項為

C0=1，C1=1，C2=2，C3=5，C4=14，C5=42，C6=132，C7=429，C8=1 430，C9=4 862，C10=16 796,……

本文首先給出對應卡塔蘭數的兩個組合問題，或者稱它的定義.不同的文獻會給出不同的定義[1]，我們后面還會給出它的其他等價形式，即卡塔蘭數在競賽中的應用.

問題1卡塔蘭數是研究由n個+1和n個-1組成的所有序列x1,x2,…,x2n中，滿足條件

x1+…+xk≥0,其中k=1,2,…,2n(2)

的序列數目.條件(2)的意思形象地說，就是在這個序列中，從左到右的任何位置及之前的位置中，數字+1出現次數不會比數字-1出現的少.

σ=(-x1)…(-xk0)xk0+1…x2n，

問題2證明：在圓上選擇2n個點，將這些點成對連接起來使得所得到的n條線段不相交的方法數就是卡塔蘭數Cn.

分析設所求方法數目是Dn，我們記y1,y2,…,y2n是圓周上依次按順時針排列的2n個點.若y1與yk相連，且能把其余點成對連接起來使得線段不相交，則k=2m必須是偶數，于是把問題轉化成y1,y2,…,yk-1,yk和yk,…y2n-1,y2n這兩個部分的對應成對連接而不相交的問題，方法數依次是Dm和Dn-1-m，對m=0,1,…,n-1求和

其中D0=1.

圖1

下面說明問題1的方法數Cn和問題2的方法數Dn是相等的.事實上，對于任意一個n個+1和n個-1的序列y1,y2,…,y2n，對從左到右的第一個-1及它前面的最近的一個+1，聯結這兩個點，然后在刪掉這兩點的序列中，重復上述過程，就得到n對不相交的連線.圖1是n=4的情形，對應序列是

(+1)(-1)(+1)(+1)(-1)(-1)(+1)(-1),

且這樣的對應是一一的，即Cn=Dn，從而也證明卡塔蘭數Cn滿足C0=1,且

(3)

許多不同形式的問題，本質上都等價于上面的基本問題，我們有時直接求得式(1)，有時導出遞推關系式(3)來求得卡塔蘭數.

2 卡塔蘭數不同形式的應用

前面給出了卡塔蘭數兩種不同的問題形式.下面來介紹一下卡塔蘭數在國內外數學競賽中的應用，有些例題是比較顯然的應用[2]，有些需要對問題進行等價轉化，才能利用卡塔蘭數.但事實上利用卡塔蘭數的原理，一些很復雜的問題都可以迎刃而解.

例1在O-xy平面的單位長度的網格線上行走，從始點(0,0)走2n步到終點(n,n)，每步只能往右或向上行走1單位長度，求滿足條件y≤x的路徑數？

分析只要把向右一步記作+1，向上一步記作-1，這和問題1是等價的.注意到：若條件y≤x替換成y

例2在2×n的表格中填入數字1，2,…,2n，求每行、每列的數字是升序排列的方案數.

分析用n個+1和n個-1排成一列σ=x1x2…x2n，若其中xi1,xi2,…,xin為+1，則表格第一行的數為i1，i2，…，in，而對應-1的數依次填入第二行，這樣每行的數字顯然是升序.再若序列σ中從左到右，數字+1的數目大于等于-1的數目，即滿足式(2)，則表格中每列的數字也是升序.反之，將數字1,2,…,2n填入2×n的表格中，第一行的數字i對應xi=±1，而第二行的數字j對應的xj=-1，于是每行、每列的數字是升序排列所得到的序列σ=x1x2…x2n滿足式(2).

例3求方程x1+x2+…+xn=n的非負整數解的個數，要求滿足

x1+…+xk≥k,其中1≤k≤n.

分析將每組解中的xi變換為11…10(其中xi個1，1個0，若xi是0則不變)，依次連在一起，會產生n個1和n個0的序列.例如n=3的一個解x1=1，x2=2,x3=0,則對應序列101100.我們可以看出，這樣的序列從左到右的任何位置，1的個數比0的個數多.如果數字0用-1來代替，則等價于問題1.于是原方程的非負整數解的個數就是卡塔蘭數.

例4設n+1個元素相乘，P=a0×a1×…×an，不改變其順序，只用括號表示成對的乘積，試問有幾種括號化的方案？

分析可以導出和式(3)相同的遞推關系.事實上，設括號化的方案數目為Dn，考慮n個乘法中最后一個運算的乘法來分類計數.若最后一個乘法是第k個，則前面由k-1個乘法，它的數目是Dk-1；而后面有n-k個乘法，數目是Dn-k.取遍k=1，2，…，n，定義D0=1，于是

這就是遞推關系(3)，從而Dn=Cn.

例5求一個凸n+2邊形區域劃分成三角形區域的方法個數.

分析設凸n+2邊形區域劃分成三角形區域的方法數為Dn，記D0=1.設凸n+2邊形的頂點按順時針方向依次記為x1，x2…，xn+2.若x1xn+2是劃分的其中一個三角形的一條邊，設另一頂點是xk(其中k=2，3，…,n+1)，即3個頂點x1，xk，xn+2是其中的一個三角形區域，則凸n+2邊形分成兩部分，凸k邊形和凸n+2-k邊形，于是

同樣得出遞推關系式(3)，也即Dn=Cn.

例6求用n個長方形填充一個高度為n的階梯狀圖形的方法個數.

分析首先看到用n個長方形填充一個高度為n的階梯狀圖形時，任何兩個矩形都不能合并成一個矩形.當n=3時，如圖2，所求的方法數是5.

圖2

圖3

對于一般的n，若記所求為Dn，規定D0=1，則當右下角是k×(n-k+1)時，如圖3，右邊剩下的是高為k-1的階梯狀圖形，上邊剩下的是高為n-k的階梯狀圖形.對k=1，2，3，…,n+1遞推計數求和,得

同樣得出遞推關系式(3)，也即Dn=Cn.

例7某班的男生和女生人數相同(全班人數不少于4人),將他們以各種不同的方式排成一行,看看能否將這一行分成兩部分,使得在每一部分中,男生和女生都各占一半,設不能這樣分開的排法種數為a,恰有一種方法可以這樣分開的排法的種數為b.求證:b=2a.

(1972年匈牙利數學奧林匹克競賽試題第2題)

分析任取一種排隊方式,若從左到右第i個人為男生,記xi=+1,否則記xi=-1,得序列x1x2…x2n.若能將隊列分為兩部分,使兩邊男女各占一半,則存在i使得

x1+x2+…+xi=0,

xi+1+xi+2+…+x2n=0,

x1+x2+…+xi=0,

xi+1+xi+2+…+x2n=0,

例8設數列{cn}定義如下:c0=1,c2n+1=cn(其中n≥0),c2n=cn+cn-2en(其中n>0),en是滿足2en|n的最大非負整數.證明:

(2011年美國國家隊選拔題第5題)

分析由于要證明的等式的右邊是第n+1個卡塔蘭數,因此,其就是n+1對括號排成一行的所有可能數.

對于某一個關于括號的排列,設其標號為k是二進制的n位數,k從左到右的第r個數碼為0或1取決于關于括號的排列從左到右的第2r+1個括號是閉(即“)”),還是開(即“(”).

設dk是所有標號為k的n+1對括號的排列數目,事實上dk與n無關.在二進制表示的k前面加一個0,相當于在關于括號的排列的第1個開括號的后面插入一對形如()的括號.故只需證明:ck=dk(其中k=0,1,…,2n-1).

對于任意的n,d0=c0=1.這是由于標號為0的關于括號的排列只能是形如:(()()…()).接下來只需證明:dk和ck滿足同樣的遞歸式.

若關于括號排列的標號為2k+1,則其末位數為1,于是關于括號排列的最后一定是().從而,關于n+1對括號且標號為2k+1的所有排列的數目就等于關于n對括號且標號為k的所有排列的數目,即d2k+1=dk(因為dk與n無關).

考慮關于n+1對括號且標號為2k的排列.設2ek|k,則k在二進制表示下末尾恰有ek個0.于是第2n-2ek-1個位置上是開括號.

1)若其右邊緊接著是一個閉括號，將兩個括號作為一對括號從這個排列中去掉，剩下的關于n對括號的排列的標號為k-2ek；

2)若第2n-2ek個位置上是開括號，它可以與其右邊緊接著的一個閉括號(因為2k在二進制表示下末尾恰有ek+1個0)作為一對括號從這個排列中去掉，剩下的關于n對括號的排列的標號為k.

因為以上兩種情形均可逆，所以

d2k=dk+dk-2ek.

由于dk,ck有相同的初始值，且由遞歸式唯一確定，故對于所有的整數k≥0，有dk=ck.

[1] 單墫．數學奧林匹克命題人講座——集合與對應[M]．上海：上?？萍冀逃霭嫔纾?009.

[2] 張垚，冷崗松，沈文選．奧林匹克數學中的組合問題[M]．長沙：湖南師范大學出版社，2009.