☉重慶市第一中學(xué)校 張志華 武 曉

2016年高考理科全國(guó)卷Ⅱ和卷Ⅲ的排列組合問(wèn)題新穎有趣，表面上卷Ⅱ考查的是實(shí)際模型中的幾何組合計(jì)數(shù)問(wèn)題，卷Ⅲ考查的是純數(shù)學(xué)的數(shù)列新定義計(jì)數(shù)問(wèn)題，而如果站在更高的觀點(diǎn)上，可以發(fā)現(xiàn)兩題同根同源，其實(shí)本質(zhì)上考查的都是組合數(shù)學(xué)上的卡特蘭數(shù)的應(yīng)用.以下詳加論述：

高考真題1（2016年全國(guó)卷Ⅱ高考）如圖1，小明從街道的E處出發(fā)，先到F處與小紅會(huì)合，再一起到位于G處的老年公寓參加志愿者活動(dòng)，則小明到老年公寓可以選擇的最短路徑條數(shù)為（ ）.

圖1

A.24 B.18 C.12 D.9

解析：小明到老年公寓的最短路徑可以分步完成：第一步，小明從街道的E處出發(fā)，先到F處與小紅會(huì)合，共走四步，只需選擇哪兩步向右走，共有種走法；第二步，會(huì)合后兩人一起到位于G處的老年公寓參加志愿者活動(dòng)，共走三步，只需選擇哪兩步向右走，共有種走法.故最短路徑條數(shù)為N==18.

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

解析:依題意，當(dāng)m=4時(shí)，數(shù)列{an}共有8項(xiàng)：4項(xiàng)為0，4項(xiàng)為1.且對(duì)任意k≤8，a1，a2，…，ak中0的個(gè)數(shù)不少于1的個(gè)數(shù)（即從左到右數(shù)，0的累計(jì)數(shù)不小于1的累計(jì)數(shù)）.

分析易得a1=0，a8=1.再采用樹(shù)形圖列舉，可知滿足題意的數(shù)列{an}共有14個(gè).

問(wèn)題：若高考真題2問(wèn)的是對(duì)于任意的m∈N*，則不同的“規(guī)范01數(shù)列”共有多少個(gè)呢？

要解決這個(gè)一般的問(wèn)題，就必須理解這個(gè)純數(shù)學(xué)問(wèn)題的實(shí)際模型，其實(shí)高考真題2也可以理解為高考真題1實(shí)際模型的幾何組合計(jì)數(shù)問(wèn)題，具體理解如下：有一個(gè)4×4方格，如圖2，一個(gè)質(zhì)點(diǎn)開(kāi)始在（0，0）（最左下角頂點(diǎn)處），每次走一步，向右走一步記為0，向上走一步記為1，最終要運(yùn)動(dòng)到（4，4）（最右上角頂點(diǎn)處）（且要保證該質(zhì)點(diǎn)始終處于對(duì)角線y=x之下（含對(duì)角線））的最短路徑的條數(shù).

其實(shí)，我們可以將問(wèn)題推廣到更一般的情況：將m個(gè)紅球，n個(gè)白球排成一排，要求任意位置及其左邊的紅球總數(shù)不小于白球總數(shù)，共有多少種排法？

可等價(jià)轉(zhuǎn)化為：存在一個(gè)m+n元數(shù)組（a1，a2，…，am+n），其中ai∈{0，1}，i=1，2，…，m+n，且有m個(gè)1，n個(gè)0（m≥n）.

圖2

記Ai={k|a1，a2，…，ai中有k個(gè)1}，Bi={k|a1，a2，…，ai中有k個(gè)0}，且Ai≥Bi對(duì)i=1，2，…，m+n都成立.問(wèn)：這樣的數(shù)組共有多少個(gè)？

證明：設(shè)點(diǎn)P（iAi，B）i（i=0，1，2，…，m+n）.

將數(shù)組元素對(duì)應(yīng)為m+n+1個(gè)點(diǎn)，數(shù)組對(duì)應(yīng)為從P0到Pm+n的一條路徑，且滿足Ai≥Bi對(duì)i=1，2，…，m+n都成立，其總的走法數(shù)為種.

若其滿足題意，則其路徑必在直線y=x的下方（含直線y=x）；

若其不滿足題意，則必然有路徑點(diǎn)在直線y=x+1上.

作P（00，0）關(guān)于直線y=x+1的對(duì)稱點(diǎn)為P0（′-1，1）.

記A={從P0到Pm+n不滿足題意的路徑}，B={從P0′到Pm+n的總路徑}，下證：A與B為一一映射.

（1）A→B：設(shè)路徑點(diǎn)第一次出現(xiàn)在直線y=x+1上的為點(diǎn)Pk.

將從P0到Pk的路徑關(guān)于直線y=x+1對(duì)稱，而從Pk到Pm+n的路徑保留，得到一條由P0′到Pm+n的路徑.

（2）B→A：從P0′到Pm+n的路徑必然經(jīng)過(guò)直線y=x+1.設(shè)第一次經(jīng)過(guò)的點(diǎn)Pk.

將從P0′到Pk的路徑關(guān)于直線y=x+1對(duì)稱，而從Pk到Pm+n的路徑保留，則得到一條由P0到Pm+n的不滿足題意的路徑.

圖3

圖4

評(píng)析：至此，我們給出了這個(gè)問(wèn)題的完整解答.如果我們繼續(xù)向上追問(wèn)，就會(huì)發(fā)現(xiàn)此題的背景其實(shí)是組合數(shù)學(xué)中的“卡特蘭數(shù)”（“卡特蘭數(shù)”源于比利時(shí)數(shù)學(xué)家卡特蘭在研究凸n+2邊形的剖分時(shí)得到的數(shù)列Cn，在組合數(shù)學(xué)、信息學(xué)、計(jì)算機(jī)編程等方面都有廣泛的應(yīng)用；卡特蘭問(wèn)題的解決過(guò)程大量應(yīng)用了映射方法，堪稱計(jì)數(shù)的映射方法的典范），這就找到了問(wèn)題的本質(zhì).從而也更加佩服高考命題人的良苦用心，原來(lái)2016年這兩個(gè)排列組合題都同根同源，可以看成是一個(gè)復(fù)雜數(shù)學(xué)問(wèn)題的兩個(gè)特例，真是“問(wèn)渠那得清如許，為有源頭活水來(lái)”.F