組合數(shù)學(xué)魅力淺析
——表格里的組合證明

郝小健 凌 浩 張康群

南京工程學(xué)院數(shù)理學(xué)院 江蘇南京 211167

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

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

眾所周知，興趣是學(xué)習(xí)最好的老師?？鬃佑醒裕骸爸卟蝗绾弥?，好之者不如樂之者。”事實上，無論是以赫爾巴特為代表的“傳統(tǒng)教育”學(xué)說，還是以杜威為代表的“現(xiàn)代教育”學(xué)說，都將興趣置于十分關(guān)鍵的地位[3]。由此，筆者希望通過本文使同學(xué)們認(rèn)識組合數(shù)學(xué)，感受組合證明的魅力，培養(yǎng)同學(xué)們對于組合數(shù)學(xué)的興趣。

一、組合數(shù)學(xué)的引入

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

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

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

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

紅色 藍(lán)色

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

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

紅色 藍(lán)色

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

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

二、組合數(shù)學(xué)的展開

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

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

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

斐波那契數(shù)列有許多廣受關(guān)注的有趣性質(zhì)。例如：

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

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

紅色 藍(lán)色

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

紅色

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

當(dāng)然講解本部分知識時，筆者將聯(lián)系黃金分割的概念、斐波那契數(shù)列與黃金分割之間的關(guān)系、黃金分割在美學(xué)中的應(yīng)用等，讓同學(xué)們進一步認(rèn)識到組合數(shù)學(xué)在生活中的巨大作用，增加同學(xué)們選課的積極性。

結(jié)語

筆者認(rèn)為通過上述教學(xué)設(shè)計可以由淺入深，由生活及課堂，借助日常工作生活中常見的表格循序漸進地引入組合數(shù)學(xué)，讓同學(xué)們領(lǐng)略組合證明的魅力。綜上，組合數(shù)學(xué)這門課程是非常有趣的，只要選擇合適的教學(xué)內(nèi)容、恰當(dāng)?shù)恼归_方式，輔以合理的教學(xué)設(shè)計，利用與組合數(shù)學(xué)相關(guān)知識的趣味性及應(yīng)用性，一定能達(dá)到極佳的教學(xué)效果。