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

《组合数学中的构造方法及其应用》由会员分享，可在线阅读，更多相关《组合数学中的构造方法及其应用（19页珍藏版）》请在金锄头文库上搜索。

1、组合数学中构造法的研究背景 1 1 组合数学中构造法的研究背景 在当今，组合数学是一门非常活跃的学科，它在各个不同的领域都有相当的应 用，尤其在日益发展的计算机科学中。因为计算机科学的核心内容是使用算法和离 散数据。而组合数学就是研究离散对象的科学。 组合数学是如此的重要，那你了解其中的构造法吗？提到构造法，我们首先来 介绍下吧。构造就是面对问题直接解决相当困难，可以借助其他的方法，用其他路 径来解决我们的问题，“曲线救国”，问题便迎刃而解。它不是一种数学方法，而 是一种数学思想，体现了数学的发现、类比、划归、猜想、试验和归纳的思想。这 就是构造法的魅力。 谓构造性的方法就是数学中的概念和方法

2、按固定的方式经有限个步骤能够定 义的概念和能够实现的方法。从数学产生那天起，数学中的构造性的方法也就伴随 着产生了。但是构造性方法这个术语的提出，以至把这个方法推向极端，并致力于 这个方法的研究，是与数学基础的直觉派有关。直觉派出于对数学的“可信性”的 考虑，提出一个著名的口号：“存在必须是被构造。”这就是构造主义。 构造法真正体现出了“数式与图形的沟通、直觉与逻辑的互动”，这也正是数 学建模的一个基本特征。 另外，在应用构造法时， 要明确目的， 需要构造的是什么， 根据什么设计构造方案。 构造的模型结构形式应尽可能的简单，以便于问题的解决， 尽可能地使复杂问题简单化；构造的模型必须是熟悉的，

3、通过熟悉的模型将难以入 手的问题转化为熟悉的问题；构造的模型尽可能地直观，通过构造使问题变的直观 明了。 组合数学中的构造方法 2 2 组合数学中的构造方法 2.1 排列组合中的构造方法及其应用 构造法即构造性解题方法，它是根据数学问题的条件或结论的特征，以问题中 的数学元素为“元件” ，构造出新的数学对象或数学模型，从而使问题转化并得到 解决的方法。构造法本质上属于转化思想的范畴，但它常常表现出简捷、明快、精 巧、新颖等特点，使数学解题突破常规，不但具有很强的创造性，而且更能让人领 悟到数学的无穷乐趣和魅力，体会数学美的无处不在。它是非常典型的数学建模， 具有独特的探讨价值。那我们就来看看构

4、造法解排列、组合题的问题。 定义 1 所谓排列，就是指从给定个数的元素中取出指定个数的元素进行排 序。从 n个不同元素中，任取nmm个元素（被取出的元素各不相同） ，按照一定 的顺序排成一列，叫做n个不同元素取出 m个元素的一个排列。 定义 2 组合则是指从给定个数的元素中仅仅取出指定个数的元素，不考虑 排序。从 n个不同元素中，任取nmm个元素并成一组，叫做从n个不同元素中 取出 m个元素的一个组合。 数学解题的一个基本思想就是设法将所要求解的问题转化为我们所熟悉的或 容易解决的问题，这一点在解排列组合问题是尤显重要。我们在学的过程中药经常 强化这一思想，以便寻求更便捷的解法。接下来所提的构

5、造模型法恰恰很好地做到 了这一点。 2.1.1 构造排列组合解数的排列问题 捆绑法 捆绑法就是把分散的几个对象构造为一个组合，把这个组合看作一个元素和其 他元素进行排列，然后再考虑大元素内部各元素间顺序，这样的构造很容易就能求 得我们的所需。 1. 7 个人站成一排，求出甲、乙、丙三人必须相邻的排法种数。 这个问题比较简单，但是它是排列组合中的相邻问题，面对这样的模型，我 们用熟知的“捆绑法” 。先将必须相邻的甲、乙、丙三个人构造成一个集合N，于 是由原来的 7 个人变为现在的“ 5 个人” ，即edcba1 ,1 ,1 ,1 ,1，对这五个元素进 行全排列，其排法种数为 5 5 A ，题中要

6、求甲、乙、丙三人必须相邻，这三个人做全排 列为 3 3 A ，经题意我们构造了这样两个数列，通过这两个数列， 我们明显看出解决这 组合数学中的构造方法 3 个问题需要分步来做，由此可用乘法原则得排法种数为 3 3 5 5 AA。 构造“捆绑法”主要用于求解“必须相邻”的模型，但是对于必不相邻的问题 呢？我们可以用另外一种模型“插入法”，它能够解决“必不相邻”的问题。 插板法 构造一个元素组合的全排列，在这一个排列的间隙中插板，不同的插板会有不 同的方法种数，换句话说就是在在n 个元素间的 （n-1）个空中插入若干个 （b）个 板，可以把 n 个元素分成 （b+1）组。 2. 现有 10个完全相

7、同的球全部分给7 个班级，每班至少一个球，问共有多少 种不同的分法？ 题目中球的分法可构造为三类： （1）有三个班每个班分到2 个球，其余 4 个班每班分到 1 个球，其分法种数 是 3 71 CN； （2）有一个班分到 4 个球，其余 6 个班每班分到 1 个球，其分法种数是 1 6 1 72 CCN； （3） 有一个班分到 4 个球， 其余 6 个班每班分到 1 个球， 其分法种数是 1 73 CN； 所以 10 个球按题意分法种数为84 1 7 1 6 1 7 3 7321 CCCCNNNN。 由上面解题过程可以明显感到，这类问题进行分类计算比较繁琐，若上题中球 的数目较多，处理起来将更

8、加困难， 一次我们需要寻求一种新的模式来解决该问题， 由此我们创设这样一种虚拟的情境插板。 我们首先将 10个相同的球构造为一个数列aaaaaaaaaaA,， 这 10 个 相同的数进行全排列，在数列中会有9 个空当（除去首尾两个空当） ，现在我们用 “挡板”把这个数列隔成有序的7 份，每个班级依此按班级序号分到对应位置的几 个球（可能是 1 个、2 个、3 个、4 个） 。这样每个班级分到球的个数不在于它们所 排的位置，借助于这样一种虚拟的“挡板”分配物品的方法称之为“插板法”。 根据上面情境分析可知，分球的方法实际便是挡板的插法：即9 个空当之中插 入 6 个“挡板”，其方法种数为84 6

9、 9 C，简洁明了。 2.1.2 构造排列组合解不定方程 3. 解不定方程2005zyx的正整数解的组数。 此题用列举法求解比较困难，而用上面提出的“隔板法”模型，题目就比较简 单了。我们首先把这个题目构造为2005个相同小球，把 2005个相同小球进行一个 组合数学中的构造方法 4 全排列，两个相邻的小球之间我们构造出一个空格，在这个排列当中会有2004 个 空格（首尾不相连），在其中两个空格中各放入一块隔板，把2005个相同的小球分 成三部分，每部分可构造为zyx,，每进行一次不同的小球分割，就会产生一组不 同正整数解，这样题目简单明了了，把一个不定方程构造成了一个有序数列，通过 构造我们

10、可得正整数解共有 2 2004 C组。 从上述两例的解法看到，这种插板法解决起来非常简单，但是也要提醒大家一 下，这类问题模型的构造要求的条件相当严格，必须具备以下三个条件： （1）所要分的物品规格必须完全相同； （2）所要分的物品必须分完，决不允许有剩余； （3）参与分物品的每个成员至少分到1 个，决不允许出现分不到物品的成 员。 2.1.3 构造排列组合解几何问题 立体几何中的排列组合问题是我们学习中的一个难点，由于解决这类问题的方 法灵活、思路独特，因此我们常常发出“解排列组合题难、解组合几何题更难”的 感慨。其实，解组合几何题也不是没有规律可循的，关键是我们要善于把有关问题 转化为排列

11、组合问题， 这就要求我们明确构成几何图形的元素，适当分步选取元素。 利用构造法解组合几何题，可先构造几何图形，再统计其中的点、线、面的数目。 4. 在平面直角坐标中， x 轴正半轴上有 5 个点， y 轴正半轴有 3 个点，将 x 轴 上 5 个点和 y 轴上 3 个点连成 15条线段，这 15 条线段在第一象限内的交点最多有 多少个？ 这样一条条的数可以很快得出结果，但是这样浪费时间，而且麻烦，我们可以 构造出四边形， 通过求构造出的四边形的个数来求点数因为凸四边的对角线有一个 交点，因此问题可转化为用8 个点可构成四边形，而且四边形必须在x 轴或者 y 轴 上都有 2 个点。 在 x 轴正

12、半轴的 5 个点，这 5 个点可构成一个全排列，在构造的排列中任取2 个点，作为四边形的两个顶点，有 3 5 C 种选法，接下来构造在y 轴正半轴的 3 个点， 构造这 3 个点的一个全排列，其中任取出2 个点作为，有 2 3 C 种选法，经过一番构 造，凸四边形的四个点找出，可构成四边形 2 3 2 5C C 2 3 2 5C C个，故在第一象限内的交点 最多有30 2 3 2 5C C。 通过构造我们使问题简单化，直接去求解，可以得到答案，付出的努力也会很 多，但是不划算，我们用构造出四边形，轻松解决掉，不费吹灰之力。 组合数学中的构造方法 5 2.1.4 构造排列组合解可重复问题 5.

13、n元集的 r- 可重复组合个数为 r rn C 1。 证明：该问题用组合的方法来解决。 首先构造 n元集nA, 2, 1， 以K表示A 的全部r-可重复组合所成之集， 1 K 表示1rn元集的全部r-组合所成之集。令 1,2 , 1 1 rnA， 设Kaaa r , 21 ， 其 中naaa r21 1， 则 11211 321 rnraaaa r 。这样很明显我们构造出了一个映射 关系，1, 2, 1, 321321 raaaaaaaa rr 是K到 1 K 上的一个一一对应 映 射 ， 通 过 构 造 好 的 映 射 转 化 为 一 个 好 求 解 的 元 集 1 K， 由 相 等 原 则

14、 有 r rn KK 1 1 ，这样便求出 n元集的 r-可重复组合的个数，用构造法把 n元 集的复杂组合问题，转化为简单的元集 1 K 的问题。 构造法在数学中占有十分重要的地位，在数学解题中亦有着十分重要的作用。 许多数学问题的求解，当我们把具体的对象构造出来以后，问题也就完全解决了。 构造法是帮助发现数学理论和解决问题的方法。它在数学解题中的作用主要表 现在两个方面： 一是许多问题本身有构造性的要求，或者可以通过构造而直接得解； 二是有些问题需要通过构造出一个与原问题有关或等价的新问题（我们亦称之为辅 助问题）帮助原问题的解决，这种巧妙构思正是构造法的技巧与魅力所在。 构造法具有较大的灵

15、活性和技巧性。根据所要解决的问题特征，既可以构造函 数、构造不等式、构造恒等式、构造数列模型，利用“数”解决数和形的问题。 我国在 1992 年的数学教学大纲关于数学能力的提法从“三大能力”改为 “四大能力”，增加了“解决实际问题”的能力。另外高中数学新课程标准对 高中生硬具备的数学能力做了较为全面的阐述，意在提高学生空间想象、 直觉猜想、 归纳抽象、符号表示、 运算求解、 演绎证明、 体系构建等诸多方面的能力，简言之， 就是提高学生“数学建模”的能力。构造法能把“数学建模”与“数学新课程”整 合起来，它重在发展学生的应用意识和创新意识并希望能够上升为一种数学意识。 2.2 构造生成函数解决组

16、合中的相关问题 生成函数又叫做母函数。生成函数方法是离散数学的重要方法，是连接离散数 学与连续数学的桥梁。在组合数学中，生成函数的典型作用主要体现在组合计数方 面，是解决组合计数问题的强有力工具之一，其基本思想为：为了获得一个序列 组合数学中的构造方法 6 0kk a的有关知识，我们引用一个幂级数来整体表示这个序列 2 210 0 xaxaaxaxG k k k （1） ， xG为序列 0kk a的生成函数。这样，一个序列和它的生成函数一一对应，我们可 以通过对生成函数的运算和分析得到这个序列的很多性质。 18 世纪，欧拉在研究正整数分拆时首先使用了母函数，19 世纪初拉普拉斯在 研究概率问题时得到进一步发展。母函数的一种自然推广，导致概率论中引进强有 力的工具特征函数，它把随机变量的分布函数变换为它的特征函数，从而把对分 布函数的研究转化为对对应的特征函数的研究，大大地推动了相互独立随机变量的 和的极限理论的研究。 2.2.1 用生成函数构造递推关系 几个常用幂级数的展开 0 1 1 n n tt