“卡塔蘭數”問題的探究

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

１ 題目呈現與解析

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

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

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

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

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

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

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

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

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

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

２ “卡塔蘭數”及其相關公式

２.１ 基本介紹

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

“卡塔蘭數”的通項公式為

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

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

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

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

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

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

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

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

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

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

３ “卡塔蘭數”的應用

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

３.１ 路徑問題

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

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

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

３.２ 序列（排序）問題

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

A．１８個 B．１６個

C．１４個 D．１２個

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

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

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

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

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

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

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

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

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

３.３ 解的個數問題

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

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

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

３.４ 找零問題

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

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

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

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

４ 小結

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

（完）