排列组合中的几种常见问题.doc

《排列组合中的几种常见问题.doc》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、问题一：均匀分组与不均匀分组的问题方法技巧　均匀分组与不均匀分组的问题处理均匀分组与不均匀分组、无序分组与有序分组是组合问题的常见题型．解决此类问题的关键是正确判断分组是均匀分组还是不均匀分组，无序均匀分组要除以均匀组数的阶乘数，还要充分考虑到是否与顺序有关；有序分组要在无序分组的基础上乘以分组数的阶乘数．【示例】按下列要求分配6本不同的书，各有多少种不同的分配方式？(1)分成三份，1份1本，1份2本，1份3本；(2)甲、乙、丙三人中，一人得1本，一人得2本，一人得3本；(3)平均分成三份，每份2本；(4)平均分配给甲、乙、丙三人，每人2本；(5)分成三份，1份4本，

2、另外两份每份1本；(6)甲、乙、丙三人中，一人得4本，另外两人每人得1本；(7)甲得1本，乙得1本，丙得4本．解　(1)无序不均匀分组问题．先选1本，有C种选法；再从余下的5本中选2本，有C种选法；最后余下3本全选，有C种选法．故共有分配方式C·C·C＝60(种)．(2)有序不均匀分组问题．由于甲、乙、丙是不同的三人，在(1)题基础上，还应考虑再分配，共有分配方式C·C·C·A＝360(种)．(3)无序均匀分组问题．先分三组，则应是C·C·C种方法，但是这里出现了重复．不妨记六本书为A，B，C，D，E，F，若第一步取了AB，第二步取了CD，第三步取了EF，记该种分法为

3、(AB，CD，EF)，则C·C·C种分法中还有(AB，EF，CD)，(CD，AB，EF)，(CD，EF，AB)，(EF，CD，AB)，(EF，AB，CD)，共有A种情况，而这A种情况仅是AB，CD，EF的顺序不同，因此只能作为一种分法，故分配方式有＝15(种)．(4)有序均匀分组问题．在(3)的基础上再分配给3个人，共有分配方式·A＝C·C·C＝90(种)．(5)无序部分均匀分组问题．共有分配方式＝15(种)．(6)有序部分均匀分组问题．在(5)的基础上再分配给3个人，共有分配方式·A＝90(种)．(7)直接分配问题．甲选1本，有C种方法；乙从余下的5本中选1本，有C

4、种方法；余下4本留给丙，有C种方法，共有分配方式C·C·C＝30(种)．问题二：同元问题“隔板法”例.10本完全相同的书，分给4个同学，每个同学至少要有一本书，共有多少种分法？分析：在排列成一列的10本书之间，有九个空位插入三块“隔板”.如图：××××××××××一种插法对应于一种分法，则共有＝84种分法.该题的数学模型为：方程……有个正整数解。问题三：配对问题1．某电视台邀请6位同学的父母共12人，请这12位家长中的4位介绍对子女的教育情况，如这4位中恰好有一对是夫妻，那么不同的选择方法种数为多少？2．10双互不相同的鞋子混装在一只口袋里，从中随意取出4只，试求各有

5、多少种情况出现以下结果：（1）4只鞋中没有成双的；（2）4只鞋中有2只成双，另2只不成双；（3）4只鞋中至少有2只配对成1双。解析：（1）（2）（3）法一：法二：分步计数（注意重复）：法三：分类计数：问题四：等价问题“转化法”MN例如图，在某个城市中，M、N两地之间有整齐的道路网，则从M到N的最近距离的走法共有几种？分析：欲使从M到N走法最近，正如“过河的卒子不后退”，横向的道路走且仅走四段，纵向的道路走且仅走两段。于是，它就等价于四个“横”字，两个“纵”字排成一列的问题。由于相同元素的排列，于是又等价于插空问题：从六个位置任取四个填“横”，剩余两个填“纵”，共有种方

6、法，即共有种走法最近。变式：如图,从一个3×4的方格中的一个顶点A到对顶顶点B的最短路线有几条?解：把质点沿网格线从点A到点的最短路径分为七步，其中四步向右，三步向上，不同走法的区别在于哪三步向上，因此，本题的结论是：．