排列组合问题解法综述
- 格式:doc
- 大小:16.00 KB
- 文档页数:4
完整版)排列组合的二十种解法(最全的排列组合方法总结)教学目标:1.理解和应用分步计数原理和分类计数原理。
2.掌握解决排列组合问题的常用策略,能运用解题策略解决简单的综合应用题。
提高学生解决问题分析问题的能力。
3.学会应用数学思想和方法解决排列组合问题。
复巩固:1.分类计数原理(加法原理):完成一件事,有n类办法,在第1类办法中有m1种不同的方法,在第2类办法中有m2种不同的方法,…,在第n类办法中有mn种不同的方法,那么完成这件事共有N=m1+m2+…+mn种不同的方法。
2.分步计数原理(乘法原理):完成一件事,需要分成n个步骤,做第1步有m1种不同的方法,做第2步有m2种不同的方法,…,做第n步有mn种不同的方法,那么完成这件事共有N=m1×m2×…×mn种不同的方法。
3.分类计数原理和分步计数原理区别:分类计数原理方法相互独立,任何一种方法都可以独立地完成这件事。
分步计数原理各步相互依存,每步中的方法完成事件的一个阶段,不能完成整个事件。
解决排列组合综合性问题的一般过程如下:1.认真审题弄清要做什么事。
2.确定采取分步还是分类,或是分步与分类同时进行,确定分多少步及多少类。
3.确定每一步或每一类是排列问题(有序)还是组合问题(无序),元素总数是多少及取出多少个元素。
4.解决排列组合综合性问题,往往类与步交叉,因此必须掌握一些常用的解题策略。
一、特殊元素和特殊位置优先策略:例1:由0,1,2,3,4,5可以组成多少个没有重复数字五位奇数。
解:由于末位和首位有特殊要求,应该优先安排,以免不合要求的元素占了这两个位置。
先排末位共有C3,然后排首位共有C4,最后排其它位置共有A4^3.由分步计数原理得C4×C3×A4^3=288.位置分析法和元素分析法是解决排列组合问题最常用也是最基本的方法,若以元素分析为主,需先安排特殊元素,再处理其它元素。
若以位置分析为主,需先满足特殊位置的要求,再处理其它位置。
完整版)☆排列组合解题技巧归纳总结分类计数原理(加法原理)指完成一件事,有n类办法,在第1类办法中有m1种不同的方法,在第2类办法中有m2种不同的方法。
在第n类办法中有mn种不同的方法,那么完成这件事共有N=m1+m2+。
+mn种不同的方法。
分步计数原理(乘法原理)指完成一件事,需要分成n个步骤,做第1步有m1种不同的方法,做第2步有m2种不同的方法。
做第n步有mn种不同的方法,那么完成这件事共有N=m1×m2×。
×mn种不同的方法。
分类计数原理和分步计数原理的区别在于,分类计数原理方法相互独立,任何一种方法都可以独立地完成这件事;分步计数原理各步相互依存,每步中的方法完成事件的一个阶段,不能完成整个事件。
解决排列组合综合性问题的一般过程如下:1.认真审题弄清要做什么事。
2.确定采取分步还是分类,或是分步与分类同时进行,确定分多少步及多少类。
3.确定每一步或每一类是排列问题(有序)还是组合(无序)问题,元素总数是多少及取出多少个元素。
4.解决排列组合综合性问题,往往类与步交叉,因此必须掌握一些常用的解题策略。
一种常用的解题策略是特殊元素和特殊位置优先策略。
例如,由0,1,2,3,4,5可以组成多少个没有重复数字五位奇数,可以先排末位共有C3^1种方法,然后排首位共有C4^3种方法,最后排其它位置共有A4^1 * 3!种方法,根据分步计数原理得到共有C4^1 * 3^1 * A4^1 * 3.= 288种不同的方法。
另一种常用的解题策略是相邻元素捆绑策略。
例如,7人站成一排,其中甲乙相邻且丙丁相邻,共有多少种不同的排法,可以先将甲乙两元素捆绑成整体并看成一个复合元素,同时丙丁也看成一个复合元素,再与其它元素进行排列,同时对相邻元素内部进行自排。
由分步计数原理可得共有A5^2 * A2^2 = 480种不同的方法。
还有一种常用的解题策略是不相邻问题插空策略。
例如,一个晚会的节目有4个舞蹈、2个相声、3个独唱,舞蹈节目不能连续出场,则节目的出场顺序有多少种,可以先将三种不同的节目分别排列,然后在舞蹈节目之间插入一个相声节目,再在相声节目之间插入一个独唱节目,根据分步计数原理可得共有A4^4 * A2^1 * A3^1 = 种不同的方法。
排列组合解法排列组合问题联系实际生动有趣,但题型多样,思路灵活,因此解决排列组合问题,首先要认真审题,弄清楚是排列问题、组合问题还是排列与组合综合问题;其次要抓住问题的本质特征,采用合理恰当的方法来处理。
教学目标1.进一步理解和应用分步计数原理和分类计数原理。
2.掌握解决排列组合问题的常用策略;能运用解题策略解决简单的综合应用题。
提高学生解决问题分析问题的能力3.学会应用数学思想和方法解决排列组合问题. 复习巩固1.分类计数原理(加法原理)完成一件事,有n 类办法,在第1类办法中有1m 种不同的方法,在第2类办法中有2m 种不同的方法,…,在第n 类办法中有m 种不同的方法,那么完成这件事共有:种不同的方法.2.分步计数原理(乘法原理)完成一件事,需要分成n 个步骤,做第1步有1m 种不同的方法,做第2步有2m 种不同的方法,…,做第n 步有n m 种不同的方法,那么完成这件事共有:种不同的方法.3.分类计数原理分步计数原理区别分类计数原理方法相互独立,任何一种方法都可以独立地完成这件事。
分步计数原理各步相互依存,每步中的方法完成事件的一个阶段,不能完成整个事件. 解决排列组合综合性问题的一般过程如下: 1.认真审题弄清要做什么事2.怎样做才能完成所要做的事,即采取分步还是分类,或是分步与分类同时进行,确定分多少步及多少类。
3.确定每一步或每一类是排列问题(有序)还是组合(无序)问题,元素总数是多少及取出多少个元素.4.解决排列组合综合性问题,往往类与步交叉,因此必须掌握一些常用的解题策略 一.特殊元素和特殊位置优先策略例1.由0,1,2,3,4,5可以组成多少个没有重复数字五位奇数.解:由于末位和首位有特殊要求,应该优先安排,以免不合要求的元素占了这两个位置.先排末位共有13C然后排首位共有14C最后排其它位置共有34A443由分步计数原理得113434288C C A =练习题:7种不同的花种在排成一列的花盆里,若两种葵花不种在中间,也不种在两端的花盆里,问有多少不同的种法?二.相邻元素捆绑策略例2. 7人站成一排,其中甲乙相邻且丙丁相邻, 共有多少种不同的排法.解:可先将甲乙两元素捆绑成整体并看成一个复合元素,同时丙丁也看成一个复合元素,再与其它元素进行排列,同时对相邻元素内部进行自排。
排列组合解题方法和策略总结排列组合是数学中一个重要的概念,它涉及到从n个不同元素中取出m个元素(n>m)进行排列或组合的问题。
排列组合问题在日常生活和科学研究中有着广泛的应用,因此掌握排列组合的解题方法和策略非常重要。
以下是排列组合解题方法和策略的总结:1.明确问题要求:在解决排列组合问题时,首先要明确问题的要求,确定是排列问题还是组合问题,以及具体的限制条件。
2.确定元素范围:根据问题要求,确定所选取元素的范围,明确哪些元素可以选取,哪些元素不能选取。
3.列出所有可能的排列或组合:根据排列组合的公式,列出所有可能的排列或组合,确保不遗漏任何一种可能性。
4.分类讨论:对于一些复杂的问题,需要进行分类讨论。
根据问题的特点,将问题分成若干个子问题,分别求解子问题的排列组合情况。
5.排除法:在某些情况下,可以通过排除法求解问题。
根据问题的限制条件,排除一些不可能的情况,从而减少计算量。
6.递推关系:对于一些具有递推关系的问题,可以利用递推关系求解。
通过递推关系,逐步推导出最终的排列组合情况。
7.容斥原理:容斥原理是解决排列组合问题的一种重要方法。
通过容斥原理,可以将多个排列或组合的情况合并为一个,从而简化计算过程。
8.实际应用:排列组合问题在日常生活和科学研究中有着广泛的应用。
通过实际应用,可以加深对排列组合概念的理解,并掌握解题方法和策略。
解决排列组合问题需要掌握一定的方法和策略。
通过明确问题要求、确定元素范围、分类讨论、排除法、递推关系、容斥原理等方法和策略,可以有效地解决各种排列组合问题。
同时,通过实际应用,可以加深对排列组合概念的理解,提高解题能力。
排列组合在日常生活和科学研究中有着广泛的应用,以下是其中一些典型的应用场景:1.生日庆祝:在生日庆祝中,排列组合可以用来确定不同的庆祝活动安排。
例如,如果有5个朋友参加生日派对,可以使用排列组合确定他们坐在一张圆桌上的不同方式。
2.彩票购买:在购买彩票时,可以使用排列组合来计算不同号码的组合。
排列组合问题的基本类型及解题方法解决排列组合问题要讲究策略,首先要认真审题,弄清楚是排列(有序)还是组合(无序),还是排列与组合混合问题。
其次,要抓住问题的本质特征,准确合理地利用两个基本原则进行“分类与分步”。
加法原理的特征是分类解决问题,分类必须满足两个条件:①类与类必须互斥(不相容),②总类必须完备(不遗漏);乘法原理的特征是分步解决问题,分步必须做到步与步互相独立,互不干扰并确保连续性。
分类与分步是解决排列组合问题的最基本的思想策略,在实际操作中往往是“步”与“类”交叉,有机结合,可以是类中有步,也可以是步中有类。
以上解题思路分析,可以用顺口溜概括为:审明题意,排(组)分清;合理分类,用准加乘;周密思考,防漏防重;直接间接,思路可循;元素位置,特殊先行;一题多解,检验真伪。
(一)特殊元素的“优先安排法”对于特殊元素的排列组合问题,一般先考虑特殊元素,再考虑其他元素的安排。
在操作时,针对实际问题,有时“元素优先”,有时“位置优先”。
例1: 0,2,3,4,5这五个数字,组成没有重复数字的三位数,其中偶数共有几个?解法一:(元素优先)分两类:第一类,含0,0在个位有24A 种,0在十位有1123A A 种;第二类,不含0,有1223A A 种。
故共有2111242323(A A A )+A A 30+=种。
注:在考虑每一类时,又要优先考虑个位。
解法二:(位置优先)分两类:第一类,0在个位有24A 种;第二类,0不在个位,先从两个偶数中选一个放个位,再选一个放百位,最后考虑十位,有111233A A A 种。
故共有21114233A +A A A =30(二)总体淘汰法对于含有否定词语的问题,还可以从总体中把不符合要求的除去,此时应注意既不能多减也不能少减,例如在例1中也可以用此法解答:5个数字组成三位数的全排列为35A ,排好后发现0不能在首位,而且3和5不能排在末尾,这两种不合题意的排法要除去,故有30个偶数.(三)合理分类与准确分步解含有约束条件的排列组合问题,应按元素的性质进行分类,事情的发生的连续过程分步,做到分类标准明确,分布层次清楚,不重不漏.例2:5个人从左到右站成一排,甲不站排头,乙不站第二个位置,不同的站法有 解:由题意,可先安排甲,并按其进行分类讨论:(1)若甲在第二个位置上,则剩下的四人可自由安排,有44A 种方法;(2)若甲在第三个或第四个位置上,则根据分布计数原理不同的站法有113333A A A 种站法;再根据分类计数原理,不同的站法共有:21134333A A A A 78+=种.(四)相邻问题:捆绑法对于某些元素要求相邻排列的问题,可先将相邻元素捆绑成整体并看作一个元素再与其它元素进行排列,同时对相邻元素内部进行自排。
排列组合问题的基本解法1. 排列问题排列问题指的是从n个元素中选取m个元素,按照一定的顺序进行排列。
这里的元素可以是数字、字母、符号等任何类型的数据。
例如,从1, 2, 3, 4中选取3个数字进行排列,共有4种排列方式:(1, 2, 3)、(1, 2, 4)、(1, 3, 4)、(2, 3, 4)。
排列问题的基本解法是使用乘法原理,即将每个位置的可能性相乘。
例如,从n个元素中选取m个元素进行排列,首先在第一个位置有n种选择,第二个位置只有n-1种选择(因为第一个位置已经选了一个),以此类推,直到最后一个位置只有n-m+1种选择。
因此,总的排列数为:n*(n-1)*(n-2)*...*(n-m+1)=n!/(n-m)!。
2. 组合问题组合问题指的是从n个元素中选取m个元素,不考虑它们的排列顺序。
例如,从1, 2, 3, 4中选取3个数字进行组合,只有4种组合方式:(1, 2, 3)、(1, 2, 4)、(1, 3, 4)、(2, 3, 4)。
组合问题的基本解法是使用组合公式,即C(n, m)=n!/m!(n-m)!。
这个公式的含义是,在排列问题中,每个组合有m!种排列方式,因此要除以m!,而同一组合中的元素可以以任意顺序出现,因此要除以(n-m)!。
3. 组合与排列混合问题有些问题既涉及到组合,又涉及到排列,例如从n个元素中选取m 个元素进行排列,或者从n个元素中选取m个元素,再选取p个元素进行排列。
这样的问题可以分解成两个步骤:先从n个元素中选取m个元素,再对这m个元素进行排列。
这种问题的基本解法是先用组合公式求出C(n, m),然后用排列公式求出A(m, p)。
两者相乘就得到了最终的结果,即排列与组合混合问题的解法公式为:C(n, m)*A(m, p)=n!/(m!(n-m)!)*m!/(m-p)!=n!/((n-m)!(n-p)!)。
排列组合常见21种解题方法排列组合是高中数学中的重要知识点,也是考试中常见的题型。
在解决排列组合问题时,我们可以运用多种方法来求解,下面将介绍常见的21种解题方法。
1. 直接法,根据排列组合的定义,直接计算排列或组合的个数。
2. 公式法,利用排列组合的公式进行计算,如排列公式P(n,m)=n!/(n-m)!,组合公式C(n,m)=n!/(m!(n-m)!)。
3. 递推法,通过递推关系式求解排列组合问题,如利用排列数的递推关系P(n,m)=P(n-1,m)+P(n-1,m-1)。
4. 分类讨论法,将问题进行分类讨论,分别求解每种情况的排列组合个数,然后合并得出最终结果。
5. 组合数性质法,利用组合数的性质,如C(n,m)=C(n,n-m),C(n,m)=C(n-1,m)+C(n-1,m-1),简化计算过程。
6. 二项式定理法,利用二项式定理展开式子,求解排列组合问题。
7. 二项式系数法,利用二项式系数的性质,如n个不同元素的排列个数为n!,n个相同元素的排列个数为1,简化计算过程。
8. 容斥原理法,利用容斥原理求解排列组合问题,排除重复计算的部分。
9. 对称性法,利用排列组合的对称性质,简化计算过程。
10. 逆向思维法,从问题的逆向思考,求解排列组合问题。
11. 生成函数法,利用生成函数求解排列组合问题,将排列组合问题转化为多项式求解。
12. 构造法,通过构造合适的排列组合模型,求解问题。
13. 图论法,将排列组合问题转化为图论问题,利用图论算法求解。
14. 动态规划法,利用动态规划算法求解排列组合问题,降低时间复杂度。
15. 贪心算法法,利用贪心算法求解排列组合问题,简化计算过程。
16. 模拟法,通过模拟排列组合过程,求解问题。
17. 枚举法,将所有可能的排列组合情况列举出来,求解问题。
18. 穷举法,通过穷举所有可能的情况,求解问题。
19. 数学归纳法,利用数学归纳法证明排列组合的性质,求解问题。
排列与组合的问题与解法排列与组合是组合数学中的一个重要概念,广泛应用于数学、计算机科学、统计学等领域。
在解决排列与组合的问题时,我们需要理解其基本定义和相关的解法。
本文将介绍排列与组合的概念和性质,并详细阐述其中的解题方法。
一、排列和组合的定义排列和组合是数学中用于描述元素选择和排列方式的概念。
它们的区别在于排列考虑元素的顺序,而组合则不考虑顺序。
1. 排列排列是指从给定元素集合中选取一部分元素进行排列,形成不同的顺序。
设有n个元素,选取m个进行排列,称为从n个元素中取m个元素的排列数,记作P(n, m)。
其计算公式为:P(n, m) = n! / (n - m)!其中,“!”表示阶乘,即连乘从1到n的所有正整数。
2. 组合组合是指从给定元素集合中选取一部分元素,但不考虑元素的顺序,形成的集合。
设有n个元素,选取m个进行组合,称为从n个元素中取m个元素的组合数,记作C(n, m)或者(n choose m)。
其计算公式为:C(n, m) = n! / (m! * (n - m)!)二、排列和组合的性质排列和组合有一些基本的性质,这些性质可以帮助我们在解决问题时快速计算排列数和组合数。
1. 互补关系排列和组合存在互补关系,即P(n, m) = C(n, m) * m!这是因为从n个元素中选取m个元素形成一个组合后,通过对选取的元素进行排列产生不同的排列方式,因此需要乘以m!。
2. 递推关系排列和组合之间还存在递推关系。
假设有n个元素,选取m个进行排列或者组合,有以下递推关系:P(n, m) = P(n-1, m) + P(n-1, m-1)C(n, m) = C(n-1, m) + C(n-1, m-1)递推关系的理解可以通过递归方式进行推导,也可以从组合数的角度去理解。
三、排列和组合的应用举例排列和组合的概念和解法在实际问题中有广泛应用。
下面通过几个典型例子来说明其应用。
1. 生日问题假设一个班级有30个学生,问至少有两个学生生日相同的概率是多少?解法:这个问题可以通过计算不同生日组合的数量,然后除以总的可能组合数量来得到概率。
解决排列组合问题常见策略学习指导1、排列组合的本质区别在于对所取出的元素是作有序排列还是无序排列。
组合问题可理解为把元素取出后放到某一集合中去,集合中的元素是无序的。
较复杂的排列组合问题一般是先分组,再排列。
必须完成所有的分组再排列,不能边分组边排列.排列组合问题的常见错误是重复和遗漏.弄清问题的实质,适当的分类,合理的分步是解决这个错误的关键,采用不同的思路检验结果是否一致是解决这个错误的技巧.集合是常用的工具之一.为了将抽象问题具体化,可以从特殊情形着手,通过画格子,画树图等帮助理解。
“正难则反”是处理问题常用的策略。
常用方法:一. 合理选择主元例1. 公共汽车上有3个座位,现在上来5名乘客,每人坐1个座位,有几种不同的坐法?例2. 公共汽车上有5个座位,现在上来3名乘客,每人坐1个座位,有几种不同的坐法?分析:例1中将5名乘客看作5个元素,3个空位看作3个位置,则问题变为从5个不同的元素中任选3个元素放在3个位置上,共有种不同坐法。
例2中再把乘客看作元素问题就变得比较复杂,将5个空位看作元素,而将乘客看作位置,则例2变成了例1,所以在解决排列组合问题时,合理选择主元,就是选择合适解题方法的突破口。
二. “至少"型组合问题用隔板法对于“至少”型组合问题,先转化为“至少一个"型组合问题,再用n个隔板插在元素的空隙(不包括首尾)中,将元素分成n+1份。
例5. 4名学生分6本相同的书,每人至少1本,有多少种不同分法?解:将6本书分成4份,先把书排成一排,插入3个隔板,6本书中间有5个空隙,则分法有:(种)三。
注意合理分类元素(或位置)的“地位”不相同时,不可直接用排列组合数公式,则要根据元素(或位置)的特殊性进行合理分类,求出各类排列组合数。
再用分类计数原理求出总数。
例6. 求用0,1,2,3,4,5六个数字组成的比2015大的无重复数字的四位数的个数。
解:比2015大的四位数可分成以下三类:第一类:3×××,4×××,5×××,共有:(个);第二类:21××,23××,24××,25××,共有:(个);第三类:203×,204×,205×,共有:(个)∴比2015大的四位数共有237个。
排列组合问题的常见解法一.元素相同问题隔板策略例1.有10个运动员名额,分给7个班,每班至少一个,有多少种分配方案解:因为10个名额没有差别,把它们排成一排.相邻名额之间形成9个空隙.在9个空档中选6个位置插个隔板,可把名额分成7份,对应地分给7个班级,每一种插板方法对应一种分法共有69C 种分法.注:这和投信问题是不同的,投信问题的关键是信不同,邮筒也不同,而这里的问题是邮筒不同,但信是相同的.即班级不同,但名额都是一样的. 练习题:个相同的球装5个盒中,每盒至少一个有多少装法 49C 2.100x y z w +++=求这个方程组的自然数解的组数 3103C 二.环排问题直排策略如果在圆周上m 个不同的位置编上不同的号码,那么从n 个不同的元素的中选取m 个不同的元素排在圆周上不同的位置,这种排列和直线排列是相同的;如果从n 个不同的元素的中选取m 个不同的元素排列在圆周上,位置没有编号,元素间的相对位置没有改变,不计顺逆方向,这种排列和直线排列是不同的,这就是环形排列的问题.一个m 个元素的环形排列,相当于一个有m 个顶点的多边形,沿相邻两个点的弧线剪断,再拉直就是形成一个直线排列,即一个m 个元素的环形排列对应着m 个直线排列,设从n 个元素中取出m 个元素组成的环形排列数为N 个,则对应的直线排列数为mN 个,又因为从n 个元素中取出m 个元素的排成一排的排列数为mnA 个,所以mn mN A=,所以m nA N m=.即从n 个元素中取出m 个元素组成的环形排列数为m nA N m =.n 个元素的环形排列数为!(1)!n n A n N n n n===-例2. 8人围桌而坐,共有多少种坐法解:围桌而坐与坐成一排的不同点在于,坐成圆形没有首尾之分,所以固定一人44A 并从此位置把圆形展成直线其余7人共有(81)!7!-=种排法,即7!7654321840=⨯⨯⨯⨯⨯⨯= 种七班练习题:6颗颜色不同的钻石,可穿成几种钻石圈 120 三.多排问题直排策略例人排成前后两排,每排4人,其中甲乙在前排,丙在后排,共有多少排法解:8人排前后两排,相当于8人坐8把椅子,可以把椅子排成一排.先排前4个位置,2个特殊元素有24A 种排法,再排后4个位置上的特殊元素丙有14A 种,其余的5人在5个位置上任意排列有55A 种,则共有215445A A A 种排法.(排好后,按前4个为前排,后4人为后排分成两排即可)练习题:有两排座位,前排11个座位,后排12个座位,现安排2人就座规定前排中间的3个座位不能坐,并且这2人不左右相邻,那么不同排法的种数是 346解:由于甲乙二人不能相邻,所以前排第1,4,8,11四个位置和后排第1,12位置是排甲乙中的一个时,与它相邻的位置只能排除一个,而其它位置要排除3个,所以共有排列11116181417108238346C C C C +=+=四.排列组合混合问题先选后排策略例4.有5个不同的小球,装入4个不同的盒内,每盒至少装一个球,共有多少不同的装法.解:第一步从5个球中选出2个组成复合元共有25C 种方法.再把4个元素(包含一个复合元素)装入4个不同的盒内有44A 种方法,根据分步计数原理装球的方法共有2454C A练习题:一个班有6名战士,其中正副班长各1人现从中选4人完成四种不同的任务,每人完成一种任务,且正副班长有且只有1人参加,则不同的选法有 192 种五.小集团问题先整体后局部策略例5.用1,2,3,4,5组成没有重复数字的五位数其中恰有两个偶数在1,5在两个奇数之间,这样的五位数有多少个(注:两个偶数2,4在两个奇数1,5之间,这是题意,说这个结构不能被打破,故3只能排这个结构的外围,也就是说要把这个结构看成一个整体与3进行排列).解:把1,5,2,4当作一个小集团与3排队共有22A 种排法,再排小集团内部共有2222A A 种排法,由分步计数原理共有222222A A A 种排法.练习题:1.计划展出10幅不同的画,其中1幅水彩画,4幅油画,5幅国画, 排成一行陈列,要求同一品种的必须连在一起,并且水彩画不在两端,那么共有陈列方式的种数为254254A A A 2. 5男生和5女生站成一排照像,男生相邻,女生也相邻的排法有255255A A A 种 六.正难则反总体淘汰策略例6.从0,1,2,3,4,5,6,7,8,9这十个数字中取出三个数,使其和为不小于10的偶数,不同的取法有多少种解:这问题中如果直接求不小于10的偶数很困难,可用总体淘汰法.这十个数字中有5个偶数5个奇数,所取的三个数含有3个偶数的取法有35C ,只含有1个偶数的取法有1255C C ,和为偶数的取法共有123555C C C +.再淘汰和小于10的偶数共9种,符合条件的取法共有1235559C C C +-练习题:我们班里有43位同学,从中任抽5人,正、副班长、团支部书记至少有一人在内的 抽法有多少种七.平均分组问题除法策略例7. 6本不同的书平均分成3堆,每堆2本共有多少分法解: 分三步取书得222642C C C 种方法,但这里出现重复计数的现象,不妨记6本书为ABCDEF ,若第一步取AB,第二步取CD,第三步取EF该分法记为(AB,CD,EF),则222642C C C 中还有(AB,EF,CD),(CD,AB,EF),(CD,EF,AB)(EF,CD,AB),(EF,AB,CD)共有33A 种取法 ,而这些分法仅是(AB,CD,EF)一种分法,故共有22264233C C C A 种分法.练习题:1 将13个球队分成3组,一组5个队,其它两组4个队, 有多少分法(544138422C C C A ) 名学生分成3组,其中一组4人, 另两组3人但正副班长不能分在同一组,有多少种不同的 分组方法 (1540)3.某校高二年级共有六个班级,现从外地转 入4名学生,要安排到该年级的两个班级且每班安排2名,则不同的安排方案种数为______(2224262290C C A A =) 八. 合理分类与分步策略例8.在一次演唱会上共10名演员,其中8人能能唱歌,5人会跳舞,现要演出一个2人唱歌2人伴舞的节目,有多少选派方法解:10演员中有5人只会唱歌,2人只会跳舞3人为全能演员.选上唱歌人员为标准进行研究 只会唱的5人中没有人选上唱歌人员共有2233C C 种,只会唱的5人中只有1人选上唱歌人员112534C C C 种,只会唱的5人中只有2人选上唱歌人员有2255C C 种,由分类计数原理共有 22112223353455C C C C C C C ++种.解含有约束条件的排列组合问题,可按元素的性质进行分类,按事件发生的连续过程分步,做到标准明确。
排列组合问题解法综述
作者:张年良
来源:《读写算》2012年第95期
排列组合问题是数学中比较抽象的问题,对学生的逻辑思维能力有较高要求。
由于其解法往往是构造性的,因此方法灵活多样,不同解法导致问题难易变化也较大,而且解题过程出现“重复”和“遗漏”的错误较难自检发现。
因而对这类问题归纳总结,并把握一些常见解题模型是必要的。
排列组合应用题的解题方法既有一般的规律,又有很多特别的技巧,它要求我们要认真地审题,对题目中的信息进行科学地加工处理。
一、基础知识复习
(1)两个原理的区别与联系
定义做一件事,完成它可以有n类办法,
第一类办法中有m1种不同的方法,
第二类办法中有m2种不同的方法…,
第n类办法中有mn种不同的方法,
那么完成这件事共有
N=m1+m2+m3+…mn 种不同的方法
做一件事,完成它可以有n个步骤,
做第一步中有m1种不同的方法,
做第二步中有m2种不同的方法……,
做第n步中有mn种不同的方法,
那么完成这件事共有
定义从n个不同元素中取出m个元
素,按一定的顺序排成一列从n个不同元素中取出m个元
素,把它并成一组
种数所有排列的的个数所有排列的的个数
符号
二、解题方法和思路
(一). 注意两个基本原理应用
加法原理和乘法原理是解排列组合应用题的最基本的出发点,可以说对每道应用题我们都要考虑在记数的时候进行分类或分步处理。
例1:n个人参加某项资格考试,能否通过,有多少种可能的结果?
解法1:用分类记数的原理,没有人通过,有种结果;1个人通过,有种结果,……;n 个人通过,有种结果。
所以一共有种可能的结果。
解法2:用分步记数的原理。
第一个人有通过与不通过有两种可能,第二个人也是这样,……,第n个人也是这样。
所以一共有种可能的结果。
例2:同室四人各写了一张贺年卡,先集中起来,然后每人从中拿一张别人的贺年卡,则四张贺年卡不同的分配方式有()
(A)6种(B)9种(C)11种(D)23种
解:设四个人分别为甲、乙、丙、丁,各自写的贺年卡分别为a、b、c、d。
第一步,甲取其中一张,有3种等同的方式;
第二步,假设甲取b,则乙的取法可分两类:
(2)乙取c或d(2种方式),不管哪一种情况,接下来丙、丁的取法也都唯一
(1)乙取a,则接下来丙、丁的取法都是唯一的,是唯一的。
根据加法原理和乘法原理,一共有种分配方式。
(二). 特殊元素(位置)优先
例3:从0,1,……,9这10个数字中选取数字组成偶数,一共可以得到不含相同数字的五位偶数多少个?
解:个位选0,有个,个位不选0且万位不能选0,有个,所以一共可以得到个偶数。
注意 0,2,4,6,8是特殊元素,元素0更为特殊,首位与末位是特殊的位置。
例4:8人站成两排,每排4人,甲在前排,乙不在后排的边上,一共有多少种排法?
解:先排甲,有种排法。
再排乙,有种排法,再排其余的人,又有种排法,所以一共有种排法。
(三). 捆绑法
例5:8人排成一排,甲、乙必须分别紧靠站在丙的两旁,有多少种排法?
解:把甲、乙、丙先排好,有种排法,把这三个人“捆绑”在一起看成是一个,与其余5个人相当于6个人排成一排,有种排法,所以一共有 =1440种排法。
(四). 插入法
例6:排一张有8个节目的演出表,其中有3个小品,既不能排在第一个,也不能有两个小品排在一起,有几种排法?
解:先排5个不是小品的节目,有种排法,它们之间以及最后一个节目之后一共有6个空隙,将3个小品插入进去,有种排法,所以一共有 =7200种排法。
注:捆绑法与插入法一般适用于有如上述限制条件的排列问题。
(五). 排除法
例7;求以一个长方体的顶点为顶点的四面体的个数。
解:从8个点中取4个点,共有种方法,其中取出的4个点共面的有种,所以符合条件的四面体的个数为个。
例8:100件产品中有3件是次品,其余都是正品。
现在从中取出5件产品,其中含有次品,有多少种取法?
解:从100件产品中取5件产品,有种取法,从不含次品的95件中取出5件产品有种取法,所以符合题意的取法有种。
例9:8个人站成一排,其中A与B、A与C都不能站在一起,一共有多少种排法?
解:无限制条件有种排法。
A与B或A与C在一起各有种排法,A、B、C三人站在一起且A在中间有种排法,所以一共有 + =21600种排法。
(六). 机会均等法
例10:10个人排成一队,其中甲一定要在乙的左边,丙一定要在乙的右边,一共有多少种排法?
解:甲、乙、丙三人排列一共有6种排法,在这6种排法中各种排列顺序在10个人的所有排列中出现的机会是均等的,因此符合题设条件的排法种数为。
例11:用1,4,5,四个数字组成四位数,所有这些四位数中的数字的总和为288,求。
解:若不为0,在每一个数位上1,4,5,,出现的机会是均等的。
由于一共可以得到24个四位数,所以每一个数字在每一个数位上出现6次,于是得到:
,解得。
若为0,无解。
排列组合应用题极易出现“重”、“漏”现象,而重”、“漏”错误常发生在该不该分类、有无次序的问题上。
为了更好地防“重”堵“漏”,在做题时需认真分析自己做题思路,也可改变解题角度,利用一题多解核对答案。
在解决排列组合问题时,既要有战略又要有战术,两个原理是战略,排列组合是战术。
战略上能总体驾御驾,战术上能积极突破。
各种解题方法能灵活运用自如,计算不出任何差错。
这才是学好数学的根本所在。