“卡塔蘭數(shù)”問題的探究

２０２４年高考數(shù)學新課標卷最大的變化就是題目數(shù)量減少、順序和分值的調(diào)整、壓軸題的創(chuàng)新設置，種種轉(zhuǎn)變都旨在反對機械刷題，是一次從考查舊知、結(jié)論到注重考查思維過程、思維品質(zhì)的轉(zhuǎn)變，有利于服務拔尖創(chuàng)新人才的選拔，反映新高考改革的導向．在此背景下，２０２５屆湖南長郡中學高三第一次調(diào)研檢測第１４題（例１）是一道“卡塔蘭數(shù)”的新定義試題，旨在考查學生的綜合能力和學科素養(yǎng)，對學生邏輯推理的素養(yǎng)和數(shù)學思維品質(zhì)要求較高．本文介紹“卡塔蘭數(shù)”的定義、相關公式和等價問題，賞析與“卡塔蘭數(shù)”相關的問題，展示“卡塔蘭數(shù)”的應用．

１ 題目呈現(xiàn)與解析

例１ 清代數(shù)學家明安圖所著?割圓密率捷法?中比西方更早提到了“卡塔蘭數(shù)”（以比利時數(shù)學家歐仁查理卡塔蘭的名字命名）．有如下問題：在n×n的格子中，從左下角出發(fā)走到右上角，每一步只能往上或往右走一格，且走的過程中只能在左下角與右上角的連線的右下方（不能穿過，但可以到達該連線），則共有多少種不同的走法？ 此問題的結(jié)果即“卡塔蘭數(shù)”Cn ＝Cn２n －Cn２n－１．如圖 １ 所示，現(xiàn)有３×４的格子，每一步只能往上或往右走一格，則從左下角A走到右上角B 共有______種不同的走法;若要求從左下角A 走到右上角B 的過程中只能在直線AC 的右下方，但可以到達直線AC，則有______種不同的走法．

解析 此題是填空題的壓軸題，有一定的難度，難點在于讀懂題意．第一個空比較簡單，第二個空可以分為兩類路徑：一類是經(jīng)過C 到B，可轉(zhuǎn)化為３×３格子中的“卡塔蘭數(shù)”問題;另一類是不經(jīng)過C到B，用列舉法可求得走法數(shù)，再用分類加法計數(shù)原理即可得總的走法數(shù)．也可以補全成４×４的格子，再套用題目所給“卡塔蘭數(shù)”公式直接得出結(jié)果．

第一個空很簡單，從A 到B 共需走７步，其中４步向右，３步向上，即共有C４７＝C３７＝３５種走法，下面重點解析第二個空．

方法１ （分類討論）從左下角A 走到右上角B可分為兩類路徑：一類是經(jīng)過C 到B，可轉(zhuǎn)化為３×３格子中的“卡塔蘭數(shù)”問題，套用公式可得有C３ ＝C３６－C２６＝２０－１５＝５種走法;另一類是不經(jīng)過C 到B，用列舉法可得走法種數(shù)．設A（０，０），C（３，３），B （４，３），還需再分為以下的三小類．

如果經(jīng)過點（３，２）（不經(jīng)過點（３，１））到B，只需考慮從A（０，０）到點（２，２）的走法種數(shù)即可，顯然有２種（一種為（０，０）→（１，０）→（１，１）→（２，１）→（２，２）;另一種為（０，０）→（１，０）→（２，０）→（２，１）→（２，２））．

如果經(jīng)過點（３，１）到B，先考慮從A （０，０）到點（３，１）的走法種數(shù)，顯然有３種（（０，０）→（１，０）→（１，１）→（２，１）→（３，１）;（０，０）→（１，０）→（２，０）→（２，１）→（３，１）;（０，０）→（１，０）→（２，０）→（３，０）→（３，１））．再考慮從點（３，１）到B（４，３）的走法種數(shù)，顯然有２種（（３，１）→（４，１）→（４，２）→（４，３）;（３，１）→（３，２）→（４，２）→（４，３）），再由分布乘法計數(shù)原理可知，共有３×２＝６種走法．

如果經(jīng)過點（３，０）（不經(jīng)過點（３，１））到B，顯然只有１種走法（（０，０）→（１，０）→（２，０）→（３，０）→（４，０）→（４，１）→（４，２）→（４，３））．

綜上，不經(jīng)過C 到B，用列舉法可得共有２＋６＋１＝９種走法，再加上經(jīng)過C 到B 的５種走法，從左下角A 走到右上角B 共有９＋５＝１４種不同的走法．

方法２ （補全表格成４×４的格子）如圖２所示，因為從B到D 只有１種走法，所以A 從直線AC 的右下方到B 的走法種數(shù)和A 從直線AD 的右下方到D 的走法種數(shù)完全相同．套用卡塔蘭數(shù)公式可知共有C４＝C４８－C３８＝７０－５６＝１４種不同的走法．

點評 第一個空只需考慮向右走的４步或向上走的３步即可，C４７＝C３７＝３５．求解第二個空顯然方法２更為簡便，充分利用了等價轉(zhuǎn)化思想將３×４的格子轉(zhuǎn)化為４×４的格子，緊扣題中所給信息———“卡塔蘭數(shù)”的計算公式，直接套用公式計算，當然方法１也是可行的方法，難點在于分類和列舉．此外，可以用直接列舉的手段，驗證“卡塔蘭數(shù)”公式的正確性，如圖３所示．

２ “卡塔蘭數(shù)”及其相關公式

２.１ 基本介紹

“卡塔蘭數(shù)”最早由清代數(shù)學家明安圖發(fā)現(xiàn)和研究，后歐拉在研究凸包劃分成三角形時也發(fā)現(xiàn)了該數(shù)（數(shù)列），最終以比利時數(shù)學家卡塔蘭的名字命名．“卡塔蘭數(shù)”常常出現(xiàn)在各種計數(shù)問題中，并在高考和競賽中有著廣泛的應用．

“卡塔蘭數(shù)”的通項公式為

通常約定C０＝C１＝１，除此之外常用的還有C２＝２，C３＝５，C４＝１４，C５＝４２，C６＝１３２等前幾項．

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

２.２ “卡塔蘭數(shù)”公式Cn ＝Cn ２n －Cn－１２n 的證明

證法１ （幾何意義）如圖４所示，在n×n 的格子中，從（０，０）到（n，n）的最短路徑走法顯然有Cn２n 種．將（０，０）到（n，n）連線（圖４中的斜線y＝x）右下方（可以到達連線）的走法稱為“合法路徑”，顯然“合法路徑”的總數(shù)即為“卡塔蘭數(shù)”Cn ;將經(jīng)過（０，０）到（n，n）連線左上方（經(jīng)過圖４中網(wǎng)格與斜線y＝x ＋１的交點）的走法稱為“非法路徑”，記“非法路徑”的總數(shù)為m ．

先考慮經(jīng)過點（１，２）（圖４中標記的“第一個觸碰點”，稱為“非法點”）的“非法路徑”數(shù)，根據(jù)對稱性，從點（１，２）到點（n，n）的最短路徑總數(shù)和從點（１，２）到點（n－１，n＋１）的最短路徑總數(shù)相等．顯然經(jīng)過其他“非法點”時也有相同的結(jié)論．由以上分析，不難得到以下結(jié)論：從點（０，０）到點（n，n）的“非法路徑”總數(shù)和從點（０，０）到點（n－１，n＋１）的最短路徑總數(shù)相等，所以m ＝Cn２n－１＝Cn＋１ ２n ，則Cn ＝Cn２n －m ＝Cn２n －Cn－１ ２n ．

證法２ （代數(shù)意義）“卡塔蘭數(shù)”的等價定義：由n 個＋１和n 個－１組成的所有序列x１，x２，，x２n中，滿足條件x１＋x２＋＋xk ≥０（k＝１，２，，２n）的序列數(shù)目即為“卡塔蘭數(shù)”

形象地說，要滿足條件，就是在這個序列中，從左到右的任何位置及之前的位置中，數(shù)字＋１出現(xiàn)的次數(shù)不比－１出現(xiàn)的次數(shù)少．

記Sn 是由n 個＋１和n 個－１組成的所有序列的集合，顯然|Sn|＝Cn２n ．

記Sn 中不滿足條件的序列的集合為An ．對于不符合要求的排法x∈An ，必有一個時刻出現(xiàn)不滿足條件的序列，即到這時為止，－１的個數(shù)多于＋１的個數(shù)．如果將－１看作白球，將＋１看作黑球，那么x 就相當于將n 個完全一樣的白球和n 個完全一樣的黑球逐一從袋中取出，且在取球過程中至少有一次取出的白球多于取出的黑球的取法．由引理１知|An|＝Cn＋１ ２n ＝Cn－１ ２n ，從而滿足條件的序列的個數(shù)為

|Sn|－|An|＝Cn２n －Cn－１ ２n ．

３ “卡塔蘭數(shù)”的應用

“卡塔蘭數(shù)”是重要的數(shù)學模型，在高考題、模擬題、競賽題中都有著廣泛的應用，需要深入研究，以培養(yǎng)數(shù)學思維，發(fā)展邏輯推理和數(shù)學建模的核心素養(yǎng)．

３.１ 路徑問題

例２ 如圖１所示，現(xiàn)有３×４的格子，每一步只能往上或往右走一格，要求從左下角A 走到右上角B的過程中，除點A 外，只能在直線AC 的右下方，且不能到達直線AC，則有______種不同的走法．

解析 記A′（１，０），問題等價于在圖２右下角３×３的格子中，從A′走到B 的過程中只能在直線A′B 的右下方，但可以到達直線A′B，則有多少種不同的走法．顯然就是“卡塔蘭數(shù)”C３＝ １／３＋１C３６＝５，所以共有５種不同的走法．

點評 更一般地，在OＧxy 平面的單位長度的網(wǎng)格線上行走，從始點（０，０）走２n 步到終點（n，n），每步只能往右或向上行走１個單位長度，滿足條件y≤x 的路徑數(shù)為“卡塔蘭數(shù)”Cn ＝ １／ n＋１Cn２n ;滿足條件y＜x 的路徑數(shù)為Cn－１＝１／ nCn－１ ２n－２．

３.２ 序列（排序）問題

例３ （２０１６年全國Ⅲ卷理１２）定義“規(guī)范０１數(shù)列”{an}如下：{an }共有２m 項，其中m 項為０，m 項為１，且對任意k≤２m ，a１，a２，…，ak 中０的個數(shù)不少于１的個數(shù)．若m ＝４，則不同的“規(guī)范０１數(shù)列”共有（ ）．

A．１８個 B．１６個

C．１４個 D．１２個

解析 方法１（直接列舉）由題意知必有a１＝０，a８＝１，其余還有三個０和三個１，可以一一列舉出來，如下：

００００１１１１，０００１０１１１，０００１１０１１，０００１１１０１，００１００１１１，００１０１０１１，００１０１１０１，００１１００１１，００１１０１０１，０１０００１１１，０１００１０１１，０１００１１０１，０１０１００１１，０１０１０１０１，共１４個排列，故選C．

方法２ （間接法）由題意知，當m ＝４時，“規(guī)范０１數(shù)列”共含有８項，其中４項為０，４項為１，且必有a１＝０，a８＝１．先不考慮限制條件“對任意k≤２m ，a１，a２，，ak 中０的個數(shù)不少于１的個數(shù)”，則中間６個數(shù)的情況共有C３６＝２０ 種，其中存在k ≤２m ，a１，a２，，ak 中０的個數(shù)少于１的個數(shù)的情況．

若a２ ＝a３ ＝ １，則有４ 種，即０１１１０００１，０１１０１００１，０１１００１０１，０１１０００１１．若a２ ＝１，a３ ＝０，則a４＝１，a５ ＝１，只有１ 種，即０１０１１００１．若a２ ＝０，則a３＝a４＝a５＝１，只有１種，即００１１１００１．

綜上，不同的“規(guī)范０１數(shù)列”共有２０－６＝１４個，故選C．

點評 由a１，a２，…，ak 中０的個數(shù)不少于１的個數(shù)，知“規(guī)范０１ 數(shù)列”的個數(shù)就是“卡塔蘭數(shù)”Cn ＝ １／ n＋１Cn２n ，當m ＝４時，C４＝ １／４＋１C４８＝１４．

例４ 設a１，a２，a３，a４，a５ 是數(shù)字１，２，３，４，５的排列，若不存在１≤i＜j＜k≤５使得ai ＜aj ＜ak 成立，則所有這樣的排列數(shù)有______種．

解析 先考慮１，２，３，４四個數(shù)字滿足條件的排列為１４ 個，即４３１２，４３２１，４２３１，４２１３，４１３２，３４１２，３４２１，３２１４，３２４１，３１４２，２１４３，２４１３，２４３１，１４３２，然后考慮數(shù)字５插入每種類型的情形，共４２種．

點評 先考慮１，２，３三個數(shù)的排列，顯然只有１２３不符合題意，此時共有A３３－１＝６－１＝５＝C３ 種．再加入４，則含有１２３，１２４，１３４，２３４（不論這三個數(shù)是否相連）排序的排列都不符合題意，共有１４＝C４ 種．再加入５，可知符合題意的排列數(shù)即為相對應的“卡塔蘭數(shù)”，即C５＝ １／５＋１C５ １０＝４２種．如果將題目中“若不存在１≤i＜j＜k≤５使得ai＜aj ＜ak 成立”的條件改為“若不存在１≤i＜j＜k≤５使得aj＜ak ＜ai 成立”，由對稱性知，排列數(shù)不變，仍為C５＝４２種．

３.３ 解的個數(shù)問題

例５ 已知xi ∈{－１，１}，i＝１，２，…，２０２１，并且x１＋x２ ＋…＋xk ≥０（k ＝１，２，…，２０２０），x１ ＋x２＋…＋x２０２１＝－１，則有序數(shù)組（x１，x２，…，x２０２１）的組數(shù)為______．

解析 由x１＋x２ ＋…＋x２０２０ ≥０，x１ ＋x２ ＋…＋x２０２１＝－１，x２０２１∈{－１，１}，得x２０２１＝－１，x１＋x２＋…＋x２０２０＝０，所以在x１，x２，…，x２０２０中有１０１０個１和１０１０個－１，且保證x１＋x２＋…＋xk ≥０（k＝１，２，…，２０２０）．

由“卡塔蘭數(shù)”的代數(shù)意義，可知有序數(shù)組（x１，x２，…，x２０２１）的組數(shù)為“卡塔蘭數(shù)”，所以有序數(shù)組（x１，x２，…，x２０２１）的組數(shù)為C１０１０＝ １／１０１１C１２００１２００．

３.４ 找零問題

例６ 某公園售票處前有２n 個人排隊，每人欲購買一張５元的門票．在這些人中，有n 個人每人有一張５元鈔票，其余的人每人有一張１０元鈔票，而售票處在賣票前并無任何鈔票．問：使得每個人都能順利地買到門票的排隊方式有多少種？

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

對于不符合要求的排法x∈A ，必有一個時刻出現(xiàn)找不出零錢的情況，即到這時為止，持１０元錢的人數(shù)多于持５元錢的人數(shù)．如果將持１０元錢的人看作白球，將持５元錢的人看作黑球，那么x 就相當于將n個完全一樣的白球和n 個完全一樣的黑球逐一從袋中取出，且在取球過程中至少有一次取出的白球多于取出的黑球的取法．由引理１知|A|＝Cn＋１ ２n ，所以找零錢不發(fā)生困難的排列方法數(shù)為Cn２n －Cn＋１ ２n ＝Cn ＝ （２n）！／（n＋１）！ n！．

注意到對應于由n 張５元和n 張１０元鈔票組成的全排列，２n 個人的排隊方式有n！ ×n！ ＝（n！）２種，于是N ＝ （２n）！／（n＋１）！ n！×（n！）２＝（２n）！／n＋１．

４ 小結(jié)

本文列舉了幾種“卡塔蘭數(shù)”的實際應用，各種問題之間有著緊密的聯(lián)系，用組合的眼光看問題，大量復雜的代數(shù)、幾何問題都可以轉(zhuǎn)化為相對簡單的組合計數(shù)問題．在解決“卡塔蘭數(shù)”相關計數(shù)問題時，要善于運用集合間的一一映射理解“卡塔蘭數(shù)”的等價定義，將問題歸結(jié)為已經(jīng)解決過的數(shù)學模型，再用熟悉的模型解決新的問題，以此培養(yǎng)化歸與轉(zhuǎn)化能力，發(fā)展邏輯推理和數(shù)學建模的核心素養(yǎng)，提升數(shù)學思維品質(zhì)．

（完）