解决排列组合问题的有效策略.doc

解决排列组合问题的有效策略可以说排列组合是研究计数问题的策略学，所以解答排列组合问题要讲究策略，首先要认真审题，弄清楚是排列(有序)还是组合(无序)，还是排列与组合混合问题。其次，要抓住问题的本质特征，准确合理地利用两个基本原则进行“分类与分步”。加法原理的特征是分类解决问题，分类必须满足两个条件：(1)类与类须互斥(保证不重)，(2)总类必须完备(保证不漏)；乘法原理的特征是分步解决问题，分步必须做到步与步互相独立，互不干扰并确保连续性。分类与分步是解决排列组合问题的最基本的思想策略，在实际操作中往往是“步”“类”交叉，有机结合，可以用下面的电路图说明之(完成一件事表明“电路打通电灯亮”)。类中有步：先分类再分步，运算特征，和中有积。步中有类：先分步再分类，运算特征：积中有和。本文对几种典型的排列组合问题进行策略分析，拟找到解决相应问题的有效方法，并辅之实例说明，供参考。1特殊优先一般在后对于问题中的特殊元素、特殊位置要优先安排。在操作时，针对实际问题，有时“元素优先”有时“位置优先”。例10,2,3,4,5这五个数字，组成没有重复数字的三位数，其中偶数共有几个？简析1这里百位与个位是特殊位置，0是特殊元素。若从“元素优先”考虑，则先对0分两类。第一类：有0，再分为两类，0在个位分两步有个，0不在个位分步有Pl1个；第二类：无0，此时只有个位是特殊位置，分两步，先由2,4选排个位有个，再由其余三个元素排其余两位，由加法原理，偶数共有=30(个 )。简析2若从“位置优先”考虑，可分0在个位与0不在个位两类。0在个位有，0不在个位时，分三步，先由2,4中选一个排个位，再由3,4(2),5中选一个排百位，最后由剩下的三个数(包括0)排十位。由加法、乘法原理得偶数共有=30(个)。注意合理分类、准确分步是确保问题解决的前提，本题是“分类与分步交叉”的典型例子。2排组混合先选后排对于排列与组合的混合问题，宜先用组合选取元素，再进行排列。例24个不同的小球放入编号为1,2,3,4的四个盒内，则恰有一个空盒的放法有几种？简析因恰有一个空盒，故必有一个盒内有2个小球，(同一盒内的球是组合)，而不同的球放入不同的盒子是排列，因此，这是一个排列与组合的混合问题。可先从四个球中选出两个有种，并把这两球视为一球与其余两球分别排入四个盒内有，由乘法原理，共有种。(同一盒内的球必须一次进入)3元素相邻捆绑为一对于某些元素要求相邻排列的问题，可先将相邻元素捆绑并看作1个元素再与其它元素进行排列，同时对相邻元素进行自排。例35个男生和3个女生排成一列，要求女生排一起，共有几种排法？简析先把3个女生捆绑为1，与其它5个男生全排有，同时，3个女生自身全排有，由乘法原理得共有种。4元素间隔分位插入对于某些元素要求有间隔的排列，用插入法。例45个男生3个女生排成一列，要求女生不相邻且不可排两头，共有几种排法？简析先排无限制条件的5个男生有种，由于女生不相邻且不可排两头，故3个女生只能分别插在5个男生的5个间隙中，有种(若允许女生排两头，则有种插法)，由乘法原理得共有种。注意(1)插入时必须分清“谁插谁”的问题。要先排无限制条件元素，再插入必须间隔的元素；(2)数清可插的位置数(如本例在男生的两头不能插)；(3)插入时是以组合形式插还是以排列形式插入要把握准。例5把1,2,3,，20这20个数分成四组，若组内的数不少于两个时必须是连续自然数，则有几种分组方法？简析由于要求组内的数是连续的，因此，只要不改变由小到大的顺序，并在19个间隙中不相邻地插入3块“挡板”，把20个数分隔成4段，即分成了四组，共有种分组法(这里是以组合形式插入)。例6马路上有编号为1,2,3,9的9盏路灯，现在关掉其中的三盏，但不能同时关掉相邻的两盏或三盏，也不能关两端的路灯，则满足要求的关灯方法有几种？简析由于问题中有6盏亮3盏暗，又两端不可暗，故可在6盏亮的5个间隙中插入3个暗即可，有种。思考：从1,2,10这十个数中任选三个互不相邻的自然数，有几种不同的取法？()5元素定序先排后除或选位不排对于某些元素的顺序固定的排列问题，可先全排，再除以定序元素的全排。或先在总位置中选出定序元素的位置而不参加排列，然后对其它元素进行排列。例75人参加百米赛跑，若无同时到达终点的情况，则甲比乙先到有几种情况？简析1先5人全排有种，由于全排中有甲、乙的全排种数，而这里只有1种符合要求的，故要除以定序元素的全排种，所以有=60种。简析2先在5个位置中选2个位置放定序元素(甲、乙)有种，再排列其它3人有种，由乘法原理得共=60种。思考：要编制一张演出节目单，6个舞蹈节目已排定顺序，要再插入5个歌唱节目，则共有几种插入方法？(有种)6元素分排直排处理若n个元素要分m排排列，可把每排首尾相连排成一列，对于每排的特殊要求，只要分段同考虑特殊元素，然后对其余元素作统一排列。例82个老师，4个女生，12个男生，排成三排照相，要求第一排5人，第二排6人，第三排7人，且老师在第一排，女生在第二排，共有几种不同的排法？简析先把5+6+7共18个位置摆成一排，自左至右分5个位、6个位、7个位三段，先在左边的5个位中排入2个老师有种，再在中段的6个位中排入4位女生有种，然后在其余位置上全排12个男生有种，由乘法原理，共有种。7“小团体”排列先“团体”后整体对于某些排列问题中的某些元素要求组成“小团队”时，可先按制约条件“组团”并视为一个元素与其它元素排列。例9四名男歌手与两名女歌手联合举行一场演唱会，演出的出场顺序要求两名女歌手之间恰有两名男歌手，则出场方案有几种？简析由于要求有“女男男女”这样的小团体，故需先“组团”，从四名男歌手中选2人排入两女歌手之间有种(两名女歌手间自排有种)，把这“两男两女”组成小团体视为1人再与其余2男进行排列有种，由乘法原理，共有种。8不同元素进盒先分堆再排列对于不同的元素放入几个不同的盒内，当有的盒内有不少于2个元素时，不可分批进入，必须先分堆再排人。例105个老师分配到3个班里搞活动，每班至少一人，有几种不同的分法？简析先把5位老师分3堆，有两类：1,1,3分布有种和1,2,2分布有种，再排列到3个班里种，由加法、乘法原理，共有种。注意不同的老师不可分批进入同一个班，须一次到位（否则有重复计数），即“同一盒内的元素必须一次进入”。9相同元素进盒用挡板分隔例11从5个班中选10人组成校篮球队，每班至少1人，有几种选法？简析这里只是人数而已，与顺序无关，故可把10个人看成10个相同的小球放入5个不同的盒内，每盒至少1球。可先把10球排成一列，再在其中的9个间隙中选4个位置插入4块“档板”分成5格(构成5个盒子)有种方法(档板分隔模型专门对付同种元素的分配问题)。10两类元素的排列用组合选位法例1210级楼梯，要求7步跨完，且每步最多跨2级，问有几种不同的跨法？简析由题意知要有4步单级、3步双级，因此，这是两类不同元素的排列，所以只要在7步中任意选3步双级即可。注意两类元素的排列问题涉及面很广，应予重视，下面给出几例作练习。(1)3面红旗2面黄旗，全都升上旗杆作信号，可打出几种不同的信号？(种)(2)沿图中的网格线从顶点A到顶点B，最短的路线有几条(条)(3)从5个班中选10人组成校篮球队(无任何要求)，有几种选法？(有种)(提示：这里是10个球与4块档板排列问题)(4)(a+b+c+d)10的展开式有几项？(提示：这是10个球与3块档板的排列，项)注意怎样把问题等价转化为“两类元素的排列”问题是解题的关键。11个数不少于盒子编号数用填满分隔例1315个相同的球放入编号为1,2,3的盒子内，盒内球数不少于编号数，则有几种不同的放法？简析由于球是相同的，故先用6个球按编号数“填满”各盒(符合起码要求)，再把9个球放入3个盒内即可(同上面的练习(3)，可用2块档板与9个球一起排列(即为两类元素的排列问题)，有种。12正难则反间接处理对于某些排列组合问题的正面情况较复杂而其反面情况却较简单时，可先考虑无限制条件的排列，再减去其反面情况的总数。例14编号为1,2,3,4,5的五人入座编号也为1,2,3,4,5的五个座位，至多有两人对号的坐法有几种？简析问题的正面有三种情况：全不对号；有且仅有一人对号；有且仅有两人对号。且每种情况均较难处理。而反面只有两种情况：全对号(四人对号时一定全对号)；有且仅有3人对号。而全对号只有1种方法，3人对号时只要先从五人中选出3人有种，其余两人不对号只有1种情况，由加法、乘法原理得反面情况共有1+1=11种，五人全排有种。所以满足要求的种数为-(1+)=109种。13环状排列剪断直排n人围成一圈的排列(称环状排列)。对于环状排列我们可想象成这n人是手拉手的排列。因此，可采用剪断直排法，由于n人有n个连结点，故有n种剪断的方法，故共有种排法。例154名学生和2名老师围圆桌入座，(1)有几种入座方法？(2)如果老师必须相邻，有几种入座方法？(3)如果老师必须不相邻，有几种入座方法？简析(