浅谈中学数学中的组合数学问题

浅谈中学数学中的组合数学问题【摘要】组合数学起源于数学游戏，但随着计算机的日益发展，组合数学已经在各个领域有了越来越广泛的应用。本文主要介绍了组合数学的几个重要原理在中学数学中的应用。【关键词】中学数学；组合计数；抽屉原理1.证明某种现象的存在性在组合数学中，证明存在性主要运用抽屉原理。抽屉原理：如果个物体被放进个抽屉，那么至少有一个抽屉包含两个或更多的物体。应用抽屉原理的关键是构造出合适的抽屉，请看下面两个例子：例1.从1～98的自然数中，任意取出50个数，证明其中一定有两个数，它们中的一个是另一个的整数倍。分析：因为要取出50个数，所以抽屉的个数要少于50个，并且同一个抽屉内的任意两个数要满足性质“其中一个是另外一个的整数倍”。证明：因为任何一个正整数都能表示成一个奇数乘以2的形式（其中n为），并且这种表示是唯一的。所以我们可以把1～98的正整数分成如下49个抽屉：（1）（2）（3）（4）（5）（25）（26）（49）这样，我们就可以将1～98的正整数无重复、无遗漏地放进这49个抽屉内了。从这98个数中任取50个数，也即将50个物体放入49个抽屉中，根据抽屉原理，其中必定至少有两个物体放入了同一个抽屉，也就是说，其中必定至少有两个数是从同一抽屉中取出的。从抽屉的构造容易看出，这两个数中的一个是另一个的整数倍。例2.证明，在整数数列中，可以找出若干个连续的数（允许），它们的和可被10整除。分析：任意整数除以10所得的余数只有这10种可能。若两个整数除以10得到相同的余数，则这两个整数的差可被10整除。由此想到用模10的剩余类来构造抽屉。证明：作如下数列：若这10个整数中至少有一个能被10整除，则结论成立。否则，设上述数列中没有一个能被10整除，于是，当我们将它们分到模10的剩余类中去时，它们只能进入以下9个类：可是数列中有10个整数，由抽屉原理，数列中至少有两个数属于同一类，从而这两个数的差可被10整除，不妨设与属于同一剩余类，其中，则可被10整除。抽屉原理在用来证明存在性的时候非常有用，但它却不能用来计数。2.组合计数问题关于组合计数问题，有下面几种常用的方法：2.1两个基本的计数原理加法原理：如果第一项任务有种方法能够完成，第二项任务有种方法能够完成，那么从这两项任务中选择一项来完成的方法共有种。乘法原理：如果完成一项任务需要两个步骤，第一个步骤有种方法能够完成，而不论第一个步骤采用什么方法，第二个步骤都有种方法能够完成，那么，完成这项任务的方法共有种。许多组合计数问题需要综合运用这两个原理，请看下面的例子：例3.某班有20名女生和15名男生，要从中选出5个代表，要求至少要有2名女生和1名男生，有多少种选择方法？分析：这种类型的题很多同学会这样思考：要求要2名女生和1名男生，就从20名女生里面选2名，再从15名男生里面选1名，最后从剩下的32名学生中任选2名，一共是种选择方法。但这种解法是错误的。例如，选择顺序为{女1，女2}，{男1}，{女3，男2}与选择顺序为{女2，女3}，{男2}，{女1，男1}的两种选择方法在上面的计算中是算作不同的方法，但实际上这两种选择方法的结果都是{女1，女2，女3，男1，男2}。所以按这种方法计算实际上重复计数了很多次。正确的方法是先分类，再计算。解：5个代表要求至少要有2名女生和1名男生可能出现以下几种情况，（1）2女3男，选择方法数（2）3女2男，选择方法数（3）4女1男，选择方法数因此总共有种选择方法。从这个例子我们可以看出，应用加法原理和乘法原理最关键的是要做到计算时“不重不漏”。但学生却往往容易出现重复计算的错误。下面的容斥原理可以帮助我们解决这一问题。2.2容斥原理容斥原理：令是中物体所涉及到的个性质，并令，则集合的不具有性质的物体的个数由下式给出：其中，第一个求和号对的所有1-组合求和，第二个求和号对的所有2-组合求和，第三个求和号对的所有3-组合求和，以此类推。使用容斥原理的方便之处在于，允许不同的集合的交不为空，这样我们就不用担心会重复计算了，应用容斥原理的公式会将重复计算的部分都减掉。请看下面的例子：例4.求不大于1000而至少能被2，3，5之一整除的自然数的个数。分析：设是不大于1000且能被整除的自然数集合则我们要求的是，而，可应用容斥原理来计算。解：由容斥原理可得不大于且能被3，5，7之一整除的自然数的个数为：应用容斥原理来计算可以避免重复计算的错误，但计算量往往比较大，因为要计算任意个集合的交的元素个数。对某些特殊类型的题目，虽然也可以用容斥原理来计算，但还有另一种计算量较小的方法――生成函数。2.3生成函数当问题可以转化为求的满足是非负整数的整数解的个数这种问题时，我们可以用生成函数的方法来计算，请看下面的例子：例5.箱子里有红、白、黑3种颜色的球，从箱子中可放回的选出5个球，要求红球至多选2次，白球至多选1次，黑球至少选3次，问有哪几种不同的选取方式？分析：这实际上是要求方程的满足的整数解个数。这类题用容斥原理也可以计算，但计算量较大。更好的方法是利用生成函数来计算。解：设表示从3种球中允许重复地选取只球的不同方式数，序列的母函数为我们用中的分别表示红球没有被选，被选1次，被选2次；中的分别表示白球没有被选，被选1次。中的分别表示黑球被选3次，4次，5次，于是得到：则展开式中的系数就是3种球中每次允许重复地选取只球的不同方式数这里的系数为5，即：故从3种球中按题设限制条件每次允许重复地选取5只球的不同方式为5.这5种方式是：红红黑黑黑；红白黑黑黑；红黑黑黑黑，白黑黑黑黑，黑黑黑黑黑。从这个例子我们可以看出，利用生成函数不仅可以很快的计算出某种组合的方法数，还能方便的看出每种组合具体的组合方式。这是一种很好的方法。组合数学还有其他一些重要的原理，但本文只讨论至此，希望各位同仁在中学数学教学中也多关注这方面知识，使我们对它的研究更深入。基金项目：2014年度广西高等教育教学改革工程项目（2014JGA116）。作者简介：李玮（1984-），女，广西桂林人，博士，广西师范大学数学与统计学院教师。