妙用卡特蘭數公式解題

尼志福++趙廣華

摘要： 卡特蘭數又稱卡塔蘭數，是組合數學中一個常出現在各種計數問題中出現的數列，是以比利時數學家歐仁.查理. 卡塔蘭命名。許多高中數學問題可以用它來解決。

關鍵詞 卡特蘭數 01數列

2016年高考數學全國丙卷有這樣一道題目。定義“規范”01數列 如下： 共有2m項，其中m項為0，m項為，1，且對任意k 2m， 中0的個數不少于1的個數。若m=4，則不同的“規范”01數列共有（ ）

A18個 B16個 C14 個 D12個

此題答案為C，多數人采用列舉的方法解決此題。思路如下：

因為m=4，所以 共有8項，4項是0，4項是1。又因為對任意k 2m， 中0的個數不少于1的個數，所以首項 ，末項 。其余6項3項為0，3項為1，共有 種，其中01110001，01101001， 01100101，01100011， 00111001， 01011001 6種情況不和題意，故“規范”01數列共有 個。筆者在講這道題目時，有頭腦靈活的學生提出這樣一個人思路：此題看成在一個4 4正方形中，由正方形一個頂點去相對頂點，行走過程中只能向上或向右，向上走一步用1表示，向右走一步用0表示，行走過程中不能經過對角線以上的點，問有幾種走法？

受學生問題啟發，我查閱相關資料發現這個題可以利用卡特蘭數公式來解決。卡特蘭數又稱卡塔蘭數，是組合數學中一個常出現在各種計數問題中出現的數列，是以比利時數學家歐仁.查理. 卡塔蘭命名。其通項公式

它能解決如下高中數學中常見問題。

1. n個+1和n個-1構成項數為2n的數列 ，其部分和滿足 問滿足條件的數列有多少個？

2. 有2n個人排成一行進入劇場，入場費5元，其中n個人只有一張5元鈔票，另外n個人只有一張10元鈔票，問有多少種方法使得只要有10元的人買票，售票處就有5元的鈔票找零？

3. 在圓上選擇2n個點，將這些點成對連接起來，使得所得到的n條線段不相交的方法數。。

這些問題的結果都為 。

有些題目看似不能用卡特蘭數公式解，決但經過轉化就可用。例如有這樣一道題：8個高矮不同的人，排成兩排，每排必須是從矮到高排列，而且第二排比對應的第一排的人高，問排列方式有多少種？

這個題可以看成把8個人排成一個數列，排在前排的為0，排在后拍的為1，這樣就轉化為這個數列4項為0，4項為1. 8個人從低到高對應數字1，2，3 8，每一個0 1數列都按照從小到大順序排列，即對應數字1，2，3 8。如：00011011對應排列

第一排1 2 3 6 第二排4 5 7 8 01110001就對應排列 第一排1 5 6 7

第二排2 3 4 8 要滿足第二排比對應的第一排的人高，必須對任意k 8， 中0的個數不少于1的個數這樣此題就轉化為和我們開始講的2016年高考數學全國丙卷那道題為同一題目了。

在我們日常教學中，對學生進行適當的知識擴充，就會使許多問題簡單化。當然這需要我們自身知識豐富，不斷學習，才能把大學知識與高中適當銜接。