■佘軍仁 陳巧紅

例題(2016年全國Ⅲ卷)定義“規(guī)范01數(shù)列”{an}如下：{an}共有2m項(xiàng)，其中m項(xiàng)為0，m項(xiàng)為1，且對任意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è)

答案：C

探究一、用分步計(jì)數(shù)原理

解：由題意，{an}中共有8項(xiàng)，4項(xiàng)為0，4項(xiàng)為1，且第一項(xiàng)為0，第八項(xiàng)為1，且要符合對任意k≤2m，a1，a2，…，ak中0 的個(gè)數(shù)不少于1的個(gè)數(shù)。如圖1 所示，此時(shí)可按項(xiàng)數(shù)從小到大分步作答，但關(guān)鍵是只要前面出現(xiàn)3個(gè)0，即結(jié)束討論，分步如下。

圖1

圖2

(2)當(dāng)?shù)诙?xiàng)為1時(shí)，第三項(xiàng)只能為0，當(dāng)?shù)谒捻?xiàng)為0 時(shí)，共種情況；當(dāng)?shù)谒捻?xiàng)為1時(shí)，第五項(xiàng)只能為0時(shí)，共種情況。如圖3。

探究二、用分類計(jì)數(shù)原理

解：由題意，{an}中共有8項(xiàng)，4項(xiàng)為0，4項(xiàng)為1，且第一項(xiàng)為0，第八項(xiàng)為1，且要符合對任意k≤2m，a1，a2，…，ak中0 的個(gè)數(shù)不少于1的個(gè)數(shù)，分為以下幾種情況：

(1)前4項(xiàng)均為0，后4項(xiàng)均為1——共1種情況；

(3)前4項(xiàng)2個(gè)0，2個(gè)1，后4項(xiàng)2個(gè)0，2個(gè)1——共2×2種情況。

所以，共有1+9+4=14(種)情況。

探究三、構(gòu)造路徑問題，通過標(biāo)數(shù)法解題

解：在直角坐標(biāo)系下，若向右走1個(gè)單位代表0，向上走1個(gè)單位代表1，該題可轉(zhuǎn)化為在4×4方格y≤x的區(qū)域內(nèi)，從O點(diǎn)走到A點(diǎn)的最短路徑的條數(shù)。如圖4 所示，給經(jīng)過的每一個(gè)格點(diǎn)(i，j)[數(shù)學(xué)上把在平面直角坐標(biāo)系中橫縱坐標(biāo)均為整數(shù)的點(diǎn)稱為格點(diǎn)(latticepoint)或整點(diǎn)]標(biāo)數(shù)，數(shù)字為從O點(diǎn)到點(diǎn)(i，j)的最短路徑條數(shù)，除y=x上格點(diǎn)(i，i)標(biāo)的數(shù)字和格點(diǎn)(i，i-1)相同外，其余y＜x的區(qū)域內(nèi)格點(diǎn)(i，j)上標(biāo)的數(shù)字為格點(diǎn)(i-1，j)與格點(diǎn)(i，j-1)上標(biāo)的數(shù)字之和，可得最后到達(dá)A點(diǎn)最短路徑的條數(shù)為14種。

注：圖4 中標(biāo)在y=x上格點(diǎn)的數(shù)字又稱為“卡特蘭數(shù)”。

進(jìn)一步歸納：

定義“規(guī)范01數(shù)列”{an}如下：{an}共有2m項(xiàng)，其中m項(xiàng)為0，m項(xiàng)為1，且對任意k≤2m，a1，a2，…，ak中0的個(gè)數(shù)不少于1的個(gè)數(shù)，則不同的“規(guī)范01數(shù)列”共有個(gè)。

圖4