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

2023年12月9日发(作者：高三高考数学试卷下载)

组合数学中构造法的研究背景

1 组合数学中构造法的研究背景

在当今，组合数学是一门非常活跃的学科，它在各个不同的领域都有相当的应用，尤其在日益发展的计算机科学中。因为计算机科学的核心内容是使用算法和离散数据。而组合数学就是研究离散对象的科学。

组合数学是如此的重要，那你了解其中的构造法吗？提到构造法，我们首先来介绍下吧。构造就是面对问题直接解决相当困难，可以借助其他的方法，用其他路径来解决我们的问题，“曲线救国”，问题便迎刃而解。它不是一种数学方法，而是一种数学思想，体现了数学的发现、类比、划归、猜想、试验和归纳的思想。这就是构造法的魅力。

谓构造性的方法就是数学中的概念和方法按固定的方式经有限个步骤能够定义的概念和能够实现的方法。从数学产生那天起，数学中的构造性的方法也就伴随着产生了。但是构造性方法这个术语的提出，以至把这个方法推向极端，并致力于这个方法的研究，是与数学基础的直觉派有关。直觉派出于对数学的“可信性”的考虑，提出一个著名的口号：“存在必须是被构造。”这就是构造主义。

构造法真正体现出了“数式与图形的沟通、直觉与逻辑的互动”，这也正是数学建模的一个基本特征。另外，在应用构造法时，要明确目的，需要构造的是什么，根据什么设计构造方案。构造的模型结构形式应尽可能的简单，以便于问题的解决，尽可能地使复杂问题简单化；构造的模型必须是熟悉的，通过熟悉的模型将难以入手的问题转化为熟悉的问题；构造的模型尽可能地直观，通过构造使问题变的直观明了。

1 组合数学中的构造方法

2 组合数学中的构造方法

2.1 排列组合中的构造方法及其应用

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

定义1 所谓排列，就是指从给定个数的元素中取出指定个数的元素进行排序。从n个不同元素中，任取mmn个元素（被取出的元素各不相同），按照一定的顺序排成一列，叫做n个不同元素取出m个元素的一个排列。

定义2 组合则是指从给定个数的元素中仅仅取出指定个数的元素，不考虑排序。从n个不同元素中，任取mmn个元素并成一组，叫做从n个不同元素中取出m个元素的一个组合。

数学解题的一个基本思想就是设法将所要求解的问题转化为我们所熟悉的或容易解决的问题，这一点在解排列组合问题是尤显重要。我们在学的过程中药经常强化这一思想，以便寻求更便捷的解法。接下来所提的构造模型法恰恰很好地做到了这一点。

2.1.1 构造排列组合解数的排列问题

捆绑法

捆绑法就是把分散的几个对象构造为一个组合，把这个组合看作一个元素和其他元素进行排列，然后再考虑大元素内部各元素间顺序，这样的构造很容易就能求得我们的所需。

1. 7个人站成一排，求出甲、乙、丙三人必须相邻的排法种数。

这个问题比较简单，但是它是排列组合中的相邻问题，面对这样的模型，我

们用熟知的“捆绑法”。先将必须相邻的甲、乙、丙三个人构造成一个集合N，于是由原来的7个人变为现在的“5个人”，即1a,1b,1c,1d,1e，对这五个元素进5行全排列，其排法种数为A5，题中要求甲、乙、丙三人必须相邻，这三个人做全排3列为A3，经题意我们构造了这样两个数列，通过这两个数列，我们明显看出解决这2 组合数学中的构造方法

53个问题需要分步来做，由此可用乘法原则得排法种数为A5A3。

构造“捆绑法”主要用于求解“必须相邻”的模型，但是对于必不相邻的问题呢？我们可以用另外一种模型——“插入法”，它能够解决“必不相邻”的问题。

插板法

构造一个元素组合的全排列，在这一个排列的间隙中插板，不同的插板会有不同的方法种数，换句话说就是在在n个元素间的（n-1）个空中插入若干个（b）个板，可以把n个元素分成（b+1）组。

2. 现有10个完全相同的球全部分给7个班级，每班至少一个球，问共有多少种不同的分法？

题目中球的分法可构造为三类：

（1）有三个班每个班分到2个球，其余4个班每班分到1个球，其分法种数3是N1C7；

（2）有一个班分到4个球，其余6个班每班分到1个球，其分法种数是

11N2C7C6；

1（3）有一个班分到4个球，其余6个班每班分到1个球，其分法种数是N3C7；3111所以10个球按题意分法种数为NN1N2N3C7C7C6C784。

由上面解题过程可以明显感到，这类问题进行分类计算比较繁琐，若上题中球的数目较多，处理起来将更加困难，一次我们需要寻求一种新的模式来解决该问题，由此我们创设这样一种虚拟的情境——插板。

我们首先将10个相同的球构造为一个数列Aa,a,a,a,a,a,a,a,a,a，这10个相同的数进行全排列，在数列中会有9个空当（除去首尾两个空当），现在我们用“挡板”把这个数列隔成有序的7份，每个班级依此按班级序号分到对应位置的几个球（可能是1个、2个、3个、4个）。这样每个班级分到球的个数不在于它们所排的位置，借助于这样一种虚拟的“挡板”分配物品的方法称之为“插板法”。

根据上面情境分析可知，分球的方法实际便是挡板的插法：即9个空当之中插6入6个“挡板”，其方法种数为C984，简洁明了。

2.1.2 构造排列组合解不定方程

3. 解不定方程xyz2005的正整数解的组数。

此题用列举法求解比较困难，而用上面提出的“隔板法”模型，题目就比较简单了。我们首先把这个题目构造为2005个相同小球，把2005个相同小球进行一个3 组合数学中的构造方法

全排列，两个相邻的小球之间我们构造出一个空格，在这个排列当中会有2004个空格（首尾不相连），在其中两个空格中各放入一块隔板，把2005个相同的小球分成三部分，每部分可构造为x,y,z，每进行一次不同的小球分割，就会产生一组不同正整数解，这样题目简单明了了，把一个不定方程构造成了一个有序数列，通过2构造我们可得正整数解共有C2004组。

从上述两例的解法看到，这种插板法解决起来非常简单，但是也要提醒大家一下，这类问题模型的构造要求的条件相当严格，必须具备以下三个条件：

（1）所要分的物品规格必须完全相同；

（2）所要分的物品必须分完，决不允许有剩余；

（3）参与分物品的每个成员至少分到1个，决不允许 出现分不到物品的成

员。

2.1.3 构造排列组合解几何问题

立体几何中的排列组合问题是我们学习中的一个难点，由于解决这类问题的方法灵活、思路独特，因此我们常常发出“解排列组合题难、解组合几何题更难”的感慨。其实，解组合几何题也不是没有规律可循的，关键是我们要善于把有关问题转化为排列组合问题，这就要求我们明确构成几何图形的元素，适当分步选取元素。利用构造法解组合几何题，可先构造几何图形，再统计其中的点、线、面的数目。

4. 在平面直角坐标中，x轴正半轴上有5个点，y轴正半轴有3个点，将x轴上5个点和y轴上3个点连成15条线段，这15条线段在第一象限内的交点最多有多少个？

这样一条条的数可以很快得出结果，但是这样浪费时间，而且麻烦，我们可以构造出四边形，通过求构造出的四边形的个数来求点数因为凸四边的对角线有一个交点，因此问题可转化为用8个点可构成四边形，而且四边形必须在x轴或者y轴上都有2个点。

在x轴正半轴的5个点，这5个点可构成一个全排列，在构造的排列中任取23个点，作为四边形的两个顶点，有C5种选法，接下来构造在y轴正半轴的3个点，构造这3个点的一个全排列，其中任取出2个点作为，有C32种选法，经过一番构22造，凸四边形的四个点找出，可构成四边形C52C32C5C3个，故在第一象限内的交点22最多有C5C330。

通过构造我们使问题简单化，直接去求解，可以得到答案，付出的努力也会很多，但是不划算，我们用构造出四边形，轻松解决掉，不费吹灰之力。

4 组合数学中的构造方法

2.1.4 构造排列组合解可重复问题

r5.

n元集的r-可重复组合个数为Cnr1。

证明：该问题用组合的方法来解决。首先构造n元集A以K表示A1,2,,n，的全部r-可重复组合所成之集，K1表示nr1元集的全部r-组合所成之集。令A11,2,,nr1，设a1,a2,,arK，其中1a1a2arn，则1a1a21a32arr1nr1。这样很明显我们构造出了一个映射关系，a1,a2,a3,,ara1,a21,a32,,arr1是K到K1上的一个一一对应映射，通过构造好的映射转化为一个好求解的元集K1，由相等原则有nr1KK1r，这样便求出n元集的r-可重复组合的个数，用构造法把n元集的复杂组合问题，转化为简单的元集K1的问题。

构造法在数学中占有十分重要的地位，在数学解题中亦有着十分重要的作用。许多数学问题的求解，当我们把具体的对象构造出来以后，问题也就完全解决了。

构造法是帮助发现数学理论和解决问题的方法。它在数学解题中的作用主要表现在两个方面：一是许多问题本身有构造性的要求，或者可以通过构造而直接得解；二是有些问题需要通过构造出一个与原问题有关或等价的新问题（我们亦称之为辅助问题）帮助原问题的解决，这种巧妙构思正是构造法的技巧与魅力所在。

构造法具有较大的灵活性和技巧性。根据所要解决的问题特征，既可以构造函数、构造不等式、构造恒等式、构造数列模型，利用“数”解决数和形的问题。

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

2.2 构造生成函数解决组合中的相关问题

生成函数又叫做母函数。生成函数方法是离散数学的重要方法，是连接离散数学与连续数学的桥梁。在组合数学中，生成函数的典型作用主要体现在组合计数方面，是解决组合计数问题的强有力工具之一，其基本思想为：为了获得一个序列5 组合数学中的构造方法

akk0的有关知识，我们引用一个幂级数来整体表示这个序列

，Gxakxka0a1xa2x2…………………………………………（1）k0Gx为序列akk0的生成函数。这样，一个序列和它的生成函数一一对应，我们可以通过对生成函数的运算和分析得到这个序列的很多性质。

18世纪，欧拉在研究正整数分拆时首先使用了母函数，19世纪初拉普拉斯在研究概率问题时得到进一步发展。母函数的一种自然推广，导致概率论中引进强有力的工具—特征函数，它把随机变量的分布函数变换为它的特征函数，从而把对分布函数的研究转化为对对应的特征函数的研究，大大地推动了相互独立随机变量的和的极限理论的研究。

2.2.1 用生成函数构造递推关系

几个常用幂级数的展开

1t1（2）

tn……………………………………………………………………n01at1

antn………………………………………………………………（3）n01tknk1n

t………………………………………………………（4）nn01at1t1knk1nn（5）

at……………………………………………………nn021n0122n112n2n（6）

t………………………………………………nn1递推关系是计算中的一个强有力工具,而递推关系的求解一般比较困难,利用母函数求解递推关系则是一种主要的、行之有效的方法。

1. 求n位十进制数中出现偶数个5的数的个数。

解：首先构造对象，令an是n位十进制数中出现偶数个5的数的个数,bn是n位十进制数中出现奇数个5的数的个数。因此有关系

6 组合数学中的构造方法

an9an1bn1919n2an1，其中a18。则an8an1910n2此关系为关于序列an的递推关系，如此解递推关系非常难于求出。我们不妨考虑生成函数，来解决下这道问题，首先我们构造序列an的母函数Ax，即

Axa1a2xa3x2，这样我们便构造出了一个简单的生成函数，构造出了生成函数，好像没多大作用，我们继续构造与递推关系想关联的生成函数左右同时成以8x即：

8xAx8a1x8a2x28a3x3

接下来我们利用错位相加减的方法，得

18xAx89x9102x28Ax9x871x

110x110x871x，再将Ax展开成幂级数的形式：

18x110x1791nkAx78910218x110x2n0x2n。

递推关系的求解主要是利用递推关系求得母函数的一种形式算法，母函数确定了，相应的递推关系对应的结果就确定了，这样的例子还有很多，想著名的Hanoi塔问题，Fibonacci数列都是典型的利用母函数解决递推关系的例子。

2. 设a01,a12且an5an16an2n2，求数列an的通项。

解：我们可以通过生成函数来解决，首先我们构造生成函数，如下：

令fxanxna0a1xa2x2anxn……………………………………(7)

n0则5xfx5a0x5a1x25an1xn………………………………………(8)

且6x2fx6a0x26a1x36an2xn………………………………………(9)

（7）（8）（9）式分别构造出了递推关系式的每一项，an,an1,an2，构造出了生成函数，根据题意让几个生成函数进行运算，可得

15x6xfxaa2015a0x，即15x6x2fx17x，

7 组合数学中的构造方法

17x54nnnnn有fx，52x43x5243x212x13x15x6xn0n0n0从而an52n43n。

构造生成函数是为了更好的了解题意，更清楚的整出解题思路，对于递推关系问题，我们可以先试着写几个相关的递推关系，用到用不到不要紧，先罗列出来，根据罗列出来的函数来看问题，再根据题意，让几个不相干的函数产生关系，这样我们就成功了一大步了，然后慢慢继续我们就会得到我们所需的关系。

我们通过生成函数，构造出递推关系。先根据题意列出我们所要的生成函数，列出的生成函数经过变换，达到我们题意所需要的形式，然后根据等式变换，变换出递推关系，这样一个简单的递推关系就得到了，再由递推关系继续求解，求得我们所需要的结果。

2.2.2 构造生成函数法解决好布局数

3. 这样一个棋盘，求该棋盘的好布局数。

看到这样我们不妨构造有坐标点的棋盘，这个棋盘我们一目了然。

棋盘是有了，可是直接去求还是比较困难，要考虑的车的好布局数还是很多，我们继续降阶t降阶为简单的棋盘就比较好，求解了，后边的棋盘可以看做是两个棋盘的乘积，我们继续求解棋盘

234原式t19t25t24t6t。求车问题就是对棋盘进行降阶，不好算的棋盘在继续降阶，直到降阶为我们好求解的棋盘，然后8 组合数学中的构造方法

对棋盘构造生成函数，展开形式幂级数，求对应的车问题。

4. 作5个相异元a1,a2,a3,a4,a5的全排列，其中a1不排在第1位和第2位，a2不排在第2位和第3位，a3不排在第5位，a4不排在第4位和第5位，a5不排在第3位和第4位，问可以作出多少个不同的全排列？

解 ：拿排列组合解决会非常麻烦，我不妨试一下看能不能转化为棋盘，把这5个数看做一行，他们会有5个位置，把这5个位置看成一列，这样我们便构造出了一个55棋盘，根据题意，这5个数会有禁位，这便是一个有禁位排列问题，对应的有禁位的棋盘为其中代表着禁位，则该禁格棋盘的车多项式为：

，Rt,Ct



t

这样便把一个复杂的问题用构造棋盘的形式形象的表示出来了，经过变化，构造成简单的棋盘，原问题经过构造转化成了现在简单的棋盘问题，通过求该棋盘的好布局数，便可得到我们所需要的结果，继续求解如下：

Rt,Ct12t14t3t213tt215t6t2t3

19t28t235t315t4t5，构造出了棋盘，我们继续构造生成函数去解决问题，如上所得，我们用生成函数求出了有禁位排列问题的车多项式，但是我们要求出在禁位上一个车也没有，即好布局数，我们接下来要求命中多项式。

Et5!94!t1283!t1352!t115t1t1，我们所要求得是2345没有在禁位上的排列数，即E016。

车多项式问题是解决实际问题时，构造法的最好体现，面对问题，我们首先看能不能符合棋盘，如果符合棋盘问题，转化为棋盘问题来解决，其中有限制的地方我们设置为禁位，列出有禁位的棋盘 ，然后构造出生成函数，求得我们的车多项9 组合数学中的构造方法

式，根据题意求有禁位的命中多项式，这样好布局数便可求出，问题便得到解决。

2.2.3 构造生成函数解决不定方程问题

r15. 求不定方程x1x2xnrrn的正整数解的个数为n1。

这是求不定方程的正整数解，一般的解法是令yixi1i1,2,3,,n，则当xi1时，有yi0，且当x1x2x3xnr时，有y1y2ynrn，反之亦然。所以不定方程的正整数解的个数等于不定方程y1y2ynrnnrn1r1的非负整数解的个数，得出结果为rnn1。

这样可以得出，但是我们还可以排列组合，用排列组合的方法来解决这道题，首先我们构造一个排列，我们有r个数，构造一个有r个数的集合，对这个集合进行全排列，而我们不定方程中有n个未知数，这样就是把有r个数的集合分成n份，接下来，我们对我们构造好的排列进行分份，在这个排列中，两个相邻的数至今，我们构造一个空隙，如此构造便可构造出r1个空隙，分成n份，在空隙中就取n11个，这样便构造成了一个组合，得出结果为Crn1，这个结果即为我们所求。

构造排列是一种途径，但是我们用生成函数来解决，更能胜过一筹，同样，构造生成函数我们要先构造x的值即x1tt2tn，我们当中有n个未知数，对这n个未知数相乘，xn1tttn，这样我们便得到一个生成函数，我nn1们最后是要得r的值，便求xr的系数，它的系数即是我们所求，得结果r1。

6. 求不定方程x1x2x314满足条件x18,x28,x38的非负整数解的个数。

解：设所求为N，则N是At1tt2t8，这样我们便构造了一个满足题设的生成函数，而我们所求为整数解的个数，则我们便取展开式中t14的系数，而

1t9At1t91t331t3313t3tt91827k22tk0k

10 组合数学中的构造方法

14252所以N23212032157，即非负整数解的个数为57。

生成函数解决不定方程问题，我们首先要做的就是构造出一个生成函数，根据题意选择我们x值为几次幂，然后相乘，取某一项符合题意的系数，这个系数即是我们所要求解的结果。

2.2.4 构造生成函数解证明组合恒等式问题

22+3C32+4C47. 求证2C22nCn(n1)n(n1)(3n2)

24可以看出，该组合恒等式左端比较复杂，不太可能利用组合公式去证明，观察后发现等式左端各项规律性较强。通过分析，设法将等式左端看作是某一函数中确2定项的系数，由Cn为1x中x2项的系数，这样我们便构造了生成函数所具备的n条件，构造生成函数为：fn(x)(1x)2(1x)2n(1x)n(x1)，即fnx是2。nCn222一个以1x为未定元的幂级数，fn(x)中x2的系数即为2C2+3C3+4C4同时，利用“错位相减法”fnx两边同时乘以(1x)得

(1x)fn(x)(1x)22(1x)3(n1)(1x)nn(1x)n1，构造好了生成函数，要往题意上靠拢，所以fnx1xfnx得：

xfn(x)(1x)(1x)2(1x)3(1x)nn(1x)n1，整理得到：

(x1)(x1)n1n(x1)n12xfn(x)，比较的系数即得所证结果。

2xx从上面这个例子可以看出，根据题意，灵活地引入构造函数是证明组合恒等式的关键所在。

2.2.5 构造生成函数在概率中的应用

8. 在做抽样调查时，采访的男士有教师，医生，律师等不同的q个行业，女士也有不同的p个行业，假设我们在每一行业中至多选取2位男士和至多选取1位女士，问有多少种不同的方法取k个人的样本？

解：要区分相同性别的人，当且仅当他们属于不同的范畴，现以选择k个人的方法数量做生成函数。在q种范畴的每一个中，我们或者选择0，1，2位男士做样本，因此每个范畴给出1xx2项，另外选择0或1位女士，所以p种范畴中的11 组合数学中的构造方法

每一个给出(1+x)项。

所以，

Gx1xx21x

qp因此选择k个人的方法数量是Gx中xk的系数。

例如pq3,k4时，Gx1xx21x1xx1x

33231x2x21x

33336624342

1x1xx1x1xx1xx1x0123365431x31xx231xx4x61x

654所以，x4的系数是43230。

即在每一行业中选取2位男士和1位女士有48种不同的方法取四个人的样本。

2.2.6 构造生成函数在几何问题中应用

9. 求由直线x3y12，直线x0及直线y0所围成的三角形内（包括边界）的整点（横坐标和纵坐标均是整数的点）的个数。

解：设所求为N，则N是满足条件x3y12的非负整数解的个数。令z12x3y，如果x3y12，则z0且x3yz12，所以N是方程

x3yz12的非负整数解的个数，这样便构造出了生成函数为

At1tt21t3t6，而N即为展开式中t12的系数，而

At1t1t22311tt221t3312t3t2tt234k22tk03k，所以4232最后N2152035。

2210. 求平面直角坐标系Oxy中，以A5,0,B5,0,C5,0,D0,5为顶点的正方形内（包括边界）的整点的个数。

解：设所求为N，过点A5,0,B0,5的直线方程为xy5，由对称性知，点

12 组合数学中的构造方法

x,y是该正方形内的一个整点充分必要条件是xy5且x和y均为整数，所以N是方程xyz5满足条件z0的整数解的个数，这样便把问题构造成了条件方程，接下来继续构造生成函数，x,y为非负整数，则构造x,y的生成函数和z的不同，他们未知元的幂数也不相同，根据题意构造出的生成函数为

At12t2t22t31tt2te，那么N则是生成函数展开式中t5的2系数，通过生成函数可以得到我们所求，生成函数是构造的关键，At变换计算得：

At21t11t1t11221t312tt2k22tk0k

524232所以N222261。

构造生成函数解几何问题时，首先将空间图形问题，转化为容易操作的数学方程，通过关系式，我们容易构造生成函数，只有构造了生成函数我们才容易解决数学方程，二者彼此相辅相成，缺一不可。

生成函数(形式幂级数)具有良好的性质，便于处理，因此它的应用较广泛。在组合分析、数论、概率论和图论等数学领域中有着广泛的应用。

2.3 鸽巢原理中的构造及其应用

鸽巢原理又叫抽屉原理，是组合数学中貌似平凡，却透着不平凡应用的原理之一，它是德国数学家狄利克雷首先发现的，因此又叫利克雷原理，它是一个重要而有基本的组合原理，是处理涉及存在性问题的重要方法，反映了整数最基本的性质，在数论和组合论中有着广泛的应用，常常结合几何、整除、数列等问题，解决初等数学中的组合问题。

2.3.1 鸽巢原理的含义

鸽巢原理的一般含义是，把3个苹果分别放在2个抽屉里，一共有4个不同的方法，0,3,1,2,2,1,3,0，无论哪种放法，都可以说“必有一个鸽巢放了两个或两个以上的苹果”，这个结论是在“任意放法”的情况下，得出一个“必然结果”。类似的，如果5只鸽子飞进4个鸽笼里，那么一定有一个鸽笼飞进了2只或2只以上的鸽子；如果有6封信，任意投入5个信箱里，那么一定有一个信箱至少有2封信。我们把这些例子中的“苹果”、“鸽子”、“信”都看作一种“物体”，把“抽屉”“鸽巢”“信箱”都抽象地看成“鸽巢”，于是可以得到鸽巢原理的简单表达形式。

13 组合数学中的构造方法

如果把mmn个物体任意放入n个鸽巢中，那么一定有某个鸽巢至少放有两个物体。换一种表达形式我们可以说把m个物体任意放入n个抽屉里，如果mkmr，那么当r0时，则其中一定有某个鸽巢至少放k个物体；当r0时，则其中一定有某个鸽巢至少放k1个物体。

1. 某棋手参加了一次为期11周共77天的集训，已知他每天至少下一盘棋，而每周之多下12盘棋。证明：在集训期间必有连续的若干天，在这几天里该棋手共下21盘棋。

证明：设该棋手从第1天到第i1,2,3,,77天共下了ai盘棋。因为该棋手每周至多下12盘棋，所以棋手77天里至多下1211132盘棋。又因为棋手每天至少下一盘棋，所以1a1a2a77132，从而

令A

1,2,3,,153，A1a1,a2,,a77，22a121a221a7721153。A2b1,b2,,b77，其中biai21i1,2,,77，则A1A2A。如果

A1A2，则AA1A2A1A27777154，这与A153矛盾，所以A1A2，从而存在akA1,b1A2，满足akbl，即akal21，这表明该棋手由第l1天到第k天这连续的kl天里共下了21盘棋。由此可看出鸽巢原理能帮我们解决不可思议的一些事情。

鸽巢原理的构造方法有几种经常用到。

（1）如果在长度为1的区间内有多于n个点，可考虑把区间n等分成n个子1区间，由鸽巢原理得知，一定有两个点落在同一子区间，它们之间的距离不大于，n这种构造法是等分区间的构造，常用于处理一些不等式的证明。

（2）涉及自然数问题，有时常用对模n同余分类法，构造n个鸽巢：如果以2为模，将全体自然数分为“余0类”(偶数)和“余1类”(奇数)；两个鸽巢以3为模，将全体自然数分为“余0类”“余1类”“余2类”；3个鸽巢以n为模，可以将全体自然数分为“余0类”“余1类”“余1类”，共n1个鸽巢。一般地，任给nn1个自然数，其中必有两个数的差是n1的倍数。任取n个数，则必有两个数在一个鸽巢内，也就是这两个数除以n1所得余数相同，所以大数减小数，它们的差就是n1的倍数。

在涉及到一个集合图形内有若干点时，常常是把图形适当的分成适当的部分，用分割所得的小图形做鸽巢，这样的划分一般符合一个“分划”的定义，即鸽巢的14 组合数学中的构造方法

元素既互不重复，也无遗憾；但有的时候根据题解需要，分割也可使得鸽巢之间含有共同元素。

2.3.2 构造鸽巢原理的途径

2. 试证任给出5个整数，必能从其中选出三个，使得它们的和能被3整除。

证明：任何数除以3所得余数为0、1、2，不妨构造3个鸽巢，0,1,2，

①若这5个自然数除以3后所得余数分别分布在3个鸽巢中(即鸽巢中分别含有余数为0、1、2的数)，我们从3个鸽巢中各取1一个必能被3整除。

②若这5个余数分布在其中的两个鸽巢里，则其中必有一个鸽巢，包含3个余数，而这三个余数之和或为0，或3，或为6，故对应的3个自然数之和是3的倍数。③若这5个余数分布在其中的一个抽屉中，很显然，必有3个自然数之和能被3整除。

有时我们可以用分组构造鸽巢的方法解题，确定分组的“对象”很关键。确定了“对象”之后，其个数相当于“求”的个数而言，又往往显得太多，只有把这些“对象”分成适当数量的组即鸽巢后，才能应用鸽巢原理。

运用鸽巢原理解题的关键，在于构造合适的“鸽巢”，我们可以把“鸽巢”的构造方法归为三大类：一类是用分割图形构造鸽巢；一类是用分类的概念构造鸽巢；最后一类是用分组来构造鸽巢，然而，其实质均是对对象进行恰当的分类，鸽巢选的秒，就可以在数学中的组合问题中得出非常漂亮的结果。

2.4 构造方法在证明组合恒等式中的应用

组合恒等式是组合数学的重要内容，其证明方法多种多样，其中的构造类方法尤为突出。

当有些组合恒等式直接运用题设条件难以证明时，不妨把所考虑的恒等式置于某种实际背景下，构造组合模型，把组合恒等式的问题转化为组合计数问题，再用两种方法计算同一个两，列出等量关系。

rrkr1. 证明CmCnCmn

k0r证：构造一个组合模型：甲班有m个学生，乙班有n个学生，今从两班抽出rr个学生参加劳动，则所有抽法数是Cmn；另一方面，可以看成由甲班抽出rk个rkrkCn学生，从乙班抽出k个学生，k从0到r取值，则所有抽法数是：Cm，从而k0可证得题设。

这样的构造方法称之为“原型构造法”，这样很实际的去了解题的意思，把实际问题与书序问题紧密联系在一起。

15 组合数学中的构造方法

012n2. 求证CnCnCnCn2n。

对这样一个恒等式，我们可以考虑成有n个元素的集合的子集，元素的个数012n为,0,1,2,n个的子集数，分别有Cn个，由加法原理得等式左边；考,Cn,Cn,,Cn虑集合中n个元素，每个都有取与不取2种可能，有乘法原理得子集个数为2n，即等式右边。

这是一种把数学问题构造为抽象的事务形态，但是有些题目的结构比较复杂，不容易找到合适的原型，可以吧原题适当改造或把原型适当变形。

12n1n3. 求证Cn2Cnn1CnnCnn2n1。

证明：适合等式左边的原型十分困难，但是容易看出它是可以变形成如下的三角形状：

012n1n

CnCnCnCnCn012n1n

CnCnCnCnCn………………………………

012n1n

CnCnCnCnCn012n1n

CnCnCnCnCn上面式子中各行的实际原型分别是n个灯泡中有1至n个亮，2至n个亮，…，n1至n个亮，n个亮的组合数，其对立面分别是n个不亮，n-1至n个不亮，…，2至n个不亮，1至n个不亮。比较一下可知所有不亮的组合数之和与所有亮的组合数之和相等。但两类情况合起来就得这n组灯泡的每一组中的每一个可以亮或不亮的全部情况，其组合数之和为n2n，从而推得所求。

把这种思路整理一下，可得比较简练的证明方法：

12n1n设MCn，则

2Cnn1CnnCnn1n210。因为

MCn2Cnn1CnnCn012n2MnCnCnCnCnn2n，所以Mn2n1，可见，这种原型构造法即使不直接用来证明，在寻找证题思路方面也大有益处。

在证题方面，原型构造法也是一种普遍使用的方法，并不限于组合问题，也不限于证明，数学的各部分都可用，证明、计算、判断等各种题型都可以。事实上举16 组合数学中的构造方法

反例证明为错的思想方法就是一种原型构造思想。

4. 判断互为反函数的两个函数图象的交点必在对称轴yx上。

这个命题，很多人会误认为是真命题，很多教学资料上也说是真命题，其实是错误的。

x1反例：fx，则f1xlog1x。

16161111两函数的图象有交点,和,，在直线yx上。这种方法不一定是最4224简单的，但是很多时候确实是一种巧妙的方法。

这种原型有时很不容易构造，需要较强的发散思维能力，构造原型本身就是一种创造工作，需要对所给问题进行深入的分析，找出它的形式特点和实际意义。在解决问题中经常用到一题多解或划归转化等方法，都可以极大地提高分析和解决问题的额能力，尤其是一些实际原型如能自己构造出来，远比能解一些给出的应用题要强得多。

17 总结

3 总结

构造法解题有着你意想不到的功效，将问题快捷简便的解决。构造法解题重在“构造”，它可以构造方程、不等式、函数、图形等，在数学中解题中的策略有：直觉构造、联想构造、你想构造，归纳构造，类比构造等。常见的构造方法有：构造数列，构造鸽巢、集合、函数。这些常见的策略与方法对我们在解数学试题有非常好的帮助，能够很好的培养与提高学生的创新思维能力。

而这组合数学中构造法的灵魂为生成函数，在组合数学中，生成函数几乎无所不能，凡是不好解决的问题，都可以试着用生成函数来解决，它是一项简单而又灵活的解题方法。

构造生成函数可以解决组合恒等式、不定方程、好布局数、递推关系等等，在这些应用中，我们首先想到的是把问题进行转化，转化为我们所熟知数学关系式，通过数学关系式，再联系实际问题的逻辑，我们可以很轻松的构造出我们所学的生成函数式，有了函数式，我们可以根据我们所需，求出我们要得到的展开式中的哪一项，不管怎么去构造，最后都需要展开形式幂级数，但是我们只需要展开我们所需的那一项，其余的项我们忽略不计。

生成函数在组合数学中占据着十分重要的地位，但是构造法的止境是无穷远的，它是一种思想，更是一种策略，一种艺术。构造生成函数只是其中的小部分，即使这样都如此重要，那么整个构造法呢？不可思量，构造法也在教我们想问题的时候可以不直接面对，而是从别的方向入手，了解到这个问题的真面目后，我们再从正面去解决这个问题，如此迂回，快乐其中。

18 致谢

致谢

本研究及学位论文是在我的导师李老师的亲切关怀和悉心指导下完成的。她严肃的科学态度，严谨的治学精神，精益求精的工作作风，深深地感染和激励着我。李老师不仅在学业上给我以精心指导，同时还在思想、生活上给我以无微不至的关怀，在此谨向李老师致以诚挚的谢意和崇高的敬意。我还要感谢在一起愉快的度过毕业论文小组的同学们，正是由于你们的帮助和支持，我才能克服一个一个的困难和疑惑，直至本文的顺利完成。

在论文即将完成之际，我的心情无法平静，从开始进入课题到论文的顺利完成，有多少可敬的师长、同学、朋友给了我无言的帮助，在这里请接受我诚挚的谢意!最后我还要感谢培养我长大含辛茹苦的父母，谢谢你们!

最后，再次对关心、帮助我的老师和同学表示衷心地感谢！

19