关于组合数学教学的一点注记

2014-02-28汪定国

教育教学论坛 2014年1期

关键词：教学

摘要：组合数学作为离散数学的一个分支，是理工科专业尤其是数学专业的大学生必须学习的一门课程。本文结合自己多年的教学实践，对组合数学的教学作了一些探讨。

关键词：组合数学；教学；组合思想

中图分类号：G642.41 文献标志码：A 文章编号：1674-9324（2014）01-0095-02

组合数学作为离散数学的一个分支，其内容驳杂，方法繁多，对长期接受连续型数学的初学者而言，往往感到抓不住要领。然而，多种组合思想方法之间并不是孤立的，它们紧密联系，相辅相成。在教学过程中，将各种思想方法能够串在一起，对于组合数学的学习、组合思维的培养会十分有益。排列组合、容斥原理、递推关系以及生成函数是本科组合数学中比较重要的教学内容，同时也是解决组合问题时常用的几种组合思想方法。本文通过利用这几种思想方法解决同一个组合问题，以此表明这几种方法之间的统一性与差异性，对组合数学的教学和学习进行一个简单探讨。问题：由0、1、2三个数字作成的含有偶数个0的n位数码的个数是多少？

一、利用组合分析法求解

组合分析法即为在证明组合恒等式或解决组合问题时不是进行代数推导，而是对组合恒等式或组合问题所代表的组合意义进行分析，通过建立一一对应的方法说明等式两边或两个组合问题恰好是对同一个组合模型进行计数。在教学时，一定要讲清组合分析法的本质，同时要指明应用组合分析法的关键是建立一一对应关系的两边一定描述的是同一个组合模型。问题的求解：将所有的n位数码分成两组：①只含2的n位数码为一组，组中只有一个n位数码，它不出现数码0，0是偶数。②至少含一个0或者1的n位数码为另一组，组中共有3n-1个n位数码。在这组数码中，按2出现的模式再分成一些类，因在每一类的数码中，0出现偶数次的数码占一半，故这一组中0出现偶数次的数码共有■。由①、②可知，0出现偶数次的数码总数共有1+■=■个。

二、利用容斥原理求解

容斥原理的基本形式的应用具有一定的局限性，在教学时，有必要介绍容斥原理的一般形式以及更广泛的应用。设n元集S，具有性质集P={P1，P2，…，Pm}。现在问题是求出集 S中恰好具有P中r个，性质的元素个数N（r）（0≤r≤m）。令：W（0）=|S|，W（1）=■N（Pi），W（2）=■N（PiPj），…，W（m）=N（P1，P2，…，Pm）。其中N（P1，P2，…，Pm）表示同时具有性质P1，P2，…，Pm的元素个数。若记W（r）表示S中至少具有r（1≤r≤m）个性质的元素个数，首先有以下的容斥原理的一般形式：定理1：N（r）=W（r）-■W（r+1）+■W（r+2）-…+（-1）m-r■W（m），其中0≤r≤m。同时，还可以很容易得到以下结论：定理2：设E（x）=N（0）+N（1）x+N（2）x2+…+N（m）xm，则：E（x）=■W（j）（x-1）j。由此定理不难得到一个推论：设n元集S={x1，x2，…，xn}的元有性质集P={P1，P2，…，Pm}，则S中具有偶数个性质的元素个数为：N（0）+N（2）+N（4）+…=W（0）+■■W（j）（-2）j；S中具有奇数个性质的元素个数为：：N（1）+N（3）+N（5）+…=-■■W（j）（-2）j。利用这些结论，可以得到上述问题应用容斥原理的解决方法。问题的求解：设由0，1，2三个数字作成的全体n位数码的集合为S，则|S|=3n。又设Pi表示n位数码中的第i个位置为0，（i=1，2，…，n）。那么因为W（0）=|S|=3n，W（j）=■3n-j，所以，恰具有偶数个0的n位数码的数目为：N（0）+N（2）+N（4）+…=W（0）+■■W（j）（-2）j=3n+■■■3n-j（-2）j=■+■■■3n-j（-2）j=■+■（3-2）n=■.

三、利用递推关系求解

给定一个数列H（0），H（1），…，H（n），…，（或H{（n）}），如果存在若干项之间的关系式（等式），从某个非负整数n起都有效，这个关系式叫做递推关系。针对一个实际问题，在教学时，应该强调递推关系的建立是正确解决相关组合问题的关键。问题的求解：用f（n）表示由0、1、2组成的且0出现偶数次的n位数码的个数，n=1，2，…，显然f（1）=2。当n≥2时，将这样的f（n）个n位数码分为以下两类。

1.第1个位置不是0的这样的n位数码为一类，这时，第1个位置必是1或2，有两种选择，而后面的n-1位只要是0出现偶数次的n-1位数码即可，故这一类共有2f（n-1）个。

2.第一个位置是0的这样的n位数码为另一类，这时后面的n-1位只要是0出现奇数次的n-1位数码即可，故这一类共有：3n-1-f（n-1）个，（后n-1位任取0、1、2共3n-1个n位数码，f（n-1）表示0出现偶数次的n-1位数码）。所以由加法原理，得：f（n）=2f（n-1）+3n-1-f（n-1）=f（n-1）+3n-1，规定f（0）=1，得递推关系：f（n）=f（n-1）+3n-1 n≥1f（0）=1。解这个递推关系：f（n）=f（n-1）+3n-1=f（n-2）+3n-2+3n-1=f（n-3）+3n-3+3n-2+3n-1，用归纳法证明：当n=0时，f（0）=■=1；当n=1时，f（1）=■=2，结论均成立。设当n=k时结论成立，下证n=k+1时：f（k+1）=f（k）+3k=■+3k=■，所以当n=k+1时结论也成立。

四、利用生成函数求解

幂级数是良好的数学工具。幂级数的系数形成的序列与幂级数是一一对应的。如果两个幂级数之间存在某种关系，那么相应的两个系数系列也必然存在一定得关系。组合分析中的许多问题可以归结为求一个与n有关的数H（n），即本质是求一个未知序列{H（n）}。在教学时，应该指出利用生成函数解决问题的关键，即合理的构造相应地生成函数，再将问题转化为求生成函数中某项的系数问题。问题的求解：设an表示由0、1、2组成的且0出现偶数次的n位数码的个数。规定a0=1，则{an}的指数型生成函数为：fe（x）=（1+■+■+…）（1+x+■+■+■+…）2=e2x·■=■（e3x+ex）=■（■3n■+■■）=■■·■

从而，an=■ （n=0，1，2，…）。

作为本科数学专业的学生，组合数学主要学习组合计数的思想方法，而排列组合、容斥原理、递推关系以及生成函数都能解决组合计数的相关问题，从而体现了它们之间的统一性，这也是能够同时利用它们解决同一计数问题的原因。但是使用不同的方法解决问题时，所表现出的难易程度又有差别，这又体现了这些方法之间的差异性。对于一个实际问题，究竟采用什么方法，这就需要根据实际情况而定。但我们在教学与学习的过程中，一题多解是掌握这些方法的一条很好的途径。

参考文献：

[1]陈敬华.关于组合数学的若干基本思想方法[J].湖北师范学院学报（自然科学版），2001，21（2）：86-89.

[2]曲婉玲.组合数学[M].北京：北京大学出版社，1989.

[3]匡正.组合数学习题精解[M].哈尔滨：哈尔滨工业大学出版社，2005.