数学竞赛讲义组合计数

1、数学竞赛讲义第一讲 组合计数本讲概述组合数学是竞赛中最重要的一个板块，也是变化最多，最灵活，难以掌握，至今还没有一个系统体系的学科.解决竞赛中的组合数学问题，往往不需要太多专门的知识，而是要求深刻的洞察能力和强大的化归、转化能力.所谓“得组合者得天下”，在联赛一二试乃至冬令营、集训队、IMO中，最后的胜者往往是成功完成组合问题的同学.因此，学习组合数学对于竞赛获奖以及数学能力的培养都有着十分重要的意义.从本讲开始，我们将用七讲来对组合数学做一个大致的勾勒.通过这七讲的学习，达到以下目的：1、掌握联赛一二试组合问题的特点与解法；2、对组合数学这门学科有一个初步的认识，为进一步学习打下基础；3、了

2、解部分冬令营级别组合问题的难度与解题模式.七讲内容分别为：一、组合计数（1） 比高考略难的基本计数问题 二、组合计数（2） 需要较多技巧的专门计数问题 三、组合恒等式 较为重要和有趣味的组合恒等式 四、抽屉原理与存在性问题 五、容斥原理与极端性原理六、染色问题与操作问题七、组合数学综合问题本讲中，假定各位同学已经大致学完了高考难度的排列组合模块内容，对加法原理、乘法原理等有一定的理解并能完成相关的问题.教师备注：本讲可与下一讲打通讲述，也可本讲专门讲常规的枚举、基本的组合问题，下一讲专门讲述一些较为高级的技巧.首先给出一些相关的基本知识：1、 加法原理与乘法原理加法原理：完成一件事的方法可分成

3、n个互不相交的类，在第1类到第n类分别有种方法，则总共完成这件事有种方法.应用加法原理的关键在于通过适当的分类，使得每一类都相对易于计数.乘法原理：完成一件事的方法有n个步骤，在第1步到第n步分别有种方法，则总共完成这件事有种方法. 应用乘法原理的关键在于通过适当的分步，使得每一步都相对易于计数.由上可见，加法原理与乘法原理也是化归思想的应用，通过这两个原理以及它们的组合，可以将一个复杂的组合计数问题分解成若干个便于计数的小问题.2、 无重排列与组合阶乘：定义 ，读作n的阶乘无重排列：从n个不同元素中任取m个不同元素排成一列，不同的排列种数称为排列数，记为（部分书中记为），由乘法原理得到 无重

4、组合：从n个不同元素中任取m个元素并为一组，不同的组合种数称为组合数，记为，其公式为3、 可重排列与组合（仅给出结论，请自证之）可重排列：从n个不同元素中可重复地任取m个元素排成一列，不同的排列种数有种；有限个重复元素的全排列：设n个元素由k个不同元素组成，分别有个（），那么这n个元素的全排列数为可重组合：从n个不同元素中，任意可重复地选取m个元素，称为n个不同元素中取m个元素的可重组合，其种数为4、 圆排列（仅给出结论，请自证之）在个不同元素中，每次取出m个元素排在一个圆环上，叫做一个圆排列（或叫环状排列）圆排列有三个特点：（i）无头无尾；（ii）按照同一方向转换后仍是同一排列；（iii）两

5、个圆排列只有在元素不同或者元素虽然相同，但元素之间的顺序不同，才是不同的圆排列在的个元素中，每次取出m个不同的元素进行圆排列，圆排列数为例题精讲 板块一 利用加法、乘法原理以及枚举方法计数联赛一试的填空题中出现的计数问题有接近一半的问题不需要用到很高深的技巧，而是直接利用最基本的加法、乘法原理，以及枚举方法来计数.这主要是考虑到有一部分参加联赛的同学并未经过专业的竞赛训练.虽然如此，这部分计数问题枚举起来往往分类复杂，需要小心仔细.从往年的联赛试题来看，枚举法解决计数问题是最主要的题型之一，其难点在于做到“不重不漏”，这是加法原理的一个简单的应用.枚举过程中，采用恰当的分类、分步形式，往往会收

6、到化难为易的效果.【例1】 (高考难度的热身问题)（1）等腰三角形的三边均为正整数它们周长不大于10这样不同的三角形的种数为A8 B9 C10 D1l （2）有两排座位，前排11个座位，后排12个座位，现安排2人就座，规定前排中间的3个座位不能坐，并且这2人不左右相邻，那么不同排法的种数是 A.234 B346 C. 350 D363【解析】 （1）设三边为x,y，z，则x+y+z10，由三边关系共有(1，1，1)，(1，2，2)，(1，3，3)，(1，4，4)，(2，2，2)，(2，2，3)，(2，3，3)，(2，4，4)，(3，3，3)，(3，3，4)共10种（2）B 前排中间的3个座位不

7、能坐，有排法，其中相邻的分三类，在前排的其中的4个座位有3；则符合条件的排法种数中=346，故选B （这是正难则反的思想，从总体中除去不符合要求的）另解：分三类：两人坐在前排，按要求有46+45=44种坐法两人坐在后排，按要求有：=110种坐法两人分别坐在前后排，有8122=192种共有346种排法【例2】 （1）有多少个能被3整除而又含有数字6的五位数？（2）集合的子集中共有多少个至少包含一个奇数？【解析】 （1）按照上题正难则反的思想，可以先找出所有的五位数，共有90000个，其中可被3整除的有30000个，下面研究这30000个数中不含数字6的数，最高位有8种选择，千、百、十位各有9种选

8、择，个位数除不能为6外，还应满足恰各位数之和可被3整除，这恰有3种选择，例如当前四位除以3余2时，个位应为1,4,7之一；故能被3整除且不含数字6的有个，故所求五位数有30000-17496=12504个（2）显然全部子集数为个，不包含任何奇数的子集即的子集共有个，故所求子集个数为个.(思考：请用最简洁的方法确定为何n元集合子集数为个)【例3】 设ABCDEF为正六边形，一只青蛙开始在顶点A处，它每次可随意地跳到相邻两顶点之一若在5次之内跳到D点，则停止跳动；若5次之内不能到达D点，则跳完5次也停止跳动，那么这只青蛙从开始到停止，可能出现的不同跳法共 种【解析】 这是标准的联赛风格的枚举问题，

9、所谓杀鸡焉用牛刀，用递归方法来解这类问题就太麻烦了.显然青蛙不能跳1，2,4次到达D点，于是青蛙的跳法只有以下两种：（1）青蛙跳3次后到达D点，有2种跳法；（2）青蛙跳5次后停止，跳3次有种，后两次有种，共计24种；所以，合计有26种跳法注 本题为1997年联赛试题【例4】 从给定的六种不同颜色中选用若干种颜色，将一个正方体的六个面染色，每面恰染一种颜色，每两个具有公共棱的面染成不同的颜色。则不同的染色方法共有 _ 种。（注：如果我们对两个相同的正方体染色后，可以通过适当的翻转，使得两个正方体的上、下、左、右、前、后六个对应面的染色都相同，那么，我们就说这两个正方体的染色方案相同。）【解析】

10、因为有公共顶点的三个面互不同色，故至少要用3种颜色，下面分四种情形来考虑.（1）6种颜色都用时，现将染某种固定颜色的面朝上，从剩下5种颜色中取一种颜色染下底面有种方法，余下4种颜色染四个侧面（应是4种颜色的圆排列）有3！种方法.所以不同的染色方案有种.（2）只用5种颜色时，从6种颜色中取5种颜色有种方法，这时必有一组对面同色.从5种颜色中取一种颜色染一组对面，并将它们朝上和朝下，有种方法，其余4种颜色染四个侧面（应是4种不同颜色的链排列）有3！种方法.所以不同的染色方案有种.（3）只用4种颜色时，从6种颜色中取4种颜色有种方法，这时必有两组对面同色，另一组对面不同色，将不同色的一组对面朝上和朝

11、下，并从4种颜色中取两种颜色染上、下底面，有种方法，其余两种颜色染四个侧面且使两组对面同色（应是两种不同颜色的链排列），只有1种方法.所以不同的染色方案有种.（4）只用3种颜色时，从6种颜色中取3种颜色有种方法，这时三组对面都同色，用三种颜色去染它们只有1种方法.所以不同的染色方案有种.综上可知，不同的染色方案共有30909020230种.注 本题为1996年联赛试题，是历年来一试计数问题中最复杂的一道，其背景与波利亚群论计数原理有关，这远远超出了高中范围，此处略去【例5】 将24个志愿者名额分配给3个学校，则每校至少有一个名额且各校名额互不相同的分配方法共有 222种【解析】 用4条棍子间的

12、空隙代表3个学校，而用表示名额如 表示第一、二、三个学校分别有4，18，2个名额若把每个“”与每个“”都视为一个位置，由于左右两端必须是“”，故不同的分配方法相当于个位置（两端不在内）被2个“”占领的一种“占位法”“每校至少有一个名额的分法”相当于在24个“”之间的23个空隙中选出2个空隙插入“”，故有种又在“每校至少有一个名额的分法”中“至少有两个学校的名额数相同”的分配方法有31种综上知，满足条件的分配方法共有25331222种解法二设分配给3个学校的名额数分别为，则每校至少有一个名额的分法数为不定方程的正整数解的个数，即方程的非负整数解的个数，它等于3个不同元素中取21个元素的可重组合：

13、又在“每校至少有一个名额的分法”中“至少有两个学校的名额数相同”的分配方法有31种综上知，满足条件的分配方法共有25331222种注 本题为2008年联赛试题，从近年来联赛一试组合问题来看，组合计数问题难度明显降低了.本题所应用的插空法是一种在高考和竞赛中常用的计数方法【例6】 将2个a和2个b共4个字母填在方格表内，每个小方格内至多填1个字母，若使相同字母既不同行也不同列，则不同的填法共有_种（用数字作答）。【解析】 使2个a既不同行也不同列的填法有C42A42=72种，同样，使2个b既不同行也不同列的填法也有C42A42=72种，故由乘法原理，这样的填法共有722种，其中不符合要求的有两种

14、情况：2个a所在的方格内都填有b的情况有72种；2个a所在的方格内仅有1个方格内填有b的情况有C161A92=1672种。所以，符合题设条件的填法共有722721672=3960种。注 本题为2007年联赛第12题【例7】 设三位数，若以a，b，c为三条边的长可以构成一个等腰（含等边）三角形，则这样的三位数n有（ ）A. 45个B. 81个C. 165个D. 216个【解析】 本题是标准的枚举问题，情况繁多.a，b，c要能构成三角形的边长，显然均不为0。即（1）若构成等边三角形，设这样的三位数的个数为，由于三位数中三个数码都相同，所以，。（2）若构成等腰（非等边）三角形，设这样的三位数的个数为

15、，由于三位数中只有2个不同数码。设为a、b，注意到三角形腰与底可以置换，所以可取的数码组（a，b）共有。但当大数为底时，设ab，必须满足。此时，不能构成三角形的数码是a987654321b4，32，14，32，13，213，211，21，211共20种情况。同时，每个数码组（a，b）中的二个数码填上三个数位，有种情况。故。综上，。注 本题为2004年联赛试题板块二 映射与对应方法由一一映射的定义可知，若存在从集合M到N的一一映射，则.于是在难以直接计算集合M中元素个数时，我们可以设法构造这样一个映射，将问题转化为计算较为容易计算的集合N的元素个数.基于这种两集合元素一一对应的特点，也称为“配对

16、法”【例8】 （1）试用对应方法证明可重组合公式：从n个不同元素中，任意可重复地选取m个元素，称为n个不同元素中取m个元素的可重组合，其种数为（2）证明：不定方程（k,n为正整数）的非负整数解组数为【解析】 （1）设n个元素为，并设取出的m个元素为，于是，作对应，易证明它为一一对应 后者为从个元素中取m个元素的组合数，故得证 （2）将n个圆圈与k-1个竖线排成一排，k-1个竖线将n个圆圈依次分成k个部分：，易见不同的排列对应不定方程不同的解，易证它为一个一一对应，而在n+k-1个元素中取出k-1个的全排列数为，故得证.【例9】 凸n边形的任意3条对角线不相交于形内一点，求其对角线在形内的交点总

17、个数.【解析】 任一形内交点对应两条对角线l,m; 反之，任意两条对角线唯一确定形内一个交点P,从而P与（l,m）构成一一对应；又任一对角线对应形内2顶点，n边形中任取4顶点即可唯一确定两对角线，于是有如下一一对应：点于是交点总个数=四顶点组个数=注 本题为组合数学一个重要分支组合几何中的非常重要的一个结论，可以利用它解决一些高难度的组合几何计数问题【例10】 将集合A中的n个元素排成一行，若某个子集中任意两元素不相邻，则称此子集为不好的，试证明：k元的不好的子集个数为【解析】 设n个元素排成一行依次为为，并设取出的k个元素为，显然有；作变换 ，并取序列：，它是1,2，n-k+1中的一个严格上

18、升的序列作对应，易证明它为一一对应，且后者的种数为从个元素中取k个元素的组合数，故得证注 本题为第16届普特南竞赛题大显身手1 （1）在100件产品中有6件次品，现从中任取3件产品，至少有1件次品的不同取法的种数是 A B C. D （2）从4名男生和3名女生中选出4人参加某个座谈会，若这4人中必须既有男生又有女生，则不同的选法共有 A.140种 B120种 C 35种 D34种【解析】 （1） C 任取3件产品有种方法，其中无次品有种方法，故至少有1件次品的方法数为（2）D 既有女生又有男生，可以分类表示，三男一女有种选法，二男二女有种，一男三女有种选法，则总的不同的选法有=34(种) 2

19、由三个数字 、 组成的 位数中, 、 都至少出现 次, 这样的 位数共有多少个？【解析】 在 位数中, 若 只出现 次，有 个；若 只出现 次，有 个； 若 只出现 次，有 个 则这样的五位数共有 个 故填 个注 本题为05年江苏省预赛试题3 已知集合，,，且，则整数对的个数为 A. 20 B. 25 C. 30 D. 42 【答】 （ ）【解析】 由；。要使，则，即。所以数对共有。注 本题为2006年联赛试题4 记集合，将M中的元素按从大到小顺序排列，则第2005个数是A. B. C. D. 【解析】 用表示k位p进制数，将集合M中的每个数乘以，得中的最大数为。在十进制数中，从2400起从大

20、到小顺序排列的第2005个数是2400-2004=396;而, 将此数除以，便得到M中的数：故选C。注 本题为2005年联赛试题，题目形式提示我们，要采用进制转换.事实上，这类题目在小学和初中是极为常见的.5 已知两个实数集合A=a1,a2,a100与B=b1,b2,b50，若从A到B的映射f使得B中每个元素都有原象，且 f(a1)f(a2)f(a100)则这样的映射共有(A) (B) (C) (D) 【解析】 不妨设b1b2b50，将A中元素a1, a2, , a100按顺序分为非空的50组，定义映射f：AB，使得第i组的元素在f之下的象都是bi (i=1,2,50)，易知这样的f满足题设要

21、求，每个这样的分组都一一对应满足条件的映射，于是满足题设要求的映射f的个数与A按足码顺序分为50组的分法数相等，而A的分法数为，则这样的映射共有，故选D。注 本题为2002年全国联赛试题6 在世界杯足球赛前，F国教练为了考察A1,A2,A7这七名，准备让他们在三场训练比赛(每场90分钟)都上场，假设在比赛的任何时刻，这些中有且仅有一人在场上，并且A1,A2,A3,A4每人上场的总时间(以分钟为单位)均被13整除，如果每场换人次数不限，那么按每名队员上场的总时间计算，共有多少种不同的情况。【解析】 设第i名队员上场的时间为xi分钟(i=1,2,3,7)，问题即求不定方程 x1+x2+x7=270

22、 在条件7|xi (1i4)且13|xj (5j7)下的正整数解的级数。 若(x1,x2,x7)是满足条件的一组正整数解，则应有 =7m =13n m,nN m,n是不定方程 7m+13n=270 在条件m4且n3下的一组正整数解。 10分 7(m-4)+13(n-3)=203 令 m=m -4 n=n -3 有 7m+13n=270 求满足条件m4且n3的正整数解等价于求的非负整数解。 易观察到 72+13(-1)=1 7406+13(-203)=203 即 m0=406 n0= -203是的整数解 的整数通解为 m=406 -13k n= -203+7k kZ 令 m0 n0,解得 29k

23、31 20分 取k=29,30,31得到满足条件的三组非负整数解： 从而得到满足条件的三组正整数解： 30分 1)在m=33,n=3时，显然x5=x6=x7=13仅有一种可能， 又设xi=7yi (i=1,2,3,4)，于是由不定方程y1+y2+y3+y4=33有组正整数解。 此时有满足条件的=4960组正整数解。 2)在m=20,n=10时，设xi=7yi (i=1,2,3,4)，xj=13yj (j=5,6,7) 由y1+y2+y3+y4=20，有组正整数解；以及y5+y6+y7=10，有组正整数解。 此时有满足条件的=34884组正整数解。 3) 在m=7,n=17时，设xi=7yi (

24、i=1,2,3,4)，xj=13yj (j=5,6,7) 由y1+y2+y3+y4=7，有组正整数解；以及y5+y6+y7=17，有组正整数解。40分 综上所述，满足条件的正整数解的组数为 =4960+34884+2400=42244 50分注 本题为2002年联赛二试最后一题，是一道不是很难的组合数论问题.问题求解过程中多次用到了我们的例8的结论.(2)本讲概述组合计数的方法很多，除了上一讲的枚举、对应方法之外还包括：算两次、递推方法、容斥原理、利用恒等式、母函数方法等；容斥原理的方法将在第四讲讲述，递推方法我们在数列部分单独讲述.本讲主要讨论利用算两次方法计数的问题以及较为简单的递推方法（

25、因为我们暂不具备完善的递推数列知识）；另外，本讲还将涉及到组合计数的二试与冬令营级别难度的少数问题.首先给出本讲问题中要用到的知识（虽然这些知识可能暂时没有学到，但本讲只需会用即可）：二项式定理：，特别地，其中特征方程与数列通项：记一列数为数列，如果它满足，那么称为此数列的特征方程，（1）当有两互异实根时，数列通项为； （2）当有二等根时，数列通项为其中为根据初值确定的待定系数例题精讲 板块一 算两次算两次是一种非常重要的思想方法，在代数、组合、几何中都有涉及.组合问题中，组合极值、组合不等式也常常涉及到算两次.组合计数中，在直接计算非常复杂甚至无从入手时，我们常常利用算两次方法.顾名思义，算

26、两次是指用不同的方法或者从不同的角度对同一个量进行计算，当两次都得到精确值时，我们就得到一个等式，当为估计式时，我们就得到一个不等式.事实上，数学中有相当大一部分定理就是利用算两次思想对原有的问题进行剖析，得到新的内在关系式.【例11】 设为1，2，n的一个排列，是集合元素的个数，而是集合元素的个数（），证明【解析】 考虑集合的元素个数。一方面，固定先对求和，然后再对求和，得；另一方面，固定先对求和，然后再对求和，又得到，所以得。注 本题只是为了说明算两次的基本思想和方法，这里的计数是抽象的，这种方法相当于考虑各个分量对总体的“贡献”，因此也有人把它叫做“贡献法”.请参考习题第一题【例12】

27、有n粒小球，任意将其分成两堆，求出两堆球数之积，再将其中一堆任意地分成两堆，求出此两堆之积，如此下去，直至将小球分成n堆（每个球1堆）为止.记此过程中所有的乘积之和为S，求S的所有可能值.【解析】 以n=8为例，不论如何分，最后总得到，于是猜想对一般情形总有，即n粒小球中任取两个组成小球对的个数；另一方面，每将一些小球分成两堆，就将原来的一些小球对（假设只有同一堆才能组成小球对）拆开，拆开的数目恰为两堆个数之积，最终的小球对个数为0，从而乘积之和即为最初的小球对个数，故得证.注 本题构造了一种巧妙的对应，使原来无法下手的问题变得有章可循.事实上，组合问题，特别是算两次问题最关键的就是寻找算两次

28、的对象，本题中就是对小球对进行算两次，使得问题清晰明了.【例13】 一张正方形纸片内有1000个点，这些点及正方形的顶点中任意3点不共线.在这些点及正方形的顶点间连一些线段将正方形全部分成小三角形（它们都以所连线段及正方形的边为边，且所连线段除端点外两两无公共点）.问一共连有多少条线段，一共得到多少个三角形？【解析】 设一共连有条线段，得到k个三角形.首先对角度和进行计数： 一方面，所得k个三角形的内角和为；另一方面，计算1000个内点及4个正方形顶点处内角和为，从而算得k=2002;其次，对边数进行计数： k个三角形共3k条边，另一方面，每条线段是两个三角形的公共边，正方形的每条边被计算1次

29、，共条边，从而，得到注 本题的背景是计算机图形学中著名的三角面片分划问题，这类问题在冯康先生的有限元中也有应用. 从本题及习题2可以得到计算这类问题的一般方法，即对边、角乃至同色角、异色角等元素进行计数.【例14】 （选讲）能否把1,1,2,2,3,3，1986,1986这些数排成一行，使得两个1之间夹着1个数，两个2之间夹着2个数，两个1986之间夹着1986个数？【解析】 设能将上述数字排成一行满足题设，这是每一个数可赋予它一对有序实数作为坐标，这里坐标值分别为它第一次与第二次出现的位置序号. 显然有关系：.现用两种方法计算全体数的坐标和：一方面，直接从整体看，坐标和为为偶数；另一方面，就

30、某一个i，两坐标和为，从而所有坐标和为=偶数+为奇数. 此两者显然矛盾注 本题为第二届冬令营的一道很难的问题,方法较多，上面给出的方法是一个很巧妙的解法，利用奇偶性导出了矛盾，是命题人所没有想到的.板块二 递推方法当所计数对象按从1到n有规律出现时，可视之为一个数列并考察其相邻项之间关系，得到递推关系式,进而利用数列知识进行求解.一般来说，这类问题的关键在于如何得到递推关系式.对于竞赛选手而言，由组合问题的递推关系式得到通项总是很简单的,因为组合问题的特性决定了递推关系式不会太过复杂.由于我们没有详细讲述数列通项求法，所以这里只给出较为简单的问题.注：建议教师主要讲述如何由题目条件得到递推式，

31、至于递推式求解可以淡化或者让学生自行求解【例15】 （Fibonacci数列）假设一对兔子每隔一月生一对小兔，每对小兔两个月后也逐月生一对小兔，如年初时放一对成年兔，那么一年以后兔房中有多少只兔子？【解析】 用表示第n个月初的小兔对数，易得到一般地，第n个月初的小兔分为两部分：第n-1个月的兔子数与第n个月初出生的小兔对数，即得到递推式，由特征方程的结论及初值，可得到注 关于斐波那契数列的进一步知识我们到数列部分再详细讲述【例16】 用1,2,3来构造一个n位数，但不允许数位中出现两个连续的1，问这样的数有多少个？【解析】 设有个，显然，讨论：若n位数第一位不是1，那么后面可以随便写，于是这样

32、的有2个，若第一位是1，第二位写2或3，第三位后可以随便写，于是这样的有2个，得到递推式，由特征方程的结论及初值，化简得到注 一般写出原始结果即可，或者把化简结果同时写出板块三 组合计数综合问题【例17】 设为整数，集合中的数由小到大组成数列：，则131 。【解析】 为整数且，最小取2，此时符合条件的数有，可在中取，符合条件有的数有同理，时，符合条件有的数有时，符合条件有的数有时，符合条件有的数有时，符合条件有的数有因此，是中的最小值，即注 本题为2005年四川预赛题，事实上此题源自2003年全国高考理科试卷压轴题，用二进制方法求解最为方便，可参考左晓明2003年高考理科数学压轴题的一种巧妙解

33、法及其推广中学教研2003.12【例18】 如果自然数的各位数字之和等于7，那么称为“吉祥数”.将所有“吉祥数”从小到大排成一列若则_ .【解析】 准确理解“吉祥数”的定义是解题的前提，根据题意，可将此计数问题转化为考虑不定方程的非负整数解的个数. 方程的非负整数解的个数为.而使的整数解的个数为.现取，可知，位“吉祥数”的个数为2005是形如的数中最小的一个“吉祥数”，且对于四位“吉祥数”，其个数为满足的非负整数解个数，即个.2005是第1+7+28+28+165个“吉祥数”，即从而又而从大到小排列的最后六个五位“吉祥数”依次是：70000，61000,60100,60010,60001,52

34、000.第325个“吉祥数”是52000，即注 1、本题为2005年全国联赛试题2、很多计数问题都可以转化为求不定方程的解的组数，一般地，有（1）不定方程的非负整数解的组数为；（2）不定方程的正整数解的组数为.【例19】 若四位数的各位数码中，任三个数码皆可构成一个三角形的三条边长，则称为四位三角形数，试求所有四位三角形数的个数【解析】 三个数构成三角形的三条边长的充要条件是任意两个数之和大于第三个数.本题需要根据四个数码的各种可能情况分类进行分析，按照四个数码取值个数的不同进行分类比较容易入手一些. 称为的数码组，则.（1）当数码组只含一个值，为，共得个值.（2）当数码组恰含二个值（）数码组

35、为型，则任取三个数码皆可构成三角形，对于每个，可取个值，则数码组个数为，对于每组，有种占位方式，于是这种有个数码组为型（），据构成三角形条件，有，的取值123456789中的个数共得个数码组，对于每组，有种占位方式，于是这种有个数码组为型（），据构成三角形条件，有，同上得个数码组，对于每组，两个有种占位方式，于是这种有个以上共计个（3）当数码组恰含三个值数码组为型，据构成三角形条件，则有，这种有组，每组中有种占位方式，于是这种有个数码组为型，此条件等价于中取三个不同的数构成三角形的方法数，有组，每组中有种占位方式，于是这种有个数码组为型，同情况，有个值以上共计个值（4）互不相同，则有，这种有组

36、，每组有种排法，共得个值综上，全部四位三角形数的个数为个注 本题为2007年江西省预赛试题.本题的情况非常多，一定要注意分类的合理性和计数的准确性.教师备注： 若例题不够可适当选择习题讲授大显身手7 在一次测验中满分100分，所有同学得分都是非负整数，设n位同学的的得分分别为，其中得分至少为k分的有个（），记，那么M,N的大小关系为？【解析】 M=N.一方面，得分为k的同学对M的贡献为k,另一方面他在中各被计算了一次，每次为1，共计为k，于是得证.注 本题为典型的算两次方法 8 在一张正方形纸片的内部给出了1985个点，现用M记这纸片的4个顶点与内部1985个点构成的集合，并按下述规则将这张纸

37、剪成一些三角形：（1） 每个三角形的三个顶点都是M中的点；（2） 除顶点外，每个三角形中不再含有M中的点.问：可剪出多少个三角形，共需剪多少刀？（剪出一条边需要剪一刀）【解析】 M中每个点都是若干三角形的公共顶点，不论怎样剪，纸的四个顶点处各三角形内角和均为90度，其余1985个点处所有三角形内角和则为360度. 设剪出了x个三角形，那么全体三角形内角和为180x度，于是我们得到：又每个三角形都有三条边，共有条边，另一方面，每剪一次产生两条三角形的边，而四边形的四条边不用剪，设共剪了y刀，于是所有三角形共有2y+4条边， 由注 考虑计算“角度”是问题的突破口.请注意比较例39 一个立方体的顶点

38、标上+1或，面上标一个数，它等于这个面的4个顶点处的数的乘积.这样所标的14个数的和能否为0？【解析】 考虑这14个数的乘积S：将每个面所标的数写成4个顶点处的数的乘积，这样，在S中，每个顶点所标的数将作为乘数出现4次（其中面上乘积中出现3次），从而它对S的贡献为1，因此；另一方面，14个数的积S为1，故这14个为1或的数中，的个数为偶数，由于的个数不为7，故和必不为0.10 一条走廊宽 2 m, 长 8 m, 用 6 种颜色的 11 m的整块地砖来铺设(每块地砖都是单色的, 每种颜色的地砖都足够多), 要求相邻(即有公共边的)的两块地砖颜色不同, 那么所有的不同拼色方法有A. 个 B. 个

39、C. 个 D. 个【解析】 铺第一列(两块地砖)有 种方法；其次铺第二列设第一列的两格铺了 、两色(如图)，那么，第二列的上格不能铺 色若铺 色，则有 种铺法；若不铺 色，则有 种方法. 于是第二列上共有 种铺法. 同理， 若前一列铺好，则其后一列都有 种铺法因此，共有 种铺法 故选 D注 本题为2005江苏预赛题.11 一次竞赛有名选手参加，每天选手的得分恰好组成集合，如果在第k天末，每两名选手的得分之和均为52分，求出使这件事成立的所有数对【解析】 一方面，k天末所有选手得分总和为，另一方面，由每两名选手的得分之和均为52分知总分为26n，从而，经检验，除第一组外其他都满足，从而共有3对.

40、注 本题为一个简单的算两次问题12 某人有n元钱，去买三种物品：甲物品1元，乙丙均为2元，求花完这n元钱有多少种方式？【解析】 ，13 将一个三位数的三个数字顺序颠倒，将所得到的数与原数相加，若和中没有一个数字是偶数，则称这个数是“奇和数”，那么，所有的三位数中，奇和数有 （ ）（A）100个（B）120个 （C）160个（D）200个【解析】 设三位数为，对的可能取值进行分析.，若不进位，则和数的十位数必为偶数，不符合题意，所以只能是11，13，15，17.因为1192837465，所以取值有种可能；因为13948576，所以取值有种可能；因为159687，所以取值有种可能；因为1798，所

41、以取值有种可能；由于不能进位，所以只能取0，1，2，3，4.因此，满足条件的数共有个，故选（A）.注 本题为2007年广西预赛试题. 对于新定义题，准确理解概念是关键，本题以的可能取值为突破口，使得计数变得简单. 这种题型在小学和初中非常常见第三讲 二项式定理与组合恒等式本讲概述本讲将涉及到组合学的一个重要内容：组合恒等式.从组合数和二项式定理开始，可以得到很多有趣的恒等式.事实上，历史上出现过数以千计的组合恒等式，直到现在仍然有新的恒等式出现.在中科大小丛书组合恒等式中，史济怀教授给出了两百多个组合恒等式.由于现在各级竞赛中对组合恒等式要求大为降低，因此本讲只涉及比较简单的恒等式，以及利用这

42、些恒等式来解决问题以下给出一些基础知识：1二项式定理 2二项展开式的通项 它是展开式的第r+1项.3二项式系数 4二项式系数的性质（1）（2）（3）若n是偶数，有，即中间一项的二项式系数最大. 若n是奇数，有，即中项二项的二项式系数相等且最大.（4）（5）（6）（7）（8） 以上组合恒等式（是指组合数满足的恒等式）是证明一些较复杂的组合恒等式的基本工具.（1）（6）请自证.（7）和（8）的证明将在后面给出.5证明组合恒等式的方法常用的有（1）公式法，利用上述基本组合恒等式进行证明.（2）利用二项式定理，通过赋值法或构造法用二项式定理于解题中.（3）利用数学归纳法.（4）构造组合问题模型，将证明

43、方法划归为组合应用问题的解决方法.（5）母函数法，此方法仅在冬令营以上级别要求例题精讲 【例20】 试证明恒等式：【解析】 由二项式定理 ，上式中取即得到上述恒等式注 可见取不同的x还可以得到一系列恒等式【例21】 证明： （1） （2） 【解析】 （1）由可得（2）由得到【例22】 证明：【解析】 首先求， ，又，相加即得原式注 类似地，我们还可以求得【例23】 证明：【解析】 ，其中令k=2n-j, ,于是【例24】 已知数列满足 求证：对于任何自然数n，是x的一次多项式或零次多项式. 【解析】 由是等差数列，则从而可将表示成的表达式，再化简即可.因为,所以数列为等差数列，设其公差为d.有

44、. 从而由二项式定理，知又因为从而 所以当的一次多项式，当零次多项式.注 本题有一定的难度，运算量也很大，需要对二项式定理及常用组合恒等式相当熟练.建议选择讲授. 本题亦可用递推方法来解【例25】 证明：（1） （2） （3）【解析】 考虑中的系数：一方面的系数即的系数，即，另一方面，利用二项式定理将展开并相乘，得到的系数即为（2）式左边，从而（2）式得证；在此式中令即得（1）式.下证（3）：利用的展开式，考虑中的系数：一方面展开式中的系数即为右端；另一方面分别用二项式展开后乘开，的系数即为左式，故得证注 本题使用的方法即母函数方法，但母函数方法在联赛中不要求，我们只举此两例，以供有兴趣的同学

45、了解一下【例26】 设，证明：【解析】 考虑从n个人中选出m名正式代表及若干名列席代表（列席代表不限，可为0）一方面，先选定正式代表，有种方法，从余下n-m人中选列席代表，有种方法，一共有种方法；另一方面，可先选出包括正式代表和列席代表共m+k人(),然后再从中选出m名正式代表，对每一个k有种选法，从而选法总数为种，故得证注 本题采用了构造组合模型的方法.事实上，近年来组合恒等式考察内容非常浅，联赛中不会涉及到利用母函数、递推方法、组合模型的复杂恒等式证明，因此，我们仅各举一例说明方法.【例27】 试用恒等变形方法证明例7的等价形式：【解析】 注意到，于是注 本题重点是前面的变形【例28】 （

46、1）试求展开式中的系数；（2）在一次实战军事演习中，红方的一条直线防线上设有20个岗位。为了试验5种不同新式武器，打算安排5个岗位配备这些新式武器，要求第一个和最后一个岗位不配备新式武器，且每相邻5个岗位至少有一个岗位配备新式武器，相邻两个岗位不同时配备新式武器，问共有多少种配备新式武器的方案？【解析】 （1）由，知只须求展开式中的系数。又因此的系数为 6152020615 580 （2）设20个岗位按先后排序为1，2， ，20，且设第k种新式武器设置的序号为 。令，则有 （*）其中，。 作代换 ，从而有 （*）其中。 问题（*）的解数等于展开式中的系数，由第一问知它等于580因为5种新式武器

47、各不相同，互换位置得到不同的排列数，所以配备新式武器的方案数等于。注 本题为2005年浙江省预赛题改编教师备注：由于本讲内容近年来考察较少，因此不安排过多题目，如内容不够可从习题中选择或适当自行增加例题备选题： 求证：【分析】考虑到恒等式，仿例2解决.【证明】令因为，令 于是由式得.这说明an为等差数列，而a0=1,a1=2，故公差d=1，且an=n+1 .【说明】此题运用变换求和指标的方法，找出了an，an1，an2之间的线性关系式，再由 初始条件求得an.这种利用递推关系求组合数的方法，在解决较复杂的计算或证明组合恒等式时经常用到.大显身手14 数码中有奇数个9的2007位十进制数的个数为

48、 A B C D 【答】（ ）【解析】 （ B ）出现奇数个9的十进制数个数有，又由于以及，从而得 15 证明：【解析】 考虑中的系数：一方面的系数即的系数，即，另一方面，利用二项式定理将展开并相乘，得到的系数即为原式左边，从而得证；注 本题为例6（2）的特例16 证明：【解析】17 数列中，求的末位数字是多少？【解析】 先利用n的初值猜想的特点与的末位数字：当n=1时，a1=3，因此的末位数字都是7，猜想， 现假设n=k时， 当n=k+1时， 从而完成了归纳论证. 所以对任意正整数n， 于是 故的末位数字是7.注 本题中利用初值得到规律进而猜想是问题解决的关键. 在很多数学竞赛问题解决过程中

49、都需要对初值进行分析从中找出规律，这是对将来进行数学研究过程中解决未解决的数学问题的一种必要训练.18 已知试问：在数列中是否有无穷多个能被15整除的项？证明你的结论.【解析】 数列的特征方程为它的两个根为，所以 （n=0，1，2，）由 则取，由二项式定理得由上式知当15|k，即30|n时，15|an，因此数列中有无穷多个能被15整除的项.第四讲 抽屉原理与存在性问题本讲概述本讲我们将讲述组合数学中一个非常简单却又十分重要，应用十分广泛的一个原理，即抽屉原理.然后我们将给出与抽屉原理内涵相通的几个变形，即平均值原理与图形重叠原理.事实上这几个原理是用来证明存在性问题的有力工具之一，当然我们还可

50、以利用极端原理、反证法、数学归纳法、算两次、计数方法和构造法等等来加以证明.本讲我们主要讲述利用平均值原理（其在整数和图形范围内的形式分别为抽屉原理和图形重叠原理）来证明存在性问题，并略举数例说明其它方法在证明存在性问题中的应用.第一抽屉原理：若将m个物件放入n个抽屉中，则必有一个抽屉内至少有个物件.第二抽屉原理：若将m个物件放入n个抽屉中，则必有一个抽屉内至多有个物件.事实上这两个原理利用极端性原理与反证法极易证明，此处从略.平均值原理1：设为实数，且，则中必有一个不小于A，也必有一个不大于A平均值原理2：设为正实数，且，则中必有一个不小于G，也必有一个不大于G图形重叠原理：把面积为的n个平

51、面图形以任意方式放入一个面积为S的平面图形A内，（1） 如果，则必有两个图形有公共点；（2） 如果，则必有一点不属于上述n个图形中任意一个可以发现，上述三组原理都是极端性原则在不同场合的具体表现形式. 极端性法则是处理组合数学中存在性的利器，通过对这三组原理及其解题技巧的深刻把握，我们也可以自己创造一些类似的极端性原理来解决问题.教师备注：本节题目有些可能学生在初中接触过，教师可以适当选择其中较有新意的问题.例题精讲 利用抽屉原理解题的关键是根据题目特点巧妙地构造“抽屉”：将题目中涉及元素按照某一性质分类，当取出足够多的元素时，即可断言必有某些元素属于同一个“抽屉”.构造抽屉的常用方法有：划分集合、分割图形、利用剩余类等等.与抽屉原理相关的试题中，联赛中的题目往往利用抽屉原理是解题的关键，但在冬令营级别的赛题中，往往抽屉原理只是其中的一小步或者利用它解决其中的小块问题而已.【例29】 将平面上的每个点都以红、蓝两色之一着色，证明：存在这样两个相似的三角形，它们的相似比为1995，并且每一个三角形的三个顶点同色。【解析】 任取一点O为圆心，以1,1995为半径作两个同心圆，在内圆上任取9点，由抽屉原理知至少有5点同色，记为,再设此五条半径与外圆交于,由抽屉原理必有3点同色，设为，于是即为所求注 本题