《组合数学方法在数学竞赛题中的应用》由会员分享，可在线阅读，更多相关《组合数学方法在数学竞赛题中的应用（9页珍藏版）》请在金锄头文库上搜索。
1、组合数学方法在数学竞赛题中的应用彭伟坚第 页 , 共 15 页1组合数学方法在数学竞赛题中的应用组合数学方法在数学竞赛题中的应用彭伟坚 温海容（中山市民众镇浪网中学，广东中山 528441,E-mail:）摘要：摘要：通过分析和研究若干有关组合数学的竞赛题并作较为系统的整理，并且利用组合数学中的几个重要的方法进行举例说明.加深对组合数学学习中发散能力的训练与培养.关键词：关键词：组合数学方法；配对原理；抽屉原理；递推关系；生成函数；应用1 引言引言组合数学是一个历史悠久的数学分支.它所研究的对象是离散构形问题.由于在现实生活和科学研究中存在着无穷无尽的离散构形问题，这就决定了组合数学内容丰富，
2、应用广泛，生命力强，讲究方法，讲究技巧的特点.数学竞赛中的组合数学，从内容上可以归结为两大类：组合计数问题，组合设计问题.组合计数问题包括有限集合元素的计算、相应子集的计算、集合分拆方法数的计算等，表现为数值计算、组合恒等式或组合不等式的证明.知识基础是加法原理、乘法原理和排列组合公式；常用的方法有：代数恒等变形、二项式定理、数学归纳法、递推、组合分拆等.2 组合数学方法的应用组合数学方法的应用2.12.1 几个重要原理在数学竞赛题中的应用几个重要原理在数学竞赛题中的应用2.1.12.1.1 加法原理加法原理 加法原理：做一件事情，完成它有N类办法，在第一类办法中有种不同的方法，1M在第二类办
3、法中有中不同的方法，在第N类办法中有种不同的方法，那2MNM么完成这件事情共有+种不同的方法.（文1和文3中都有详细地介绍1M2MNM概念，例题是选自文2.） 【例题例题 1 1】 （1998 年全国高中数学联赛）在正方体的 8 个顶点，12 条棱的中点，6 个面的中心及正方体的中心共 27 个点中，共线的三点组的个数是多少？【分析分析】按性质分类计数.组合数学方法在数学竞赛题中的应用彭伟坚第 页 , 共 15 页2因为每两个顶点为端点的线段的中点都是 27 点组中的点.所以以顶点为线段端点的共线三点组有.2828个 又因为对棱中点连线的中点在 27 点组中，所以这一类的共线三点组有.1823
4、12个两端点为面的中心的共线三点组共有 3 个.故满足条件的共线三点组共有 49 个.【注注 1 1】计数中的加法原理，也即分类的思想方法，是将复杂的问题转化为若干简单问题来处理的极为重要的思想方法.2.1.22.1.2 乘法原理乘法原理 乘法原理：做一件事，完成它需要分成个步骤，做第一 步有种不同的方法，做n1m第二步有不同的方法，做第步有不同的方法.那么完成这件事共有=2mnnmN1m种不同的方法. （文1和文3中都有详细地介绍概念，文2中也有介绍此例2mnm题.）【例题例题 2 2】1996 年全国高中数学联赛从给定的六种不同颜色中选用若干种颜色，将一个正方体的六个面染色，每两个具有公共
5、棱的面染成不同的颜色.则不同的染色方案共有多少种？【分析分析】这里由于有多种不同的情况，则需考虑利用加法原理分类，称法原理分步进行讨论.显然，至少需要三种颜色.（1）用了 6 种颜色，确定某种颜色例如红色所染面为下底，则上底颜色可有 5 种选择；再上、下底已染色后，再确定其余 4 种颜色中的某一种所染面为左侧面，则其余三个面有 3！种染色方案，根据乘法原理，得：30.! 351n（2）共用 5 种颜色.选定 5 种颜色有种方法.必有两面同色必为相对面，确定656 为上、下底面，其颜色可有 5 种选择，再确定一种颜色为左侧面，此时的方法数取决于右侧面的颜色，有 3 种选择，于是有：90.3556
6、2 n组合数学方法在数学竞赛题中的应用彭伟坚第 页 , 共 15 页3（3）共用 4 种颜色.仿以上的分析可得：90.24 463 n（4）共用 3 种颜色，有：20.364 n综上，得总的染色方案有 230 种.【注注 2 2】加法原理和乘法原理始终是处理排列组合应用问题的化难为易、化繁为简的重要工具.通过上述的求解分析过程，我们还要掌握严密的逻辑推理方法，使得解答完整.2.1.32.1.3 配对原理配对原理 对于两个不具有同类元素的有限集合A和B，如果存在从集合A到B上的双射f，则集合A和集合B的元素个数相等，即这就是所谓的配对原理，有时也称作一一对.BA 应技术，它为我们提供了一种计算集
7、合A元素个数的有较强技巧性的常用方法.应用配对原理的关键在于构造出恰当的配对.它充分体现了问题转化的解题策略.下面就将通过具体的例子来介绍这种转化的典型技巧.【例题例题 3 3】求不定方程的非负整数解的个数.(此例题文3中也有rxxxn21介绍) 【分析分析】令 niyxyiii, 2 , 11, 1，则则 1 21nryyyn很明显，原方程的非负整数解救与方程1的正整数解一一对应，其解数也就是彼此相等.方程1的每一组正整数解可以直观的表示如下：取 n+r 个相同的小球排成一行，则相邻两球之间有一个空隙，共有 n+r-1 个空隙.任取 n-1 个空隙并在每个空隙出插入一个“隔板” ，那么，这
8、n-1 个“隔板”将 n+r 个小球分成 n 段因为有 n 个未知数，若自左至右各段中的小球的个数依次是则可以得到方程1的一组正整数解；, , , ,21nyyy反之，方程1的任意一组正整数解则显然对应一种插板方式.于是方程, , , ,21nyyy1的正整数解个数与在 n+r-1 个空隙中插入 n-1 个“隔板”的方式一一对应.后者共有种方法.因此，原方程的非负整数解的个数是，它也是方 rrnnrn11 1 1 1nrn组合数学方法在数学竞赛题中的应用彭伟坚第 页 , 共 15 页4程1的正整数解的个数.【注注 3 3】如:求由 1，2，3，n这n个数组成的允许重复的r个数的数组数.这个问题
9、可以转化为以上的例题.设想有n种颜色的小球，让你随便从中拿r个，则每种拿法可以得到一种组合.设第k种颜色的球拿个k=1，2，n，则全部组合kx数与不定方程的非负整数解是一一对应的，这个组合数是.rxxxn21 1 1nrn2.1.42.1.4 抽屉原理抽屉原理 它的内容可以用形象的语言表述为： “把 m 个东西任意分放进个空抽屉里，那么一定有一个抽屉中放进了至少nnm 2 个东西.”抽屉原理的一种更一般的表述为： “把多于个东西任意分放进个空抽屉（是正整数） ，那么一定有一个抽屉中放knnk进了至少+1 个东西.”k如果问题所讨论的对象有无限多个，抽屉原理还有另一种表述： “把无限多个东西任意
10、分放进个空抽屉（是自然数） ，那么一定有一个抽屉中放nn进了无限多个东西.” 抽屉原理的内容简明朴素，易于接受，它在数学问题中有重要的作用.许多有关存在性的证明都可用它来解决. 【例题例题 4 4】1958 年 7 月 6 号的美国数学月刊“证明在任意 6 个人的集会上，或者有 3 个人以前彼此相识，或者有三个人以前彼此不相识.”【分析分析】这个问题可以用如下方法简单明了地证出： 在平面上用 6 个点A、B、C、D、E、F分别代表参加集会的任意 6 个人.如果两人以前彼此认识，那么就在代表他们的两点间连成一条红线；否则连一条蓝线.考虑A点与其余各点间的 5 条连线AB，AC，.，AF，它们的颜
11、色不超过 2 种.根据抽屉原理可知其中至少有 3 条连线同色，不妨设AB，AC，AD同为红色.如果BC，BD ，CD 3 条连线中有一条不妨设为BC也为红色，那么三角形ABC即一个红色三角形，A、B、C代表的 3 个人以前彼此相识：如果BC、BD、CD 3 条连线全为蓝色，那么三角形BCD即一个蓝色三角形，B、C、D代表的 3 个人以前彼此不相识.不论哪种情形发生，都符合问题的结论. 【注注 4 4】最原始的抽屉原理即把多于个苹果放到个抽屉中，无论怎样放，一定能找nn组合数学方法在数学竞赛题中的应用彭伟坚第 页 , 共 15 页5到一个抽屉，它里面至少有两个苹果.广义的抽屉原则是把多于个苹果放
12、到个抽屉nmn中，无论怎样放，一定能找到一个抽屉，它里面至少有个苹果.一些比较基础的抽1m屉原理问题， “抽屉”比较明显，无论计算还是证明都比较容易.但有一些题是需要自己构造“抽屉”的问题，难度相对较大，需要结合其它方面的知识.六人集会问题是组合数学中著名的拉姆塞定理的一个最简单的特例，这个简单问题的证明思想可用来得出另外一些深入的结论.这些结论构成了组合数学中的重要内容-拉姆塞理论.从六人集会问题的证明中，我们又一次看到了抽屉原理的应用.2.22.2 建立递推关系解数学竞赛题建立递推关系解数学竞赛题 设是一数列，通项与其前面若干项的关系式通常称为关于该数列通项的一个递 nana推关系.许多组
13、合计数问题都归结为求某个数列的通项公式.直接去求数列的通项公式往往比较困难，此时我们可考虑去求关于该数列通项的递推关系，然后去解这个递推关系.如果能顺利完成这两个步骤，则问题就得到了解决.建立递推关系进而解递推关系是解决组合计数问题的一种常用而重要的方法.【例题例题 5 5】 （匈牙利，1974）证明：若 n 为非负整数，则能被 197412121329646nn整除.【分析分析】令，且，.12121329646nn na21164621x1691322x则.nnnn nxxa2112123848461329646因为，是方程的两个根.21161x1692x035760422852xx从而，.
14、357604228522 1xx357604228522 2xx. nnnnnnnnnn naaxxxxxxxxxxa3576042285 )384846(357604)384846(2285 )3576042285(3848)3576042285(46 3848461211 21 122112 22 12 因为)0( n又因为，2197438943848460a都是 1974 的倍数.3841974747648132964633 1a组合数学方法在数学竞赛题中的应用彭伟坚第 页 , 共 15 页6则由可知能被 1974 整除.nnnaaa357604228512na【注注 5 5】这题的解答过程中介绍了如何构造递推关系的一般方法，其他类似这样的题同样可以用这种方法来找递推关系.2.32.3 应用生成函数方法解数学竞赛题应用生成函数方法解数学竞赛题 生成函数是一种非常有用的方法，其应用很广，特别是对组合问题的求解有一个比较统一的处理方法.这个方法的系统叙述，最早见于 Laplace 在 1812 年出版的名著概率解析理论中.这种方法的思想是把离散数列和幂级数一一对应起来，把离散数列间的相互结合关系对应成为幂级数间的运算关系，最后由幂级数形式来确定离散数列的构造.简单的说，生成函数方法是把一个有限或无限的数列,210kaaaa和如下形式的多项式
