卡塔蘭數的等價定義及其應用

摘要：介紹卡塔蘭數并推導出其等價定義，通過舉例說明卡塔蘭數等價定義的應用.

關鍵詞：卡塔蘭數；等價定義；組合計數；路徑

中圖分類號：G632文獻標識碼：A文章編號：1008-0333（2024）28-0012-05

卡塔蘭數列是組合數學中一個重要的數列，這個數由比利時數學家卡塔蘭（Eugene Charles Catalan，1814-1894）命名，它常常出現在各種計數問題中，并在高考和競賽中有著廣泛的應用.

1卡塔蘭數的遞推公式與通項公式[1]

它的通項公式為

Cn=1n+1Cn2n=（2n）！（n+1）！n！.

它的遞推公式為

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

Cn-2C1+Cn-1.①

通常約定C0=C1=1，它的前幾項為：

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.

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

2兩個引理

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

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

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

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

證明設集合

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

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

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

這個映射f是單射，因為對另一種取法x′，或者在x′中第一次出現取出的白球多于黑球的時刻不同于x，或者在相同時刻首次出現取出的白球多于黑球，而以后的取法有所不同.無論哪一種情況，f（x′）均與y=f（x）不同.

映射f是滿射，因為對任一y∈Y，依排列y的順序數過去，在白球個數第一次超出黑球后，將以后的黑球與白球互換，就產生一種取球方法x∈X，并且顯然f（x）=y.

于是f是一一對應的，所以X=Y=Cn+12n.

3卡特蘭數的等價定義

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

x1+x2+…+xk≥0，②

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

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

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

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

從而滿足條件（2）的序列的個數為

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

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

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

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

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

例如，當n=2時，有2種不同的結果：

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

當n=3時，有5種不同的結果：

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

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

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

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

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

4應用

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

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

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

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（分類計數法）首先明確“規范01數列”的含義，根據組合知識求解.由題意知：當m＝4時，“規范01數列”共含有8項，其中4項為0，4項為1，且必有a1＝0，a8＝1.

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

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

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

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

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

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

Cn=1n+1Cn2n.

因為m=4，所以所求的結果為C4=14+1C48=14.

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

解析由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知，有序數組（x1，x2，…，x2 021）的組數為卡塔蘭數，所以答案為C1 010=11 011C1 0102 020.

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

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

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

所以，找零錢不發生困難的排列方法數為

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

注意到對應于由n張5元和n張10元鈔票組成的全排列，2n個人的排隊方式有（n！）2種，于是

N=（2n）！（n+1）！n！·（n！）2=（2n）！n+1.

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

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

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.

即所求的不同連線法的總數為16 796.

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

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

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

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

5變式訓練

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

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

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

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

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

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

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

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

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

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

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

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

變式6求將一個凸n+2邊形區域劃分成三角形區域的方法數.

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

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

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

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

6結束語

卡塔蘭數在高考數學中為解決特定類型的計數問題提供了新的思路和方法.掌握卡塔蘭數可以拓寬學生的解題視野，提高解題效率.在未來的高考中，卡塔蘭數可能會以更加多樣化的形式出現，學生應加強對這類特殊數學概念的理解和應用，為高考數學取得優異成績奠定基礎.

參考文獻：

［1］

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

［責任編輯：李璟］