数学竞赛讲义组合计数

联赛班·第1讲·教师版1数学竞赛讲义第一讲组合计数本讲概述组合数学是竞赛中最重要的一个板块，也是变化最多，最灵活，难以掌握，至今还没有一个系统体系的学科.解决竞赛中的组合数学问题，往往不需要太多专门的知识，而是要求深刻的洞察能力和强大的化归、转化能力.所谓“得组合者得天下”，在联赛一二试乃至冬令营、集训队、IMO中，最后的胜者往往是成功完成组合问题的同学.因此，学习组合数学对于竞赛获奖以及数学能力的培养都有着十分重要的意义.从本讲开始，我们将用七讲来对组合数学做一个大致的勾勒.通过这七讲的学习，达到以下目的：1、掌握联赛一二试组合问题的特点与解法；2、对组合数学这门学科有一个初步的认识，为进一步学习打下基础；3、了解部分冬令营级别组合问题的难度与解题模式.七讲内容分别为：一、组合计数（1）比高考略难的基本计数问题二、组合计数（2）需要较多技巧的专门计数问题三、组合恒等式较为重要和有趣味的组合恒等式四、抽屉原理与存在性问题五、容斥原理与极端性原理六、染色问题与操作问题七、组合数学综合问题本讲中，假定各位同学已经大致学完了高考难度的排列组合模块内容，对加法原理、乘法原理等有一定的理解并能完成相关的问题.教师备注：本讲可与下一讲打通讲述，也可本讲专门讲常规的枚举、基本的组合问题，下一讲专门讲述一些较为高级的技巧.首先给出一些相关的基本知识：1、加法原理与乘法原理加法原理：完成一件事的方法可分成n个互不相交的类，在第1类到第n类分别有12,,...,nmmm种方法，则总共完成这件事有121...ninimmmm种方法.应用加法原理的关键在于通过适当的分类，使得每一类都相对易于计数.乘法原理：完成一件事的方法有n个步骤，，在第1步到第n步分别有12,,...,nmmm种方法，则总共完成这件事有121...ninimmmm种方法.应用乘法原理的关键在于通过适当的分步，使得每一步都相对易于计数.由上可见，加法原理与乘法原理也是化归思想的应用，通过这两个原理以及它们的组合，可以将一个复杂的组合计数问题分解成若干个便于计数的小问题.2、无重排列与组合阶乘：定义!(1)(2)...21nnnn，读作n的阶乘无重排列：从n个不同元素中任取m个不同元素排成一列，不同的排列种数称为排列数，记为mnA（部分书中记为mnP），由乘法原理得到!(1)...(1)()!mnnAnnnmnm无重组合：从n个不同元素中任取m个元素并为一组，不同的组合种数称为组合数，记为mnC，其公式为(1)...(1)!!!()!!mmnnAnnnmnCmmnmm3、可重排列与组合（仅给出结论，请自证之）可重排列：从n个不同元素中可重复地任取m个元素排成一列，不同的排列种数有mn种；有限个重复元素的全排列：设n个元素由k个不同元素12,,...,kaaa组成，分别有12,,...,knnn个（12...knnnn），那么这n个元素的全排列数为12!!!...!knnnn可重组合：从n个不同元素中，任意可重复地选取m个元素，称为n个不同元素中取m个元素的可重组合，其种数为1mnmC4、圆排列（仅给出结论，请自证之）在n个不同元素中，每次取出m个元素排在一个圆环上，叫做一个圆排列（或叫环状排列）．圆排列有三个特点：（i）无头无尾；（ii）按照同一方向转换后仍是同一排列；（iii）两个圆排列只有在元素不同或者元素虽然相同，但元素之间的顺序不同，才是不同的圆排列．在},,,,{321naaaaA的n个元素中，每次取出m个不同的元素进行圆排列，圆排列数为mnAm．例题精讲板块一利用加法、乘法原理以及枚举方法计数联赛一试的填空题中出现的计数问题有接近一半的问题不需要用到很高深的技巧，而是直接利用联赛班·第1讲·教师版2最基本的加法、乘法原理，以及枚举方法来计数.这主要是考虑到有一部分参加联赛的同学并未经过专业的竞赛训练.虽然如此，这部分计数问题枚举起来往往分类复杂，需要小心仔细.从往年的联赛试题来看，枚举法解决计数问题是最主要的题型之一，其难点在于做到“不重不漏”，这是加法原理的一个简单的应用.枚举过程中，采用恰当的分类、分步形式，往往会收到化难为易的效果.【例1】(高考难度的热身问题)（1）等腰三角形的三边均为正整数．它们周长不大于10．这样不同的三角形的种数为A．8B．9C．10D．1l（2）有两排座位，前排11个座位，后排12个座位，现安排2人就座，规定前排中间的3个座位不能坐，并且这2人不左右相邻，那么不同排法的种数是A.234B．346C.350D．363【解析】（1）设三边为x,y，z，则x+y+z≤10，由三边关系共有(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个座位不能坐，有排法220A，其中相邻的分三类，在前排的其中的4个座位有322A；则符合条件的排法种数中2222222201133AAAA=346，故选B（这是正难则反的思想，从总体中除去不符合要求的）另解：分三类：①两人坐在前排，按要求有4·6+4·5=44种坐法．②两人坐在后排，按要求有：211A=110种坐法．③两人分别坐在前后排，有8×12×2=192种∴共有346种排法．【例2】（1）有多少个能被3整除而又含有数字6的五位数？（2）集合{1,2,...,100}的子集中共有多少个至少包含一个奇数？【解析】（1）按照上题正难则反的思想，可以先找出所有的五位数，共有90000个，其中可被3整除的有30000个，下面研究这30000个数中不含数字6的数，最高位有8种选择，千、百、十位各有9种选择，个位数除不能为6外，还应满足恰各位数之和可被3整除，这恰有3种选择，例如当前四位除以3余2时，个位应为1,4,7之一；故能被3整除且不含数字6的有8999317496个，故所求五位数有30000-17496=12504个（2）显然全部子集数为1002个，不包含任何奇数的子集即{2,4,6,...,98,100}的子集共有502个，故所求子集个数为1005022个.(思考：请用最简洁的方法确定为何n元集合子集数为2n个)【例3】设ABCDEF为正六边形，一只青蛙开始在顶点A处，它每次可随意地跳到相邻两顶点之一．若在5次之内跳到D点，则停止跳动；若5次之内不能到达D点，则跳完5次也停止跳动，那么这只青蛙从开始到停止，可能出现的不同跳法共种【解析】这是标准的联赛风格的枚举问题，所谓杀鸡焉用牛刀，用递归方法来解这类问题就太麻烦了.显然青蛙不能跳1，2,4次到达D点，于是青蛙的跳法只有以下两种：（1）青蛙跳3次后到达D点，有2种跳法；（2）青蛙跳5次后停止，跳3次有322种，后两次有22种，共计24种；所以，合计有26种跳法注本题为1997年联赛试题【例4】从给定的六种不同颜色中选用若干种颜色，将一个正方体的六个面染色，每面恰染一种颜色，每两个具有公共棱的面染成不同的颜色。则不同的染色方法共有__________种。（注：如果我们对两个相同的正方体染色后，可以通过适当的翻转，使得两个正方体的上、下、左、右、前、后六个对应面的染色都相同，那么，我们就说这两个正方体的染色方案相同。）【解析】因为有公共顶点的三个面互不同色，故至少要用3种颜色，下面分四种情形来考虑.（1）6种颜色都用时，现将染某种固定颜色的面朝上，从剩下5种颜色中取一种颜色染下底面有15C种方法，余下4种颜色染四个侧面（应是4种颜色的圆排列）有3！种方法.所以不同的染色方案有30!315C种.（2）只用5种颜色时，从6种颜色中取5种颜色有56C种方法，这时必有一组对面同色.从5种颜色中取一种颜色染一组对面，并将它们朝上和朝下，有15C种方法，其余4种颜色染四个侧面（应是4种不同颜色的链排列）有213！种方法.所以不同的染色方案有56C90!32115C种.（3）只用4种颜色时，从6种颜色中取4种颜色有46C种方法，这时必有两组对面同色，另一组对面不同色，将不同色的一组对面朝上和朝下，并从4种颜色中取两种颜色染上、下底面，有24C种方法，其余两种颜色染四个侧面且使两组对面同色（应是两种不同颜色的链排列），只有1种方法.所以不同的染色方案有46C90124C种.（4）只用3种颜色时，从6种颜色中取3种颜色有36C种方法，这时三组对面都同色，用三种颜色去染它们只有1种方法.所以不同的染色方案有36C201种.综上可知，不同的染色方案共有30＋90＋90＋20＝230种.注本题为1996年联赛试题，是历年来一试计数问题中最复杂的一道，其背景与波利亚群论计数原理有关，这远远超出了高中范围，此处略去【例5】将24个志愿者名额分配给3个学校，则每校至少有一个名额且各校名额互不相同的分配方法共有222种．【解析】用4条棍子间的空隙代表3个学校，而用表示名额．如||||表示第一、二、三个学校分别有4，18，2个名额．若把每个“”与每个“|”都视为一个位置，由于左右两端必须是“｜”，故不同的分配方法相当于24226个位置（两端不在内）被2个“｜”占领的一种“占位法”．“每校至少有一个名额的分法”相当于在24个“”之间的23个空隙中选出2个空隙插入“｜”，故联赛班·第1讲·教师版3有223C253种．又在“每校至少有一个名额的分法”中“至少有两个学校的名额数相同”的分配方法有31种．综上知，满足条件的分配方法共有253－31＝222种．[解法二]设分配给3个学校的名额数分别为123,,xxx，则每校至少有一个名额的分法数为不定方程12324xxx．的正整数解的个数，即方程12321xxx的非负整数解的个数，它等于3个不同元素中取21个元素的可重组合：2121232323HCC253．又在“每校至少有一个名额的分法”中“至少有两个学校的名额数相同”的分配方法有31种．综上知，满足条件的分配方法共有253－31＝222种注本题为2008年联赛试题，从近年来联赛一试组合问题来看，组合计数问题难度明显降低了.本题所应用的插空法是一种在高考和竞赛中常用的计数方法【例6】将2个a和2个b共4个字母填在44方格表内，每个小方格内至多填1个字母，若使相同字母既不同行也不同列，则不同的填法共有________种（用数字作答）。【解析】使2个a既不同行也不同列的填法有C42A42=72种，同样，使2个b既不同行也不同列的填法也有C42A42=72种，故由乘法原理，这样的填法共有722种，其中不符合要求的有两种情况：2个a所在的方格内都填有b的情况有72种；2个a所在的方格内仅有1个方格内填有b的情况有C161A92=16×72种。所以，符合题设条件的填法共有722−72−16×72=3960种。注本题为2007年联赛第12题【例7】设三位数nabc，若以a，b，c为三条边的长可以构成一个等腰（含等边）三角形，则这样的三位数n有（）A.45个B.81个C.165个D.216个【解析】本题是标准的枚举问题，情况繁多.a，b，c要能构成三角形的边长，显然均不为0。即,,{1,2,...,9}abc（1）若构成等边三角形，设这样的三位数的个数为1n，由于三位数中三个数码都相同，所以，1199nC。（2）若构成等腰（非等边）三角形，设这样的三位数的个数为2n，由于三位数中只有2个不同数码。设为a、b，注意到三角形腰与底可以置换，所以可取的数码组（a，b）共有292C。但当大数为底时，设ab，必须满足2bab。此时，不能构成三角形的数码是a987654321b4，32，14，32，13，213，211，21，211共20种情况。同时，每个数码组（a，b）中的二个数码填上三个数位，有23C种情况。故2222399(220)6(10)156nCCC。综上，121