摘要：介紹卡塔蘭數(shù)并推導(dǎo)出其等價定義，通過舉例說明卡塔蘭數(shù)等價定義的應(yīng)用.

關(guān)鍵詞：卡塔蘭數(shù)；等價定義；組合計(jì)數(shù)；路徑

中圖分類號：G632文獻(xiàn)標(biāo)識碼：A文章編號：1008-0333（2024）28-0012-05

卡塔蘭數(shù)列是組合數(shù)學(xué)中一個重要的數(shù)列，這個數(shù)由比利時數(shù)學(xué)家卡塔蘭（Eugene Charles Catalan，1814-1894）命名，它常常出現(xiàn)在各種計(jì)數(shù)問題中，并在高考和競賽中有著廣泛的應(yīng)用.

1卡塔蘭數(shù)的遞推公式與通項(xiàng)公式[1]

它的通項(xiàng)公式為

Cn=1n+1Cn2n=（2n）?。╪+1）！n！.

它的遞推公式為

Cn=∑n-1m=0CmCn-1-m=Cn-1+C1Cn-2+C2Cn-3+…+

Cn-2C1+Cn-1.①

通常約定C0=C1=1，它的前幾項(xiàng)為：

C0=C1=1，C2=2，C3=5，C4=14，C5=42，C6=132，

C7=429，C8=1 430，C9=4 862，C10=16 796，….

常用公式：Cn=1n+1Cn2n=Cn2n-Cn-12n.

有讀者會問：由遞推公式①怎樣求得其通項(xiàng)公式？如果直接求的話，需要用到母函數(shù)的知識，感興趣的讀者可自行嘗試推導(dǎo).

2兩個引理

引理1n個球中有k個是完全相同的白球，其余的是完全相同的黑球，將它們排成一排，有Ckn種不同的排法.

證明（方法1）由多重集的全排列，可知答案為n！k！（n-k）！=Ckn.

（方法2）即是從n個位置中取出k個位置放白球，因而答案為Ckn.

引理2將n個完全一樣的白球和n個完全一樣的黑球逐一從袋中取出，直至取完.在取球過程中，至少有一次取出的白球多于取出的黑球的取法有Cn+12n種.

證明設(shè)集合

X={在取球過程中至少有一次取出的白球多于黑球的取法}，

Y={將n+1個白球和n-1個黑球排成一列的方法}.

對于x∈X，根據(jù)定義，在這種取法中，必有某一時刻首次出現(xiàn)取出的白球多于黑球，這時未取的黑球比未取的白球多1.將未取的白球與未取的黑球顏色互換，則總球數(shù)仍為2n，但白球總數(shù)變?yōu)閚+1，黑球總數(shù)變?yōu)閚-1，這就將取法x映射為某個y∈Y.

這個映射f是單射，因?yàn)閷α硪环N取法x′，或者在x′中第一次出現(xiàn)取出的白球多于黑球的時刻不同于x，或者在相同時刻首次出現(xiàn)取出的白球多于黑球，而以后的取法有所不同.無論哪一種情況，f（x′）均與y=f（x）不同.

映射f是滿射，因?yàn)閷θ我粂∈Y，依排列y的順序數(shù)過去，在白球個數(shù)第一次超出黑球后，將以后的黑球與白球互換，就產(chǎn)生一種取球方法x∈X，并且顯然f（x）=y.

于是f是一一對應(yīng)的，所以X=Y=Cn+12n.

3卡特蘭數(shù)的等價定義

問題1由n個+1和n個-1組成的所有序列x1，x2，…，x2n中，求滿足條件

x1+x2+…+xk≥0，②

（其中k=1，2，…，2n）的序列數(shù)目.

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

證明記Sn是由n個+1和n個-1組成的序列的集合，則由引理1知Sn=Cn2n.

記Sn中不滿足條件②的序列的集合為An，則對于不符合要求的排法x∈An，必有一個時刻出現(xiàn)不滿足條件②的序列，即到這時為止，-1的個數(shù)多于+1的個數(shù).如果將-1看作白球，將+1看作黑球，那么x就相當(dāng)于將n個完全一樣的白球和n個完全一樣的黑球逐一從袋中取出，且在取球過程中至少有一次取出的白球多于取出的黑球的取法.由引理2知，An=Cn+12n.

從而滿足條件（2）的序列的個數(shù)為

Sn-An=Cn2n-Cn-12n=1n+1Cn2n.

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

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

Dn=∑nk=1Dk-1Dn-k=∑n-1m=0DmDn-1-m.

這就是遞推公式①，從而Dn=Cn=1n+1Cn2n.

例如，當(dāng)n=2時，有2種不同的結(jié)果：

（a0×a1）×a2，a0×（a1×a2）.

當(dāng)n=3時，有5種不同的結(jié)果：

（a0×a1）×（a2×a3），

［（a0×a1）×a2］×a3，

［a0×（a1×a2）］×a3，

a0×［（a1×a2）×a3］，

a0×［a1×（a2×a3）］.

4應(yīng)用

例1（2016年全國Ⅲ卷）定義“規(guī)范01數(shù)列”an如下：an共有2m項(xiàng)，其中m項(xiàng)為0，m項(xiàng)為1，且對任意k≤2m，a1，a2，…，ak中0的個數(shù)不少于1的個數(shù).若m=4，則不同的“規(guī)范01數(shù)列”共有（）.

A.18個B.16個C.14個D.12個

解法1（列舉法）由題意，必有a1=0，a8=1，其余還有三個0和三個1，可以一一列舉出來，除第一項(xiàng)和第八項(xiàng)外，中間六項(xiàng)的排列如下：

000 111，001 011，001 101，001 110，010 011，010 101，010 110，011 001，011 010，100 011，100 101，100 110，101 001，101 010，共14個.

解法2（分類計(jì)數(shù)法）首先明確“規(guī)范01數(shù)列”的含義，根據(jù)組合知識求解.由題意知：當(dāng)m＝4時，“規(guī)范01數(shù)列”共含有8項(xiàng)，其中4項(xiàng)為0，4項(xiàng)為1，且必有a1＝0，a8＝1.

不考慮限制條件“對任意k≤2m，a1，a2，…，ak中0的個數(shù)不少于1的個數(shù)”，則中間6個數(shù)的情況共有C36＝20（種），其中存在k≤2m，a1，a2，…，ak中0的個數(shù)少于1的個數(shù)的情況有：

①若a2=a3=1，則有4種；

②若a2=1，a3=0，則a4=1，a5=1，只有1種；

③若a2=0，則a3=a4=a5=1，只有1種.

綜上，不同的“規(guī)范01數(shù)列”共有20-6＝14（種）.

評析由a1，a2，…，ak中0的個數(shù)不少于1的個數(shù)，知“規(guī)范01數(shù)列”的個數(shù)就是卡塔蘭數(shù)：

Cn=1n+1Cn2n.

因?yàn)閙=4，所以所求的結(jié)果為C4=14+1C48=14.

例2（2021年重慶數(shù)學(xué)競賽試題）已知xi∈{-1，1}，i=1，2，…，2 021，并且x1+x2+…+xk≥0（k=1，2，…，2 020），x1+x2+…+x2 021=-1，則有序數(shù)組（x1，x2，…，x2 021）的組數(shù)為.

解析由x1+x2+…+x2 020≥0，

x1+x2+…+x2 021=-1，

x2 021∈{-1，1}，

得x2 021=-1，x1+x2+…+x2 020=0.

所以在x1，x2，…，x2 020中有1 010個1和1 010個-1，且隨時保證x1+x2+…+xk≥0（k=1，2，…，2 020）.

由問題1知，有序數(shù)組（x1，x2，…，x2 021）的組數(shù)為卡塔蘭數(shù)，所以答案為C1 010=11 011C1 0102 020.

例3（強(qiáng)基計(jì)劃模擬題）某電影院票房前有2n個人排隊(duì)，每人欲購買一張5元的電影票.在這些人中，有n個人，每人有一張5元鈔票，其余的人每人有一張10元鈔票，而票房在賣票前并無任何鈔票.問：能夠讓每個人都能順利地買到電影票的排隊(duì)方式有多少種？

解析首先，不考慮找零錢是否發(fā)生困難，將n個持10元錢的人與n個持5元錢的人排成一列，有Cn2n種方法.其中找零錢發(fā)生困難的那些排法需要剔除，它們的集合記為A.

對于不符合要求的排法x∈A，必有一個時刻出現(xiàn)找不出零錢的問題，即到這時為止，持10元錢的人數(shù)多于持5元錢的人數(shù).如果將持10元錢的人看作白球，將持5元錢的人看作黑球，那么x就相當(dāng)于將n個完全一樣的白球和n個完全一樣的黑球逐一從袋中取出，且在取球過程中至少有一次取出的白球多于取出的黑球的取法.由引理2知，A=Cn+12n.

所以，找零錢不發(fā)生困難的排列方法數(shù)為

Cn2n-Cn+12n=Cn=（2n）?。╪+1）！n！.

注意到對應(yīng)于由n張5元和n張10元鈔票組成的全排列，2n個人的排隊(duì)方式有（n?。?種，于是

N=（2n）?。╪+1）！n！·（n?。?=（2n）！n+1.

例4（1950年第13屆莫斯科數(shù)學(xué)奧林匹克競賽）在圓周上給定20個點(diǎn)，并用10條既無公共端點(diǎn)又互不相交的弦來連接它們.問：共有多少種不同的連線法？

解析設(shè)當(dāng)圓周上有2n個點(diǎn)，用n條弦來連接它們時，滿足要求的不同連線法總數(shù)為kn.如圖1，在給定點(diǎn)中選定一點(diǎn)A，并設(shè)它與點(diǎn)B間有弦AB相連，則點(diǎn)A和B將圓周分成的兩條弧中，每條內(nèi)部都有偶數(shù)個給定點(diǎn).設(shè)由A順時針到B的圓弧內(nèi)部有2j個點(diǎn)，則另一條弧的內(nèi)部有2（n-1-j）個點(diǎn).兩條弧內(nèi)給定點(diǎn)的不同連線數(shù)分別為kj和kn-1-j，故知以弦AB為一條弦的不同連線數(shù)為kj·kn-1-j，從而得到如下的遞推關(guān)系：

kn=kn-1+k1kn-2+k2kn-3+…+kn-2k1+kn-1.

容易看出，k1=1，k2=2.而此遞推公式就是遞推公式

①，從而kn=Cn.

所以k10=C10=111C1020=20！11！10！=16 796.

即所求的不同連線法的總數(shù)為16 796.

評析（1）我們根據(jù)遞推公式及k1=1，k2=2可以依次算出：k3=5，k4=14，k5=42，k6=132，k7=429，k8=1 430，k9=4 862，k10=16 796.

（2）本題也是卡塔蘭數(shù)的著名例子，是一個遞推用得比較透徹的問題.由該題的解答過程，我們知道：

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

如圖2所示，是當(dāng)n=3時的連法，共有5組.

5變式訓(xùn)練

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

解析只要把向右一步記作+1，向上一步記作-1，則滿足條件y≤x的路徑數(shù)就是在任何時刻向右走的步數(shù)不能少于向上走的步數(shù)，也即在由n個+1和n個-1組成的所有序列x1，x2，…，x2n中，必須滿足從左到右的任何位置+1的個數(shù)不能少于-1的個數(shù).這和問題1是等價的，所以滿足條件y≤x的路徑數(shù)為卡塔蘭數(shù)Cn=1n+1Cn2n.

評析本題的結(jié)論也可以這樣通俗地表述：在n×n的格子中，只在下三角行走，每次橫或豎走一格，則有Cn=1n+1Cn2n種走法.這樣的路線稱為惠特沃思（Whitworth）路線，簡稱W線.

若n=4，路徑數(shù)為C4=14+1C48=14，如圖3所示.

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

解析這時已經(jīng)把始點(diǎn)（0，0）和終點(diǎn)（n，n）除去，故只要考慮從點(diǎn)（1，0）到點(diǎn)（n，n-1）且滿足條件y<x的路徑數(shù)就可以了.此時只要把y軸向右移動一個單位到y(tǒng)′，使得（1，0）變?yōu)椋?，0），（n，n-1）變?yōu)椋╪-1，n-1）（如圖4）.則問題等價于在新坐標(biāo)系中，從點(diǎn)（0，0）到點(diǎn)（n-1，n-1）且滿足條件y≤x的路徑數(shù).由第1題知，答案為Cn-1=1nCn-12n-2.

變式3男生、女生各n人，排成兩列.男生隊(duì)列的次序?yàn)閍1，a2，…，an，女生隊(duì)列的次序?yàn)閎1，b2，…，bn.將他們并為一列，如果男生的先后次序保持不變，女生的先后次序保持不變，且ai必須在bi前面（i=1，2，…，n），那么有多少種排法？

解析把a(bǔ)i記作+1，把bi記作-1（i=1，2，…，n），則ai必須在bi前面，即是在從左到右的任何位置ai的個數(shù)都不少于bi的個數(shù)，即在由n個+1和n個-1組成的所有序列x1，x2，…，x2n中，從左到右的任何位置+1的個數(shù)不能少于-1的個數(shù).這和問題1是等價的，所以排隊(duì)的方法數(shù)為Cn=1n+1Cn2n.

變式42n個人高矮互不相同，有多少種方法將他們由矮到高的次序排成兩行，每行n人，并且第一行的第j個人比第二行的第j個人高（j=1，2，…，n）？

解析將這2n個人由矮到高排成一排，并將其中原來屬于第一行的人記作+1，原來屬于第二行的人記作-1，此時滿足題設(shè)要求的排隊(duì)即在由n個+1和n個-1組成的所有序列x1，x2，…，x2n中，從左到右的任何位置+1的個數(shù)不能少于-1的個數(shù).這和問題1是等價的，所以排隊(duì)的方法數(shù)為Cn=1n+1Cn2n.

變式5求方程x1+x2+…+xn=n的非負(fù)整數(shù)解的個數(shù)，要求滿足x1+x2+…+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)序列101 100.可以看出，這樣的序列從左到右的任何位置，1的個數(shù)不少于0的個數(shù).

如果數(shù)字0用-1來代替，則等價于問題1，于是原方程的非負(fù)整數(shù)解的個數(shù)就是卡特蘭數(shù)Cn=1n+1Cn2n.

變式6求將一個凸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），此時凸n+2邊形被劃分成三個部分，一個是由3個頂點(diǎn)x1，xk，xn+2構(gòu)成的三角形區(qū)域，另外兩個分別是凸k邊形和凸n+2-k邊形，于是

Dn=∑n+1k=2Dk-2Dn+1-k=∑n-1m=0DmDn-1-m.

這就是遞推公式①，從而Dn=Cn=1n+1Cn2n.

評析若是凸六邊形，即n=4，則劃分成三角形區(qū)域的方法數(shù)為C4=14+1C48=14，如圖5所示.

6結(jié)束語

卡塔蘭數(shù)在高考數(shù)學(xué)中為解決特定類型的計(jì)數(shù)問題提供了新的思路和方法.掌握卡塔蘭數(shù)可以拓寬學(xué)生的解題視野，提高解題效率.在未來的高考中，卡塔蘭數(shù)可能會以更加多樣化的形式出現(xiàn)，學(xué)生應(yīng)加強(qiáng)對這類特殊數(shù)學(xué)概念的理解和應(yīng)用，為高考數(shù)學(xué)取得優(yōu)異成績奠定基礎(chǔ).

參考文獻(xiàn)：

［1］

李鴻昌.高考題的高數(shù)探源與初等解法[M].合肥：中國科學(xué)技術(shù)大學(xué)出版社，2022.

［責(zé)任編輯：李璟］