1、目 录1.引言 .12 组合数学与数学竞赛简介. .12.1 组合数学 .12.2 数学竞赛 .13 组合数学的几种方法在数学竞赛中的应用 .23.1 抽屉原理 .23.2 容斥原理 .23.3 排列组合 .84.探索高中数学竞赛中的组合问题 .104.1 熟练掌握四个基本的技术原理 .104.2 学习组合数学的几点建议 .104.3 培养学生的组合性思维和组合思想 .114.4 常见排列组合的解题策略 .11参考文献 .12致 谢 .12组合数学在数学竞赛中的应用Combinatorial Mathematics in Applied Mathematics (0521110329 Clas
2、s 2 Grade 2005 Mathematics combination; drawer principle; Exclusion principle1. 引言组合数学是可以追溯到公元前 2200 既古老而又年轻的数学分支, 它的源泉可以追溯到公元前 2200 年的大禹时期，中外历史上许多著名的数字游戏是它古典部分的主要内容. 公元 1666 年，德国著名数学家莱布尼茨为它请名为“组合学”(Combinatorics),并预言了这一数学分支的诞生. 随着科学技术的发展，组合数学这门历史悠久的学科得到了迅速发展数学活动离不开解题，掌握数学的一个重要标志就是善于解题现在专门以中学生为对象的数学
3、竞赛成为时代的时尚，本论文希望结合组合数学和数学竞赛有关理论知识，针对在数学竞赛中占很大比例的组合问题，利用大学组合数学理论给出解释，并结合初等数学向学生渗透和合理讲解在此过程中，提出自己直接的见解和总结2.组合数学与数学竞赛简介2.1 组合数学组合数学历史悠久，几千年前，我国的河图 、 洛书就已涉及一些简单有趣的组合问题组合问题在日常生活中也随处可见例如，在玩扑克牌游戏中计算“同花顺”的概率、一笔画和幻方等都是组合数学问题组合数学自 20 世纪 60 年代急速发展的部分原因在于计算机在我们的生活中所发挥的重要影响，而且这种影响还在继续发挥由于远算速度的持续增加，计算机已经能够解决大型问题，这
4、在以前是不可能做到的近年来，由于计算机科学、编码理论、规划论、数字通讯、试验设计、社会科学、生物科学等学科的迅猛发展，大大促进了组合数学的研究，使这一古老的数学分支成为了一门充满活力的数学学科组合数学可以一般地描述为：组合数学是研究离散结构的存在、计数、分析和优化等问题的一门学科现代的组合数学几乎是与图论不可分割的图论是数学的一个分支，它以图为研究对象，研究顶点和边组成的图形的数学理论和方法有关图论的第一篇文章是由著名瑞士学家欧拉写于 1736 年，他探讨的是著名的哥尼斯堡七桥问题，图论在智力难题和游戏方面有着历史根源，而今天它为许多学科的研究提供了一种非常重要的语言和框架2.2 数学竞赛围绕
5、着数学竞赛而开展的各种活动已经搭起了一个数学教育新分支的框架，其特点是以开发智力为根本目的、以问题解决为基本形式、以竞赛数学为主要内容最本质的是对中学生进行“竞赛数学”的教育，这种教育的性质是：较高层次的基础教育、开发智力的素质教育、生动活泼的业余教育、现代教学的普及教育竞赛数学是一中“中间数学” ，介乎于中小学与大学数学之间；竞赛数学是一种“前沿数学” ，追求内容的新颖性，不断推陈出新，时刻涌现出新问题新方法和新结果；竞赛数学是一种“艺术数学” ，它把现代化的内容与趣味性的问题有机结合，把普遍性的问题与独创性的技巧有机结合，展示出数学美的魅力；竞赛数学是一种“教育数学” ，它称为教育数学中最
6、接近研究数学的“先头部队” ，利用自己所处的地位，大量地、方便地吸收着前沿成果初等化，也把古典问题高等化3. 组合数学的几种方法在数学竞赛中的应用3.1 抽屉原理抽屉原理又称鸽巢原理或重叠原理，是组合数学的两大基本原理之一，是一个极其初等而又应用较广的数学原理抽屉原理要解决的是存在性问题，即在具体的组合问题中，要解决某些特定问题求解的方案数，其前提就是要知道这些方案的存在性定理 3.1.1（基本形式）将 1n个物品放入 n个抽屉，则至少有一个抽屉中的物品数不少于两个证 反证之 将抽屉编号为： ,2.，设第 i个抽屉放有 iq个物品，则 12.nq但若定理结论不成立，即 1i，亦有 12.nq，
7、从而有 12.nq矛盾定理 3.1.2（推广形式）将 12.nq个物品放入 n个抽屉，则下列事件至少有一个成立：即第 i个抽屉的物品数不少于 iq个， ,.证 反证不然，设第 个抽屉的物品数小于 (12)i（即该抽屉最多有 1iq个物品） ，则有 1niq物品总数 11nnii与假设矛盾根据定理的结果，不难得出下述结论推论 3.1.1 将 (1)nr个物品放入 n个抽屉，则至少有一个抽屉中的物品个数不少于 r个推论 3.1.2 将 m个物品放入 个抽屉，则至少有一个抽屉中的物品个数不少于1n个其中 x表示取正数 x的整数部分， x表示不小于 x的最小整数推论 3.1.3 若 个正整数 (1,2
8、.)iqn满足 2.1nqr则至少有一个 i，满足 ir利用抽屉原理可以得到下面两个性质：性质 1 任意三个整数中，必有两个整数的和是 2 的倍数性质 2 任意五个整数中，必有三个整数的和是 3 的倍数例 1 任意 15 个整数中，必有 8 个整数的和是 8 的倍数证 5个整数是任意的，所以我们用 123145,.,aa这 15 个字母来表示，有性质 1，123,a中 12a（a 为整数） ，同理可得， 6中有 452ab（b 为整数） ，789中 78c（c 为整数） ， 102,中 10d（d 为整数） 。有性质 1 得bm（m 为整数） dn（n 为整数） ， 3,mn中 e（e 为整数
9、）128.()4()8be证毕例 2 任意三个整数，必有两个之和为偶数（其差也为偶数） 证 制造两个抽屉：“奇数”和“偶数” ，3 个数放入两个抽屉，必有一个抽屉中至少有两个数有整数求和的奇、偶性质，即知此二数之和比为偶数同理可知，二者之差也为偶数例 3 某俱乐部有 31n名成员对每一个人，其余的人中恰好有 n个愿与他打网球，n个愿与他下象棋， 个愿与他打乒乓球证明该俱乐部至少有 3 个人，他们之间玩的游戏三种俱全证 将每个人作为平面上的一个点，且任何三点不共线由每一点引出 条红边、 n条蓝边、 条黑边，分别代表打网球、下象棋及打乒乓球问题等价于要证明图中至少有一个三边颜色全部相同的三角形考虑
10、有这个 31n点的所有连边构成的异色角（即两条异色的边所构成的角）的总数每个顶点处有 2个异色角，所以 23(1)Ln平均每个三角形有231()62nC个异色角因此，至少有一个三角形有 3 个异色角，那么，这个三角形的三条边当然互不同色证毕例 4 设 ABC为一等边三角形， E是三边上点的全体对于每一个把 E分成两个不交子集的划分，问这两个子集中是否至少有一个子集包含着一个直角三角形的三个顶点证 如下图，在边 AB上分别取三点P、Q、R，显然ARQ，BPR，CQP 都是直角三角形它们的锐角是 30及 60设 E1，E 2是 E 的两个非空子集，且 1212,EE由抽屉原则 P、Q、R 中至少有
11、两点属于同一子集，不妨设 P、QE 1如果 BC 边上除 P之外还有属于 E1的点，那么结论已证明设 BC 的点除 P 之外全属于 E2，那么只要 AB 上有异于 B 的点 S 属于 E2，设 S 在 BC 上的投影点为 S，则SSB 为直角三角形再设 AB 内的每一点均不属于 E2，即除 B 之外全属于 E1，特别，R、AE 1，于是 A、Q、RE 1，且 AQR 为一直角三角形， 从而命题得证【评述】此例通过分割图形构造抽屉在一个几何图形内有若干已知点，我们可以根据问题的要求把图形进行适当的分割，用这些分割成的图形作为抽屉，再对已知点进行分类，集中对某一个或几个抽屉进行讨论，使问题得到解决
12、例 5：在 1,470,31 中任选出 20 个数，其中至少有不同的两组数，和都等于104，试证明之 （第 39 届美国普特南数学竞赛题）证 给定的数共有 34 个，其相邻两数的差均为 3，我们把这些数分成如下 18 个不相交的集合1,524,07,94,5且把它们分作是 18 个抽屉，从已知的 34 个数中任取 20 个数，即把前面两个抽屉中的数 1 和 52 都取出，则剩下的 18 个数在后面的 16 个抽屉中至少有不同的两个抽屉中的数全被取出，这两个抽屉中的数互不相同，每个抽屉中的两个数的和都是 104【评述】此例是根据某两个数的和为 104 来构造抽屉一般地，与整数集有关的存在性问题也
13、可根据不同的需要利用整数间的倍数关系、同余关系来适当分组而构成抽屉小结： 用抽屉原则解题的本质是把所要讨论的问题利用抽屉原则缩小范围，使之在一个特定的小范围内考虑问题，从而使问题变得简单明确用抽屉原则解题的基本思想是根据问题的自身特点和本质，弄清对哪些元素进行分类，找出分类的规律用抽屉原则解题的基本思想是根据问题的自身特点和本质，找出分类的规律用抽屉原则解题的关键是利用题目中的条件构造出与题设相关的“抽屉” 3.2 容斥原理 当我们试图对某些对象的数目从整体上计数碰到困难时，考虑将整体分解为部分，通过对每个部分的计数来实现对整体的计数是一种明智的选择将整体分解为部分也就是将有限集 X 表示成它
14、的一组两两互异的非空真子集 A1，A 2，A n的并集，即,.2121 nnAA 集 合叫做集合 X 的一个覆盖。一个特殊情况是，集族 中的任意两个集合都不相交，这时我们称集族 为集合 X 的一个（完全）划分如 为集合 X 的划分，则对集合 X 的计数可通过熟知的加法公式| 321 n进行，但是，要找到一个划分并且其中所有子集易于计数的有时并非易事我们可以考虑通过对任意的集族中的子集的计数来计算|X|，当集族 中至少存在两个集合的交非空时，我们称这个覆盖为集合 X 的不完全划分对于集合 X 的不完全划分，显然有有 |21nAAX因为在计算| Ai|时出现了对某些元素的重复计数，为了计算|X|，
15、就得将式右边重复计算的部分减去，如果减得超出了，还得再加上，也就是说我们要做“多退少补”的工作完成这项工作的准则就是容斥原理， 是十九世纪英国数学家西尔维斯提出的容斥原理有两个公式1、容斥公式定理 1 设 则为 有 限 集 ,),2(niA i nji injiini AA1 11 |)(| 证明：当 ,/,/, 212 BB设时 由加法公式有| |)()(| |,|,21212121 2AABB结论成立若 n=k 时结论成立，则由 ki kji kiikjii iikiki kiiki AAAA1 111111 |)(| |(| |)| ki kikikjik1 111 |)(|()(| 1
16、1 1|)|i kji ikjii AAA知，kn时结论成立由归纳原理知，对任意自然数 n，公式成立公式称为容斥公式，显然它是公式的推广如果将 iA看成具有性质 iP的元素的集合，那么 nAX21就是至少具有n 个性质 nP,21 之一的元素的集合 因此，容斥公式常用来计算至少具有某几个性质之一的元素的数目容斥原理用法总结：在应用容斥原理求解计数问题时，可按下列步骤进行：（1）根据问题的实际情况，构造一个有限集 12,.tSe和一个性质集2,.nPp， iA是 S中具有性质 P的所有元素的子集，问题的关键是构造的性质集 ，要使得 12|.|k容易计算出来 (,.)|kn（2）当统计 中恰好具有
17、 种特征的元素的个数时，将问题转化为求 S中恰好具有种 k个性质的元素个数 (1,2.)N，可利用逐步淘汰原理或一般公式（3）当统计 S中至少有 中一种性质的元素个数 1L时，利用容斥原理，或由1|0L求得（4）注意 |.n，故可由此求得 S中至少具有 k种特征的元素个数k如 2时，有|1SN2筛法公式与容斥公式讨论的计数问题相反，有时需要计算不具有某几个性质中的任何一个性质的元素的个数，为此，我们先引入下面的引理引理 1 设 A 关于全集 I 的补集为 A，则.|I每个元素引理 2 ,1ini,1ini引理简单证略利用二引理改写公式便是定理 2 设 ),2(niA 为有限集 I 的子集，则
18、| 111 inininAIAni nji injii AI11 |)(| 3.错排问题利用容斥原理可以轻而易举地得出同一个公式 个元素依次给以标号 1,2n , 个元素的全排列中，求每个元素都不在原来自己位置上的排列数设 iA为数 在第 i位上的全体排列， 1,2in 因数字 i不动,故|(1)!,2,inn同理 |()!,ijAjj 每个元素都不在原来位置上的排列数为12| ()!(,2)!(,)1!()!nCnCn 例 1 数 ,239 的全排列中，求偶数在原来位置上，其余都不在原来位置上的错排列数目，实际上是 1,57五个数的错排问题，总数为!()4!(,2)3!(5,)!(,4)1!
19、(5,)20606CCC例 2 某校六年级二班有 49 人参加了数学、英语、语文学习小组，其中数学有 30 人参加，英语有 20 人参加，语文小组有 10 人老师告诉同学既参加数学小组又参加语文小组的有 3 人，既参加数学又参加英语和既参加英语又参加语文的人数均为质数，而三种全参加的只有 1 人，求既参加英语又参加数学小组的人数分析与解：根据已知条件画出图三圆盖住的总体为 49 人，假设既参加数学又参加英语的有 x 人，既参加语文又参加英语的有 y 人，可以列出这样的方程：整理后得：由于 x、y 均为质数，因而这两个质数中必有一个偶质数 2，另一个质数为 7例 3 求 1 到 100 的自然数
20、中，所有既不是 2 的倍数又不是 3 的倍数的整数之和 S解：1 到 100 的自然数中，所有自然数的和是： 1+.0=51 到 100 的自然数中，所有 2 的倍数的自然数和是：*1+.*50=(23&5) 2*71 到 100 的自然数中，所有 3 的倍数的自然数和是：.1+.= 61831 到 100 的自然数中，所有既是 2 的倍数又是 3 的倍数，即是 6 的倍数的自然数和是：6*1+.6*=(.) *所以，1 到 100 的自然数中，所有既不是 2 的倍数又不是 3 的倍数的整数之和S50-18+=3.3 排列组合定义一（排列 Permutation）设 m元集 12,.mAa，从
21、 A中取出 n个不同元素按次序排列，称为 A的一个 n排列，其个数称为 n排列数，记作 (,)Pm或 n当nm时 的 排列又称为 的全排列，其个数 (,)又称全排列数命题 1 101(,)()()nnkkP证明 A的一个 排列由 个不同的元素组成，其中第一位有 m种可能第二位有 m种可能； 第 n位有 (1)种可能。由乘法原理,元集 的不同排列数为 101(,)()2.)nnkkPm推论 (,)!Pm例 1 从 ,Aabc 中任取两个不同的字母构成的字共有 326 个罗列如下：,abc定义 2 （组合 Combination）设 m元集 12,.mAa，从 A中取出 n个不同元素构成一组，称为
22、 A的一个 n组合，其个数称为 n组合数，记作 (,)C，或 m命题 2 有 m个不同的元素共可构成 (,)/!P种组合，即 ,(,)/!P证明 由定义 n组合与 排列的区别在于前者不计较元素的先后顺序，因此由每个 n组合可以作出 !个不同的 排列于是若有 (,)Cmn种 组合，则有 (,)*!Cmn种排列，因此 (,)(,)/!CmP推论 1 任意 个相继的正整数之积可被 !整除形成多少条，即有 1!()k推论 2 !(,)()n推论 3 ,Cm推论 4 元集 A的 元子集的个数等于 (,)Cmn推论 5 设 元集 12,.ma，其字典序如下标所示，则从 A中每次取出满足条件 12.niii
23、a的 个元的方式数等于 (,)证明 的任一组合都可调整为 12,.niia并使其满足 12.niiiaa；另一方面，任一满足条件 12.niiia的 个元都是 A的一个 组合例 2 平面上任三点都不共线的 25 个点，可形成多少条直线？可形成多少个三角形？解 25 点中任取 2 点即可惟一确定一条直线，故可形成 (25,)!/(,23)0C条直线；同理，任取 3 点即可惟一确定一个三角形，故三角形的数目等于(5,3)!/(,)0C例 3 把 n个有标号的珠子排成一个圆圈，共有多少种不同的排法？解 这是典型的圆排列问题对于围成圆圈的 n个元素，同时按同一方向旋转，即每个元素都向左（或向右）转动一个位置，虽然元素的绝对位置发生了变化但相对位置未变，即元素之间的相邻关系未变，这样的圆排列认为是同一种，否则便是不同的圆排列下面从两种角度推导圆排列数的计算公式方法一：先令 n个相异元素任意排成一行（称为线排列） ，共有种 n!排法，再将其首位相接围成一个圆，当圆转动一个角度时，对应另一个线排列，当每个元素又转回到原先的位置时，相当于 个不同的线排列，故圆排列数为 p(n,)CP,=1!.方法二：先取出某一元素 k，放于圆上某确定位置，再另余下的 1n个元素作为一个线排列，首尾置于 的两侧构成一个圆排列同样可得到 CP(,)=-!.
