组合数学中的构造方法及其应用

河北建筑工程学院理学院学士学位论文组合数学中构造法的研究背景③若这5个余数分布在其中的一个抽屉中，很显然，必有3个自然数之和能被3整除。有时我们可以用分组构造鸽巢的方法解题，确定分组的“对象”很关键。确定了“对象”之后，其个数相当于“求”的个数而言，又往往显得太多，只有把这些“对象”分成适当数量的组即鸽巢后，才能应用鸽巢原理。运用鸽巢原理解题的关键，在于构造合适的“鸽巢”，我们可以把“鸽巢”的构造方法归为三大类：一类是用分割图形构造鸽巢；一类是用分类的概念构造鸽巢；最后一类是用分组来构造鸽巢，然而，其实质均是对对象进行恰当的分类，鸽巢选的秒，就可以在数学中的组合问题中得出非常漂亮的结果。2.4构造方法在证明组合恒等式中的应用组合恒等式是组合数学的重要内容，其证明方法多种多样，其中的构造类方法尤为突出。当有些组合恒等式直接运用题设条件难以证明时，不妨把所考虑的恒等式置于某种实际背景下，构造组合模型，把组合恒等式的问题转化为组合计数问题，再用两种方法计算同一个两，列出等量关系。1.证明证：构造一个组合模型：甲班有m个学生，乙班有n个学生，今从两班抽出r个学生参加劳动，则所有抽法数是；另一方面，可以看成由甲班抽出个学生，从乙班抽出k个学生，k从0到r取值，则所有抽法数是：，从而可证得题设。这样的构造方法称之为“原型构造法”，这样很实际的去了解题的意思，把实际问题与书序问题紧密联系在一起。2.求证。对这样一个恒等式，我们可以考虑成有n个元素的集合的子集，元素的个数为,n个的子集数，分别有个，由加法原理得等式左边；考虑集合中n个元素，每个都有取与不取2种可能，有乘法原理得子集个数为，即等式右边。这是一种把数学问题构造为抽象的事务形态，但是有些题目的结构比较复杂，不容易找到合适的原型，可以吧原题适当改造或把原型适当变形。3.求证。证明：适合等式左边的原型十分困难，但是容易看出它是可以变形成如下的三角形状：………………上面式子中各行的实际原型分别是n个灯泡中有1至n个亮，2至n个亮，…，至n个亮，n个亮的组合数，其对立面分别是n个不亮，n-1至n个不亮，…，2至n个不亮，1至n个不亮。比较一下可知所有不亮的组合数之和与所有亮的组合数之和相等。但两类情况合起来就得这n组灯泡的每一组中的每一个可以亮或不亮的全部情况，其组合数之和为，从而推得所求。把这种思路整理一下，可得比较简练的证明方法：设，则。因为，所以，可见，这种原型构造法即使不直接用来证明，在寻找证题思路方面也大有益处。在证题方面，原型构造法也是一种普遍使用的方法，并不限于组合问题，也不限于证明，数学的各部分都可用，证明、计算、判断等各种题型都可以。事实上举反例证明为错的思想方法就是一种原型构造思想。4.判断互为反函数的两个函数图象的交点必在对称轴上。这个命题，很多人会误认为是真命题，很多教学资料上也说是真命题，其实是错误的。反例：，则。两函数的图象有交点和，在直线上。这种方法不一定是最简单的，但是很多时候确实是一种巧妙的方法。这种原型有时很不容易构造，需要较强的发散思维能力，构造原型本身就是一种创造工作，需要对所给问题进行深入的分析，找出它的形式特点和实际意义。在解决问题中经常用到一题多解或划归转化等方法，都可以极大地提高分析和解决问题的额能力，尤其是一些实际原型如能自己构造出来，远比能解一些给出的应用题要强得多。总结3总结构造法解题有着你意想不到的功效，将问题快捷简便的解决。构造法解题重在“构造”，它可以构造方程、不等式、函数、图形等，在数学中解题中的策略有：直觉构造、联想构造、你想构造，归纳构造，类比构造等。常见的构造方法有：构造数列，构造鸽巢、集合、函数。这些常见的策略与方法对我们在解数学试题有非常好的帮助，能够很好的培养与提高学生的创新思维能力。而这组合数学中构造法的灵魂为生成函数，在组合数学中，生成函数几乎无所不能，凡是不好解决的问题，都可以试着用生成函数来解决，它是一项简单而又灵活的解题方法。构造生成函数可以解决组合恒等式、不定方程、好布局数、递推关系等等，在这些应用中，我们首先想到的是把问题进行转化，转化为我们所熟知数学关系式，通过数学关系式，再联系实际问题的逻辑，我们可以很轻松的构造出我们所学的生成函数式，有了函数式，我们可以根据我们所需，求出我们要得到的展开式中的哪一项，不管怎么去构造，最后都需要展开形式幂级数，但是我们只需要展开我们所需的那一项，其余的项我们忽略不计。生成函数在组合数学中占据着十分重要的地位，但是构造法的止境是无穷远的，它是一种思想，更是一种策略，一种艺术。构造生成函数只是其中的小部分，即使这样都如此重要，那么整个构造法呢？不可思量，构造法也在教我们想问题的时候可以不直接面对，而是从别的方向入手，了解到这个问题的真面目后，我们再从正面去解决这个问题，如此迂回，快乐其中。致谢致谢本研究及学位论文是在我的导师李老师的亲切关怀和悉心指导下完成的。她严肃的科学态度，严谨的治学精神，精益求精的工作作风，深深地感染和激励着我。李老师不仅在学业上给我以精心指导，同时还在思想、生活上给我以无微不至的关怀，在此谨向李老师致以诚挚的谢意和崇高的敬意。我还要感谢在一起愉快的度过毕业论文小组的同学们，正是由于你们的帮助和支持，我才能克服一个一个的困难和疑惑，直至本文的顺利完成。在论文即将完成之际