组合问题的解决方案.doc

组合问题的解决方案

《试题调研》网站免费精品资料下载： http:/
试题调研，金考卷等天星产品低价直销(批量)，联系人李老师， QQ45589335

一、对应思想解组合问题，即所研究的问题对应着某些元素的组合．解决此类问题要注意把握每一具体问题中“对应”的确切含义．

例1(1)圆上有10个点,两两连成弦,这些弦在圆内最多可形成_____个交点.
(2)平面上有4条水平直线,5条竖直直线,能形成矩形______个.
（3）马路上有编号为1，2，3，…，10的十盏路灯，为节约用电又不影响照明，可以

把其中3盏灯关掉，但不可以同时关掉相邻的两盏或三盏，在两端的灯都不能关掉的情况下，有多少种不同的关灯方法？
（4）如图是由12个小正方形组成的矩形网格，一质点
沿网格线从点到点的不同路径之中 条
解析：(1)每一个交点对应着两条相交弦，而两条相交弦又对应着圆上4点，故交点数等于从圆上的10个点中取4点的方法数，为个.
(2) 每一个矩形对应着两条水平直线和两条竖直直线，所以形成的矩形数等于个.（3）把问题想象成在可以移动的10盏灯中关掉3盏灯后剩下7盏灯，在7盏灯产生的6个空位中选出3个位置安排移走的3盏灯（为熄灭的灯）所对应的方法数，为种；
（4）相邻两点算作一步，则从点到点的最短路径对应着7步，其中横向安排4步、纵向安排3步，所以最短路径对应着7步中安排4步横向走的方法数,有．
附：1、（2004湖北文科）将标号为1，2，…，10的10个球放入标号为1，2，…，10的10个盒子里，每个盒内放一个球，恰好3个球的标号与其在盒子的标号不一致的放入方法种数为（ ）
A．120 B．240 C．360 D．720
解析：每一种符合要求的方法对应着10个位置选定7个对号安排和余下3个位置的完全不对号安排，10个位置选定7个的方法数为种，3个位置的完全不对号安排有2种，故总数为种．故选（ B ）．
2、（2001全国，16）圆周上有2n个等分点（n＞1），以其中三个点为顶点的直角三角形的个数为 .
解析：每一种符合要求的方法对应着选定一条直径的两个端点和在余下的2n-2个点中选择1点，方法数为种．

二、至多至少组合问题:即分类后某元素个数满足至多多少个或至少多少个的要求的组合问题.可分类或用间接法,体会两者是可以相互转化的．此类问题一定要注意避免不完全分组会产生重复造成记数出错．

例2、某班有54位同学，正、副班长和学习委员各1名，现选派6名同学参加某课外小组，在下列各种情况中，各有多少种不同的选法？
（1）正、副班长和学习委员至少有一人入选
（2）正、副班长和学习委员至多有一人入选
解析：（1）正、副班长和学习委员至少一人入选可分为只有一人入选、有两人入选和三人都入选三类，方法数为，本题也可用间接法：没有任何限制的选法为，而不符合要求即正、副班长和学习委员都不入选的方法数为，所以满足题目要求的选法数为；对本题的进一步理解：从54人中选出题目要求的选法可画图理解为如图的分类，由此可见本题既可用直接分类法也可用间接排除法解决，这对至多至少组合问题具有一般性．
（2）由以上分类易知正、副班长和学习委员至多有一人入选包含两类:3人均不入选和3人中恰有1人入选，则满足要求的方法数为.

附：1、(2005全国卷Ⅰ)从6名男生和4名女生中，选出3名代表，要求至少包含1名女生，则不同的选法有 种．
解：此题是典型的“至多至少组合问题”，可分类（以选出3人中包含女生的人数分为3类），共有种，或用间接法为种．
2、（2005浙江卷）从集合{ P，Q，R，S}与{0，1，2，3，4，5，6，7，8，9}中各任选2个元素排成一排(字母和数字均不能重复)．每排中字母Q和数字0至多只能出现一个的不同排法种数是_________．(用数字作答)．
解：此题为“至多至少组合问题”，计算出满足要求的2字母和2数字的组合的总数（采用间接法）为种，故不同排法种数是种．

三、分组搭配组合问题:即对某些元素按一定要求分组或按一定要求分配的问题.要掌握平均分组和不平均分组的处理方法；注意对平均分组又分配和不平均分组又分配的两种处理方法—--“先分（分组）后给（分配）”和“边分（分组）边给（分配）”的把握．

例3、 6本不同的书，按下列要求各有多少种不同的选法或分法：
(1)分为三份，一份一本，一份两本，一份三本；
(2)分为三份，每份两本；
(3)分给甲、乙、丙三人，一人一本，一人两本，一人三本；
(4)分给甲、乙、丙三人，每人两本；
⑸分给甲、乙、丙三人，每人至少一本．
解析：(1)此为不平均分组的题目，只须按三个步骤分别选出1本的一份、2本的一份和3本的一份即可，方法总数为种；
(2) 此为平均分组的题目，只须先假定三个位置A、B、C，每个位置安排2本书，按三个步骤分别选出2本安排在A、B和C，共有种方法，而此题为平均分组，上述算法已对每一分组在A、B、C三个位置进行了排列，故满足要求的平均分组为种；(3) 此为不平均分组又分配的题目，可采用先分组后分配的方法，即第一步分组共有种方法，第二步每一种分法得到的3组分给甲、乙、丙三人的方法都是种，故采用先分组后分配的方法得分配方法共种；本题也可采用“边分边给”的方法解决，即先选出1本书并将这本书分配给1人的方法数为种，再选出2本书并将这2本书分配给1人的方法数为种，第三步选出3本书并将这3本书分配给1人的方法数为种，故采用“边分边给”的方法得方法总数为种；(4)此为平均分组又分配的问题，可采用“先分（分组）后给（分配）”得方法数为种；若采用“边分（分组）边给（分配）”的方法理解本题可分三步完成：甲分得2本书、乙分得2本书、丙分得2本书，方法数为种；
⑸先分类再结合上述解法得方法数为++种．
例4、3名司机和6名售票员分别分配到3辆不同的公交车上,每辆车上1名司机2
名售票员,分配方法共多少种?
解析：将问题分两步：对3名司机和6名售票员分为3组，每组1名司机和2名售票员，先
假定司机不动，则分组方法为种，再对每一分法分得的3组在3个位置（3辆不同的公交车）进行排列得分配方法共有种；若采用边分边给的方法则分3步完成：第一、二、三辆公交车分别选1名司机2名售票员,分配方法共种．
附：1、北京《财富》全球论坛期间，某高校有14名志愿者参加接待工作．若每天排早、中、晚三班，每班4人，每人每天最多值一班，则开幕式当天不同的排班种数为( )
（A） （B） （C） （D）
解析：本题是典型的分组搭配问题（平均分组），注意对该类问题的两种处理方法—--“先分（分组）后给（分配）”和“边分（分组）边给（分配）”的把握．在解答本题时请仔细体会“边分（分组）边给（分配）”的运用．答案为(A ).
2、把一同排6张座位编号为1，2，3，4，5，6的电影票全部分给4个人，
每人至少分1张，至多分2张，且这两张票具有连续的编号，那么不同的分法种数是（ ）
A．168 B．96 C．72 D．144
解析：本题是典型的分组搭配问题（不平均分组），注意对该类问题的两种处理方法—--“先分（分组）后给（分配）”和“边分（分组）边给（分配）”的把握．本题把一同排6张座位编号为1，2，3，4，5，6的电影票分为4组的方法数为6种，每一种分组的分配方法均为，故本题的方法数为种．故选（D）．请仔细体会“先分（分组）后给（分配）”的运用．
3、四棱锥的8条棱代表8种不同的化工产品,有公共点的两条棱代表的化工产品放在同一仓库是危险的,没有公共顶点的两条棱多代表的化工产品放在同一仓库是安全的,现打算用编号为①、②、③、④的4个仓库存放这8种化工产品,那么安全存放的不同方法种数为 ( )
（A）96 （B）48 （C）24 （D）0
解析：本题是典型的分组搭配问题（平均分组），本题适用“先分（分组）后给（分配）”法，没有公共顶点的两条棱一组的分组有（PA，BC）、（PB，CD）、（PC，AD）、（PD，AB）或（PA，CD）、（PB，DA）、（PC，AB）、（PD，BC）共2大组，而每大组的4小组在4个位置的分配就是4个元素在4个位置的全排列，所以安全存放的不同方法种数为 种．故选( B)．

4