满射观点下的排列组合问题第3稿.docVIP

《高中数学研究性学习案例》 映射观点下的一些组合问题及其计数公式 王跃进 用映射的观点研究高考中的一些排列组合问题，将它们统一为映射和满射问题并进行推广，得出关于满射个数的计数公式等结果，可以帮助我们用较高的理论观点统一看待和理解这些问题的本质及其一般解法． 一、映射 例1（06年高考湖南理科卷）某外商计划在4个候选城市投资3个不同的项目,且在同一个城市投资的项目不超过2个,则该外商不同的投资方案有 种． 例2（07年高考陕西文科卷）安排3名教师去4所学校任教，每校至多2人，则不同的分配方案共有 种． 评析 用映射的观点看，设X为 3个不同项目（3名教师）的集合，Y为4个候选城市（4所学校）的集合，则例1、例2可统一为：从X向Y作映射，不能将X中3个元素全映射到Y中同一个元素上的映射有多少个？因为从X到Y的映射共有个，其中3个元素全映射到Y中同一个元素上的映射有= 4个，故例1、例2的解均为－4=60种．用映射的观点可将两例推广为： 定理1设集合X为元集合，集合Y为元集合，从X向Y作映射，不能将X中个元素全映射到Y中同一个元素上，则这样的映射共有=个． 二、单射 例（08年上海中等职业学生高考题第4题）某校设有6个不同的兴趣小组，每名学生限报一个组，现有3名学生报名，假设每名学生报每个组的可能性相同，则任何两名学生不报同一个组的概率为 (A)； (B)； (C)； (D). 解 问题为从3元集合到6元集合的单射有多少种。满足条件的报名方法有=种，而3名同学的报名方法共有种（样本空间中的样本点总数）。故所求概率为=。选C。 说明：排列组合， 概率，高中课程标准先讲概率再讲组合，目的？ 三、满射 例3 (04年高考全国文科卷) 将4名教师分配到3所中学任教，每所中学至少一名教师，则不同的分配方案共有 种． 解 由题意知，3所中学必恰有一所分到2名教师，另外2所各分1名教师，用“捆绑法”得所求分配方案共有=36种． 评析 用映射的观点看，例3实质上是从4元集合到3元集合的满射个数问题．利用容斥原理可得关于满射个数的一般计数公式： 定理2 设集合X为元集合，集合Y为元集合，,，，则由X到Y的满射共有 = =－… 个． 证明 设Y=，为X到Y的所有映射构成的集合，,，即为使没有原象的中所有映射构成的集合，则 ；，；，；…， 一般地，有 ，，． 则中不是满射的映射共有个，根据容斥原理，所求满射个数为 = =… + + … + = －… =． 例4（08年湖北理6题）将5名志愿者分配到3个不同的奥运场馆参加接待工作，每个场馆至少分配一名志愿者的方案种数为 A.540 B.300 C.180 D.150 解：为从5元集合到3元集合的满射个数问题．由定理2得所求分法种数为 = =+ =150． 选D。用“捆绑法”同样可得所求结果为 =60+90=150 例5 (06年高考全国文科卷) 5名志愿者分到3所学校支教，要求每所学校至少有1名志愿者，则不同的分法共有 种. 解 为从5元集合到3元集合的满射个数问题．由定理2得所求分法种数为 = =+ =150． 例6（0７年高考宁夏等理科卷）某校安排5个班到4个工厂进行社会实践,每个班去一个工厂,每个工厂至少安排一个班,不同的安排方法共有 种. 解 问题为求从5元集合到4元集合的满射个数问题．由定理2得所求安排方法共有==240种．（若用“捆绑法”同样可得结果为=240） 例7 (07年高考湖北文科卷）将5本不同的书全发给4名同学,每名同学至少有一本书的概率是 ． 解 满足条件的分书方法与例4完全相同，都是从5元集合到4元集合的满射问题，故分书方法也是240种；因为从5元集合到4元集合的映射共有种，故所求概率为． 例8（06年高考重庆理科卷）将5名实习教师分配到高一年级的３个班实习，每班至少１名，最多２名，则不同的分配方案有 种. 解 问题为：从5元（5名教师）集合X向3元（３个班）集合Y作满射，不能将X中3个元素映射到Y中同一个元素上的满射有多少个？同例4得，从5元集合到3元集合的满射共有150个，其中X中有3个元素映射到Y中同一个元素上的满射有=60个，故所求方案有150-60=90种. 注： 用“捆绑法”也可得结果为=90． 三、一个元素入盒问题的推广 例9（95年全国高考题）将4个不同的小球放入编号为1，2，3，4的4个盒子中，则恰有1个空盒的放法共有 种． 解 从4个盒子中选出1个作为空盒，有种方法；对选定的1个空盒，将4个不同的小球放入其余的3个盒子且每个盒子都不空，