卡塔蘭數(shù)的等價(jià)定義及其應(yīng)用

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

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

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

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

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

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

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，它的前幾項(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.

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

2兩個(gè)引理

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

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

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

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

證明設(shè)集合

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

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

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

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

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

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

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

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

x1+x2+…+xk≥0，②

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

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

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

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

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

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

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

證明可以導(dǎo)出和①式相同的遞推公式.事實(shí)上，設(shè)添括號(hào)的方案為Dn，考慮n個(gè)乘法中最后一個(gè)運(yùn)算的乘法來(lái)分類計(jì)數(shù).若最后一個(gè)乘法是第k個(gè)，則前面有k-1個(gè)乘法，它的添括號(hào)的數(shù)目是Dk-1；而后面有n-k個(gè)乘法，它的添括號(hào)的數(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時(shí)，有2種不同的結(jié)果：

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

當(dāng)n=3時(shí)，有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ó)Ⅲ卷）定義“規(guī)范01數(shù)列”an如下：an共有2m項(xiàng)，其中m項(xiàng)為0，m項(xiàng)為1，且對(duì)任意k≤2m，a1，a2，…，ak中0的個(gè)數(shù)不少于1的個(gè)數(shù).若m=4，則不同的“規(guī)范01數(shù)列”共有（）.

A.18個(gè)B.16個(gè)C.14個(gè)D.12個(gè)

解法1（列舉法）由題意，必有a1=0，a8=1，其余還有三個(gè)0和三個(gè)1，可以一一列舉出來(lái)，除第一項(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個(gè).

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

不考慮限制條件“對(duì)任意k≤2m，a1，a2，…，ak中0的個(gè)數(shù)不少于1的個(gè)數(shù)”，則中間6個(gè)數(shù)的情況共有C36＝20（種），其中存在k≤2m，a1，a2，…，ak中0的個(gè)數(shù)少于1的個(gè)數(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（種）.

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

Cn=1n+1Cn2n.

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

例2（2021年重慶數(shù)學(xué)競(jìng)賽試題）已知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個(gè)1和1 010個(gè)-1，且隨時(shí)保證x1+x2+…+xk≥0（k=1，2，…，2 020）.

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

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

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

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

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

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

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

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

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

解析設(shè)當(dāng)圓周上有2n個(gè)點(diǎn)，用n條弦來(lái)連接它們時(shí)，滿足要求的不同連線法總數(shù)為kn.如圖1，在給定點(diǎn)中選定一點(diǎn)A，并設(shè)它與點(diǎn)B間有弦AB相連，則點(diǎn)A和B將圓周分成的兩條弧中，每條內(nèi)部都有偶數(shù)個(gè)給定點(diǎn).設(shè)由A順時(shí)針到B的圓弧內(nèi)部有2j個(gè)點(diǎn)，則另一條弧的內(nèi)部有2（n-1-j）個(gè)點(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.

評(píng)析（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ù)的著名例子，是一個(gè)遞推用得比較透徹的問(wèn)題.由該題的解答過(guò)程，我們知道：

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

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

5變式訓(xùn)練

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

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

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

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

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

解析這時(shí)已經(jīng)把始點(diǎn)（0，0）和終點(diǎn)（n，n）除去，故只要考慮從點(diǎn)（1，0）到點(diǎn)（n，n-1）且滿足條件y<x的路徑數(shù)就可以了.此時(shí)只要把y軸向右移動(dòng)一個(gè)單位到y(tǒng)′，使得（1，0）變?yōu)椋?，0），（n，n-1）變?yōu)椋╪-1，n-1）（如圖4）.則問(wèn)題等價(jià)于在新坐標(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的個(gè)數(shù)都不少于bi的個(gè)數(shù)，即在由n個(gè)+1和n個(gè)-1組成的所有序列x1，x2，…，x2n中，從左到右的任何位置+1的個(gè)數(shù)不能少于-1的個(gè)數(shù).這和問(wèn)題1是等價(jià)的，所以排隊(duì)的方法數(shù)為Cn=1n+1Cn2n.

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

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

變式5求方程x1+x2+…+xn=n的非負(fù)整數(shù)解的個(gè)數(shù)，要求滿足x1+x2+…+xk≥k，其中1≤k≤n.

解析將每組解中的xi變換為11…10（其中xi個(gè)1，1個(gè)0，若xi是0則不變），依次連在一起，會(huì)產(chǎn)生n個(gè)1和n個(gè)0的序列.

例如n=3的一個(gè)解x1=1，x2=2，x3=0，則對(duì)應(yīng)序列101 100.可以看出，這樣的序列從左到右的任何位置，1的個(gè)數(shù)不少于0的個(gè)數(shù).

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

變式6求將一個(gè)凸n+2邊形區(qū)域劃分成三角形區(qū)域的方法數(shù).

解析設(shè)凸n+2邊形區(qū)域劃分成三角形區(qū)域的方法數(shù)為Dn，記D0=1.設(shè)凸n+2的頂點(diǎn)按順時(shí)針?lè)较蛞来斡洖閤1，x2，…，xn+2.若x1xn+2是劃分的其中一個(gè)三角形的一條邊，設(shè)另一個(gè)頂點(diǎn)是xk（其中k=2，3，…，n+1），此時(shí)凸n+2邊形被劃分成三個(gè)部分，一個(gè)是由3個(gè)頂點(diǎn)x1，xk，xn+2構(gòu)成的三角形區(qū)域，另外兩個(gè)分別是凸k邊形和凸n+2-k邊形，于是

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

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

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

6結(jié)束語(yǔ)

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

參考文獻(xiàn)：

［1］

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

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