公务员 排列组合入门.doc

排列：由上面两道题入手：排列就是从p中选出k个元素出来进行排列A（p，k）就是p递减相乘，直到第k个数，p*(p-1)*(p-2)例如说A(3,2)=3*2 A(100,99)=100*99*98*97*2A（7，4）=7*6*5*4 A（7，2）=7*6，比较好理解吧？我们用下面两道题进行练习：组合：同样，我们还是以题目来引入Eg：从三个同学中选出两个来参加乒乓球赛，有多少种选择呢？可以是这样：ab ac bc一共有三种所以我们可以得出这样的结论：组合就是从p个元素中选出k个出来，但是不需要进行排列！而具体计算是怎样的呢？C（5，1）=5/1=5 C（8，2）=8*7/（2*1） C（8，6）=（8*7*6*5*4*3）/（6*5*4*3*2*1）我们以下面习题来练习：而且还有一个小公式：也就是c（8，1）=c(8,7) c(11,3)=c(11,8) 这样的话我们在计算的时候就可以简化很多了，例如c（9，8）如果按照常规的话就得计算得很长了，通过上面那个小公式我们就可以知道C（9，8）=c（9，1）=9习题：插板法：简单点说就是相同的一堆东西在那里，放在那里（形成n-1个空），我们通过插一块板，两块板，三块板，四块板一直到n-1块板（n是这堆东西的个数，比如说一堆苹果有2个，那么我们最多只能放一块板进去把他分成两堆）插板法的前提是每堆至少一个，那么假如没有说要每堆至少一个呢？（我们可以自己构造，等一下会讲到）Eg：将十台电脑分给三个学校，每个学校至少一台，试问有多少分法呢？要分成三堆，那么就要放进去两块板，而十台电脑一共构成了多少个空呢？9个所以就是c（9，2）易错题：有8个相同的球放到三个不同的盒子里，共有（ ）种不同方法.很多人可能会直接用c（7，2）来做吧？但是这道题，并没有告诉我们说每个盒子至少要分到一个球啊？这个时候我们可以来构造成“至少一个”，我们往这八个球再加多三个进去，等一下分成“每堆至少有一个了”，在分好之后我们在各堆抽出一个出来，就行了，这个时候就符合了插板法了，c（10，2）=45还有一种题是这样的：往编号为123这三个盒子放15个球，要求每个球的个数不能少于盒子的编号，这样的题同样我们也是可以通过构造插板法来做，首先我们往这三个盒子里面放进去0 1 2个球，那么再加上等一下每个盒子至少一个球，就绝对会超过他们编号数，这样插板法不是又构造出来了吗？c（11，2）二项式定理：为什么要讲到这个呢？跟我们接下来的一道题有关，上面这个公式我们观察发现假如我们把a设定为1，b也设定为1的话，那么（a+b）N=2N=c（n，0）+c（n，1）+c（n，n）就是这道题：有10粒苹果，每天至少吃一粒，有几种吃法？每天至少一粒，我们还是用插板法来做，十个苹果有九个空，假如是一天吃完的话那就是插进去0块板，两天吃完的话就是插进去1块板知道分十天吃完插进去九块板那么就是c（9,0）+c（9,1）+c(9,2)+c(9,3)C(9,9)=29以下是一些真题以及其他习题：1. 某单位有三名职工和六名实习生需要被分配到ABC三个地区进行锻炼，每个地区分配一名职工和二名实习生，刚不同的分配方案有多少种？解析：职工到不同地方A(3,3)，然后三个地区每个地区选两人则是c（6，2）c（4，2）c（2，2），所以结果就是A(3,3)*(C6,2)*C(4,2)，因为c（2，2）这里等于1，写不写都无所谓2. 某单位今年新进了3个工作人员，可以分到3个不同的部门，但是每个部门最多只能接收两个人，问，共有几种不同的分配方案？解析：这道的话我们用极端的方法来做，题目说到最多只能接收2个人，本来如果不限制说只能接受最多两个人的话，每个人的选择都是3，那么一共有3*3*3=27中组合，我们再减去3个人都在同一个部门的情况（有三种），那剩下的就是最多两个人咯，所以是27-3=243. 5男4女排成一排，要求男生必须按从高到矮的顺序，共有多少种不同的方法? （曾经做错过的题）解析：刚才我们上面学习了插板法，大家理解一些，这里用的这一种叫插空法，五个男在站在那里，那么形成的空加上旁边的空一共有6个，下面图示男 男 男 男 男 那么四个女生只需要逐个往着六个逐渐站进去就行了，第一个女生站进去的时候有6个选择（当这个女生站进去了之后，空就成了7个了），同意，依次7 8 9所以最终答案就是6*7*8*9也可以换一种思路，就是这九个人同时在那里排列，有A（9，9），而五个男生排列有A(5,5)而且从高到低只有一种，所以A(9,9)/ A(5,5)等一下也是9*8*7*6（类似题） 一张节目表上原有3个节目，如果保持这3个节目的相对顺序不变，再添进去2个新节目，有多少种安排方法？（08国考）A.20 B.12 C.6 D.44. 厨师从12种主料中挑出2种，从13种配料中挑选出3种来烹饪某道菜肴，烹饪的方式共有7种，那么该厨师最多可以做出多少道（09国考）不一样的菜肴A.131204 B.132132 C.130468 D.133456解析：c12 2*c13 3*7=6*11*13*2*11*7尾数是2，直接选b，或者看哪一个数能被3整除也是选b6. 有6个不同的徽章分给4个人有几种分法？有6个相同的徽章分给4个人有几种分法？解析：1.因为这里徽章是不同的，那么相对于徽章来说，他们的选择对象都是四个，所以就是4*4*4*4*4*4=46 2.这里徽章是相同的，但是因为构不成插板法的条件（插板法的条件是个体一样，而且最少一个），所以我们在这里要构造出插板法的条件出来，也就是说先加4个，然后每人至少一个，等一下分好后再拿掉四个，所以呢就是c9 37. 10个人坐成一个圆圈，问不同坐法有多少种？解析：一开始我们这样看，别看成圆圈的，假如十个人做成一排一共有多少种排列呢？a10 10，这里被坐成圆圈了，所以等一下有十种情况重复了，所以结果要除以10a10 10/10=a9 9或者这样看，我们先固定住一人，剩下九人相对于这个人来进行排列，也就是a9 98. 用1、2、3、4、5、6、7、8、9组成数字不重复的九位数，但要求1排在2前面，求符合要求的九位数的个数。解析：直接A9 9，然后因为1要嘛在2前面要嘛在后面，所以直接A99/2就可以了9. 7个人坐成一排照像, 其中甲、乙、丙三人的顺序不能改变且不相邻, 则共有多少排法解析：假设剩余的四人已经站好在那里了，那么四个人一共形成了5个空格，我们只需要在做五个空格里面选三个空格让人站进去就行了，而因为这里甲乙丙三人顺序不能改变了，所以我们不用再乘以a33什么的了。10. 一排共9个座位，甲、乙、丙三人按如下方式入座，每人左、右两旁都有空座位，且甲必须在乙、丙两人之间，则不同的坐法共有几种解析：这道题跟上面有点不一样的地方就是，每人左右两旁要有空座位，那么我们抽3人出来后，剩下6个座位，六个座位之间（是他们之间，并不包括旁边两个空）的空就是5，在这五个空里面选三个c53，然后因为甲必须在乙，丙中间，所以只有乙甲丙，丙甲乙这两种情况而已，所以就是c53*2=2011. 将9个学生分配到甲乙丙三个宿舍，每宿舍至多四人（床铺不分次序），则不同的分配方法有：A.3710 B.11130 C.21420 D.9!解析：因为九个学生，每间宿舍最多4人，那么可以是这样3 3 3或者是2 3 4或者441先分堆，然后再乘以a33c94*c54*c11/a22+c93*c63*c33/a33+c94*c53*c22所以结果就是（c94*c54*c11/a22+c93*c63*c33/a33+c94*c53*c22）*a33曾经我们为之奋斗过 QQ群95036772 隔板法及其隔板法的应用基础题型：将n个相同元素分给m个不同对象（nm），每个对象至少有一个元素，由C（n-1，m-1）种方法。 解析：本题型可描述为n-1个空中插入m-1块板，共有C（n-1，m-1）种方法。此种解法称为隔板法。下面通过几个例题体会一下隔板法的应用。 例1 从5个学校选出8名学生组成代表团，每校至少有一人的选法种数是多少？ 解析：按常规，从5个学校选8名学生，要考虑5个学校人员的分配，需要分类讨论，太繁琐。逆向思考，假设8名学生的代表团已组建好，现将其返回到5个学校， 每校至少一人，用“0”表示学生，如图， 00000000 问题转化为将8个学生分成5组，每组至少一人，在上图中，7个空档中插入4块隔板即可将其分成5组，故有C（7，4）=35种选法。 例2 20个不加区别的小球放入编号为1号、2号、3号的三个盒子里，要求每个盒内的球数不小于盒子的编号数，问有多少种放法？ 解析：先取出3个球，其中1个球放入2号盒内，再将其余的2个球放入3号盒内。则此题转化为17个球放入3个不同盒内，每盒至少一球，有多少种放法？即16个空档中插入2个隔板即可将其分成3组，故有C（16，2）=120种放法。 例3 (1)12个相同的小球放入编号为1、2、3、4的盒子中，问每个盒子中至少有一个小球的不同放法有多少种? (2)12个相同的小球放入编号为1、2、3、4的盒子中，每盒可空，问不同的放法有多少种? (3)12个相同的小球放入编号为1、2、3、4的盒子中，要求每个盒子中的小球数不小于其编号数，问不同的放法有多少种? 解：(1)将12个小球排成一排，中间有11个间隔，在这11个间隔中选出3个，放上“隔板”，若记作“1”看作隔板，则如图001000010000100隔板将一排小球分成4块，从左到右可以 看成4个盒子放入的球数，即上图中1、2、3、4四个盒子相应放入2个、4个、4个、2个小球，这样每一种隔板的插法，就对应了球的一种放法，即每一种从11个间隔中选出了3个间 隔的组合对应于一种放法，所以不同的放法有C（11，3）=165(种)。 (2)先借4个球分别放入4个盒子里，此题转化为把把16个球放到4个盒子里，每个盒子至少要有一个球，不同的放法有多少种？由隔板法可知：C(15,3)=455种。(3)解法一：用(1)的处理问题的方法。 将1个、2个、3个小球放入编号为2、3、4的盒子中，将余下的6个小球放在4个盒子中，每个盒子至少一个小球，据(1)有C(5,3)=10(种)。 解法(2)：用(2)的处理问题的分法。 将1个、2个、3个、4个小球分别放在编号为1、2、3、4的盒子中，将余下的2个小球放在四个盒子中，每盒允许有空盒，据(2)有C(5,3)=10(种)。 不小心搜到一个05年的人教论坛高中数学版块的问题，正好练练手。隔板法：盒子可空与不可空解法有没有区别？10个相同球，放入4个不同盒子中。求：（1）盒子不可以空的种数（2）盒子可以空的种数 (1)直接用隔板法C（9，3）=84种方法。（2） 方法1（分类考虑（1）放入1个盒子里：1种放法。，但注意一共是4个盒子，可以放进4个盒子中的任何一个，所以共有1XC（4，1）=4种放法。（2）放入2个盒子里;相当于9个空隙里插入1个板，所以有C（9，1）=9种放法；但是共有4个盒子，可以放进去任意4个中的任意两个，所以共有9XC(4,2)=54种放法。（3）放入3个盒子里：相当于9个空隙里插入2个板，所以有C（9，2）=36种放法；但是共有4个盒子，可以放进去任意4个盒子中的3个，所以共有36XC（4，3）=144种放法。（4）放入4个盒子里：相当于9个空隙里插入3个板，所以共有C(9,3)=84种放法；所以共有4+54+144+84=286种放法。方法210个相同球，放入4个不同盒子中，求盒子可以空的种数先借4个球，每个盒子里放一个，这样就转化成14个球放进4个盒子里，每个盒子里至少有一个球，有多少种放法？直接用公式C（13，3）=286种放法。 烦人的球子问题我是看完论坛的帖子自己总结的，给大家分享，最主要是自己巩固一下：高手来指点一下我说的对不对！主要形式有八种：1、 球同、盒同、无空箱例：8个相同的球放到4个相同的箱子里面，每个箱子至少放一个，问有多少种放法？方法一：先把四个箱子分别放入一个球，还剩4个球，这四个球只能有4000 3100 2200 1210 1111 所以有五种。（包括零的正整数有几种情况加四次等于4）方法二，：更容易些，放球最少的箱子放一个球，则取球第二少的可以取1115 1124 1133 1232 四种放球最少的箱子放两个球，则取球第二少的可以取2222 一种总共：5种（此方法好处是不容易重复或漏数）。2、 球同、盒同、有空箱例：8个相同的球放到4个相同的箱子里面，可以空箱，问有多少种放法？这个如果考试遇到数字也不会太大，自己在草稿纸上画画1分钟怎么也画出来了。0008 0017 0026 0035 0044 0116 0125 0134 2222 0224 0233 1115 1124 1133 1223共15种较简便放法：放球最少的箱子取零个球，0008 0017 0026 0035 0044 0116 0125 0134 0224 0233 放球最少的箱子取一个球，1115 1124 1133 1223 放球最少的箱子取两个球，2222 共15种3、 球同、盒不同、无空箱这个是球球里面最简单的题了，也最容易理解。例：8个相同的球放到4个不同的箱子里面，每个箱子至少放一个，问有多少种放法？插板法：8个相同的球有7个空，把8个球分成4份要插3块板，所以有C73=35种4、 球同、盒不同、有空箱这个也比较容易理解例：8个相同的球放到4个不同的箱子里面，可以有空箱，问有多少种放法？还是用插板法，现在是可以有空箱子，把8个相同的球分成四份要三个插板，把插板看成是空箱子，就有C11 3=165种以