問渠那得清如許，為有源頭活水來
—— 兩道高考真題的高觀點透視

☉重慶市第一中學校 張志華 武 曉

2016年高考理科全國卷Ⅱ和卷Ⅲ的排列組合問題新穎有趣，表面上卷Ⅱ考查的是實際模型中的幾何組合計數問題，卷Ⅲ考查的是純數學的數列新定義計數問題，而如果站在更高的觀點上，可以發現兩題同根同源，其實本質上考查的都是組合數學上的卡特蘭數的應用.以下詳加論述：

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

圖1

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

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

高考真題2 （2016年全國卷Ⅲ高考）定義“規范01數列”{an}如下：{an}共有2m項，其中m項為0，m項為1，且對任意k≤2m，a1，a2，…ak中0的個數不少于1的個數.若m=4，則不同的“規范01數列”共有（ ）.

A.18個 B.16個 C.14個 D.12個

解析:依題意，當m=4時，數列{an}共有8項：4項為0，4項為1.且對任意k≤8，a1，a2，…，ak中0的個數不少于1的個數（即從左到右數，0的累計數不小于1的累計數）.

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

問題：若高考真題2問的是對于任意的m∈N*，則不同的“規范01數列”共有多少個呢？

要解決這個一般的問題，就必須理解這個純數學問題的實際模型，其實高考真題2也可以理解為高考真題1實際模型的幾何組合計數問題，具體理解如下：有一個4×4方格，如圖2，一個質點開始在（0，0）（最左下角頂點處），每次走一步，向右走一步記為0，向上走一步記為1，最終要運動到（4，4）（最右上角頂點處）（且要保證該質點始終處于對角線y=x之下（含對角線））的最短路徑的條數.

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

可等價轉化為：存在一個m+n元數組（a1，a2，…，am+n），其中ai∈{0，1}，i=1，2，…，m+n，且有m個1，n個0（m≥n）.

圖2

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

證明：設點P（iAi，B）i（i=0，1，2，…，m+n）.

將數組元素對應為m+n+1個點，數組對應為從P0到Pm+n的一條路徑，且滿足Ai≥Bi對i=1，2，…，m+n都成立，其總的走法數為種.

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

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

作P（00，0）關于直線y=x+1的對稱點為P0（′-1，1）.

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

（1）A→B：設路徑點第一次出現在直線y=x+1上的為點Pk.

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

（2）B→A：從P0′到Pm+n的路徑必然經過直線y=x+1.設第一次經過的點Pk.

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

圖3

圖4

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