組合數學課程的教學實踐

劉瑞芳，賈會才

(1.鄭州大學 數學系，河南 鄭州 450001； 2.河南工程學院 數理科學系，河南 鄭州 451191)

組合數學又稱離散數學，通常也把組合數學和圖論加在一起稱為離散數學.組合數學是計算機出現以后迅速發展起來的一門數學分支.計算機科學是算法的科學，而計算機所處理的對象是離散的數據，所以離散對象的處理就成了計算機科學的核心，研究離散對象的科學就是組合數學.組合數學的發展改變了傳統數學中分析和代數占統治地位的局面.

組合數學作為一門重要的數學課程，在教學中如何引入與展開才能使學生更好地學習和掌握就成了一個重要的課題.組合數學有別于其他一些數學課程的是它與實際問題聯系密切，強調數學應用能力和創造能力的培養.組合數學解決問題的方法沒有連續性和固定套路，往往一個問題一種解法，這些特征促使教師在教學中要避免填鴨式的講授，要在講解知識的過程中激發學生的學習興趣和創造性思維能力.下面將結合教學中的實踐來論述組合數學教學的引入與展開方法.文中所涉及的一些概念和術語如無詳細說明，可參見文獻[1-3].

1 課程設計

學生經過幾年數學基礎課和專業課的學習之后,很容易對數學產生枯燥、難懂、脫離實際的印象，組合數學課正好為改變學生的這些想法提供了一個契機，要通過第一堂課的引入使學生對課程產生興趣.

例1 甲、乙兩個人輪流從k堆錢幣中取錢，每次選定一堆，從中至少取出一個錢幣(可全取)，取到最后一個錢幣者勝(組合數學中著名的Nim對策).

例2 獵人帶著一擔白菜、一只羊和一條狼要過河，但是只有一條小船，只有獵人會劃船并且他一次至多只能帶白菜、羊和狼三者之一過河.如果讓狼和羊在一起而獵人不在旁邊的話，狼就會把羊吃掉；如果讓羊和白菜在一起而獵人不在旁邊的話,羊就會把白菜吃掉.問如何讓他們都平安過河?(組合數學中著名的船過河問題)

組合數學中類似的有趣問題非常多，如河洛圖(幻方)、穩定婚姻問題、鋪地磚問題等.這樣的課程引入方式通過一個個生動有趣的問題組成了別致而生動的第一堂組合數學課，完全顯示了組合數學的神奇和奧妙.

2 教學中的引入與展開

2.1 激發學生的學習興趣

課程有了一個好的引入方式，能給學生帶來輕松的氣氛，進一步展開課程以激發學生的學習興趣就成了下一個問題.在實際的教學中，可以從貼近生活的一個個有趣的例子入手來講解組合數學中重要的原理和概念，比如組合數學中重要的鴿籠原理.要想很好地運用鴿籠原理激發學生的學習興趣,可以從日常生活中有趣的小問題入手.

例3 某棋手有11周的備戰訓練，每天至少下一盤棋，但每周不超過12盤.試證：必有連續的若干天恰好下21盤棋.

例4 100個人參加一個聚會，其中每個人都有偶數(可能是零)個朋友.證明：在這100個人中必定有3個人有相同數目的朋友.

給半小時的時間讓學生自己試著證明上述兩個貼近生活的例子，學生們在獨立思考與激烈爭論之后無形中已經分別用了鴿籠原理的簡單形式(n+1個球放入n個盒子中，必有一個盒子含有兩個或者更多的球)和平均形式(將nr+1個球放入n個盒子中，必有一個盒子至少含有r+1個球)解決了例3和例4.最后，教師可再提出鴿籠原理，并指出鴿籠原理運用的關鍵是如何合理地選擇鴿子和籠子.這樣的講授方式學生很容易理解，可以激發學生學習鴿籠原理的積極性，讓學生感覺到學習組合數學簡單有趣，學習興趣得到了極大提高.

2.2 調動學生的學習主動性

教師可以采用啟發式的教學方式使教學進一步深入，充分調動學生學習的積極性，提高學生的自學能力和獨立思考問題的能力.

例如，在講授第二類Stirling數和第一類Stirling數時，因為二者是對偶的概念，先詳細給出第二類Stirling數的定義，接著介紹它的遞推公式及其詳細證明，最后給出第二類Stirling數的組合意義.利用反演和對偶的思想，關于第一類Stirling數的定義、遞推公式和組合意義，可以留給學生自己去證明.教師可采取上課提問的方式，這樣既可以調動學生的主動性，也可以加深學生對兩類Stirling數的比較與理解.

除此之外，對于重要的原理和方法，可以給出很多例子讓學生練習.教師可以首先給出一個典型的例子加以詳細介紹，然后找學生當堂練習一些類似的題目，這樣既活躍了課堂氣氛，又調動了學生學習的主動性，并且還能查漏補缺，從而達到最好的教學效果.

2.3 提高學生發現問題的能力

要提高學生學習的主動積極性，就必須讓學生自己想出一些問題并試著解決它.給學生一個好問題，不如教會學生如何發現問題.在講解組合數學中的原理、模型及其思想方法時，應該經常提醒學生發散自己的思維，去建立一個新的概念或模型并研究其性質.當然,這種發散不是漫無邊際的發散，通常是基于原有概念(模型)的推廣或者遷移.

以排列組合為例，n元集S的r-排列是指具有n個元素的集合S中r個元素的有序安排方式數，其中n個元素是完全不重復的.我們可以把集合的排列進行推廣，引導學生考慮多重集合的r排列.首先，給出多重集S的定義，即集合S中每一個元素都有一個重數，例如S={2·a，3·b，5·c}表示集合S由2個a，3個b和5個c組成.然后，讓學生思考重數無限的多重集的排列和重數有限的多重集的排列.在講授組合數學的過程中，當講述完一個概念或者模型時，鼓勵大家提出改進模型的辦法，并提醒大家注意兩個原則——合理性和可行性.教師在講解的過程中一定要引導學生采用推廣或者遷移的方式獨立地提出新的問題，能夠提出一個好的問題也是獨立科學研究能力的象征，對培養學生的數學素養大有裨益.

2.4 培養學生解決問題的能力

盡管如前所述，組合數學解題的具體方法是靈活的、離散的與不可模仿的，但我們還是可以在教學過程中有意識地訓練學生的宏觀證明能力.通常來說，解決組合數學問題有貢獻法、數學歸納法、容斥原理、鴿籠原理、母函數法和二項式(多項式)定理等幾種基本方法，有時需要結合使用，下面舉例介紹.

貢獻法適用于證明計數恒等式.首先選定一個特殊的元素x，然后分別分析等式的左端和右端，看看兩端對這個事先選定好的元素的統計次數是否一樣多，如果一樣多則原計數恒等式得證.貢獻法在組合數學的證明中應用廣泛，起到了不可替代的作用.巧妙運用貢獻法，可給出容斥原理的完美證明.

例5S中不具有任何一個性質的元素數目為：

證明：設任意元素xS,它恰有m個性質中的n個性質(0≤n≤m).若n=0,則上式兩端對它的計算次數都是1；若n≥1,則x在左端計數0次，而在右端的計數為上述等式成立.

上面例子給出了容斥原理的簡單證明，可以發現該原理雖然重要，但是它的內容和證明并不復雜，也不難理解.最重要的是，如何利用這個原理來解決更多的數學問題以及怎樣才能恰如其分地運用它，這就需要一種解決數學問題的綜合品質.

3 結語

以上組合數學課程教學中的引入和展開方式適用于各個層次的數學課程，教師要關注和重視這些課程教學中的技巧，充分調動學生課堂學習的積極性，傾聽他們的想法，使學生在交流互動中增強數學技能.

參考文獻：

[1] Brualdi R A. Introductory Combinatorics[M].Beijing:China Machine Press,2009.

[2] Cameron P J.Combinatorics Topics, Techniques, Algorithms[M].Beijing:Posts Telecom Press,2009.

[3] 盧開澄，盧華明.組合數學[M].4版.北京：清華大學出版社，2006.