排列组合问题的解答策略.doc

排列组合问题的解答策略 天门市高中复读中心 王克进一、排列组合综合应用的一般方法在解决实际问题中，要认真审题，分清是排列还是组合，有序排列，无序组合。（1）直接法。对于存在特殊元素或特殊位置的排列组合问题，从特殊入手，先满足特殊元素或特殊位置，再满足其他元素或位置。（2）间接法（正难则反）。对于某些排列组合问题，正面情况比较复杂，而反面情况比较简单，可先不考虑限制条件，计算出排列组合总数，再减去其反面情况的排列组合数。例11名老师和4名学生排成一排照相留念，若老师不排在两端，共有多少种排法？解法1：（特殊元素法）老师在中间的三个位置上任选一个位置的选法有种，然后4名学生在剩余的位置上排列，排法有种，所以共有=72种。解法2：（特殊位置法）先安排两端站2名学生，有种方法，其余位置的排法有种方法，所以排法种数是=72种。解法3：（间接法）先把1名老师和4名学生全排法有种，老师排在两端排法有种，所以排法种数是=72种二、常见的排列问题1、含有特殊元素，特殊位置问题特殊优先法对于带有特殊元素、特殊位置的排列问题，一般应先考虑特殊元素、特殊位置，再考虑其他元素与位置，即特殊优先法。2、相邻问题捆绑法对于某几个元素要求相邻的排列问题，可将相邻的元素捆绑在一起看作一个“元”，与其他元素排列，然后松绑对“元”内部元素排列。例26名同学排成一排，其中甲、乙两人必须排在一起的不同排法有（ ）种。A、720种 B、360种 C、240种 D、120种解析： 选C3、“小团体”排列问题捆绑法对于“小团体”排列问题，可先将“小团体”捆绑看作一个元素与其余元素排列，最后再进行“小团体”内部的排列。例36名同学排成一列，甲乙之间恰好隔两人，有多少种不同排法？解：先从甲乙以外的4人中任选2人排在甲乙之间的两个位置上有种，然后把甲、乙及中间2人看作一个“大”元素与余下2人全排有种方法，最后对甲乙进行排列有种方法。故共有=144种4、不相邻问题插空法对于某几个元素不相邻的排列问题，可先将其他元素排好，然后将不相邻元素在已排好的元素之间和两端插入即可。例45个男生和3个女生排成一排，要求女生不相邻且不可排在两头，共有几种排法。解：先排无限条件的5个男生有种排法，由于女生不相邻且不可排两头，故3个女生只能分别插在5个男生的4个空隙中有种。故共有=2880种。5、定序问题先排后除（或只选不排）对于某几个元素顺序固定的排列问题，可先把这几个元素与其他元素一同排列，然后除以定序元素的全排；或先在总体位置中选出定序元素的位置不参加排列，然后对其他元素进行排列。例55人并排站成一排，甲必须站在乙的左边（甲乙可以不相邻），则不同的排法有多少种？解法1：（先排后除）种解法2：（只选不排）=60种6、重排问题先排后除（或只选不排）含有相同元素重复排列的问题，可先把重复元素与其他元素一同排列然后用总排列数除以重复元素的全排列数，或在总体位置中选出重复元素的位置不参加排列，然后对其他元素进行排列。例6把拼成“success”这个单词的各字母作各种排列有多少种拼法？解法1：（先排后除）种解法2：（只选不排）种7、分排问题直排处理把n个元素排成前后若干排的排列问题，若没有其他特殊要求，要采取统一排成一排的方法处理，若每排有特殊要求，把每排首尾都连排成一排，只需分段考虑特殊元素，然后对其他元素作统一排列。例79人排成3行，每行3人，其中甲乙丙3人要排在同一行，有多少种不同排法？解：种8、混合问题先选后排对于排列组合混合问题，先用组合选取元素，再进行排列。例8从黄瓜、白菜、芹菜、扁豆4种蔬菜品种中选出3种分别种在不同土质的三块土地上，其中黄瓜必须种植，不同的种植方法有（ ）种。A、24 B、18 C、12 D、6解：先选后排有种不同选法，不同种法有种，故不同种植方法有种，故选B。9、不到位问题及错位问题容斥原理不到位问题：编号为1，2，3n的n个球放入编号为1，2，3n的n个盒子中，其中1，2，3m（mn）号球，不放入1，2，3m号盒子的放法种数为例96名同学排成一排，甲不站在左端，乙不站右端，有多少种站法。错位问题：编号为1，2，3n的n个球放入编号为1，2，3n的n个盒子，则球号与盒子全不相同的放法种数为：例10同室四人各写一张贺年卡，先集中起来，然后每人从中拿一张别人写的驾年卡，则四张贺年卡不同分配方式有（ ）A、23种 B、22种 C、9种 D、6种三、常见的组合问题1、遇到“至少”、“最多”“含”等词要认真审题理解题意。例11某球队有2名队长和10名队员，现派6人上场参加比赛，如果场上最少有1名队长，那么共有多少种不同的选法。直接法：种间接法：种2、分组与分配有区别，分组只分成组，分配即先分组后分到人。3、分组问题不均分组问题：由于各组数目都不相等，所以按组合数直接取。均分组问题：一般地将km个不同元素分成k组，每组m个元素的不同分法分法=部分均分组问题：先将不均分的那一部分直接取出，然后将剩下部分均分组。例12将6本不同的书按下列要求分成三份，各有多少种分法。（1）分成三份，1份1本，1份2本，1份3本；（2）平均分成三份，每份2本；（3）分成三份，1份4本，另两份各1本。解：（1） （2） （3）4、不同元素的分配按需分配即定人又定数直接取，也可先分组后分配。例13将6本不同的书按下列要求分给甲乙丙三人。（1）甲得1本，乙得2本，丙得3本；（2）平均分配给甲乙丙三人，每人2本；（3）甲乙丙三人中，一人得1本，一人得2本，一个得3本。解：（1） （2）解法1 解法2 （3）5、相同元素的分配（指标、名额等）隔板法处理。将N个相同的元素分成k（Nk）个部分，每个部分至少含一个元素的分法为：先将N个元素排成一排，在它们之间（N-1）个空隙中插入（k-1）个隔板，共有种插法，每一种插法对应着一种符合题意的分法；但若允许有组无元素，把（k-1）个隔板当作元素与N个元素并排成一排，从（N+k-1）个位置中选（k-1）个位置放隔板即可，分法为例14方程有多少组正整数解。解：将20个1排成一排，在中间19个空隙中插入2个隔板有 分法：即有171组正整数解。方程有多少组非负整数解。解：将20个1与2个隔板排成一排,在22个位置中选2个位置放隔板有 分法：即有231组非负整数解。6、等价转化将原组合问题转化成另一个问题，通过对新问题的研究达到解决原问题的目的。例1510级楼梯，要求7步跨完，且每步可跨1级或2级，问有多少种不同的跨法？解：设有x步跨1级，y步可跨2级7步中选4