●

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

1 卡塔蘭數(shù)的介紹

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

(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,……

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

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

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

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

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

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

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

其中D0=1.

圖1

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

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

且這樣的對應(yīng)是一一的，即Cn=Dn，從而也證明卡塔蘭數(shù)Cn滿足C0=1,且

(3)

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

2 卡塔蘭數(shù)不同形式的應(yīng)用

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

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

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

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

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

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

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

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

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

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

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

例5求一個凸n+2邊形區(qū)域劃分成三角形區(qū)域的方法個數(shù).

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

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

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

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

圖2

圖3

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

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

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

(1972年匈牙利數(shù)學(xué)奧林匹克競賽試題第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設(shè)數(shù)列{cn}定義如下:c0=1,c2n+1=cn(其中n≥0),c2n=cn+cn-2en(其中n>0),en是滿足2en|n的最大非負(fù)整數(shù).證明:

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

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

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

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

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

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

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

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

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

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

d2k=dk+dk-2ek.

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

[1] 單墫．?dāng)?shù)學(xué)奧林匹克命題人講座——集合與對應(yīng)[M]．上海：上?？萍冀逃霭嫔纾?009.

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