排列组合全集

排列组合全集 一．排列，就是从M个元素中选出N个元素来排，其中要考虑各元素的先后次序，记为：P(M,N) P(M,N)=M*(M-1)*(M-2)*……*(M-N+1),如P(7,5)=7*6*5*4*3, 组合，就是从M个元素中选出N个元素来组合在一起，不考虑元素的先后次序，记为：C(M,N) C(M,N)=P(M,N)/N!，P(M,N)除以N的阶乘，如C(7,5)=7*6*5*4*3/(5*4*3*2*1) 在近几年的公考中，这类题目常有出现，通常情况下，出题者不会简单的只出单独的排列或者单独的组合，而是综合在一起进行考察，再结合一些排列组合的变形式，使得此类题目成为了广大考生的难中之难，考生经常走入误区，时常出现讨论不完全或者讨论情况超出了题干的范围，当然，由于是选择题，所以很多了选择了猜答案的办法，如果在2分钟之内仍没有思路，那就只有猜了，做这个专题，是想告诉大家，其实排列组合并不是大家想象的那么难的，花点时间学习这个专题，对自己必将有很大的收获。 二．基本原理 ①加法原理：完成一件事有K类，第一类中有M1种不同的方法，第二类中有M2种不同的方法……第K类中有Mk种不同的方法，那么完成这件事的方法就是M1+M2+……Mk,即常用到的分类讨论方法。 例如：7个人排座位，其中甲乙都只能坐在边上。问有几种方法。根据分类的方法。我们可以看， 第一类情况：甲坐在左边，乙坐在右边，其他人全排，P（5，5） 第二类情况：甲坐在右边，乙坐在左边，其他人全排，P（5，5） 我们分别计算出2种情况进而求和即得到答案。 这就是分类原则。 这样就是P（5，5）＋P（5，5）＝240 ②乘法原理：做一件事，完成它需要分成n个步骤，做第一步有M1种不同的方法，做第二步有M2种不同的方法，……，做第n步有Mn种不同的方法，那么完成这件事共有N＝M1×M2×M3×…×Mn种不同的方法． 例如： 7个人排座位，其中甲乙都只能坐在边上。问有几种方法，按照分步原则， 第一步：我们先对甲乙之外的5个人先排序座位，把两端的座位空下来，P（5，5） 第二步：我们再排甲乙，P（2，2） 这样就是 P（5，5）×P（2，2）＝240 三．特殊元素或特殊位置优先考虑。 对参与排列的某元素或某一位置进行特殊的限制，往往首先考虑这个特殊的情况， 例1. 6人站成一横排，其中甲不站左端也不站右端，有多少种不同站法? 解析： 方法1. 对甲的位置进行了特殊的限制，首先考虑甲的位置，甲只能在中间4个位置选择，有4种方法，剩下5人全排，根据乘法原理有： 4*P(5,5)=480 方法2.先从余下的5人中选2个来排在两端，然后余下4人全排。 C(5,2)*P(2,2)*P(4,4)=480 例2．用0、2、3、4、5这五个数字，组成没有重复数字的三位数，其中偶数共有多少个？ 解析： 3位数的偶数，尾数只能是0，2，4，十位数任意，百位上不能为0， 这里0的位置出现了特殊情况，所以可以从0的位置着手来讨论，分含0和不含0 含0：0在个位：P(4,2)=12 0在十位：个位为2或4，C(2,1),百位为余下3个非0数中任意一个，C(3,1) 2*3=6 不含0：C(2,1)*C(3,1)*C(2,1)=12 根据加法原理，答案就为：12+6+12=30 四．相邻问题——捆绑法 对于某几个元素相邻的排列问题，可先将相邻的元素“捆绑”在一起看作一个元素与其它元素进行排列，然后再对这几个捆绑了的元素进行全排列。 例3. 5名学生和3名老师排在一起照相，要求3名老师必须站在一起，求不同的排列方法。 解析： 3名老师必须在一起，那么捆绑3名老师，看成一个具体的元素，与5名学生排列，为P(6,6)，然后再在3名老师内部进行全排列，P(3,3)，根据乘法原理有： P(6,6)*P(3,3)=4320 五．不相邻即相离问题用插空法。 对于某几个元素要求不相邻的排列问题，可先将余下的元素进行排列，然后在这些元素形成的空隙中将不相邻的元素插入，然后再进行排列。 例4. 有10个学生，其中4人中任意两个不能站在一起，有多少种不同的排列次序？ 限制4人 解析：限制了4人的位置，这4人任意两两不能站在一起，那么先全排其他6人，在这6人行成的空隙中来插入这4个人，就满足了任意2个不能在一起的情况，6人中间5个空，这4人还可以站在6人的两端，所以有7个位置可以安排这4人， 所以答案就为：P(6,6)*P(7,4)=25200 例5. 5个男生3个女生排成一列，要求女生不相邻且不可排两头，共有几种排法？ 解析：先排男生,P(5,5),再插入女生，由于女生不能站在排头，所以不能站在男生的两端，可以插入的位置就只有4个了，P(4,3) 答案就为：P(5,5)*P(4,3)=2880 例6. 马路上有编号为1、2、3、…、9的9盏路灯，现要关掉其中的三盏，但不能同时关掉相邻的两盏或三盏，也不能关两端的路灯，则满足要求的关灯方法有几种？ 解析：关掉3盏，还有6盏是亮着的，不能同时关掉相邻的2盏或3盏，即在6盏之间插入3盏即可，两端的不能关，即只有中间5个空可以利用， 答案就为：C(5,3)=10 对于插空法的使用，必须注意的是： ① 必须分清“谁插入谁”的问题。要先排无限制条件的元素，再插入必须间隔的元素。 ② 数清可插的位置数。 ③ 插入时是以组合形式插入还是以排列形式插入要把握准。 六．元素定序，先排后除或选位不排或先定后插 对于某些元素的顺序固定的排列问题，可先全排，再除以定序元素的全排，或先在总位置中选出定序元素的位置而不参加排列，然后对其它元素进行排列。也可先放好定序的元素，再一一插入其它元素。 例7．5人参加百米跑，若无同时到达终点的情况，则甲比乙先到有几种情况？ 解法一：先5人全排有P(5,5)种，由于全排中有甲、乙的全排种数P(2,2)，而这里只有1种是符合要求的，即甲乙先到后到的几率是均等的，各占一半，故要除以定序元素的全排P(2,2)种，所以有P(5,5)/P(2,2)=60种。 解法二：先在5个位置中选2个位置放定序元素(甲、乙)有C(5,2)种，再排列其它3人有P(3,3)，由乘法原理得共有C(5,2)P(3,3)=60种。 解法三：先固定甲、乙，再插入另三个中的第一人有3种方法，接着插入第二人有4种方法，最后插入第三人有5种方法。由乘法原理得共有3×4×5=60种 七．正面解答很困难时，用排除法（逆向思维处理法） 逆向思维解某些复杂的排列组合，先不管条件，找出所有可能的情况，然后再排除掉所有与条件不符合的情况，剩下的就是题干所需要的情况。 例7. 三行三列共9个点，以这些点可以组成多少个三角形？ 解析：9个点选3个点的所有选法是：C(9,3)，排除掉3点共线的情况，就是答案了 3点共线共有3+3+2=8种，所以结果是：C(9,3)-8=76 例8. 从1，2，3，4……9，9个数字中取出2个分别作为对数的底数和真数，可组成多少个不同数值的对数？ 解析：对数中底数大于0且不能为1，当选出的2个数字含1时，1必为真数，此时只有1种数值， 当不选1的时候，从2……9中选2个来作为底数和真数，有P(8,2) 其中，Log(2,4)=Log(3,9), Log(4,2)=Log(9,3) Log(2,3)=Log(4,9), Log(3,2)=Log(9,4) 所以结果是：1+P(8,2)-4=53 例9. 从4名男生和3名女生中选出4人参加某个座谈会，若这4人中必须既有男生又有女生，则不同的选法共有多少种？ 解析：先不考虑附加条件，从7名学生中选出4名共有C(7,4) 种选法，其中不符合条件的是选出的4人都是男生，即1 种。所以符合条件的选法是C(7,4)-1 =34种. 八．分组分配额问题（不同元素进盒），先分组后排列。 例10. 5个老师分配到3个班搞活动，每班至少一个，有几种不同的分法？ 解析：先把5位老师分3堆，有两类：①3、1、1分布有C53种； ②1、2、2分布有C51C42C22/P22种，再排列到3个班里有P33种，故共有(C53+C51C42C22/P22)·P33=240 例11. 有6名同学，求下列情况下的分配方法数： 　　①分给数学组3人，物理组2人，化学组1人； 　　②分给数学组2人，物理组2人，化学组2人； 　　③分给数学、物理、化学这三个组，其中一组3人，一组2人，一组1人； ④平均分成三组进行排球训练。 解析： 1． C(6,3)*C(3,2) 2． C(6,2)*C(4,2) 3． C(6,3)*C(3,2)*P(3,3)，具体哪组多少人没有确定，所以多了个3组的全排。 4． C(6,2)*C(4,2)/P(3,3)，相当于是3个相同的元素，所以要用除法排除掉重复计算的。 九．插板法（隔板法）及其变形式 插板法就是在n个元素间的（n-1）个空中插入 若干个（b）个板，可以把n个元素分成（b+1）组的方法。 一般式是把M个相同的元素放入到N个不同的箱子，每个箱子至少一个，求放法。 应用插板法必须满足三个条件： （1） 这n个元素必须互不相异 （2） 所分成的每一组至少分得一个元素 ，这个条件尤其重要 (3) 分成的组别彼此相异 举个很普通的例子来说明 把10个相同的小球放入3个不同的箱子，每个箱子至少一个，问有几种情况？ 问题的题干满足 条件（1）（2），适用插板法， C（9 ,2）=36 A． 条件（2）的隐藏模式 例12. 某学校四、五、六三个年级组织了一场文艺演出，共演出18个节目，如果每个年级至少演出4个节目，那么这三个年级演出节目数的所有不同情况共有几种？ 解析：发现3个年级都是需要至少4个节目以上！ 跟插板法的条件有出入， 插板法的条件是至少1个，这个时候对比一下，我们就有了这样的思路 ，为什么我们不把18个节目中分别给这3个年级各分配3个节目。 这样这3个班级就都少1个，从而满足至少1个的情况了 3×3＝9 还剩下18－9＝9个 剩下的9个节目就可以按照插板法来解答。 9个节目排成一排共计8个间隔。分别选取其中任意2个间隔就可以分成3份（班级）！ C8取2＝28 例13. 有10个相同的小球。 分别放到编号为1，2，3的盒子里 要使得每个盒子的小球个数不小于其编号数。那么有多少种放法？ 解析：还是同样的原理。 每个盒子至少的要求和插板法有出入 那么我们第一步就是想办法满足插板法的要求。 编号1的盒子是满足的 至少需要1个， 编号2至少需要2个，那么我们先给它1个， 这样就差1个 编号3至少需要3个，那么我们先给它2个， 这样就差1个 现在三个盒子都满足插板法的要求了 我们看还剩下几个小球 ？ 10－1－2＝7 7个小球6个间隔 再按照插板法来做 C（6,2）＝15种. B. 凑元素插板法 例14 ：把10个相同的小球放入3个不同的箱子，问有几种情况？ 解析：此题中3个箱子都可能取到空球，条件（2）不满足，此时如果在3个箱子种各预先放入 1个小球，则问题就等价于把13个相同小球放入3个不同箱子，每个箱子至少一个，有几种情况？ 显然就是 C(12,2)=66 例15： 把10个相同小球放入3个不同箱子，第一个箱子至少1个，第二个箱子至少3个，第三个箱子可以放空球，有几种情况？ 解析：我们可以在第二个箱子预先放入10个小球中的2个，使第二个箱子满足条件（2）此时小球剩余8个放3个箱子，然后在第三个箱子放入8个小球之外的1个小球，则问题转化为 把9个相同小球放3不同箱子，每箱至少1个，几种方法？ C(8,2)=28 C. 添板插板法 例16. 有一类自然数，从第三个数字开始，每个数字都恰好是它前面两个数字之和，直至不能再写为止，如257，1459等等，这类数共有几个？ 解析：此题目注意直到不能写为止， 列如：123，1235，12358.这样的3个数属于一类数，123，1235都还可以往下写，而12358不能再往下写了，故12358就属于符合条件的一类数。 从这里可以看出只要前面的2个数字确定了，那么这样的一类数就确定了， 假设前面的2位数为ab,那么可以的出a+b<=9,且a不等于0， 1 -1- 1 -1 -1 -1 -1 -1 -1 - - a不能取0，而b却可以取0，9个1，8个空，插入2个板，分成3个部分，a,b分别取前2部分，不管怎么插，第二组不可能取空，这时候就需要添板来处理了，在第9个1后面添加1个板，此时同样不能满足b取0，那么继续添加第10个板，此时当取到第10个板的时候，刚好可以满足第二组可以取空的情况，即b=0，那么就变成了10个板取2个，所以一共有 c10 2=45 例17. 有一类自然数，从第四个数字开始，每个数字都恰好是它前面三个数字之和，直至不能再写为止，如2349，1427等等，这类数共有几个？ 解析：跟例16一样，只是变成了a+b+c <=9的情况， 1 -1- 1 -1 -1 -1 -1 -1 -1 - - - 这里a不能为0，而b,c均可以为0，9个1，8个空，插入3个板，分成4个部分，a,b,c分别取前3部分，不管怎么插，第二组不可能取空，这时候就需要添板来处理了，在第9个1后面添加1个板，此时同样不能满足b取0，那么继续添加第10个板，此时当取到第10个板的时候，刚好可以满足第二组可以取空的情况，即b=0，然而此时还不能满足C取0的情况，故而继续添加第11个板，设取到第11个板时，第三组取空，即c=0。此时就变成了11个板取3个情况所以一共有C(11,3)=165。 D．选板法 例18： 有10粒糖，如果每天至少吃一粒(多不限)，吃完为止，求有多少种不同吃法？ 解析： o - o - o - o - o - o - o - o - o - o     o代10个糖，-代表9块板 10块糖，9个空，插入9块板，每个板都可以选择放或是不放，相邻两个板间的糖一天吃掉 这样一共就是 2^9= 512 E．分类插板 例19： 小梅有15块糖，如果每天至少吃3块，吃完为止，那么共有多少种不同的吃法？ 解析：此问题不能用插板法的原因在于没有规定一定要吃几天，因此我们需要对吃的天数进行分类讨论 最多吃5天，最少吃1天 1： 吃1天或是5天，各一种吃法 一共2种情况 2：吃2天，每天预先吃2块，即问11块糖，每天至少吃1块，吃2天，几种情况？ c10 1=10 3：吃3天，每天预先吃2块，即问9块糖，每天至少1块，吃3天? c8 2=28 4：吃4天，每天预先吃2块，即问7块糖，每天至少1块，吃4天？c6 3=20 所以一共是 2+10+28+20=60 种 F．多次插板法 例20 ：在一张节目单中原有6个节目，若保持这些节目相对次序不变，再添加3个节目，共有几种情况？ 解析：6个节目之间5个空，加上两端的2个，共是7个空，用一个节目去插7个空位，再用第二个节目去插8个空位，用最后个节目去插9个空位 所以一共是 C(7,1)*C(8,1)*C(9,1)=504种 十. 关于a+b+c<=10以及a+b+c+d<=10的问题。 例21. 求a+b+c<=10 ，a+b+c+d<=10 ，这两个不等式的非负整数解各有几种？ 对于此类题目，比如a+b+c<=10的情况可以看成是将10个1分成4部分，前面的3部分分别代表a,b,c,这里要分成4部分来取前面3部分，主要是考虑到小于10的情况，然后在将这3部分放入到3个盒子里面，可以预先在3个盒子中均放入1个元素，那么就可以转化成：13个1分成4部分，每部分至少取1个，有几种分法？ 显然是C(13,3)=286 对于a+b+c+d<=10的一样的解法，C(14,4)=1001 十一．全错位排列 把编号 1……n的小球放到编号1……n的盒子里，全错位排列（1号球不在1号盒，2号球不在2号盒，依次类推），共有几种情况？ 设n个球全放错的情况有 s（n）种 1号盒子可以选[2,n] 共（n-1）种选择，设1号盒选择某号球后对应的错排次数是 a （n-1）个选择对应的错排次数是相同的 ，则 s（n）=（n-1）a 不妨设1号盒选择2号球 ①： 2号盒选择1号球，剩下 （n-2）个球去错排，有 s（n-2）种情况 ②： 2号盒不选择1号球，则后面总有一个盒子选择1号球，我们可以把1号球换成2号球， 对问题没有影响，此时就相当于对（n-1）个球去错排，有s（n-1）种情况 于是a= s（n-1)+s(n-2) s(n)=(n-1) [ s（n-1）+s（n-2）] s(2)=1,s(3)=2 s(4)=3*(1+2)=9 s(5)=4*(2+9)=44 s(6)=5*(9+44)=265 ………… 例22．五个瓶子都贴了标签，全部贴错的可能性有多少种？ 解析：S5=4*（2+9）=44 十二.N种元素选M个的情形。 C(N+M-1,M) 例23. 幼儿园买来9种不同的籍，每个小朋友领3本，问至少几个小朋友领过后，一定会出现两个小朋友领的书是相同的？ 解析：首先要理解题目的意图，相当于是9个不同的箱子里面装有足够多的书籍，现在有n个小朋友去取，每人取3本，取法任意，当第几个小朋友取过之后，在这个取过的n个小朋友之中，一定可以找到2个人的取法一致，即这2个小朋友取的书籍是一样的，类似于抽屉原理，首先讨论各不相同的情况，在这些情况取完之后，再来1个小朋友取书籍，不管其怎么个取法，都会与前面的某个小朋友取法一致， 0 0 0 0 0 0 0 0 0— — 9个0代表不同书籍 （1） 3本都不同 c9 3，从9个0里选3个 （2）2本不同，由于需要取3本，在9个元素里面取，不管怎么取，都不可能出现只有2本不同的情况，此时就需要凑元素了，在第9个0后面插入一个元素“—”，这样就可以取到了， （3）1本不同 对应 取到0 — —，在（2）的基础上还需要插入1个元素才可以满足这种情况，2个—必须取到，而0有9种取法，所以是C(9,1)， 进行到（3）的时候，插入了2个元素，逆回到（2），在（2）中，“—”的取法就出现了2种，所以（2）应为：C(9,2)*C(2,1) 3种情况相加：C(9,3)+C(9,2)*C(2,1)+C(9,1)=165, 直到目前，各不相同的情况已经讨论完毕，假设此之后再来一个小朋友取书，那么这个小朋友的取法必然是前面165种之中的任意一种，所以满足条件的取法是：165+1=166，一种取法对应1个小朋友，所以在第166个小朋友取过之后，一定会出现2个小朋友取的书籍一致的情况。 利用公式就是：C(9+3-1,3)+1=166 例24. 幼儿园买来9种不同的书籍，每个小朋友领5本，问至少几个小朋友领过后，一定会出现两个小朋友领的书是相同的？ 解析：0 0 0 0 0 0 0 0 0 - - - - （1）5本不同，从9个0里选5个 ，C(9,5)=126 （2）4本不同(选了4个0），可能第1或第2或第3或第4 个0取到2本，分别对应0000 - （有4个-可选，对应前面4个0）, C(9,4)× C(4,1)=504 （3）3本不同(选了3个0），还有2本分配到3个位置，有6种情况，选了3个0，再从4个-里选2个-，也是C(4,2)=6，对应了前面6种分类,C(9,3)×C(4,2)（插板法）=504 （4）2本不同(选了2个0），还有3本分配到2个位置，有4种情况，选了2个0，再从4个-里选3个-，c4 3=4 对应了前面4种分类, C(9,2)×C(4,1)（插板法）=144 （5）1本不同(选了1个0），选了一个0，还要从4个-里选4个-，c4 4=1，与前面一一对应，C（9，1） 所以从13个空里选 5个的算法 包括了上述的5种分类，且不遗漏，不重复，答案是C(13,5)+1=1288 十三. 篮球传接球回到初始人的次数问题 四人进行篮球传接球练习，要求每人接球后再传给别人。开始由甲发球，并作为第一次传球，若第五次传球后，球又回到甲手中，则共有传球方式多少种? ………………………… 先考虑 m个人进行传球，甲第一次传球，传了2次，最后回到甲的次数是多少？ 把m个人分成2类，甲和非甲，回到(m-1)个非甲的次数显然是相同的，因为他们彼此不具有特殊性 传了2次，回到甲的次数 a=（m-1）×1，总的传球方式b=（m-1）^2 回到非甲的次数c= （b-a)/ (m-1)= m-1-1=a-1 即回到甲的次数比回到非甲的次数多1 如果是传了3次的情况，考虑 回到甲 和回到乙 （代表非甲）的次数 1 甲传乙，持球人是乙，再传2次，由上面的讨论可知，回到乙的次数比甲的次数多1 2 甲传给 非乙 球回到甲，乙的次数相同（ 因为此时甲乙都不是持球人，是对称的） 所以传3次的情况是 回到乙的次数比回到甲次数多1，即回到 甲次数比 非甲 的次数 少1 由归纳法，可知： 球传了奇数次 回到甲的次数比回到非甲的次数 少1 球传了偶数次 回到甲的次数比回到非甲的次数 多1 因此，对于一般的问题， m个人传球，甲第一次传，传了n次，球又回到甲手中，有几种方式？ 设有x种方式，则 x+（m-1）（x+1）=（m-1）^n n为奇数 x+（m-1）（x-1）=（m-1）^ n n为偶数 十四．环形排列组合。 ,环形排列相对于直线排列缺少的就是参照物.第一个坐下来的人是没有参照物的,所以无论做哪个位置都是一样的. 所以从这里我们就可以看出 环形排列的特征是 第一个人是做参照物,不参与排列. 例25. 李先生与其太太有一天邀请邻家四对夫妇共10人围坐一圆桌聊天，试求下列各情形之排列数：  （1）男女间隔而坐。　　 （2）主人夫妇相对而坐。　 （3）每对夫妇相对而坐。  （4）男女间隔且夫妇相邻。 （5）夫妇相邻。　 （6）男的坐在一起，女的坐在一起。 解析：(1)先让5个男的或5个女的先坐下来 全排列应该是 P44, 空出来的位置他们的妻子(丈夫), 妻子(丈夫)的全排列这个时候有了参照物所以排列是P55 答案就是 P44*P55=2880种 (2)先让主人夫妇找一组相对座位入座 其排列就是P11(记住不是P22 ),这个时候其他8个人再入座,就是P88,所以此题答案是 P88 (3)每对夫妇相对而坐,就是捆绑的问题.5组相对位置有一组位置是作为参照位置给第一个入座的夫妇的,剩下的4组位置就是P44, 考虑到剩下来的4组位置夫妇可以互换位置即 P44*2^4=384 (4)夫妇相邻,且间隔而坐. 我们先将每对夫妇捆绑 那么就是5个元素做环形全排列 即P44 这里在从性别上区分 男女看作2个元素 可以互换位置 即答案是P44*2=48种(值得注意的是,这里不是*2^4 因为要互换位置,必须5对夫妇都得换 要不然就不能保持男女间隔) (5) 夫妇相邻 这个问题显然比第4个问题简单多了,即看作捆绑 答案就是P44 但是这里却是每对夫妇呼唤位置都可以算一种方法的. 即 最后答案是P44*2^5 (6)先从大方向上确定男女分开座,那么我们可以通过性别确定为2个元素做环形全排列.即P1,1 , 剩下的5个男生和5个女生单独做直线全排列 所以答案是P1,1 *P55*P55 十五.几个容易混淆的题目， ①8个相同的球放进3个相同的盒子里，每盒至少一个，有几种方法 ②8个相同的球放进3个不同的盒子里，每盒至少一个，有几种方法 ③8个不同的球放进3个相同的盒子里，每盒至少一个，有几种方法 ④8个不同的球放进3个不同的盒子里，每盒至少一个，有几种方法 ⑤8个相同的球放进3个相同的盒子里，有几种方法 ⑥8个相同的球放进3个不同的盒子里，有几种方法 ⑦8个不同的球放进3个不同的盒子里，有几种方法 ⑧8个不同的球放进3个相同的盒子里，有几种方法 解析：①取球最少的盒子取1，取球第二少的盒子可以取[1,3] 3种 取球最少的盒子取2，取球第二少的盒子可以取[2,3] 2种 取球最少的盒子取3，此情况不存在，一共5种 按取球多寡来分类讨论可以做到不遗漏，不重复 ②插板法，C(7,2)=21 ③取球最少盒子取1时，有116，125，134三种情况，分别有c8 6=28, c8 1*c7 2=168, c8 1*c73=280 取球最少盒子取2时，有224，233二种情况，分别有c82*c62/2=210，c83×c53/2=280 一共28+168+280+210+280=966 ④3问中的966种情况，每种情况的三个元素都是互异的，比如 116（因为球是不同的），这三个元素进行全排列p33=6,乘以966=5796即为所求 ⑤最少盒子取0，次盒子取[0,4] 最少盒子取1，次盒子取[1,3] 最少盒子取2，次盒子取[2,3] 一共5+3+2=10种 ⑥预先在三个盒子种各放入一小球，则问题转化为11同球放3不同盒子，每盒至少1个，几种方法？ 用插板法，才（10，2）=45 ⑦每个球都有3种选择，8个球就有3^8=6561 ⑧7问中的一般情况(3个元素都相异），比如116，一共有6种排列（球是不同的），此问中，盒子是相同的，因此这6种排列都只算一种情况。 但如果2个元素相同的时候，有且只有 008，只有3种排列，我们多添加3种进去，令其也重复6次，则（6561+3）就是 所有的情况都重复了6次，（6561+3）/6=1094即为所求。 针对第8问，还有一种方法： 如果有8个不同的小球放进3个相同的盘子 第一行数列就写8个1，就是：1，1，1，1，1，1，1，1 第二行的数列的每一位数字就是本行的前一位数字*2+上一行的对应数字，然后写7组 （7个空），也就是：1，3，7，15，31，63，127 第三行的数列的每一位数字就是本行的前一位数字*3+上一行的对应数字，然后写6组（第二列6个空），也就是：1，6，25，90，301，966 然后把最后的3个数字加起来，即为所求， 但是如果是8个不同小球放进3个相同盘子，每个盘子至少放一个，这时就是第三行数列的最后一个数字，即966，与第三问一致！ 十六. N个不同的小球，放进M个相同的盘子 例题解析：10个不同的球放到4个相同的盒子,求各种不同的方法总数? 解析：A.常规解法： ①每个球4种方法，总的放法是4^10, ②每个盒子都放球，对应XYZT，全排列是P(4,4)=24，由于盒子相同，所以这24种只能算1种，即重复了24次， ③2个盒子为空， 对应00XY，有5种情况，每种重复12次 0019 C(10,1)=10 0028 C(10,2)=45 0037 C(10,3)=120 0046 C(10,4)=210 0055 C(10,5)/2=126 （10+45+120+210+126）*12=6132，加上6132种情况，让其也重复24次 ④3个盒子为空，即0，0，0，10的情况，只有4种，再加上20，让这种情况也重复24次 所以最终结果=(4^10+6132+20)/p(4,4) =43947 B.特殊解法 4个盒子，写4个数列 第一列：1 1 1 1 1 1 1 1 1 1 第二列：1 3 7 15 31 63 127 255 511 第三列：1 6 25 90 301 966 3025 9330 第四列：1 10 65 350 1701 7770 34105 结果就=1+511+9330+34105 =43947 如果将题目改为：10个不同的球放到4个相同的盒子,要求每个盒子至少一个球，求各种不同的方法总数? 那么答案就是第四列的尾数，即为34105 陶泽友于2010.7.2深夜整理