数学竞赛讲义：排列与组合

数学竞赛讲义：排列与组合【赛点直击】一、两个基本原理加法原理 设A为完成一件事情的所有方法的集合，它可以划分为n个互不相交的非空子集A1，A2，An，|Ai|=mi(i=1,2,n)，那么完成这件事情的总方法数为：N=|A|=m1+m2+mn；使用加法原理的关键在于对所计数的对象进行完全分类乘法原理 设A为完成一件事情的所有方法的集合，且完成这件事情需要几个步骤，实现第i(i=1,2,n)个步骤的方法的集合为Ai，|Ai|=mi,那么完成这件事情的总方法数为N=|A|=m1m2mn；使用乘法原理的关键在于对所计数的对象进行完全分步二、相异元素的排列与组合（1）从n个不同元素中，任取m个不同元素的排列数是；（2）从n个不同元素中，任取m个不同元素的组合数是；三、圆排列定义 从n元集中任取r个不同元素，仅按元素之间的相对位置而不分首尾排成一个圆圈，这种排列称为n个不同元素的r-圆排列，其排列数记为由定义，不难求得：与组合数和排列数的关系为：事实上设已将某r个不同元素在圆周上排好，并从某个元素开始将它们依次记为，现在保持这个顺序不变，让去任意选择圆周上的r个位置之一，有r种不同的选择，这r种选择所对应的排列形式不同实则相同由于r个元素的全排列数为，故r个元素的圆排列数为，故n个元素的圆排列数为四、重复排列定义 从n元集中允许重复地任取r个元素排成一列，称为n个不同元素的r-可重排列利用乘法原理易证明，n个不同元素的r-可重排列数为，这类问题一般可直接用乘法原理求解五、不全相异元素的全排列定义 设n个元素可分为k组，每一组中的元素是相同的，不同组间的元素是不同的，其中第i组的元素个数为，则这n个元素的全排列称为不全相异元素的全排列n个元素的不全相异元素的全排列个数为，证明如下：先把每组中的元素看作是不相同的，则n个不同元素的全排列数为，然后分别将每个组的元素还其本来面目每个组的元素是相同的，则在这个全排列中，每个排列都重复出现了次，所以不全相异元素的全排列数为六、多组组合定义 将n个不同的元素分成k组的组合称为n个不同元素的k-组合对于一个n个不同元素的k-组合，若第i组有个元素，（），则不难证明不同的分组方法数为事实上，我们把分组的过程安排成相继的k个步骤：第一步，从n个不同元素中选个，有种方法；第二步，从个元素中选个有种方法，第k步，从个元素选个元素，有种方法，再由乘法原理得证七、重复组合定义 从n个不同的元素中任取r个允许重复出现的组合称为n个不同元素的r可重组合不难证明，n个不同元素的r可重组合的个数为事实上，设（）是取自1,2,n中的任一r-可重复组合，并设，令，从而，显然下面两组数是一对一的：，设，则由A、B之间存在一一对应，可知，得证在上述证明中，设r-可重复组合中含有个1，个2，个n，则，且显然有（）与（）一一对应，因此我们立即可得：定理1 不定方程的非负整数解的个数为定理2 不定方程的正整数解的个数为证明：令，其中，（）是已知方程的正整数解，则 （*），由定理1知，方程（*）有个正整数解【赛题解析】例1在由n2个小方格组成的正方形中，有多少个由整数个小方格组成的大小或位置不同的正方形？解：由整数个小方格组成的大小位置不同的正方形可分成n类，第k类为kk的正方形，共有个(k=1,2,n)，于是由加法原理得所求正方形的总个数为说明：此题将问题进行分类，直接用加法及乘法原理进行求解，两个原理是解决排列组合问题最基本的工具例2设整数a,b,c为三角形三边，a+b=nN,1cn-1，求这样的整边三角形的个数解：不妨设ba，有1a，这样的整边三角形可分为两类第一类：c为最大边，令，则，n-icn-1，这样的三角形有个；第二类：c不为最大边，则，故，故，这样的三角形有由加法原理，使a+b=n的整边三角形的个数为例3有多少个能被3整除而又含有数字6的五位数？解：易知，在由1000099999这90000个五位数中，共有30000个可被3整除，下面先求其中不含数字6的有多少个这件事情可分步来完成：在最高位，不能为0和6，因此有8种可能的情况，在千、百、十位上，不能为6，各有9种可能的情况，在个位上，不能为6，且应使整个五位数能被3整除，因此所出现的数应与前4位数字之和被3除的余数有关：当该余数为2时，个位上可为1，4，7中的一个；当该余数为1时，个位上可为2，5，8中的一个；当该余数为0时，个位上可为0，3，9中的一个，总之，不论前4位数如何，个位数字都有3种可能情况所以这类五位数的个数为89993=17496，因此，含数字6而又可被3整除的五位数的个数为30000-17496=12504种可能例4从1，2，3，4，49中取出六个不同的数字，其中至少有两个是相邻的取法种数是多少？解：设是取自1，2，3，4，49中的六个不同的数，不妨设，显然，且互不相同的充要条件是：中不含相邻的数作六元数组对应于，则在取自1至49之间的六个不同且没有相邻的数构成的六元组集合与所有取自1至44之间的六个不同的数构成的六元组集合之间建立了一一对应，因此这两个集合中六元组的个数都为，而1至49之间的六个不同的数构成的六元组的个数为，于是，其中有相邻数的六元组的个数为说明：本题通过对应的方法将数相邻的问题转化为元素互异的问题，从而得到求解，对应的方法是解决排列组合问题的一种常用方法ABCDEF例5如图ABCDEF为六边形，一只青蛙开始在顶点A处，它每次可随意跳到相邻两个顶点之一（1）若在5次内跳到D点，则停止跳动；若5次内不能跳到D点，跳完5次也停止跳动问这只青蛙从开始到停止，可能出现的不同跳法有几种？（2）若青蛙共跳12次，最终跳回到A点的不同跳法有几种？解：（1）由条件，青蛙的跳法只可能出现两种情况： 跳3次到达D点，有2种跳法跳5次停止（前3次不到D点），注意到前3次的种跳法中，有2种到达D点，故前3次有种跳法，而后2次有种跳法，因此有种跳法由、可知，共有2+24=26种不同的跳法（2）设青蛙每逆时针跳一步记为+1，每顺时针跳一步记为-1，共跳12次，将所有这些数相加，若其和为6的倍数，则青蛙跳回A处，若其和不为6的倍数，则青蛙不可能跳回原处，若其和为0，则必为6个+1和6个-1相加，共有种可能；若其和为6，则必为9个+1和3个-1相加，共种；若其和为-6，则必为3个+1和9个-1相加，共种；若其和为12，则有1种可能，若其和为-12，也有一种可能，因此满足要求的不同跳法总数为种例6将一个四棱锥S-ABCD的每个顶点染上一种颜色，并使同一条棱的两端点异色，如果只有5种颜色可供使用，那么不同的染色方法的总数是多少？解法一：由题设，四棱锥S-ABCD的顶点S、A、B所染的颜色互不相同，它们共种染色方法当S、A、B已染好时，不妨设其颜色分别为1、2、3，若C染颜色2，则D可染颜色3、4、5之一，有3种染法；若C染颜色4，则D可染颜色3或5，有2种染法；若C染颜色5，则D可染颜色3或4，也有2种染法，由此可见，当S、A、B已染好时，C与D还有7种染法，从而总的染色方法数为7=420种解法二：满足题设条件的染色至少要用三种颜色（1）若恰用三种颜色，可先从5种颜色中任选一种染顶点S，再从余下的四种颜色中任选两种染A、B、C、D四点，此时只能A与C、B与D分别同色，故有种方法；（2）若恰用四种颜色染色，可以先从5种颜色中任选一种染顶点S，再从余下的四种颜色中任选两种染A与B，由于A与B颜色可以交换，故有种染法，再从余下的两种颜色中任选一种染D或C，而D与C中另一个只需染与其相对顶点同色即可，故有种方法；（3）若恰用5种颜色染色，易知有种染法综上所知，满足题意的总染色方法数为60+240+120=420种类题：（2003年高考江苏第15题）某城市在中心广场建造一个花囿，花囿分为6个部分（如图），现要栽种4种不同颜色的花，每部分栽种一种且相邻部分不能栽种同样颜色的花，不同的栽种方法有 _种（以数字作答）解法一：1、2、3两两相邻，颜色应互不相同，故有种不同种法；1、2、3种好后，用树图方法不难得到4、5、6共有5种种法，由乘法原理得共有5=120种种法解法二：先种1，有4种颜色可选取，2、3、4、5、6形成一个圆环，要求用3种颜色涂上，且相邻的颜色不同即可转化为如下问题：将一个圆分成5个扇形，将三种颜色涂入其中，相邻的扇形涂不同的颜色先涂，有三种涂法，再涂，有两种涂法，再涂3、4各有两种涂法，再涂5，如果只要求它与4颜色不同，则仍有两种涂法，这样共有32222=48种涂法，但这48种涂法中有两类：一类5与1颜色不同，这种涂法符合题意，其数设为一类5与1颜色相同，这种涂法不合题意，如果把5与1合并看成一个扇形，这类涂法就相当于把圆分成4个扇形，按题设要求，其数为，即+=48，同理，=24，而，=30，故最后的结果为：304=120种此问题可一般化为：把一个圆分成个扇形，依次记为每个扇形都可用红、白、蓝三种不同颜色之任一种涂色，且三种颜色均至少用一次，要求相邻的扇形颜色互不相同，问有多少种涂色法？略解：同上可得：，若没有条件“颜色均至少用一次”，结果为，更一般的情形是：把一个圆分成个扇形，依次记为每个扇形都可用r种不同颜色之任一种涂色，要求相邻的扇形颜色互不相同，问有多少种涂色法？有，可得说明：当我们用集合划分的方法对问题进行分类计数时，有时不可能一次性获得成功，这就需要通过建立递推关系来求解，我们把这种计数方法称为递推方法例7设集合A=1,2,3,366，如果A的一个二元子集B=a,b满足17|a+b，则称B具有性质P（1） 求A的具有性质P的所有二元子集的个数；（2） 求A的两两不相交且具有性质P的所有二元子集的个数解：（1）a+b0(mod17)，即ak(mod17)且b17-k(mod17)，k=0,1,2,16，将1,2,3,366按模17可分为17类0,1,16；因366=1721+9，故|1|=|2|=|9|=22，|10|=|11|=|16|=|0|=21，欲17|a+b，当且仅当a,b0或ak，b17-k，当a,b0时，具有性质P的二元子集的个数为个；当ak，b17-k，k=1,2,7时，具有性质P的二元子集有个；当a8，b9时，具有性质P的二元子集有个；所以A的具有性质P的二元子集总个数为个说明：如果把子集换成数对（a,b），则共有23928个（2）为使二元子集两两不交，可作如下搭配：a,b0时，共有10个子集；ak，b17-k，k=1,2,7，有21个子集；当a8，b9时，有22个子集故A的具有性质P的两两不交的二元子集共有10+721=179个例88个女孩和25个男孩围成一圈，任何两个女孩之间至少站两个男孩，问共有多少种不同的排列方法（只要把圈旋转一下就重合的排法认为是相同的）解：以1个女孩和2个男孩为一组，且使女孩恰好站在两个男孩中间，余下的9个男孩和这8个组被看成是17个元素，显然这17个元素任意的圆排列数为种再次，分在8个组内的16个男孩在16个位置上的排列是，所以总的排列方法数为：说明：此题为圆排列问题例9试求从集合到集合的映射的个数解：由映射的定义知，每一个到B的映射对应着个不同元素的-可重排列，故从A到B的映射的个数为例10一段楼梯共有12级台阶，某人上楼时，有时一步迈一台阶，有时一步迈两台阶，问此人共有多少种上楼的方法？解：现将“一步迈两级台阶”这一动作记为a，因为楼梯共有12级台阶，故动作a至多只能做6次；再记“一步迈一级台阶”的动作为b，则上楼的整个过程由k个a及12-2k个b组成，这里k可取0，1，2，3，4，5，6，对于某个k，其全排列数为：，因此，上楼的方法共有：=233种解法2：以k=4为例，即4个两级，4个一级，相当于共8步，其中有四步为两级，即相当于从8步中选4步跨两级，其余跨一级，故结果应为；一般地上楼的整个过程由k个a及12-2k个b组成，相当于共跨k+(12-2k)=12-k步，其中有k步为a，故结果为,这里k可取0,1,2,3,4,5,6，故最终结果为解法3：设走n次台阶的方法总数为，对每种走法可划分为两类第一类：第一步走1级，有种走法；第二类：第一步走2级，有种走法，故，且，故易得因Fibonacci数列满足，故，由上面的一些方法还可知：若将所跨的每一级台阶，此人均用红、白两种颜色做上记号，则标有不同颜色的路线共有种，其递推关系式为例11把n个不同的球，分别装入m个盒子中，使其中个盒子中每个都有个球，个盒子中每个都有个球，个盒子中每个都有个球，这里，求下列情况下，各有多少种不同放法：（1）盒子均不相同；（2）装有相同数目的球的盒子相同解：（1）这是一个将n个不同元素分为m组的多组组合，故不同的放法数有；（2）因为相同数目的球的盒子相同（不加区别），故所求放法数为例12电视台在n天内共播出r次商业广告，问若每天至少播p次广告（），就每天播出广告的次数而言，共有几种播出方法？解：设第天播出广告次，由题设知：，令，则，故问题转化为求上述不定方程的非负整数解的个数，从而知广告播放的方法数为巩 固 练 习1n名同学(n3)站成一圈，其中A、B两人不能相邻的站法有多少种？解：n名同学站成一圈有(n-1)!种站法，其中使A、B相邻的站法有2(n-2)!种，从而A、B不相邻的站法为(n-1)!-2(n-2)!=(n-3)(n-2)!种站法2设集合A、B的并集为一个n元集，AB（1） 若（A，B）与（B，A）视为不同的对，则这样的A、B共有多少个？（2） 若（A，B）与（B，A）视为相同的对，则这样的A、B共有多少个？解：（1）设集合A中有k个元素，则集合B中必含有A中没有的n-k个元素，再加上A的k个元素中取0个、1个、k个，故共有个，故总数为=个，除去A与B相同（均为全集）的1个，共-1个；（2）由题意，（A，B）与（B，A）一一对应，故结果为个ABCDEF3在一个正六边形的六个区域栽种观赏植物，如图，要求同一块中种同一植物，相邻的两块种不同的植物，现有4种不同的植物可供选择，则有多少种不同的栽种方案解：考虑A、C、E种同一种植物，此时共有4333=108种；考虑A、C、E种两种植物，此时共有343322=432种方法；考虑A、C、E种三种植物，此时共有222=192种方法；故总计有108+432+192=732种方案4如图，矩形ABCD的边在网格线上，并且AB是AD的k倍（k为正整数），考虑沿网格的边从A到C所有可能的最短路径证明：在这些路径中，含AB1的条数是含AD1的条数的k倍解：含AB1的最短路径，除AB1外，还应含横向的m-1节，纵向的n节，因此共有条，同理，含AD1的最短路径有条，而，因此命题得证5马路上有编号为1，2，3，2005的2005只路灯，为节约用电，现要求把其中的200只灯关掉，但不能同时关掉相邻的两只或三只，也不能关掉两端的路灯，求满足条件的关灯方法共有多少种？解：任意一种关灯的方法，都对应着一种满足题设条件的亮灯与暗灯的排列，于是总是转化为1805只亮灯中插入200只暗灯，且任何两只暗灯不相邻，而且不在两端，也就是在1805只亮灯所形成的1804个间隙中选200个插入暗灯，其方法有种6把2005个不加区别的小球分别放在10个不同的盒子里，使得第i个盒子中至少有i个球，问不同放法的总数是多少？解：先在第个盒子里放入个球，这时共放了1+2+10=55个球，还余下2005-55=1950个球，故问题转化为把1950个球任意放入10个盒子（允许有的盒子不放球），相当于一个不定方程的非负整数解的个数问题，共有种7个人站成一圈，其中某指定的两人A、B肯定不相邻的站法有多少种？答案：8甲、乙两队各出7名队员按事先排好的顺序出场参加围棋擂台赛，双方先由一号队员比赛，负者被淘汰，胜者再与负方2号队员比赛，直到一方队员全部淘汰为止，另一方获得胜利，形成一种比赛过程，那么所有可能出现的比赛过程的种数是多少？解：不妨先设甲方胜出，则问题等价于求方程的非负整数解的个数，有种，同理，乙方胜的比赛过程也有种，故可能出现的比赛过程有种9有男生人，女生人（），（1）这个人排成一列，女生不相邻，首尾都是男生，有多少种排法？ （2）这个人围成一圈，女生不相邻，有多少种排法？解：（1）；（2）先作男生圆排列，然后插入，共10方程的非负整数解共有多少个？解：由题意，故分情况讨论如下：若，则，非负整数解的个数为：；若，则，非负整数解的个数为：综上，非负整数解的个数为：165+9=174个11一个盒子里有7个分别标有号码1，2，7的球，每次取出一个，记下它的号码后再放回盒子，共取（放）4次，求4次中最大标号恰是5的取法数？解：最大标号为5，相当于从1，2，5中取，共取（放）4次，共有种取法；从中剔除四次中最大标号均不是5的种数，结果为=36912已知集合，在复平面上，以A中的复数的对应点为顶点可构成多少个直角三角形？解：易求得，其中（n2）设各复数在复平面上对应点依次为O、A0、A1、A2、A2n-1，则A0A1A2A2n-1为正2n边形，易知在中以为顶点的内角均为锐角，所以，由O、A0、A1、A2、A2n-1为顶点的直角三角形可分为两类：第一类：以O为直角顶点的直角三角形，不失一般性，可设，则，所以，这说明这类直角三角形存在当且仅当n为偶数时，这时，这样的直角三角形有2n个；第二类：不以O为直角顶点的直角三角形这样的直角三角形的顶点均匀分布在单位圆周上，即由A0、A1、A2、A2n-1构成，这些点可确定n条直径，于是可构成个直角三角形综上所述，由加法原理，所求直角三角形的总个数为友情提示：部分文档来自网络整理，供您参考！文档可复制、编制，期待您的好评与关注！10 / 10