高中数学学案 培优点　排列、组合问题的几种解法.docVIP

培优点排列、组合问题的几种解法

类型一相邻排列——捆绑法

n个不同元素排列成一排，其中某k个元素排在相邻位置上，有多少种不同排法？

先将这k个元素“捆绑在一起”，看成一个整体，当作一个元素同其它元素一起排列，共有Aeq\o\al(n－k＋1,n－k＋1)种排法.然后再将“捆绑”在一起的元素进行内部排列，共有Aeq\o\al(k,k)种方法.由分步乘法计数原理得符合条件的排法共Aeq\o\al(n－k＋1,n－k＋1)·Aeq\o\al(k,k)种.

例1有5名女生4名男生站成一排，女生必须相邻，男生必须相邻，共有多少种不同的站法？

解先把5名女生作为一个整体，看成一个元素，4名男生作为一个整体，看成一个元素，两个元素排列成一排共有Aeq\o\al(2,2)种排法；

女生内部的排法有Aeq\o\al(5,5)种，男生内部的排法有Aeq\o\al(4,4)种.

故符合题意的排法有Aeq\o\al(2,2)·Aeq\o\al(5,5)·Aeq\o\al(4,4)＝5760(种).

类型二相离排列——插空法

元素相离(即不相邻)问题，可先把无位置要求的几个元素全排列，再把规定的相离的几个元素插入上述几个元素之间的空位和两端.

将n个不同元素排成一排，其中k个元素互不相邻(k≤n－k)，有多少种排法？

先把(n－k)个元素排成一排，共有Aeq\o\al(n－k,n－k)种排法，然后把k个元素插入(n－k＋1)个空隙中，共有排法Aeq\o\al(k,n－k＋1)种，故符合条件的排法共有Aeq\o\al(n－k,n－k)·Aeq\o\al(k,n－k＋1)种.

例2五位科学家和五名中学生站成一排照像，中学生不相邻的站法有多少种？

解先把科学家作排列，共有Aeq\o\al(5,5)种排法；

然后把5名中学生插入6个空中，

共有Aeq\o\al(5,6)种排法，

故符合条件的站法共有Aeq\o\al(5,5)·Aeq\o\al(5,6)＝86400(种).

类型三定序问题——倍缩法

在排列问题中限制某几个元素必须保持一定的顺序，可用缩小倍数的方法，此法也被叫消序法.

将n个不同元素排列成一排，其中某k个元素的顺序保持一定，有多少种不同排法？

n个不同元素排列成一排，共有Aeq\o\al(n,n)种排法；k个不同元素排列成一排共有Aeq\o\al(k,k)种不同排法.于是，k个不同元素顺序一定的排法只占排列总数的Aeq\o\al(k,k)分之一.故符合条件的排法共eq\f(Aeq\o\al(n,n),Aeq\o\al(k,k))种.

例3a，b，c，d，e五人并排站成一排，如果b必须站在a的右边(a，b可以不相邻)，那么不同的排法种数是()

A.24种 B.60种

C.90种 D.120种

答案B

解析b在a的右边与b在a的左边排法数相同，所以题设的排法只是5个元素全排列数的一半，即eq\f(1,2)Aeq\o\al(5,5)＝60(种)，选B.

类型四“隔板法”在计数问题中的妙用

(1)排列组合中的相同小球放进不同的盒子、名额分配或相同物品的分配等问题，是排列组合中的难点问题，这类问题的基本模型是：将n个相同元素分组到m个不同对象中(n≥m)，每个对象至少有一个元素.这类问题必须满足三个条件：①元素必须相同；②对象必须不同；③每个对象至少有一个元素.当满足这三个条件时，我们可以采用隔板法.

(2)通过对隔板法的应用，可得下列结论.

结论1：把n个相同的元素分成m组分配给m个人，每组不允许落空，则可将n个元素排成一排，从n－1个间隔中，选出m－1个插上隔板，每一种隔板的插法对应一种分配方法，则分配方法数N＝Ceq\o\al(m－1,n－1).

结论2：把n个相同的元素分成m组分配给m个人，某些组允许落空，则可将m－1个隔板和n个元素排成一排，每一种隔板的插法对应一种分配方法，则分配方法数N＝Ceq\o\al(m－1,m＋n－1).

例4将7个相同的小球放入4个不同的盒子中.

(1)不出现空盒时的放入方式共有多少种？

(2)可出现空盒时的放入方式共有多少种？

解(1)将7个相同的小球排成一排，在中间形成的6个空格中插入无区别的3个“隔板”将球分成4份，每一种插入隔板的方式对应一种球的放入方式，则不同的放入方式共有Ceq\o\al(3,6)＝20(种).

(2)每种放入方式对应于将7个相同的小球与3个相同的“隔板”进行一次排列，即从10个位置中选3个位置安排隔板，故共有Ceq\o\al(3,10)＝120(种)放入方式.