組合數學魅力淺析
——表格里的組合證明

郝小健 凌 浩 張康群

南京工程學院數理學院 江蘇南京 211167

組合數學又稱離散數學，是研究離散結構的存在、計數、分析和優化等問題的一門學科，其在群論、概率論、數理統計學、粒子物理學及計算機相關領域均有著重要的應用。特別是近些年來，隨著人工智能的迅猛發展，組合數學已成為一個非常活躍的數學分支[1]。高等院校對于組合數學的教學工作日益重視，許多高校都將組合數學作為面向數學及計算機專業開設的重要選修課程。

不得不提的是，由于組合數學主要考察離散結構，強調構造性證明，涉及的組合物體性質繁多且聯系緊密，研究問題的技巧更是千變萬化，是一門非常具有挑戰性的科目[2]。正因為如此，許多同學在選課時往往將其作為第二甚至第三選擇，在同等學分的前提下盡量避開這門科目，選擇一些相對簡單，容易通過的科目。

眾所周知，興趣是學習最好的老師。孔子有言：“知之者不如好之者，好之者不如樂之者。”事實上，無論是以赫爾巴特為代表的“傳統教育”學說，還是以杜威為代表的“現代教育”學說，都將興趣置于十分關鍵的地位[3]。由此，筆者希望通過本文使同學們認識組合數學，感受組合證明的魅力，培養同學們對于組合數學的興趣。

一、組合數學的引入

筆者認為組合數學的課程引入環節非常重要，它會影響同學們對于課程的判斷，進而左右其選課意愿。因此，筆者希望借助部分中小學知識作為鋪墊，由熟悉至陌生，由簡單到復雜，讓同學們意識到組合證明并沒有想象中的百轉千回、變幻莫測。同學們只是習慣了連續性思維，對于離散性思維感到陌生和本能的抗拒，而這些都是不難克服的。

其實許多同學平時接觸的問題都可以通過組合方法給出簡潔優美的證明。例如，自小學階段就爛熟于心的求和公式：

當初筆者的老師是借助首尾相加的方式來推導這個公式的，而本文則希望給出一個組合證明，從全新的角度解讀上述公式，也讓同學們意識到構造性證明遠非想象中那么困難。

組合證明的前提是對等式兩端進行組合解釋，即選擇恰當的組合物體被等式兩端的數字所計數，這也是組合證明的準備環節。為了讓同學們更好地了解構造性證明，本文選取日常工作生活中所熟悉的表格作為證明工具，讓同學們切身感受到，離散性思維訓練至巔峰，則“飛花摘葉皆可傷人，草木竹石亦為鋒刃”。

紅色 藍色

不失一般性，我們取n=7，并對等式左端進行組合解釋：自上而下，自左至右依次染紅第一行的第一個格子，第二行的前兩個格子，直至第七行前七個格子。顯然所有的紅格數目為:

1+2+3+4+5+6+7.

紅色 藍色

任取一個紅格，例如第四行第二個(這里我們以淺紅色標示)，作過其中心及底邊中點的直線和過其中心及右下角頂點的兩條直線，這兩條直線分別穿過第八行兩個不同藍格的中心，取出這兩個藍格(以第四行第二個紅格為例，即須取出第二及第六個藍格)。至此，筆者建立了一個簡潔的映射。注意到對于任意兩個藍格，同學們反向操作也可以唯一確定一個紅格，從而該映射是一個一一映射，筆者也給出了上述求和公式的組合證明。

通過該題，筆者希望同學們認識到組合證明雖然注重構造，技巧性很高，但是并不是每一個都那么復雜，熟練地掌握組合解釋，組合證明可以簡潔而有趣。并且本部分證明用到的工具是大家日常生活經常接觸的表格，很容易被理解。這樣的教學方式從全新的角度給出了理解問題的方法，對于公式的記憶和應用都是大有幫助的。

二、組合數學的展開

在引入組合數學以后，筆者希望從現在大學生的日常生活出發，拉近同學們與組合數學之間的距離。比如，同學們所熟知的三國時期著名的軍事家諸葛亮，在一部手游當中就有一款精致的專屬皮膚叫作“黃金分割率”，而與其相匹配的臺詞更是飄逸與雄渾并立:“完美的幾何學者，以斐波那契數列分割戰場”。顯而易見，即便沒有經過高等數學訓練的人也一定聽說過黃金分割率，隱約知曉這個數字是0.618。事實上，黃金分割率有著廣泛的應用，尤其是在工藝學、建筑學以及美學等方面，而這一比例和一個著名的組合序列——斐波那契數列緊密相關。

斐波那契數列是由十一世紀意大利數學家斐波那契通過理想狀態下兔子的繁殖情況引入的。其在現代物理、準晶體結構以及化學等領域都有著直接的應用。為此，美國數學會從1963年起出版了以《斐波納契數列季刊》為名的數學雜志，用于專門刊載這方面的研究成果。組合數學中斐波那契數列一般通過如下遞推公式來定義：

f1=1，f2=2，fn=fn-1+fn-2(n>2).

斐波那契數列有許多廣受關注的有趣性質。例如：

相信同學們初看這個性質會有一些摸不到頭腦，大都希望借助遞推公式進行推導，這樣難免過程煩瑣。筆者希望本文的組合證明能帶給同學們耳目一新的感覺，讓同學們進一步領略組合數學的魅力。通過前述等差數列求和公式的組合證明，筆者認為同學們不難發現組合證明的前提是建立恰當的組合解釋。而斐波那契數列極高的關注度，使其擁有很多組合解釋，結合本文的主題，筆者選取其中與表格覆蓋相關的一個。

首先我們生成一個1行n列的表格。繼而我們用1×1的藍格及1×2的紅格來對上述表格進行覆蓋，則覆蓋該表格的方法數即為fn。這個結論的證明非常直接，同學們只需考慮覆蓋時放的第一塊是紅格還是藍格即可。

紅色 藍色

通過上述觀察可知，造成左右兩側覆蓋方式差值的原因恰恰在于極右切割線存在與否，如果存在就可以依極右切割線進行前述切割換表的操作。講解到這里，筆者希望引導同學們做出另外一個重要的觀察：如果位于上側的表格包含藍格，則該藍格左右兩側縫隙所對應的兩條垂線中至少有一條不切割下側的表格，從而極右切割線必然存在。因此,上方表格是否一定存在藍格就是影響等號右側-1冪次的關鍵。容易看出,當n為偶數時n+1為奇數，從而左側兩個表格按照上圖方式進行堆疊時，極右切割線必然存在，繼而左側覆蓋方式小于等于右側覆蓋方式。根據藍格不出現準則不難發現，當n為偶數時，除了右側上下方均為紅格的覆蓋方式以外，我們都可以找到一個左側的覆蓋與之相對應，從而右側的覆蓋方式僅僅比左側多1，反之亦然。下圖分別給出了兩側堆疊表格無法通過切割換表所映射掉的特殊覆蓋。

紅色

至此,筆者完成了對上述性質的組合證明。這個證明避免了煩瑣的計算，映射簡潔優美，能夠極大激發同學們的學習興趣，喚起其對組合數學的熱愛。而且證明的方式非常類似同學們小時候玩的積木堆疊，所用的工具唯一張紙而已，俯拾即是，同學們甚至可以動手去裁剪，去實驗這個漂亮的映射。更進一步地，筆者還可以做如下延伸，讓同學們思考如何利用表格組合證明下述公式：

當然講解本部分知識時，筆者將聯系黃金分割的概念、斐波那契數列與黃金分割之間的關系、黃金分割在美學中的應用等，讓同學們進一步認識到組合數學在生活中的巨大作用，增加同學們選課的積極性。

結語

筆者認為通過上述教學設計可以由淺入深，由生活及課堂，借助日常工作生活中常見的表格循序漸進地引入組合數學，讓同學們領略組合證明的魅力。綜上，組合數學這門課程是非常有趣的，只要選擇合適的教學內容、恰當的展開方式，輔以合理的教學設計，利用與組合數學相關知識的趣味性及應用性，一定能達到極佳的教學效果。