十五、排列组合的应用
教学目标
1．指导学生通过分析、比较掌握解排列组合问题的基本方法(利用两个原理分类分步解题与结合容斥原理用排除法解题)与常见的特殊方法(如整元法、插空法、除序法、挡板法等等)．
2．这部分知识应用性非常强，要在教学过程中反复强调充分理解每个算符每步计算所对应的实际背景，使学生能认同唯有不断提高自己的应用意识才能越来越熟练地顺利解决排列组合问题．
3．这部分所涉及的题目解题方法常常多种多样，应鼓励学生尝试、探索各种不同的解题方案，分析比较各种方法的适用范围及特点，使学生在探索分析中确实感受到探索与分析的必要性，以增强学生提高探索能力的自觉性．
4．这部分题目难度较大，学生解题时难免出现错误，要鼓励学生大胆说出不同的甚至是错误的解题方法，与同伴一起分析自己思路中的合理成分与不足，使自己与同伴都可以从错误中进一步准确理解各种解题方法的正确使用方法，在这种讨论过程中增强学生自我反省的批判能力和合作意识．
重点难点
每种排列组合的解题方法都对应着一个具体的“完成某件任务”的过程，使学生明确每个算符与每步所对应的具体完成任务的办法是最大的难点．特别是某些错误使用乘法原理时出现的“完成任务”的办法，学生常常很难识别其中出现的重复或漏计不同方法数的具体情况，因此教学重点不仅是讲清每种正确的解题方法，而且应诱使学生暴露自己的思维过程，及时纠正对每种方法的误解误用．
教学过程
一、引言
回顾学过的知识：两个原理；排列组合概念及排列数、组合数公式．强调两点：1．每个概念与公式都与具体完成每件任务的办法设计密切相关，因此解排列组合问题首先要明确题目中要“完成的任务”是什么，再确定你准备如何完成任务的方案，最后再将方案中的每类、每步办法种数译成数学运算符号．2．前面所涉及的题目大多数是为介绍概念或公式所出现的比较单纯的问题，这节课将在更为实际因而也更为复杂的问题上进一步探讨排列组合知识的具体应用．
二、排列组合的应用问题(一)
这部分主要解决1．不同类问题(可重复排列问题，不可重复排列问题，组合问题)的辩析．2．多类多步排列组合问题的解决方法，主要是两个特元以上的特元法或特位法、排除法的应用．
例1有一些书要借给一些人，按下列要求各有多少种不同的借书方法．
(1)六本不同的书全部借给五个人，每人至少一本；
(2)五本不同的书借给六个人，五本书全部被借走；
(3)三本相同的书借给五个人，三本书全部借出，每人最多借走一本；
(4)三本相同的书借给五个人，三本书全部被借走．
(2)65=7776；
教学过程设计：例1的四个小问题同时给出，给学生自己思考并交流的时间．四问同时给出的好处在于学生能够通过比较题目不同的叙述方法自我纠正对题意的误解，弱点是学生自我纠正后可能会不甚重视产生误解的原因，因此，在教学过程中应通过设问让学生重视并反思可能出现误解的原因及避免误读的审题重点。要引导学生暴露所有可能的错误解法，并引导学生理解产生错误的原因．认真分析例1(1)，为后面介绍整元法、除序法做一定的准备．
逐一分析解题方法：
第一组提问：(解例1(1)时)
问1：据乘法原理，可以考虑每本书有五个去向，因此，借法总数为56，对吗？
(期望学生认识到这种算法无法保证“每人至少借一本的要求)
问2：可以设计借书过程：先选出5本书借给5个人，再将剩下的
(期望学生认识到借到两本书的人的同一种借法被计算了两次，如果学生不能意识到这种重复计算，就举出一个具体的被重复计算的例子：如“第一、二、三、四、五本书分别借给A，B，C，D，E五人，又将第六本书借给A，”与“第六、二、三、四、五本书分别借给A，B，
原理被计算为两种不同的方法，但在实际上应视为一种借法)．
问3：怎样纠正上述的错误呢？
(期望学生认识到：可以先决定哪两本书借给同一个人，再将五“份”
也可以注意到所重复计算的方法数都出现在某个借了两本书的人
序法”做一铺垫)．
(注：这一提问顺序是假设学生只提出了两种错误解法时所用．若学
问4：再看题目，题目中如果改为“四人”？
(课上只须让学生认识到需分类讨论，做为课后选做，令学生课下完成具体计算过程)．
使问题复杂一些，以突出此方法的本质特点．)
第二组提问：(解例1(2)时)
问1：(估计大部分学生会利用“乘法原理”找到解题正确办法．)这个问题中哪些因素使你想到要从书的去向分析解题过程从而得到借法数为“65”？
(期望学生能体会若从借书者分析，分类情况太复杂，另外，没有限定每人的借书量又是极重要的提示)．
问2：题目中的“全部借出”的作用是什么？
(期望学生能体会若无此限制，则每本书的去向应增添“未被借走”一种情况，于是不同的借法种数为“75”．)
第三组提问：(解例1(3)时)
问1：(估计有一些学生可以得出正确答案)为什么不能设计借书的过程是选一个人取走一本书，再选一人取走一本书，再选第三个人取走最后一本书？这种算法中是否已经反映了“书是相同的”这一条件？)
面上看并没有考虑书之间的差别，但实际上“乘法原理”的使用中将三个人得书的过程分成“步”就造成了与实际情况相比的重复计算，也相当于将书放于不同的位置，让借书人去取，这就造成了书实际上不相同的效果．)
问2：为什么不可用“53”来计算不同的借法种数？
(期望学生意识到这种算法无法保证“每人最多一本”的要求．)
第四组问题：(解例1(4)时)
五人中一人有两本，一人有一本的合理性及其中隐含的“整元”思想．)
么都是“相同的书”，有时是排列问题，有时又是组合问题，不可拆成“组合数”的积来解题？
(引导学生认识到不可据一些固定的系词来盲目区分组合与排列问题，而是要在充分理解乘法原理的基础上，据实际情况判断乘法原理中所体现的“分步”所导致的计数方法是否适合实际问题的要求，并进一步体会在实际问题中排列组合问题的联系与区别．)
例1小结两组元素(书、人)建立某种对应关系(借书)，计算不同的对应方法(借法)种数时，应特别注意：
1．每组元素的个数，每组元素间是否相同．
2．对应关系的要求：每个元素是否必须要有与之对应的元素？可以对应几个等等．
3．特别重视想清楚应用乘法原理时，所计算的方法种数是否与实际方法数相比有重复计数的情况．
例2有一些不同的工作需分配一些人去做，满足下列条件的分配工作方法种数各为多少？
(1)有六人，五种不同的工作，在六人中任选三人去做五种工作中的三种，每人做且只做一种工作；
(2)有五人，五种不同的工作，每人做且只做一种工作，其中甲不能做第一种工作，乙不能做第二种工作；
(3)有六人，四种不同的工作，选四人做且每人只做一种工作，且甲、乙不能做第一种工作．
解(1)将分配工作的过程分为三步：第一步决定选哪三个人；第二步决定做哪三件工作；第三步决定哪个人担任哪个工作，则分配工作方法种数为：
教学过程设计：
令学生经讨论后提出各种解法，分析正确方法之间的等价性，如：
(2)解法一甲、乙两人有特殊要求，可先考虑这两个特殊元素工作的分配方法(特元法)，由于甲担任第二种工作与否会导致乙可选择的工作方法数的不同变化，所以可分甲做或不做第一种工作，两类分别计算分配工作的种数：
解法二由于甲、乙分别担任第一、二种工作的分配方法数很易计算，所以可以用排除法计算不同的分配工作方法种数：
教学过程设计：
令学生经讨论提出各种解法．分析第一种解法或与之类似解法的关键是连续考虑特殊元素，并特别关注第一位特殊元素的“排法”给第二位特殊元素提供的排法种数是否一致，以此判断是否需分类及分类的办
分析第二种解法中容斥原理的背景，特别注意有两个限制条件的使用排除法与只有一个限制条件的使用排除法的异同．应特别注意分析错
(3)解法一可用排除法(排除甲或乙任第一种工作的情况)：
解法二可先考虑第一种工作这一特殊位置工作的分配方法，再考虑其它工作的分配方法(特位法)，则不同的分配工作方法种数为：
解法三从甲、乙这两个特殊元素考虑，可分三类情况计算分配方法种数．在被选出的四人中分“没有甲、乙”，“有且仅有甲、乙中的一人”、“既有甲、又有乙”三类：
教学过程设计：
除类似例2(1)(2)求解过程中组织学生探讨各种解题方法的正误以外，应着重引导学生认识到从不同角度分析解题过程时的难易程度，使学生能认识到有意识地从多种角度分析问题的必要性．
例2小结解决有特殊元素(或特殊位置)的排列、组合问题时，基本方法是特元(或特位)法，排除法，例2提示了各种方法在使用时应注意的问题，并且提示了根据已知从不同角度寻求解决问题的办法．
三、排列组合的应用问题(二)
这部分主要让学生基本掌握排列组合问题中的几个特殊方法：整元法，插空法，除序法，挡板法．
例3 A，B，C等六人排成一队，满足下列要求的排队方法种数各有多少：
(1)A，B，C三人要排在一起
(2)A不能与B，C相邻．
解(1)将A，B，C先排在一起，再与其他人排．
(2)分“A在两端”与“A不在两端”两种情况求解，即
教学过程设计：
解例3(1)时，估计不少学生可以想到“整元”的思想，应在学生讲述自己解法时将“整元法”提练得更为明确清晰．在讲评中注意分析使用“整元法”时易
出现的错误：①忽略了视为整元的各元素之间应确定排列顺序．②数错在组成“整元”后应排列的元素个数．
解例3(2)时，估计会有学生参照例3(1)的想法沿用“整元”思想解题，注意在评述学生解题方案时提醒学生注意三类常见错误：①不考虑A在或不在两边应分类计算；②在计算“A不在两端”时，不注意排列在A两边的人的顺序，或是错将整元排列数计算为
认为“A与B，C不相邻”的否定是“A与B，C都相邻”，实际上应为“A 与B或C相邻”．
例3小结：
1．“整元法”可用于解决“相邻”问题．又因“整元法”在排好整元后与其它元素再排列时不拆散整元，所以“整元”也可以起到“隔离”的作用，可用于解决某些“不相邻”问题．
2．在使用“整元法”时应特别注意①据实际情况确定构成“整元”的方法数．②构成“整元”后数清进一步需排列的元素的个数．
例4(1)三位女生、四位男生排成一排，女生不能相邻，有多少种不同的排队方法？
(2)三位女生、四位男生排成一排，女生不能相邻，男生也不能相邻，有多少种不同的排队方法？
(3)有七个空位子，三位女生去坐，女生不能相邻而坐，有多少种不同的坐法？
解(1)用插空法，令男生排好，再将女生插入男生之间及两头所形成的可排入女生的五个空位中去：
(2)男、女生应互相隔开，所以不同排法种数为
(3)三个女生坐好后还应有4个空位，所以可设想女生是被插入到四个空位所形成的五个位置中去的，不同的排法种数为
教学过程设计：
解例4(1)时，无论是否有学生找到了正确简捷的解题方法，都应引导学生认识到，前面所使用的各种解题方法，均是由具有特殊要求的元素入手从正面或从不适应题目要求的反面(排除法)优先考虑特殊要求来解题的，但若仍沿用这种想法想解决题目要求的不相邻问题，就很困难，所以可以换一个角度，先处理没有限制条件的元素(题目中的男生)，再看是否能更简捷地解决有限制条件的元素(题目中的女生)的排列问题．
解例4(2)时，应引导学生认识到，遇两组不同元素不相邻问题时，仍可用插空法，但两组元素的个数需有一定限制，若一组元素的个数为m，则另一组元素的个数只可以取m-1，m，m+1，否则题目无解．
解例4(3)时，应引导学生认识到这一问题的解法是一组相同元素与一组不相同元素之间不相邻问题的解法示例．
在讲解过程中应适时引导学生分析比较两个问题．(1)比较“插空法”与“整元法”在解不相邻问题时的异同．(2)比较例4(1)、(3)之间的异同，为“除序法”做一些铺垫．
例4小结插空法主要用于两组元素中有一组或两组元素彼此不能相邻的特殊排列或组合问题．
例5用0，1，2，3，4，5组成满足下列条件的无重复数字的数，各有多少个不同的数：
(1)不含0的五位数，其中奇数数字需由大到小从左至右排列；
(2)六位数，其中偶数数字由大至小从左至右排列．
(1)解法一可以考虑在五位数中确定两个偶数所在的位置及相对排列顺序，即
解法二先将五位数任意排好，再将奇数所在的位数相同且偶数的
个五位数在且仅在一组数中，所以不同的五位数为
(2)解法一类(1)解法一，选三个位置将三个奇数排入，此时，由于偶数必须从左至右由大到小排列，所以不会出现最高位为0的情况，即所有不同的满足条件的不同六位数个数为：
解法二类(1)解法二，将奇数所在位置及排列顺序都相同的六个数归并为一组，不同的满足条件的六位数为
教学过程设计：
解例5(1)时，引导学生认识到从奇数、偶数排列方法入手解决问题的等价性，同时体会两种方法中算符与算式的不同含意，必要时应回顾
为一组，同时由于应使偶数从左至右由大到小排列，所以不会出现最高位为0的情况．
视情况而定，引导学生将问题发展成有两组或两组以上元素的排列顺序是确定(定序)的，或这些元素是相同的(无序)时，解题的思想与方法．
例5小结除序法可用于解决被排列元素中有一组或一组以上的元素是无序的(无差别)或定序的(排列顺序事先指定)问题．
例6有10个数学竞赛名额要分配给7个学校，每校至少分给一个名额，有多少种不同的名额分配方法？
解法一若每校各分一个名额后、还有三个名额待分配，可分将名额分给“三校”、“两校”“一校”三类情况计算分配总数：
解法二(挡板法)设想将名额排成一列，则每两个相邻名额之间可形成共9个空隙，在9个空隙中选6个空隙插入“挡板”，将名额分割成7段，则第一、二、…七段名额数可视为分别分给第一、二、…七所学校的名额数不同的分配方法为
教学过程设计：
估计有些同学可以正确地按解法解题，但独立寻找到解法二很困难，所以可在充分讨论与解法一相类似的各种正、误解法后将名额数增加(如增到20个)，使分类的办法显得很繁，再引入解法二．若有学生已经预习可提出解法二，则可直接令学生比较两种解法的难易程度．
例6小结：
挡板法可使用于解决待分配的元素无差别且每个位置至少分配一个元素的问题中．
四、课堂小结
在解决排列组合应用问题时
1．先确定问题的类型．
2．考虑是否可用特法解决问题．
3．若无法用特殊办法解题，可考虑分别从两组元素入手结合两个原理的解题方法(特位或特元法)，或是利用排除法解题．应注意比较不同分析角度所得的解题过程的难易程度．
4．每种解题方法皆有其适用范围及易错点，应在使用中不断注意分析归纳，以加深对每种方法的认识．
能力训练
1．在1000和9999之间由四个不同数字组成且个位数字和千位数字的差的绝对值为2，则这样的自然数的个数为[] A．896B．840 C．128D．448
2．用0，1，2，3，4，5可以组成比400小的自然数的个数是[] A．80B．90 C．142D．143
3．八个人站成一排，其中A，B两人要排在一起，且C要站在D的左边(可不相邻)，则不同的排队方法种数为[] A．2520B．5040 C．720D．10080
4．集合A=｛1，2，3，4｝，集合B=｛1，5，7｝定义以A为定义域，B
为值域的函数，则不同的函数个数为[] A．81B．72 C．36D．18
5．由0，1，2，3，4，5组成2不在百位，0不在个位的无重复数字的三位数，则不同的三位数的个数为[] A．64B．60 C．84D．80
6．从0，1，2，3，4，5，6中选出三个不同的数作为二次函数y=ax2+bx+c 的系数a，b，c，其中a＞b，这样可以得到的不同的二次函数的个数为[] A．90B．105 C．210D．35
7．以0，1，2，3，4中的数作为直线方程Ax+By=0中的系数A，B，则可以表示的不同的直线条数为[] A．12B．13 C．14D．15
8．八人排队，站成前后两排，前后各四人且甲不在第一排，乙不在第二排，则不同的排队方法种数为[] A．720B．2880 C．11520D．576
9．直线x=0，y=0将圆x2+y2=1分成四个区域，用5种不同的颜色给这四
个区域涂色，有公共边的区域颜色互异，每块区域只涂一种颜色，则不同的涂色办法种数为[]
A．260B．200 C．250D．190
10．一条铁路原有m个车站，为适应客运需要新增加n个车站(n＞1)，则客运车票增加58种(从甲站到乙站和从乙站到甲站需要两种不同的车票)，则原有的车站数是[]
A．12B．13 C．14D．16
11．三位男生三位女生排成一排，男生与男生不相邻，女生与女生也不相邻，则不同的排队方法种数为______．
12．安排甲、乙、丙三人从周一到周六值班，每天一人，每人值两天，但周一不能排甲，周六必须排乙，则有______种不同的排班方法．
13．六人站成前后两排，每排三人，前排的人，要比他正后方的人矮，则不同的排队方法有______种．
14．由1，4，5，x四个数字组成无重复数字的四位数，所有这些四位数各位上的数字之和是288，则x=______．
15．方程x1+x2+x3+x4=10的正整数解有______组．
答案提示
1．B2．D3．B4．C5．A6．B7．B8．C
9．A10．1411．7212．1813．9014．215．84
设计说明
排列组合是高中数学教学的难点之一，在教学中感到使用“基本思想反复重复，难度螺旋式上升”的教学方法效果比较好．因此，在教学整体安排时，大致可分为三个阶段：第一阶段：基本概念与公式的介绍．着重于两个原理、排列组合之间的联系与区别，有一个限制条件的题目的处理．第二阶段：排列组合问题的基本应用，即本教案的内容，着重于解题方法的学习．第三阶段：更为复杂的排列组合综合应用，即本教案的后继课．着重于各种解题方法的识别与灵活、综合应用，及与其它数学内容的综合应用．
本教案的教学重点应为各种解题基本方法的介绍及互相的联系与区别，所以以“解题方法”组织例题，使方法的使用范围、特点更为清晰．结合第三阶段以“问题”组织例题增强学生对使用各方法的辩析能力，可以帮助学生更深刻地理解各种方法，并增强灵活使用各种方法的能力．
本教案在北京四中使用，四中的学生自学能力比较强，很多方法皆可不经教师提示即有部分学生掌握，则此时应特别重视学生之间学习能力与学习习惯的差异，力求尽可能多的学生切实掌握所探讨的各种解题方法，因此鼓励学生在课上大胆表述自己的想法，切实认真分析评价学生所提出的解题方案显得尤为重要．
解排列组合应用题的21种策略 排列组合问题是高考的必考题，它联系实际生动有趣，但题型多样，思路灵活，不易掌握，实践证明，掌握题型和解题方法，识别模式，熟练运用，是解决排列组合应用题的有效途径；下面就谈一谈排列组合应用题的解题策略. 1.相邻问题捆绑法:题目中规定相邻的几个元素捆绑成一个组，当作一个大元素参与排列. 例 1.E D C B A ,,,,五人并排站成一排，如果B A ,必须相邻且B 在A 的右边，那么不同的排法种数有（ ） A 、60种 B 、48种 C 、36种 D 、24种 解析：把B A ,视为一人，且B 固定在A 的右边，则本题相当于4人的全排列,4 4A =24种，答案：D . 2.相离问题插空排:元素相离（即不相邻）问题，可先把无位置要求的几个元素全排列，再把规定的相离的几个元素插入上述几个元素的空位和两端. 例2.七人并排站成一行，如果甲乙两个必须不相邻，那么不同的排法种数是（ ） A 、1440种 B 、3600种 C 、4820种 D 、4800种 解析：除甲乙外，其余5个排列数为55A 种，再用甲乙去插6个空位有2 6A 种，不同的排法种数是36002655=A A 种，选B . 3.定序问题缩倍法:在排列问题中限制某几个元素必须保持一定的顺序,可用缩小倍数的方法. 例3.E D C B A ,,,,五人并排站成一排，如果B 必须站在A 的右边（B A ,可以不相邻）那么不同的排法种数是（ ） A 、24种 B 、60种 C 、90种 D 、120种 解析：B 在A 的右边与B 在A 的左边排法数相同，所以题设的排法只是5个元素全排列数的一半，即602 155=A 种，选B 4.标号排位问题分步法:把元素排到指定位置上，可先把某个元素按规定排入，第二步再排另一个元素，如此继续下去，依次即可完成. 例4.将数字1，2，3，4填入标号为1，2，3，4的四个方格里，每格填一个数，则每个方格的标号与所填数字均不相同的填法有（ ） A 、6种 B 、9种 C 、11种 D 、23种 解析：先把1填入方格中，符合条件的有3种方法，第二步把被填入方格的对应数字填入其它三个方格，又有三种方法；第三步填余下的两个数字，只有一种填法，共有3×3×1=9种填法，选B . 5.有序分配问题逐分法:有序分配问题指把元素分成若干组，可用逐步下量分组法. 例5.（1）有甲乙丙三项任务，甲需2人承担，乙丙各需一人承担，从10人中选出4人承担这三项任务，不同的选法种数是（ ） A 、1260种 B 、2025种 C 、2520种 D 、5040种 解析：先从10人中选出2人承担甲项任务，再从剩下的8人中选1人承担乙项任务，第三步从另外的 7人中选1人承担丙项任务，不同的选法共有25201718210=C C C 种，选C . （2）12名同学分别到三个不同的路口进行流量的调查，若每个路口4人，则不同的分配方案有（ A ） A 、44484 12C C C 种 B 、344484 12C C C 种 C 、33484 12A C C 种 D 、33 4448412A C C C 种 6.全员分配问题分组法: 例6.（1）4名优秀学生全部保送到3所学校去，每所学校至少去一名，则不同的保送方案有多少种？ 解析：把四名学生分成3组有24C 种方法，再把三组学生分配到三所学校有33A 种，故共有363324=A C 种
排列组合的应用 一、填空题： 1、有不同的书6本，平均分给甲、乙两人，有种分法。 2、某校举办排球赛，有10支队参赛，赛制为单循环赛，这次比赛共要进行场，冠军和亚军的获得者有种可能情况。 3、有5本不同的故事书，准备送给3个小朋友，如果每人只能得1本，有种送法；如果5本书都要送出，但不限定每个小朋友都得到，有种送法。 4、有8台车床，分配给甲、乙、丙三名技工管理，如果甲管4台，乙管3台，丙管1台，有 种分配方法；如果甲管4台，其余两人是一人管3台，1人管1台有种分配方法。 5、从1，2，3，4，5，6这六个数字中，任取两个相减，可得到个不同的差。 6、有8位男生，7位女生，现准备从中选出6人组成试验小组，如果男女各占一半，有种选法；如果最多只能有3位女生，有种选法。 二、选择题： 1、6个队员排成一列进行操练，其中新队员甲不能站排首，也不能站排尾，有（）种不同排法。 A、4P55 B、4P66 C、2P55 D、2P66 2、6件不同的商品将它们排成一列，陈列在橱窗里，如果a、b两件商品要分别放在两端，有（）种不同排法。 A、P44 B、P66-2 C、2P44 D、P46 3、某铁路线上一共有51个大小车站，铁路局要为这条路线准备（）种不同的车票。 A、102 B、2601 C、1275 D、2550 4、有甲、乙、丙、丁、戊5个队比赛足球，分主客场比赛，总共要比赛（）场。 A、10 B、20 C、25 D、120 5、如果从4，5，6，7，8，9，10，14，17各数中每次取出两个数，使其和为偶数，共有（）种选法。 A、20 B、16 C、9 D、32 6、从12名学生中选3人参加歌咏比赛的选法有（）种。A、1320 B、220 C、3960 D、660 7、某校文艺演出的节目中有5个是唱歌的，3个是舞蹈，若舞蹈节目不能安排成连续的，有（）种出场顺序。 A、120 B、240 C、336 D、14400 8、参加小组唱的6个男生和4个女生站成一排，要求女生站在一起有（）种不同站法。 A、10！ B、4！×6! C、4×7！ D、4！×7！ 9、若x、y分别在1、2、3、4、5、6中取值，则x+y=7有（）组解。 A、3 B、6 C、7 D、9 10、若x、y分别在0，1，2，…，9中取值，则点P（x,y）在第一象限中的点的个数是（） A、100 B、99 C、121 D、81 三、解答题： 1、某厂生产一批五档数字的号码锁（每档数字都可以是0，1，2，…，9这十个数字中的任一个），问产品中总共可有多少不同的锁？ 2、某市的电话号码从原来的7个数码，升位为8个数码，电话号码升位后，可增加多少用户（如果规定号码的第1个数字不得用0）。 3、用5面不同颜色的小旗升上旗杆，以作出信号，总共可作出多少种不同的信号（作信号时，可以只用一面小旗，也可以用多面小旗）？
两个计数原理的应用 一、选择题 1．如图，小明从街道的E处出发，先到F处与小红会合，再一起到位于G处的老年公寓参加志愿者活动，则小明到老年公寓可以选择的最短路径条数为【答案】B （A）24 （B）18 （C）12 （D）9 【解析】 试题分析：由题意，小明从街道的E处出发到F处最短路径的条数为6，再从F处到G ?=，故处最短路径的条数为3，则小明到老年公寓可以选择的最短路径条数为6318 选B. 【考点】计数原理、组合 【名师点睛】分类加法计数原理在使用时易忽视每类中每一种方法都能完成这件事情，类与类之间是相互独立的；分步乘法计数原理在使用时易忽视每步中某一种方法只是完成这件事的一部分，而未完成这件事，步步之间是相互关联的． 2．如图，一只蚂蚁从点出发沿着水平面的线条爬行到点，再由点沿着置于水平面的长方体的棱爬行至顶点，则它可以爬行的不同的最短路径有（ B ）条
A. 40 B. 60 C. 80 D. 120 【解析】试题分析：蚂蚁从到需要走五段路，其中三纵二竖，共有条路径，从到共有条路径，根据分步计数乘法原理可知，蚂蚁从到可以爬行的不同的最短路径有条，故选B. 考点：分步计数乘法原理. 二、解答题 3．某城市有连接8个小区A、B、C、D、E、F、G、H和市中心O的整齐方格形道路网，每个小方格均为正方形，如图，某人从道路网中随机地选择一条最短路径，由小区A前往H. (1)列出此人从小区A到H的所有最短路径(自A至H依次用所经过的小区的字母表示)； (2)求他经过市中心O的概率． 【答案】(1)见解析（2）2 3 【解析】 解：(1)此人从小区A前往H的所有最短路径为：
高三数学(理一轮复习—— 10.3排列与组合的综合应用 教学目标:1. 进一步加深对排列、组合意义理解的基础上,掌握有关排列、组合综合题的基本解 法,提高分析问题和解决问题的能力,学会分类讨论的思想. 2. 使学生掌握解决排列、组合问题的一些常用方法。 教学重点:排列组合综合题的解法。教学过程: 一.主要知识: 解排列组合问题,首先要弄清一件事是“分类”还是“分步”完成,对于元素之间的关系, 还要考虑“是有序”的还是“无序的” ,也就是会正确使用分类计数原理和分步计数原理、排列定义和组合定义,其次,对一些复杂的带有附加条件的问题,需掌握以下几种常用的解题方法: 1.特殊优先法:对于存在特殊元素或者特殊位置的排列组合问题,我们可以从这些特殊的东西入手,先解决特殊元素或特殊位置,再去解决其它元素或位置,这种解法叫做特殊优先法。 2.科学分类法:对于较复杂的排列组合问题,由于情况繁多,因此要对各种不同情况,进行 3.分配、分组(堆问题的解法: 4. 插空法 :解决一些不相邻问题时, 可以先排一些元素然后插入其余元素, 使问题得以解决。 5.捆绑法:相邻元素的排列,可以采用“整体到局部”的排法,即将相邻的元素当成“一个” 6.排除法:从总体中排除不符合条件的方法数,这是一种间接解题的方法 . 7.剪截法(隔板法 :n 个相同小球放入m(m≤ n 个盒子里 , 要求每个盒子里至少有一个小球
的放法等价于 n 个相同小球串成一串从间隙里选 m-1个结点剪成 m 段 (插入 m -1块隔板 , 有 11 --m n C 种方法 . 8. 错位法:编号为 1至 n 的 n 个小球放入编号为 1到 n的 n 个盒子里 , 每个盒子放一个小球 . 要求小球与盒子的编号都不同 , 这种排列称为错位排列 . 特别当 n=2,3,4,5时的错位数各为 1,2,9,44.2个、 3个、 4个元素的错位排列容易计算。关于 5个元素的错位排 列的计算,可以用剔除法转化为 2个、 3个、 4个元素的错位排列的问题: ① 5个元素的全排列为:5 5120A =; ②剔除恰好有 5对球盒同号 1种、恰好有 3对球盒同号 (2个错位的 351C ?种、恰好有 2对球盒同号 (3个错位的 252C ?种、恰好有 1对球盒同号 (4个错位的 1 59C ?种。 ∴ 120-1-351C ?-252C ?-1 59C ?=44. 用此法可以逐步计算:6个、 7个、 8个、……元素的错位排列问题。 二.典例分析 【题型一】“分配” 、“分组”问题 例 1.将 6本不同的书按下列分法,各有多少种不同的分法? ⑴分给学生甲 3 本,学生乙 2本,学生丙 1本;
难点29 排列、组合的应用问题 排列、组合是每年高考必定考查的内容之一，纵观全国高考数学题，每年都有1～2道排列组合题，考查排列组合的基础知识、思维能力. ●难点磁场 (★★★★★)有五张卡片，它们的正、反面分别写0与1，2与3，4与5，6与7，8与9，将其中任意三张并排放在一起组成三位数，共可组成多少个不同的三位数？ ●案例探究 ［例1］在∠AOB 的OA 边上取m 个点，在OB 边上取n 个点(均除O 点外)，连同O 点共m +n +1个点，现任取其中三个点为顶点作三角形，可作的三角形有( ) 12 12111121 21 2121 211211C C C D.C C C C C C C.C C C C .C B C C C A.C n m n m n m m n n m m n n m m n n m +++++++++ 命题意图：考查组合的概念及加法原理，属★★★★★级题目. 知识依托：法一分成三类方法；法二，间接法，去掉三点共线的组合. 错解分析：A 中含有构不成三角形的组合，如：C 11+m C 2n 中， 包括O 、B i 、B j ;C 1 1+n C 2m 中，包含O 、A p 、A q ，其中A p 、A q ,B i 、B j 分别表示OA 、OB 边上不同于O 的点；B 漏掉△A i OB j ； D 有重复的三角形.如C 1 m C 21+n 中有△A i OB j ,C 21+m C 1n 中也有△A i OB j . 技巧与方法：分类讨论思想及间接法. 解法一：第一类办法：从OA 边上(不包括O )中任取一点与从OB 边上(不包括O )中任取 两点，可构造一个三角形，有C 1 m C 2n 个；第二类办法：从OA 边上(不包括O )中任取两点与 OB 边上(不包括O )中任取一点，与O 点可构造一个三角形，有C 2 m C 1n 个；第三类办法：从 OA 边上(不包括O )任取一点与OB 边上(不包括O )中任取一点，与O 点可构造一个三角形， 有C 1 m C 1n 个.由加法原理共有N =C 1m C 2n +C 2m C 1n +C 1m C 1n 个三角形. 解法二：从m +n +1中任取三点共有C 3 1++n m 个，其中三点均在射线OA (包括O 点)，有 C 31+m 个，三点均在射线OB (包括O 点)，有C 31+n 个.所以，个数为N =C 3 1++n m －C 31+m －C 31+n 个. 答案：C ［例2］四名优等生保送到三所学校去，每所学校至少得一名，则不同的保送方案的总数是_________. 命题意图：本题主要考查排列、组合、乘法原理概念，以及灵活应用上述概念处理数学问题的能力，属★★★★级题目. 知识依托：排列、组合、乘法原理的概念. 错解分析：根据题目要求每所学校至少接纳一位优等生，常采用先安排每学校一人，而后将剩的一人送到一所学校，故有3A 3 4种.忽略此种办法是：将同在一所学校的两名学生按 进入学校的前后顺序，分为两种方案，而实际题目中对进入同一所学校的两名学生是无顺序要求的.
目录 摘要 (1) 1.组合数学概述 (1) 2.组合数学在生活中的应用 (1) 3.组合数学与计算机软件 (1) 3.1 信息时代的组合数学 (2) 3.2 组合数学在计算机软件的应用 (2) 3.3组合数学与计算机软件的关系 (2) 3.4组合数学在国外软件业的发展状况 (2) 4 Ramsey 数在计算机科学中的应用 (3) 4.1Ramsey 定理和Ramsey 数 (3) 4.2信息检索 (3) 参考文献 (5)
组合数学在计算机中的应用 摘要：介绍了组合数学的概念、起源与研究的主要内容,分析了组合数学的特点以及其在生活中的应用,阐述了组合数学与计算机软件的联系,并着重通过两个例子说明了Ramsey 数在计算机科学的信息检索中的重要应用。 关键词：组合数学;组合算法;Ramsey 数;信息检索; 1：组合数学概述 组合数学，又称为离散数学，但有时人们也把组合数学和图论加在一起算成是离散数学。组合数学是计算机出现以后迅速发展起来的一门数学分支。计算机科学就是算法的科学，而计算机所处理的对象是离散的数据，所以离散对象的处理就成了计算机科学的核心，而研究离散对象的科学恰恰就是组合数学。组合数学的发展改变了传统数学中分析和代数占统治地位的局面。现代数学可以分为两大类：一类是研究连续对象的，如分析、方程等，另一类就是研究离散对象的组合数学。组合数学不仅在基础数学研究中具有极其重要的地位，在其它的学科中也有重要的应用，如计算机科学、编码和密码学、物理、化学、生物等学科中均有重要应用。微积分和近代数学的发展为近代的工业革命奠定了基础。而组合数学的发展则是奠定了本世纪的计算机革命的基础。计算机之所以可以被称为电脑，就是因为计算机被人编写了程序，而程序就是算法，在绝大多数情况下，计算机的算法是针对离散的对象，而不是在作数值计算。正是因为有了组合算法才使人感到，计算机好象是有思维的。 2：组合数学在生活中的应用 在日常生活中我们常常遇到组合数学的问题。如果你仔细留心一张世界地图，你会发现用一种颜色对一个国家着色，那么一共只需要四种颜色就能保证每两个相邻的国家的颜色不同。这样的着色效果能使每一个国家都能清楚地显示出来。但要证明这个结论确是一个著名的世界难题，最终借助计算机才得以解决，最近人们才发现了一个更简单的证明。 当你装一个箱子时，你会发现要使箱子尽可能装满不是一件很容易的事，你往往需要做些调整。从理论上讲，装箱问题是一个很难的组合数学问题，即使用计算机也是不容易解决的。航空调度和航班的设定也是组合数学的问题。怎样确定各个航班以满足不同旅客转机的需要，同时也使得每个机场的航班起落分布合理。此外，在一些航班有延误等特殊情况下，怎样作最合理的调整，这些都是组合数学的问题。 组合数学在企业管理，交通规划，战争指挥，金融分析等领域都有重要的应用。在美国有一家用组合数学命名的公司，他们用组合数学的方法来提高企业管理的效益，这家公司办得非常成功。此外，试验设计也是具有很大应用价值的学科，它的数学原理就是组合设计。用组合设计的方法解决工业界中的试验设计问题，在美国已有专门的公司开发这方面的软件。最近，德国一位著名组合数学家利用组合数学方法研究药物结构，为制药公司节省了大量的费用，引起了制药业的关注。 总之，组合数学无处不在，它的主要应用就是在各种复杂关系中找出最优的方案。所以组合数学完全可以看成是一门量化的关系学，一门量化了的运筹学，一门量化了的管理学。 3：组合数学与计算机软件 随着计算机网络的发展，计算机的使用已经影响到了人们的工作，生活，学习，社会活动以及商业活动，而计算机的应用根本上是通过软件来实现的。
排列组合问题的解题策略 关键词：排列组合,解题策略 ①分堆问题； ②解决排列、组合问题的一些常用方法：错位法、剪截法（隔板法）、捆绑法、剔除法、插孔法、消序法(留空法). 一、相临问题——捆绑法 例1．7名学生站成一排，甲、乙必须站在一起有多少不同排法？ 解：两个元素排在一起的问题可用“捆绑”法解决，先将甲乙二人看作一个元素与其他五人进行排列，并考虑甲乙二人的顺序，所以共有种。 评注：一般地: 个人站成一排,其中某个人相邻,可用“捆绑”法解决，共有种排法。 二、不相临问题——选空插入法 例2．7名学生站成一排，甲乙互不相邻有多少不同排法？ 解：甲、乙二人不相邻的排法一般应用“插空”法，所以甲、乙二人不相邻的排法总数应为：种 . 评注：若个人站成一排，其中个人不相邻，可用“插空”法解决，共有种排法。 三、复杂问题——总体排除法 在直接法考虑比较难，或分类不清或多种时，可考虑用“排除法”，解决几何问题必须注意几何图形本身对其构成元素的限制。 例3.(1996年全国高考题)正六边形的中心和顶点共7个点，以其中3个点为顶点的三角形共有多少个. 解：从7个点中取3个点的取法有种，但其中正六边形的对角线所含的中心和顶点三点共线不能组成三角形，有3条，所以满足条件的三角形共有－3＝32个. 四、特殊元素——优先考虑法 对于含有限定条件的排列组合应用题，可以考虑优先安排特殊位置，然后再考虑其他位置的安排。
例4．(1995年上海高考题) 1名老师和4名获奖学生排成一排照像留念，若老师不排在两端，则共有不同的排法种． 解：先考虑特殊元素（老师）的排法，因老师不排在两端，故可在中间三个位置上任选一个位置，有种，而其余学生的排法有种，所以共有＝72种不同的排法. 例5．（2000年全国高考题）乒乓球队的10名队员中有3名主力队员，派5名队员参加比赛，3名主力队员要安排在第一、三、五位置，其余7名队员选2名安排在第二、四位置，那么不同的出场安排共有种. 解：由于第一、三、五位置特殊，只能安排主力队员，有种排法，而其余7名队员选出2名安排在第二、四位置，有种排法，所以不同的出场安排共有＝252种. 五、多元问题——分类讨论法 对于元素多，选取情况多，可按要求进行分类讨论，最后总计。 例6．（2003年北京春招）某班新年联欢会原定的5个节目已排成节目单，开演前又增加了两个新节目.如果将这两个节目插入原节目单中，那么不同插法的种数为（A ） A．42 B．30 C．20 D．12 解：增加的两个新节目，可分为相临与不相临两种情况：1.不相临：共有A62种；2.相临：共有A22A61种。故不同插法的种数为：A62 +A22A61=42 ，故选A。 例7．（2003年全国高考试题）如图，一个地区分为5个行政区域，现给地图着色，要求相邻地区不得使用同一颜色，现有4种颜色可供选择，则不同的着色方法共有多少种？（以数字作答） 解：区域1与其他四个区域相邻，而其他每个区域都与三个区域相邻，因此，可以涂三种或四种颜色．用三种颜色着色有=24种方法, 用四种颜色着色有=48种方法,从而共有24+48=72种方法,应填72. 六、混合问题——先选后排法 对于排列组合的混合应用题，可采取先选取元素，后进行排列的策略． 例8．（2002年北京高考）12名同学分别到三个不同的路口进行车流量的调查，若每个路口4人，则不同的分配方案共有（） A．种B．种
排列数、组合数及二项式定理整理 慈济中学全椒 刘 1、排列数公式 m n A =)1()1(+--m n n n Λ=！！ )(m n n -.(n ，m ∈N*，且m n ≤)． 2、排列恒等式 (1) 1(1)m m n n A n m A -=-+;(2) 1m m n n n A A n m -= -;(3)11m m n n A nA --=; (4)11n n n n n n nA A A ++=-; (5) 1 1m m m n n n A A mA -+=+.(6) 1!22!33!!(1)!1n n n +?+?++?=+-L . 3、组合数公式 m n C =m n m m A A =m m n n n ???+--ΛΛ21)1()1(=！！！)(m n m n -?(n ∈N*，m N ∈，且m n ≤). 4、组合数的两个性质 (1) m n C =m n n C - ; (2) m n C +1 -m n C =m n C 1 +. 5、排列数与组合数的关系 m m n n A m C =?！ . 6、二项式定理： 011()()n n n r n r r n n n n n n a b C a C a b C a b C b n N --*+=+++++∈L L 【注】： 1．基本概念： ①二项式展开式：右边的多项式叫做()n a b +的二项展开式。 ②二项式系数:展开式中各项的系数r n C (0,1,2,,)r n =???. ③项数：共(1)r +项，是关于a 与b 的齐次多项式 ④通项：展开式中的第1r +项r n r r n C a b -叫做二项式展开式的通项。用1r n r r r n T C a b -+=表示。 2．注意关键点： ①项数：展开式中总共有(1)n +项。 ②顺序：注意正确选择a ,b ,其顺序不能更改。()n a b +与()n b a +是不同的。 ③指数：a 的指数从n 逐项减到0，是降幂排列。b 的指数从0逐项减到n ，是升幂排列。
模块：十二、排列组合、二项式定理、概率统计 课题：3、排列与组合的综合应用 教学目标：进一步加深对排列、组合意义理解的基础上，掌握有关排列、组合综合题的基本解法，提高分析问题和解决问题的能力，学会分类讨论的思想． 掌握解决排列、组合问题的一些常用方法． 重难点：掌握解决排列、组合问题的一些常用方法． 一、知识要点 常用解题方法： 1、特殊优先法 2、分类讨论法 3、分组（堆）问题 4、插空法 5、捆绑法 6、排除法 7、隔板法 8、错位法 9、容斥法 二、例题精讲 例1、将6本不同的书按下列分法，各有多少种不同的分法？ （1）分给学生甲3 本，学生乙2本，学生丙1本； （2）分给甲、乙、丙3人，其中1人得3本、1人得2 本、1 人得1 本； （3）分给甲、乙、丙3人，每人2本； （4）分成3堆，一堆3 本，一堆2 本，一堆1 本； （5）分成3堆，每堆2 本 （6）分给分给甲、乙、丙3人，其中一人4本，另两人每人1本； （7）分成3堆，其中一堆4本，另两堆每堆1本。 答案：（1）60；（2）360；（3）90；（4）60；（5）15；（6）90；（7）15． 例2、求不同的排法种数： （1）6男2女排成一排，2女相邻； （2）6男2女排成一排，2女不能相邻； （3）4男4女排成一排，同性者相邻； （4）4男4女排成一排，同性者不能相邻． 答案：（1）10080；（2）30240；（3）1152；（4）1152.
例3、有13名医生,其中女医生6人．现从中抽调5名医生组成医疗小组前往灾区,若医疗小组至少有2名男医生，同时至多有3名女医生，设不同的选派方法种数为P ，则下列等式 （1）514 1376;C C C - （2）23324157676767C C C C C C C +++; （3）514513766C C C C --; （4）23 711C C ; 其中能成为P 的算式有_________种． 答案：（2）（3） 例4、对某种产品的6件不同正品和4件不同次品,一一进行测试,到区分出所有次品为止．若所有次品恰好在第五次测试被全部发现,则这样的测试方法有 种． 答案：576种 例5、某班新年联欢会原定的5个节目已排成节目单,开演前有增加了2个新节目,如果将这两节目插入节目单中,那么不同的插法种数为 ． 答案：42. 例6、从10 种不同的作物中选出6 种放入6个不同的瓶子中展出，如果甲、乙两种种子不能放入第1号瓶内,那么不同的放法共有 种． 答案：120960 例7、将3种作物种植在如图的5块试验田里,每块种植一种作物且相邻的 试验田不能种植同一种作物,不同的种植方法共有________种． 答案：42 例8、四面体的顶点和各棱中点共10个点,在其中取4个不共面的点,不同的取法共有 种． 答案：141种 例9、从黄瓜，白菜，油菜，扁豆4种蔬菜品种中选出3种，分别种在不同土质的三块土地上，其中黄瓜必须种植，不同的种植方法共有 种． 答案：18种 例10、有四个不同的小球,全部放入四个不同的盒子内,恰有两个盒子不放球的放法总数为
课题：___排列组合应用_ 教学任务 教学过程设计 排列组合应用 一、选择： 1、某班元旦联欢会原定的5个学生节目已排成节目单，开演前又增加了两个教师节目 入原节目单中，那么不同插法的种数为（） A．42B．30C．20D．12 2、将1，2，3，4填入标号为1，2，3，4的四个方格里，没格填一个数字，则每个方格的标号与所填的数字均不相同的填法（）种. A． 6 B． 9 C． 11 D．23 3、6张同排连号的电影票，分给3名教师与3名学生，若要求师生相间而坐，则不同的分法有（）A．33 34 p p?B．33 33 p p?C．33 44 p p?D．33 33 2p p? 4、有两条平行直线a和b，在直线a上取4个点，直线b上取5个点，以这些点为顶点作三角形，这样的三角形共有（） A．70B．80C．82D．84 二、填空： 5、从4种蔬菜品种中选出3种，分别种在不同土质的3块土地上进行实验，有 _____种不同的种植方法。 6、9位同学排成三排，每排3人，其中甲不站在前排，乙不站在后排，这样的排法种数共有种 7、3名医生和6名护士被分配到3所学校为学生体检，每所学校分配1名医生和2名护士，不同的分配方法共有_____________种。 8、某兴趣小组有4名男生，5名女生：（1）从中选派5名学生参加一次活动，要求必须有2名男生，3名女生，且女生甲必须在内，有种选派方法；（2）从中选派5名学生参加一次活动，要求有女生但人数必须少于男生，有_ _ __种选派方法；（3）分成三组，每组3人，有种不同分法 9、一天课表中，6节课要安排3门理科，3门文科，要使文、理科间排，不同的排课方法有 _ 种；要使3门理科的数学与物理连排，化学不得与数学、物理连排，不同的排课方法有种
组合的综合应用 探究点1 有限制条件的组合问题 课外活动小组共13人，其中男生8人，女生5人，并且男、女生各有一名队长，现从中选5人主持某项活动，依下列条件各有多少种选法？ (1)至少有一名队长当选． (2)至多有两名女生当选． (3)既要有队长，又要有女生当选． 【解】 (1)至少有一名队长含有两种情况：有一名队长和两名队长，故共有C12·C411＋C22·C311＝825种．或采用排除法有C513－C511＝825种． (2)至多有两名女生含有三种情况：有两名女生、只有一名女生、没有女生，故共有C25·C38＋C15·C48＋C58＝966种． (3)分两种情况： 第一类：女队长当选，有C412种； 第二类：女队长不当选， 有C14·C37＋C24·C27＋C34·C17＋C44种． 故共有C412＋C14·C37＋C24·C27＋C34·C17＋C44＝790种． [变问法]在本例条件下，至多有1名队长被选上的方法有多少种？ 解：分两类情况： 第一类：没有队长被选上，从除去两名队长之外的11名学生中选取5人有C511＝462种选法．第二类：一名队长被选上，分女队长被选上和男队长被选上，不同的选法有：C411＋C411＝660种选法． 所以至多1名队长被选上的方法有462＋660＝1 122 种． 有限制条件的组合问题分类 有限制条件的抽(选)取问题，主要有两类： 一是“含”与“不含”问题，其解法常用直接分步法，即“含”的先取出，“不含”的可把所指元素去掉再取，分步计数； 二是“至多”“至少”问题，其解法常有两种解决思路：一是直接分类法，但要注意分类要不重不漏；二是间接法，注意找准对立面，确保不重不漏． 1.若从1，2，3，…，9这9个整数中取4个不同的数，使其和为奇数，则不同的取法共有( ) A．60种B．63种
“解排列、组合应用问题”的思维方法 一、优先考虑： 对有特殊元素（即被限制的元素）或特殊位置（被限制的位置）的排列，通常是先排特殊元素或特殊位置，再考虑其它的元素或其它的位置。 例1．（1）由0、1、2、3、4、可以组成 个无重复数字的三位数。 （2） 由1、2、3、4、5组成没有重复数字的五位数，其中小于50000的偶数共有 个。 （3） 5个人排成一排，其中甲不排在两端也不和乙相邻排列的排列共有 种。 二、“捆”在一起：有要求元素相邻（即连排）的排列问题，可以先将相邻的元素看作一个“整体”与其它元素排列，然后“整体”内部再进行排列。 例2．（1） 有3位老师、4名学生排成一排照相，其中老师必须在一起的排法共有 种。 （2） 有2位老师和6名学生排成一排，使两位老师之间有三名学生，这样的排法共有 种。 三、插空档：有要求元素不相邻（即间隔排）的排列问题，可以制造空档插空。 例3．（1）五种不同的收音机和四种不同的电视机陈列一排，任两台电视机不靠在一起，有 种陈列方法。 （2）6名男生6名女生排成一排，要求男女相间的排法有 种。 四、减去特殊情况（即逆向思考）：先算暂时不考虑限制条件的排列或组合种数，然后再从中减去所有不符合条件的排列或组合数。 例4．（1）以正方体的顶点为顶点的四面体共有 个。 （2） 由0、1、2、3、4、可以组成 个无重复数字的三位数。 （3）集合A 有8个元素，集合B 有7个元素，B A 有4个元素，集合C 有3个元素且满足下列条件： B C A C B A C ,,的集合C 有几个。 （4）从6名短跑运动员中选4人参加4 100米的接力赛，如果其中甲不能跑第一棒，乙不能跑第四棒，共有多少种参赛方案？ 五、先组后排：排列、组合综合题，通常都是先考虑组合后考虑排列。 例5（1）用1、2、3、 9这九个数字，能组成由3个奇数数字、2个偶数数字的不重复的五位数有 个。 （2）有8本不同的书，从中取出6本，奖给5位数学优胜者，规定第一名（仅一人）得2本，
排列与组合的应用 四川成都市大弯中学 李植武 摘要 在信息学奥林匹克竞赛中，多次出现了排列与组合的竞赛题目。本文介绍了排列与组合的概念、公式，重点讲解了排列与组合的生成算法，最后通过几个竞赛题目的解决，体现了排列与组合在信息学竞赛中的应用。 关键词 排列 组合 生成 应用 说明：本文中的pascal 程序在Lazarus v0.9.22 beta 下调试完成，c 程序dev-c++ 4.9.9.2下调试完成，所有程序通过相应数据测试。 一、排列与组合 1．排列及公式 (1)线排列 一般地，从n 个不同元素中，取出m(m ≤n)个元素按照一定的顺序排成一列，叫做从n 个不同元素中取出m 个元素的一个线排列；从n 个不同元素中取出m(m ≤n)个元素的所有线排列的个数，叫做从n 个不同元素中取出m 个元素的排列数， 用符号 m n A 表示。 )! (!A 1)-m -...(n )2)(1(m n m n n n n n A m n -= --= 规定 0！＝1。 (2)圆排列 从n 个不同元素中取出m 个元素按照某种次序（如逆时针）排成一个圆圈， 称这样的排列为圆排列，圆排列个数为)! (! m n m n m A m n -= 。 因为从n 个不同元素中取出m 个元素排成一列的个数是m n A 。不妨设一个排 列是：a 1a 2…a m 。而这个排列与排列a 2…a m a 1, a 3…a m a 1a 2,…, a m a 1a 2…a m-1，是一样 的圆排列，共有m 个，所以一个圆排列对应m 个普通排列，所以有圆排列数m A m n 。 (3)无限重排列 从n 个不同元素中取r 个元素按次序排列，每个元素可以取无限次，这样的排列称为无限重排列。显然，其排列数为n r 。 (4)有限重排列 从k 个不同元素{ a 1a 2…a k }中取n 个元素按次序排列，元素a i 可以取r i 次,r 1+r 2+...+r k =r ，这样的排列称为有限重排列。 实际上,这个问题与下面的问题等价：
第九讲 排列组合综合应用 【内容概述】 乘法原理是指做一件事，完成它需要分成几个步骤，做第一步有m 1种不同的方法， 做第二步有m 2种不同的方法…做第n 步有m n 种不同的方法，那么完成这件事共有N=m 1×m 2×……×m n 种不同方法（即每一步都不能单独完成这件事情，需要所有步骤合在一 起才能完成这件事情） 加法原理是指做一件事，完成它可以有几类办法，在第一类办法中，有m 1种不同的 方法，在第二类办法中，有m 2种不同的方法……在第n 类办法中，有m n 种不同的方法。 那么完成这件事共有N=m 1+m 2+m n 种不同方法。（即每一类办法都能独立完成，每一类与 另一类不重复，所有这些类型合起来构成这个事情） 【典型题解】 例1 某人到食堂去买饭，食堂里有4种荤菜，3种素菜，2种汤，他要各买一样，共有多少种不同的买法？ 【答案解析】根据题目条件可知，买饭可以分3个步骤。直接利用乘法原理计算。 不同的买法的种数：24234=??（种） 练习一“IMO ”是国际数学奥林匹克的缩写，把这三个字母用三种不同的颜色来写，现有五种不同颜色的笔，问共有多少种不同的写法？ 【答案解析】根据题目条件可知，写完IMO 可以分三个步骤，第一步写“I ”有5种写法，第二步写“M ”有4种写法，第三步写“O ”有3种写法。直接利用乘法原理计算。 不同的写法的种数60345=??（种） 例2 一个篮球队，五名队员A 、B 、C 、D 、E ，由于某种原因，C 不能做中锋，而其余 四人可以分配到五个位置的任何一个上，问：共有多少种不同的站位方法？ 【答案解析】把球场的上的五个位置分别称为1、2、3、4、5号位；令1号位为中锋，由于C 不能做中锋，那么还有4种不同的选择方法，2号位还有剩下的4个人可供选择，3号位还有剩下的3个人可供选择，4号位还有剩下的2个人可供选择，5号位只剩个人可供选择，根据乘法原理，它们的积就是全部的选择方法． 不同的站位方法：9612344=????（种） 练习二 广州电话号码有8个数码，其中第一个数字不为0，而且数字不重复，这样的电话号码共有多少个？ 【答案解析】首先考虑第1个位置，有9种选择。其它位置根据乘法原理，依次有9、8、7、6、5、4、3种选择。 电话号码个数：163296034567899=???????（个）
课题：___排列组合应用_教学任务 教学流程说明 教学过程设计
排列组合应用 一、选择： 1、某班元旦联欢会原定的5个学生节目已排成节目单，开演前又增加了两个教师节目如果将这两个教师节目插入原节目单中，那么不同插法的种数为（ A ） A ．42 B ．30 C ．20 D ．12 2、将1，2，3，4填入标号为1，2，3，4的四个方格里，没格填一个数字，则每个方格的标号与所填的数字均不相同的填法（B ）种. A ． 6 B ． 9 C ． 11 D ． 23 3、6张同排连号的电影票，分给3名教师与3名学生，若要求师生相间而坐，则不同的分法有 （ D ） A ．333 4p p ? B ．3333p p ? C ．3344p p ? D ．33332p p ?
4、有两条平行直线a 和b ，在直线a 上取4个点，直线b 上取5个点，以这些点为顶点作三角形，这样的三角形共有（A ） A ．70 B ．80 C ．82 D ．84 二、填空： 5、从4种蔬菜品种中选出3种，分别种在不同土质的3块土地上进行实验，有 __24___种不同的种植方法。 6、9位同学排成三排，每排3人，其中甲不站在前排，乙不站在后排，这样的排法种数共有 166320 种 7、3名医生和6名护士被分配到3所学校为学生体检，每所学校分配1名医生和2名护士，不同的分配方法共有______540________种。 8、某兴趣小组有4名男生，5名女生：（1）从中选派5名学生参加一次活动，要求必须 有2名男生，3名女生，且女生甲必须在内，有 22 4436C C = 种选派方法；（2）从 中选派5名学生参加一次活动， 要求有女生但人数必须少于男生，有__14235 4 5 4 45C C C C +=__种选派方法；（3）分成三组，每组3人，有 333963 3 3280C C C P = 种不同分法 9、一天课表中，6节课要安排3门理科，3门文科，要使文、理科间排，不同的排课方法有 72种；要使3门理科的数学与物理连排，化学不得与数学、物理连排，不同的排课方法有 144种 三、解答 10、甲、乙、丙三人值周，从周一至周六，每人值两天，但甲不值周一，乙不值周六，问可以排出多少种不同的值周表 ？ 答案：解法一：（排除法）4221 31424152426=+-C C C C C C ． 解法二：分为两类：一类为甲不值周一，也不值周六，有2 324C C ；另一类为甲不值周一，但值周六，有2 41 4C C ，∴一共有2 41 4C C +2 32 4C C ＝42种方法． 11、某科技组有6名同学，现在从中选出3人去参观展览，至少有1名女生入选时的不同 选法有16种，则小组中的女生数目是多少？ 答案：2 12、赛艇运动员10人，3人会划右舷，2人会划左舷，其余5人两舷都能划，现要从中挑选6人上艇，平均分配在两舷上划桨，共有多少种选法？ 答案：333223133 3763553545675C C C C C C C C C +++=． 13、有5张卡片，它们的正反面分别写0或1，2或3，4或5，6或7，8或9，将其中任 意3张并放在一起组成三位数，共可组成多少个不同的三位数？ 答案：986432??= 14、将标号为1，2，…，10的10个球放入标号为1，2，…，10的10个盒子里，每个盒 子放一个球，恰好3个球的标号与盒子的标号不一致的放入方法的种数是多少？ 答案：240 15、第17届世界杯足球赛于2002年夏季在韩国、日本举办、五大洲共有32支球队有幸参
排列与组合的综合应用题（2） 授课教师：黄冈中学高级教师汤彩仙 一、知识概述 例1、有13名医生，其中女医生6人．现从中抽调5名医生组成医疗小组前往灾区，若医疗小组至少有2名男医生，设不同的选派方法种数为P，则下列等式： ①②；③；④； 其中能成为P 的算式有________．（填序号） 答案：②③ 例2、袋中有3个不同的红球，4个不同的黄球，每次从中取出一球，直到把3个红球都取出为止，共有多少种不同的取法？ 解：＋＋＋＋=4110（种）． 例3、某停车场有连成一排的9个停车位，现有5辆不同型号的车需要停放，按下列要求各有多少种停法？（1）5辆车停放的位置连在一起； （2）有且仅有两车连在一起； （3）为方便车辆进出，要求任何3辆车不能在一起. 解：（1）（种）．
（2）（种）． （3）要求任何3辆车不能连在一起，可以分成①5辆车均不相邻，②有且仅有两辆车相邻，③有2组2辆车相邻，三种情况． 有． 例4、设有编号为1，2，3，4，5的五个球和编号为1，2，3，4，5的五个盒子，现将这五个球放入5个盒子内： （1）只有一个盒子空着，共有多少种投放方法？ （2）没有一个盒子空着，但球的编号与盒子编号不全相同，有多少种投放方法？ （3）每个盒子内投放一球，并且至少有两个球的编号与盒子编号是相同的，有多少种投放方法？解：（1）． （2）． （3）（种）． 法二：恰有两个球的编号与盒子编号是相同时，投法数为种； 恰有三个球的编号与盒子编号是相同时，投法数为种； 恰有五个球的编号与盒子编号是相同时，投法数为1种； 故至少有两个球的编号与盒子编号是相同的投法数为
例5、某学习小组有8名同学，从男生中选2人，女生中选1人参加数学、物理、化学三种竞赛，要求每科均有一人参加，共有180种不同的选法，那么该小组中男女同学分别有多少人？ 解：设有男生x人，女生8－x人，（x∈N＋，且2≤x≤7）． 则有，即x（x－1）（8－x）=60． ∴x＝6或x＝5． ∴男生6人，女生2人或男生5人，女生3人． 例6、一栋7层的楼房备有电梯，现有A，B，C，D，E五人从一楼进电梯上楼，求：（1）有且仅有一人要上7楼，且A不在2楼下电梯的所有可能情况种数． （2）在（1）的条件下，一层只能下1个人，共有多少种情况？ 解：（1）分A上不上7楼两类A上7楼，有54种；A不上7楼，有4×4×53种．共有54＋4×4×53=2625种． （2）（种）． 例7、某城市在中心广场建造一个花圃，花圃分为6个部分（如图）．现要栽种4种不同颜色的花，每部分栽种一种且相邻部分不能栽种同样颜色的花，不同的栽种方法有__________种．（以数字作答） 解：（种）．
种。故不同插法的种数为：26A + 22A 16A =42 ，故选A 。 例7．（2003年全国高考试题）如图，一个地区分为5个行政区域，现给地图着色，要求相邻地区 不得使用同一颜色，现有4种颜色可供选择，则不同的着色方法共有 种.（以数字作答） 解：由题意，选用3种颜色时，C 43种颜色，必须是②④同色，③⑤同色，与①进行全排列，涂色 方法有C 43A 33=24种4色全用时涂色方法：是②④同色或③⑤同色，有2种情况，涂色方法有 C 21A 44=48种所以不同的着色方法共有48+24=72种；故答案为72 六、混合问题--先选后排法 对于排列组合的混合应用题，可采取先选取元素，后进行排列的策略． 例8．（2002年北京高考）12名同学分别到三个不同的路口进行车流量的调查，若每个路口4 人，则不同的分配方案共有（ ）种 A. B.3种 C. 种 D. 解：本试题属于均分组问题。则12名同学均分成3组共有 种方法,分配到三 个不同的路口的不同的分配方案共有： 种，故选A 。 例9．（2003年北京高考试题）从黄瓜、白菜、油菜、扁豆4种蔬菜品种中选出 3种，分别种在不同土质的三块土地上，其中黄瓜必须种植，不同的种植方法共 有（） A ．24种 B ．18种 C ．12种 D ．6种
解：黄瓜必选，故再选2种蔬菜的方法数是C32种，在不同土质的三块土地上种植的方法是A33， ∴种法共有C32A33=18，故选B． 七．相同元素分配--档板分隔法 例10．把10本相同的书发给编号为1、2、3的三个学生阅览室，每个阅览室分得的书的本数不小于其编号数，试求不同分法的种数。请用尽可能多的方法求解，并思考这些方法是否适合更一般的情况？本题考查组合问题。 解一：先让2、3号阅览室依次分得1本书、2本书；再对余下的7本书进行分配，保证每个阅览室至少得一本书，这相当于在7本相同书之间的6个“空档”内插入两个相同“I”（一般可视为“隔板”）共有2 C种插法，即有15种分 6 法。 2、解二：由于书相同，故可先按阅览室的编号分出6本，此时已保证各阅览室所分得的书不小于其编号，剩下的4本书有以下四种分配方案：①某一阅览室独得4本，有种分法；②某两个阅览室分别得1本和3本，有种分法；③某两个阅览室各得2本，有种分法；④某一阅览室得2本，其余两阅览室各得1本，有种分法.由加法原理，共有不同的分法3+=15种. 八．转化法: 对于某些较复杂的、或较抽象的排列组合问题，可以利用转化思想,将其化归为简单的、具体的问题来求解 。例11 高二年级8个班,组织一个12个人的年级学生分会,每班要求至少1人,名额分配方案有多少种? 分析此题若直接去考虑的话,就会比较复杂.但如果我们将其转换为等价的其他