妙用卡特蘭數(shù)公式解題

尼志福++趙廣華

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

關(guān)鍵詞 卡特蘭數(shù) 01數(shù)列

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

A18個 B16個 C14 個 D12個

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

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

受學(xué)生問題啟發(fā)，我查閱相關(guān)資料發(fā)現(xiàn)這個題可以利用卡特蘭數(shù)公式來解決?？ㄌ靥m數(shù)又稱卡塔蘭數(shù)，是組合數(shù)學(xué)中一個常出現(xiàn)在各種計(jì)數(shù)問題中出現(xiàn)的數(shù)列，是以比利時數(shù)學(xué)家歐仁.查理. 卡塔蘭命名。其通項(xiàng)公式

它能解決如下高中數(shù)學(xué)中常見問題。

1. n個+1和n個-1構(gòu)成項(xiàng)數(shù)為2n的數(shù)列 ，其部分和滿足 問滿足條件的數(shù)列有多少個？

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

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

這些問題的結(jié)果都為 。

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

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

第一排1 2 3 6 第二排4 5 7 8 01110001就對應(yīng)排列 第一排1 5 6 7

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

在我們?nèi)粘＝虒W(xué)中，對學(xué)生進(jìn)行適當(dāng)?shù)闹R擴(kuò)充，就會使許多問題簡單化。當(dāng)然這需要我們自身知識豐富，不斷學(xué)習(xí)，才能把大學(xué)知識與高中適當(dāng)銜接。