论文部分内容阅读
排列组合问应用题高考中多以客观题出现，每年必考。它们具有较强的灵活性和抽象性，故解题时要求我们认真地审题，对题目中的信息进行科学地加工与处理。本文说明几种常见的解法：
一、直接法
例1：n个人参加某项资格考试，能否通过，有多少种可能的结果？
解法1：用分类计数原理。没有人通过，有C0n种结果；1个人通过，有C01种结果，……；n个人通过，有Cnn种结果。所以一共有C0n C1n …Cnn=2n种可能的结果。
解法2：用分步计数原理。第一个人有通过与不通过两种可能，第二个人也是这样，……，第n个人也是这样。所以一共有种可能的结果。
二、间接法（排除法）
例2.8个人站成一排，其中A与B、A与C都不能站在一起，一共有多少种排法？
解：无限制条件有A88种排法。A与B或A与C在一起各有A22A77种排法，A、B、C三人站在一起且A在中间有A22A66种排法，所以一共有A88-2A22A77 A22A66=21600种排法。
例3：以一个长方体的顶点为顶点的四面体的个数。
解：从8个点中取4个点，共有C48种方法，其中取出的4个点共面的有6 6=12种，所以符合条件的四面体的个数为个C48-12=58个。
三、特殊元素（位置）法
例4：从0，1，……，9这10个数字中选取数字组成偶数，一共可以得到不含相同数字的五位偶数多少个？
解：个位选0，有A49个，个位不选0且万位不能选0，有C14C18C38个，所以一共可以得到A49 C14C18C38=13775个偶数。
例5：8人站成两排，每排4人，甲在前排，乙不在后排的边上，一共有多少种排法？
解：先排甲，有A14种排法。再排乙，有A15种排法，再排其余的人，又有A66种排法，所以一共有A14A15A66=14400种排法。
四、查字典法
例6：由0，1，2，3，4，5六个数字可以组成多少个无重复数字且比324105大的数？
解：（1）查首位，有4×××××与5×××××，共有2A55个；（2）查头两位，有34××××与35××××两种，共有2A44个；（3）查头三位，有325×××一种，共A33个；（4）查头四位，有3245××，共A22个；（5）查头五位，仅324150一个，故共有2A55 2A44 A33 A22 1=297个。
五、捆绑法（当需排元素中有必须相邻的元素时）
例7：8人排成一排，甲、乙必须分别紧靠站在丙的两旁，有多少种排法？
解：把甲、乙、丙先排好，有A22种排法，把这三个人“捆绑”在一起看成是一个，与其余5个人相当于6个人排成一排，有A66种排法，所以一共有A22A66=1440种排法。
六、插空法（当需排元素中有不能相邻的元素时）
例8：从6名男工和4名女工中选3男2女担任5种不同工作，有多少种不同的排法？
解：第一步，5男全排列，有A55种，第二步，在5男之间（包括两端）的6个空档中插入4女，有A46种，故得种A55A46=43200种。
注：捆綁法与插入法一般适用于有如上述限制条件的排列问题。
七、除序法（平均分组法）
例9：10个人排成一队，其中甲一定要在乙的左边，丙一定要在乙的右边，一共有多少种排法？
解：甲、乙、丙三人排列一共有A33种排法，在这A33种排法中各种排列顺序在10个人的所有排列中出现的机会是均等的，因此符合题设条件的排法种数为A1010A33=604800。
例10：用1，2，3，4，5，6，7这七个数字组成没有重复数字的七位数中，（1）若偶数2，4，6次序一定，有多少个？（2）若偶数2，4，6次序一定且奇数1，3，5，7次序也一定，有多少个？
分析：这1，2，3，4，5，6，7七个数字全排列有A47个，而2，4，6之间的排列数A33在次序一定时只能算作一种，同理，1，3，5，7之间的排列数A44也只能算一种。
解：（1）A77A33=A47个；（2）A77A33A44=C47个。
八、隔板法
例11：20个相同的球分给3个人，允许有人可以不取，但必须分完，有多少种分法？
解：将20个球排成一排，一共有21个空隙，将两个隔板插入这些空隙中（两个隔板可以插在同一空隙中），规定由隔板分成的左、中、右三部分球分别分给3个人，则每一种隔法对应了一种分法，每一种分法对应了一种隔法，于是分法的总数为C221=210种方法。
九、合并单元格法（染色问题宜用此法）
例12：如图，一个地区分为5个行政区域，现给地图着色，要求相邻区域不得使用同一颜色，现在四种颜色可供选择，则不同的染色方法有多少种？
分析：颜色相同的区域可能是2、4或3、5。
解：（1）当2、4同色而3、5不同色时，将2、4合并成一个单元格，此时不同的着色方法相当于4个元素的全排列数A44种；
（2）当2、4不同色而3、5同色时，同理可得有A44种；
（3）当2、4与3、5分别同色时，将2、4，3、5分别合并，这样仅有三个单元格，从4种颜色中选3种来着色这三个单元格，共有C34A33种。
由分类计数原理可知：不同的着色方法共有2A44 C34A33=72种。
十、转化命题法
例13：一个楼梯共10级台阶，每步走1级或2级，8步走完，一共有多少种走法？
解：10级台阶，要求8步走完，并且每步只能走一级或2级。显然，必须有2步中每步走2级，6步中每步走一级。记每次走1级台阶为A，记每次走2级台阶为B，则原问题就相当于在8个格子中选2个填写B。其余的填写A，这是一个组合问题，所以一共有种C28=28走法。
例14：圆周上共有15个不同的点，过其中任意两点连一弦，这些弦在圆内的交点有多少个？
解：因两弦在圆内若有一个交点，则该交点对应于一个以两弦的四端点为顶点的圆内接四边形，则问题转化为用圆周上的15个不同的点能构成多少个圆内接四边形。因此这些弦在圆内的交点最多有C415=1365个。
一、直接法
例1：n个人参加某项资格考试，能否通过，有多少种可能的结果？
解法1：用分类计数原理。没有人通过，有C0n种结果；1个人通过，有C01种结果，……；n个人通过，有Cnn种结果。所以一共有C0n C1n …Cnn=2n种可能的结果。
解法2：用分步计数原理。第一个人有通过与不通过两种可能，第二个人也是这样，……，第n个人也是这样。所以一共有种可能的结果。
二、间接法（排除法）
例2.8个人站成一排，其中A与B、A与C都不能站在一起，一共有多少种排法？
解：无限制条件有A88种排法。A与B或A与C在一起各有A22A77种排法，A、B、C三人站在一起且A在中间有A22A66种排法，所以一共有A88-2A22A77 A22A66=21600种排法。
例3：以一个长方体的顶点为顶点的四面体的个数。
解：从8个点中取4个点，共有C48种方法，其中取出的4个点共面的有6 6=12种，所以符合条件的四面体的个数为个C48-12=58个。
三、特殊元素（位置）法
例4：从0，1，……，9这10个数字中选取数字组成偶数，一共可以得到不含相同数字的五位偶数多少个？
解：个位选0，有A49个，个位不选0且万位不能选0，有C14C18C38个，所以一共可以得到A49 C14C18C38=13775个偶数。
例5：8人站成两排，每排4人，甲在前排，乙不在后排的边上，一共有多少种排法？
解：先排甲，有A14种排法。再排乙，有A15种排法，再排其余的人，又有A66种排法，所以一共有A14A15A66=14400种排法。
四、查字典法
例6：由0，1，2，3，4，5六个数字可以组成多少个无重复数字且比324105大的数？
解：（1）查首位，有4×××××与5×××××，共有2A55个；（2）查头两位，有34××××与35××××两种，共有2A44个；（3）查头三位，有325×××一种，共A33个；（4）查头四位，有3245××，共A22个；（5）查头五位，仅324150一个，故共有2A55 2A44 A33 A22 1=297个。
五、捆绑法（当需排元素中有必须相邻的元素时）
例7：8人排成一排，甲、乙必须分别紧靠站在丙的两旁，有多少种排法？
解：把甲、乙、丙先排好，有A22种排法，把这三个人“捆绑”在一起看成是一个，与其余5个人相当于6个人排成一排，有A66种排法，所以一共有A22A66=1440种排法。
六、插空法（当需排元素中有不能相邻的元素时）
例8：从6名男工和4名女工中选3男2女担任5种不同工作，有多少种不同的排法？
解：第一步，5男全排列，有A55种，第二步，在5男之间（包括两端）的6个空档中插入4女，有A46种，故得种A55A46=43200种。
注：捆綁法与插入法一般适用于有如上述限制条件的排列问题。
七、除序法（平均分组法）
例9：10个人排成一队，其中甲一定要在乙的左边，丙一定要在乙的右边，一共有多少种排法？
解：甲、乙、丙三人排列一共有A33种排法，在这A33种排法中各种排列顺序在10个人的所有排列中出现的机会是均等的，因此符合题设条件的排法种数为A1010A33=604800。
例10：用1，2，3，4，5，6，7这七个数字组成没有重复数字的七位数中，（1）若偶数2，4，6次序一定，有多少个？（2）若偶数2，4，6次序一定且奇数1，3，5，7次序也一定，有多少个？
分析：这1，2，3，4，5，6，7七个数字全排列有A47个，而2，4，6之间的排列数A33在次序一定时只能算作一种，同理，1，3，5，7之间的排列数A44也只能算一种。
解：（1）A77A33=A47个；（2）A77A33A44=C47个。
八、隔板法
例11：20个相同的球分给3个人，允许有人可以不取，但必须分完，有多少种分法？
解：将20个球排成一排，一共有21个空隙，将两个隔板插入这些空隙中（两个隔板可以插在同一空隙中），规定由隔板分成的左、中、右三部分球分别分给3个人，则每一种隔法对应了一种分法，每一种分法对应了一种隔法，于是分法的总数为C221=210种方法。
九、合并单元格法（染色问题宜用此法）
例12：如图，一个地区分为5个行政区域，现给地图着色，要求相邻区域不得使用同一颜色，现在四种颜色可供选择，则不同的染色方法有多少种？
分析：颜色相同的区域可能是2、4或3、5。
解：（1）当2、4同色而3、5不同色时，将2、4合并成一个单元格，此时不同的着色方法相当于4个元素的全排列数A44种；
（2）当2、4不同色而3、5同色时，同理可得有A44种；
（3）当2、4与3、5分别同色时，将2、4，3、5分别合并，这样仅有三个单元格，从4种颜色中选3种来着色这三个单元格，共有C34A33种。
由分类计数原理可知：不同的着色方法共有2A44 C34A33=72种。
十、转化命题法
例13：一个楼梯共10级台阶，每步走1级或2级，8步走完，一共有多少种走法？
解：10级台阶，要求8步走完，并且每步只能走一级或2级。显然，必须有2步中每步走2级，6步中每步走一级。记每次走1级台阶为A，记每次走2级台阶为B，则原问题就相当于在8个格子中选2个填写B。其余的填写A，这是一个组合问题，所以一共有种C28=28走法。
例14：圆周上共有15个不同的点，过其中任意两点连一弦，这些弦在圆内的交点有多少个？
解：因两弦在圆内若有一个交点，则该交点对应于一个以两弦的四端点为顶点的圆内接四边形，则问题转化为用圆周上的15个不同的点能构成多少个圆内接四边形。因此这些弦在圆内的交点最多有C415=1365个。