第２４卷第１期 河南工程学院学报（自然科学版） Ｖ０１．２４．Ｎｏ．１ ２０１２年３月 ＪＯＵＲＮＡＬ ＯＦ ＨＥＮＡＮ ＩＮＳＴＩｑ、ＵＴＥ ＯＦ ＥＮＧＩＮＥＥＲＩＮＧ Ｍａｒ．２Ｏ１２ 组合数学课程的教学实践 刘瑞芳 ，贾会才 （１．郑州大学数学系，河南郑州４５０００１；２．河南工程学院数理科学系，河南郑州４５１１９１） 摘要：组合数学从广义上讲是一门研究离散对象的科学，从狭义上讲主要研究满足一定条件的组态（也称组合模型）的 存在、计数以及构造等方面的问题，它的主要内容包括组合计数、组合设计、组合结构和组合优化等，是数学专业高年级本科 生和研究生的必修课程，也是计算机专业本科生离散数学课程的重要组成部分．从一些教学的设计出发，探讨如何在教学中 引入和展开以及如何在该课程的教学过程中激发学生的学习兴趣，最大限度地调动学生学习的主动性和培养学生发现和解 决问题的能力，为学生今后做毕业论文或者进一步从事科学研究工作打下坚实的基础． 关键词：组合数学；教学；科研 中图分类号：Ｇ６４２．１ 文献标志码：Ａ 文章编号：１６７４—３３０Ｘ（２０１２）０１—００７５—０３ 组合数学又称离散数学，通常也把组合数学和图论加在一起称为离散数学．组合数学是计算机出现以后 迅速发展起来的－－１＇７数学分支．计算机科学是算法的科学，而计算机所处理的对象是离散的数据，所以离散 对象的处理就成了计算机科学的核心，研究离散对象的科学就是组合数学．组合数学的发展改变了传统数学 中分析和代数占统治地位的局面． 组合数学作为一门重要的数学课程，在教学中如何引入与展开才能使学生更好地学习和掌握就成了一 个重要的课题．组合数学有别于其他一些数学课程的是它与实际问题联系密切，强调数学应用能力和创造能 力的培养．组合数学解决问题的方法没有连续性和固定套路，往往一个问题一种解法，这些特征促使教师在 教学中要避免填鸭式的讲授，要在讲解知识的过程中激发学生的学习兴趣和创造性思维能力．下面将结合教 学中的实践来论述组合数学教学的引入与展开方法．文中所涉及的一些概念和术语如无详细说明，可参见文 献［１—３］． １课程设计 学生经过几年数学基础课和专业课的学习之后，很容易对数学产生枯燥、难懂、脱离实际的印象，组合数 学课正好为改变学生的这些想法提供了一个契机，要通过第一堂课的引人使学生对课程产生兴趣． 例１ 甲、乙两个人轮流从 堆钱币中取钱，每次选定一堆，从中至少取出一个钱币（可全取），取到最后 一个钱币者胜（组合数学中著名的Ｎｉｍ对策）． 例２猎人带着一担白菜、一只羊和一条狼要过河，但是只有一条小船，只有猎人会划船并且他一次至 多只能带白菜、羊和狼三者之一过河．如果让狼和羊在一起而猎人不在旁边的话，狼就会把羊吃掉；如果让羊 和白菜在一起而猎人不在旁边的话，羊就会把白菜吃掉．问如何让他们都平安过河？（组合数学中著名的船 过河问题） 组合数学中类似的有趣问题非常多，如河洛图（幻方）、稳定婚姻问题、铺地砖问题等．这样的课程引入 方式通过一个个生动有趣的问题组成了别致而生动的第一堂组合数学课，完全显示了组合数学的神奇和奥 妙． 收稿日期：２０１１—０８—２０ 作者简介：刘瑞芳（１９８０一），女，河南郑州人，讲师，博士，主要从事代数图论的教学与研究 ・７６・ 河南工程学院学报（自然科学版） ２教学中的引入与展开 ２．１激发学生的学习兴趣 课程有了一个好的引入方式，能给学生带来轻松的气氛，进一步展开课程以激发学生的学习兴趣就成了 下一个问题．在实际的教学中，可以从贴近生活的一个个有趣的例子人手来讲解组合数学中重要的原理和概 念，比如组合数学中重要的鸽笼原理．要想很好地运用鸽笼原理激发学生的学习兴趣，可以从日常生活中有 趣的小问题人手． 例３某棋手有ｌｌ周的备战训练，每天至少下一盘棋，但每周不超过１２盘．试证：必有连续的若干天恰 好下２１盘棋． 例４ １００个人参加一个聚会，其中每个人都有偶数（可能是零）个朋友．证明：在这１００个人中必定有３ 个人有相同数目的朋友． 给半小时的时间让学生自己试着证明上述两个贴近生活的例子，学生们在思考与激烈争论之后无 形中已经分别用了鸽笼原理的简单形式（ ＋１个球放人ｎ个盒子中，必有一个盒子含有两个或者更多的球） 和平均形式（将ｎｒ＋１个球放人ｎ个盒子中，必有一个盒子至少含有ｒ＋１个球）解决了例３和例４．最后，教 师可再提出鸽笼原理，并指出鸽笼原理运用的关键是如何合理地选择鸽子和笼子．这样的讲授方式学生很容 易理解，可以激发学生学习鸽笼原理的积极性，让学生感觉到学习组合数学简单有趣，学习兴趣得到了极大 提高． ２．２调动学生的学习主动性 教师可以采用启发式的教学方式使教学进一步深入，充分调动学生学习的积极性，提高学生的自学能力 和思考问题的能力． 例如，在讲授第二类Ｓｔｉｆｌｉｎｇ数和第一类Ｓｔｉｒｌｉｎｇ数时，因为二者是对偶的概念，先详细给出第二类 Ｓｔｉｒｌｉｎｇ数的定义，接着介绍它的递推公式及其详细证明，最后给出第二类Ｓｔｉｒｌｉｎｇ数的组合意义．利用反演和 对偶的思想，关于第一类Ｓｔｉｒｌｉｎｇ数的定义、递推公式和组合意义，可以留给学生自己去证明．教师可采取上 课提问的方式，这样既可以调动学生的主动性，也可以加深学生对两类Ｓｔｉｒｌｉｎｇ数的比较与理解． 除此之外，对于重要的原理和方法，可以给出很多例子让学生练习．教师可以首先给出一个典型的例子 加以详细介绍，然后找学生当堂练习一些类似的题目，这样既活跃了课堂气氛，又调动了学生学习的主动性， 并且还能查漏补缺，从而达到最好的教学效果． ２．３提高学生发现问题的能力 要提高学生学习的主动积极性，就必须让学生自己想出一些问题并试着解决它．给学生一个好问题，不 如教会学生如何发现问题．在讲解组合数学中的原理、模型及其思想方法时，应该经常提醒学生发散自己的 思维，去建立一个新的概念或模型并研究其性质．当然，这种发散不是漫无边际的发散，通常是基于原有概念 （模型）的推广或者迁移． 以排列组合为例，ｎ元集５的ｒ一排列是指具有ｎ个元素的集合ｓ中ｒ个元素的有序安排方式数，其中ｎ 个元素是完全不重复的．我们可以把集合的排列进行推广，引导学生考虑多重集合的，排列。首先，给出多重 集．ｓ的定义，即集合 中每一个元素都有一个重数，例如Ｓ＝｛２・ ，３・ｂ，５・Ｃ｝表示集合ｓ由２个。，３个ｂ 和５个Ｃ组成．然后，让学生思考重数无限的多重集的排列和重数有限的多重集的排列．在讲授组合数学的 过程中，当讲述完一个概念或者模型时，鼓励大家提出改进模型的办法，并提醒大家注意两个原则——合理 性和可行性．教师在讲解的过程中一定要引导学生采用推广或者迁移的方式地提出新的问题，能够提出 一个好的问题也是科学研究能力的象征，对培养学生的数学素养大有裨益． ２．４培养学生解决问题的能力 尽管如前所述，组合数学解题的具体方法是灵活的、离散的与不可模仿的，但我们还是可以在教学过程 第１期 刘瑞芳，等：组合数学课程的教学实践 ・７７・ 中有意识地训练学生的宏观证明能力．通常来说，解决组合数学问题有贡献法、数学归纳法、容斥原理、鸽笼 原理、母函数法和二项式（多项式）定理等几种基本方法，有时需要结合使用，下面举例介绍． 贡献法适用于证明计数恒等式．首先选定一个特殊的元素 ，然后分别分析等式的左端和右端，看看两 端对这个事先选定好的元素的统计次数是否一样多，如果一样多则原计数恒等式得证．贡献法在组合数学的 证明中应用广泛，起到了不可替代的作用．巧妙运用贡献法，可给出容斥原理的完美证明． 例５ ．ｓ中不具有任何一个性质的元素数目为： Ｊ ‘一 Ｉ＝ｌ ｓ Ｉ一∑Ｉ Ａｉ Ｉ＋∑ｌ ｎ Ｉ一∑Ｉ ｎ ｎ ４ Ｉ＋…＋（一１）～ Ａｉ Ｊ（组合数学中有名 ｉ＝ｌ ＜ ｉ＜ ＜ ，‘一 的容斥原理）． 证明：设任意元素ｘＥＳ，它恰有ｍ个性质中的ｎ个性质（Ｏ≤ｎ≤ｍ）．若ｎ＝０，则上式两端对它的计算次 数都是ｌ；若ｎ≥ｌ，则 笙左端计数０次，而在右端的计数为ｌ一（ ）＋（ ）一（ ）＋一一十（－１ ｎ．．） ０，上述 等式成立． 上面例子给出了容斥原理的简单证明，可以发现该原理虽然重要，但是它的内容和证明并不复杂，也不 难理解．最重要的是，如何利用这个原理来解决更多的数学问题以及怎样才能恰如其分地运用它，这就需要 一种解决数学问题的综合品质． ３结语 以上组合数学课程教学中的引入和展开方式适用于各个层次的数学课程，教师要关注和重视这些课程 教学中的技巧，充分调动学生课堂学习的积极性，倾听他们的想法，使学生在交流互动中增强数学技能． 参考文献： ［１］Ｂｒｕａｌｄｉ Ｒ Ａ．Ｉｎｔｒｏｄｕｃｔｏｒｙ Ｃｏｍｂｉｎａｔｏｒｉｃｓ［Ｍ］．Ｂｅｉｊｉｎｇ：Ｃｈｉｎａ Ｍａｃｈｉｎｅ Ｐｒｅｓｓ，２００９． ［２］Ｃａｍｅｒｏｎ Ｐ Ｊ．Ｃｏｍｂｉｎａｔｏｒｉｃｓ Ｔｏｐｉｃｓ，Ｔｅｃｈｎｉｑｕｅｓ，Ａｌｇｏｒｉｔｈｍｓ［Ｍ］．Ｂｅｉｊｉｎｇ：Ｐｏｓｔｓ Ｔｅｌｅｃｏｍ Ｐｒｅｓｓ，２００９． ［３］卢开澄，卢华明．组合数学［Ｍ］．４版．北京：清华大学出版社，２００６． Ｔｈｅ ｔｅａｃｈｉｎｇ ｐｒａｃｔｉｃｅ ｏｆ ｃｏｍｂｉｎａｔｏｒｉｃｓ ＬＩＵ Ｒｕｉ．ｆａｎｇ ．ＪＩＡ Ｈｕｉ－ｃａｉ （１．Ｄｅｐａｒｔｍｅｎｔ ｏｆＭａｔｈｅｍａｔｉｃｓ，Ｚｈｅｎｇｚｈｏｕ Ｕｎｉｖｅｒｓｉｔｙ，Ｚｈｅｎｇｚｈｏｕ ４５０００１，Ｃｈｉｎａ； ２．Ｄｅｐａｒｔｅｍｎｔ ｏｆＭａｔｈｅｍａｔｃｉａｌ ａｎｄ Ｐｈｙｓｉｃａｌ Ｓｃｉｅｎｃｅｓ，Ｈｅｎａｎ Ｉｎｓｔｉｔｕｔｅ ｆｏＥｎｇｉｎｅｅｒｉｎｇ，Ｚｈｅｎｇｚｈｏｕ ４５１１９１，Ｃｈｉｎａ） Ａｂｓｔｒａｃｔ：Ｃｏｍｂｉｎａｔｏｒｉｃｓ ｉｓ ａ ｓｃｉｅｎｃｅ ｒｅｓｅａｒｃｈｉｎｇ ｄｉｓｃｒｅｔｅ ｏｂｊｅｃｔｓ．Ｉｎ ｎａｒｒｏｗ ｓｅｎｓｅ，ｉｔ ｍａｉｎｌｙ ｒｅｓｅａｒｃｈｅｓ ｔｈｅ ｅｘｉｓｔｅｎｃｅ，ｃｏｕｎｔｉｎｇ ａｓ ｗｅｌｌ ａｓ ｓｔｒｕｃｔｕｒｅ ｑｕｅｓｔｉｏｎｓ ｏｎ ｃｏｎｆｉｇｕｒａｔｉｏｎ（ａｌｓｏ ｃａｌｌｅｄ ｃｏｍｂｉｎａｔｏｒｉａｌ ｍｏｄｅ１）ｗｈｉｃｈ ｓａｔｉｓｉｆｅｓ ｔｈｅ ｉｆｘｅｄ ｃｏｎｄｉｔｉｏｎｓ．Ｔｈｅ ｐｒｉｍａｒｙ ｃｏｎ－ ｔｅｎｔ ｏｆ ｃｏｍｂｉｎａｔｏｒｉｅｓ ｉｎｃｌｕｄｅｓ ｃｏｍｂｉｎａｔｏｒｉａｌ ｃｏｕｎｔｉｎｇ，ｃｏｍｂｉｎａｔｏｒｉｌａ ｄｅｓｉｇｎ，ｃｏｍｂｉｎａｔｏｒｉａｌ ｓｔｒｕｃｔｕｒｅ，ａｎｄ ｃｏｍｂｉｎａｔｏｒｉａｌ ｏｐｔｉｍｉｚａｔｉｏｎ ａｎｄ ＳＯ ｏｎ．Ｉｔ ｉｓ ａ ｒｅｑｕｉｒｅｄ ｃｏｕｒｓｅ ｆｏｒ ｍａｔｈｅｍａｔｉｃｓ ｈｉｇｈｅｒ ｇｒａｄｅ ｕｎｄｅｒｇｒａｄｕａｔｅ ｓｔｕｄｅｎｔｓ ａｎｄ ｇｒａｄｕａｔｅ ｓｔｕｄｅｎｔｓ，ａｌｓｏ ａｎ ｉｍｐｏｒｔａｎｔ ｃｏｍｐｏ－ ｎｅｎｔ ｏｆ ｄｉｓｃｒｅｔｅ ｍａｔｈｅｍａｔｉｃｓ ｆｏｒ ｕｎｄｅｒｇｒａｄｕａｔｅ ｓｔｕｄｅｎｔｓ ｉｎ ｃｏｍｐｕｔｅｒ ｓｃｉｅｎｃｅ．Ｔｈｉｓ ｓｔｕｄｙ ｍａｉｎ ｅｘｐｌｏｒｅｓ ｈｏｗ ｔｏ ｉｎｔｒｏｄｕｃｅ ａｎｄ ｅｘｐａｎｓｅ ｉｎ ｔｈｅ ｂｅｇｉｎｎｉｎｇ，ａｎｄ ｈｏｗ ｔｏ ｓｔｉｍｕｌａｔｅ ｓｔｕｄｅｎｔｓ’ｓｔｕｄｙ ｉｎｔｅｒｅｓｔ，ｔｒａｎｓｆｅｒ ｓｔｕｄｅｎｔｓ’ｓｔｕｄｙ ｉｎｉｔｉａｔｉｖｅ ｉｎ ｍａｘｉｍｕｍ ｌｉｍｉｔ ａｎｄ ｆｏｓｔｅｒ ｓｔｕｄｅｎｔｓ ａ— ｂｉｌｉｔｙ ｏｆ ｉｆｎｄｉｎｇ ａｎｄ ｓｏｌｖｉｎｇ ｔｈｅ ｐｒｏｂｌｅｍ ｉｎ ｃｏｍｂｉｎａｔｏｒｉｃｓ ｔｅａｃｈｉｎｇ ｄｅｓｉｇｎ．Ｔｈｕｓ ｔｈｉｓ ｃａｎ ｍａｋｅ ａ ｓｏｌｉｄ ｆｏｕｎｄａｔｉｏｎ ｆｏｒ ｔｈｅ ｓｔｕｄｅｎｔｓ ｔｏ ａｅ— ｃｏｍｐｌｉｓｈ ｔｈｅ ｒｅｓｅａｒｃｈ ｆｏｒ ｔｈｅ ｆｕｔｕｒｅ． Ｋｅｙ ｗｏｒｄｓ：ｃｏｍｂｉｎａｔｏｒｉｅｓ；ｔｅａｃｈｉｎｇ；ｓｃｉｅｎｔｉｉｆｃ ｒｅｓｅａｒｃｈ
