nbhkdz.com冰点文库

第4节 计数原理与排列组合方法汇总


第 4 节 计数原理与排列组合方法汇总

1、分类加法计数原理 完成一件事,有 n 类不同方案,在第 1 类方案中有种不同的方法,在第 2 类办法中有种不同的方法, ??在第 n 类办法中有种不同的方法。那么完成这件 事共有:N=++??+种不同的方法。 注意: (1)分类加法计数原理的使用关键是分类,分类必须明确标准,要求 每一种方法必须属于某一类方法,不同

类的任意两种方法是不同的方法,这时分 类问题中所要求的“不重复” 、 “不遗漏” 。 (2)完成一件事的 n 类办法是相互独立的。从集合角度看,完成一件事分 A、B 两类办法,则 AB=,AB=I(I 表示全集) 。 (3)明确题目中所指的“完成一件事”是指什么事,完成这件事可以有哪 些办法,怎样才算是完成这件事。 2、分步乘法计数原理 完成一件事,需要 n 个步骤,做第 1 步有种不同的方法,做第 2 步有种不同 的方法,??做第 n 步有种不同的方法,那么完成这件事共有:N=· ·??·种 不同的方法。 注意: (1)明确题目中所指的“做一件事”是什么事,单独用题中所给的某 种方法是不是能完成这件事,是不是要经过几个步骤才能完成这件事。 (2)完成这件事需要分成若干个步骤,只有每个步骤都完成了,才算完成 这件事,缺少哪一步,这件事都不可能完成。 (3)根据题意正确分步,要求各步之间必须连续,只有按照这几步逐步去 做,才能完成这件事,各步之间不能重复也不能遗漏。 3、分类加法计数原理与分步乘法计数原理的联系与区别 联系:两个计数原理,都是关于完成一件事的不同方法种数的问题。 区别:分类计数原理与分类有关,各种方法相互独立,用其中任何一种方法 都可以完成这件事;分步计数原理与分步有关,各个步骤相互依存,只有各个步 骤都完成了,这件事才算完成。 分类计数原理与分步计数原理体现了解决问题时将其分解的两种常用方法, 即分步解决或分类解决,是推导排列数与组合数计算公式的依据。要注意“类” 间互相独立, “步”间互相联系。 4、解决基本计数原理问题所用的思想方法及技巧 (1)建模法:建立数学模型,将排列组合问题转化为数学问题,是计数方 法中的基本方法。 (2)枚举法:利用枚举法(如树状图)可以使问题的分析更直观、清楚, 便于发现规律,从而形成恰当的分类或分步的设计思想。 总之, 对于一些较复杂的既要用分类加法计数原理又要用分步乘法计数原理 的问题, 恰当地画出表格, 合理建模或用树状图枚举全部结果是解决问题的基本 思想方法。 5、两个原理的综合运用 (1)必须分清楚两个原理的条件和结论。 如果完成一件事情有两类方案,这两类方案彼此之间是相互独立的,无论哪 一类方案中的哪一种方法都能单独完成这件事情,求完成这件事情的方法种数, 就用分类计数原理。 如果完成一件事情需要分成几个步骤,各个步骤都是不可缺少的,需要依次

完成所有步骤,才能完成这件事情,而完成每一个步骤有若干种不同的方法,求 完成这件事情的方法种数就用分步计数原理。 (2)在解决具体问题时,首先必须弄清楚是“分类”还是“分步” ,接着还 要清楚“分类”或者“分步”的具体标准是什么简单地说“分类互斥” “分步互 依” ,关键是看能否独立完成这件事。与此同时还要注意分类、分步不能重复和 遗漏。 (3)对于较为复杂的既要用分类计数原理,又要用分步计数原理的问题, 我们可以根据题意恰当合理的画出示意图或列出表格, 使问题的实质直观地显现 出来,从而便于我们解题。 (4)分类计数原理和分步计数原理是排列、组合问题的最基本的原理,同 时也是推导排列数、组合数公式的理论依据,还是求解排列、组合问题的基本思 想方法。 6、排列与排列数公式 从 n 个不同元素中,任取 m(m≤n)个元素(这里的被取元素各不相同) 按照一定的顺序排成一列,叫做从 n 个不同元素中取出 m 个元素的一个排列。 注意: (1)排列定义包含两个基本内容:一是“取出元素” ,二是“按照一 定顺序”排列。 (2)定义中“一定顺序”就是说与位置有关,在实际问题中,要由具体问 题的性质和条件决定,这一点是与组合的根本区别。 7、排列数 从 n 个不同元素中取出 m(m≤n)个元素排成一列, 称为从 n 个不同元素中取 出 m 个元素的一个排列.从 n 个不同元素中取出 m 个元素的一个排列数,用符号
m An 表示。排列数公式:

A m ? n(n ? 1) ? (n ? m ? 1) ?

n! (m ? n, n, m ? N ) (n ? m)!

注意:我们把正整数由 1 到 n 的连乘积,叫做 n 的阶乘,用 n!表示。规定 0!=1。 当 m=n 时, n 个不同元素全部取出的一个排列, 叫做 n 个不同元素的一个全 排列,记为 An
n

? n(n ? 1)(n ? 2)? 2 ?1 ? n !
n! (n ? m)!

? (m ? n, n, m ? N ) 注意: (1)排列数公式 A m ? n(n ? 1) ? (n ? m ? 1) 适用于具体计算以及解当 m较

小时含排列数的方程和不等式。 在运用该公式时要注意它的特点:第一个因数是 n,最后一个因数是 n-m+1,共 m 个连续自然数的连乘积。 (2)排列数公式= ,适用于与排列数有关的证明、解方程、解不等式等, 在具体运用时, 则应注意先提取公因式, 再计算, 同时还要注意隐含条件 “m≤n, m,n”的运用。 8、排列的应用 8.1 解排列应用题的基本思想:

解简单的排列应用题首先必须认真分析理解题意, 看能否把问题归结为排列 问题,即是否有顺序。如果是的话,再进一步分析,这里 n 个不同的元素指的是 什么,以及从 n 个不同的元素中任取 m 个元素的每一种排列对应的是什么事情, 然后才能运用排列数公式求解。 8.2 对于有限制条件的排列应用题,要注意: (1)排列的有序性; (2)对受限制条件的位置与元素首先排列,并适当选用直接发或间接法; (3)从位置出发的“填空题”和不相邻问题的“插空法”是解答排列应用 题中常用的方法。某些元素的相邻问题,常用“捆绑法” ,先看成一个元素; (4) 要注意通过排列应用题,神话对分类计数原理和分步计数原理的理解, 培养“全局分类”和“局部分布”意识。 8.3 在有些排列问题中,某些元素的前后顺序是固定的(但不一定相邻) 。 解决这类某些元素顺序确定的问题的基本方法有两种:一是整体法,即若有 m+n 个元素排成一列, 其中有 m 个元素之间的顺序固定不变,将这 m+n 个元素任意排 成一列,共有种不同的排法,然后任取一个排列,固定其他的 n 个元素的位置不 动,把着 m 个元素交换顺序,共有种排法,其中只有一个排列是我们需要的,因 而共有种不同的排法。二是插空法,即逐步插空法。 9、组合 从 n 个不同的元素中任取 m(m≤n)个元素并成一组,叫做从 n 个不同元素中 取出 m 个元素的一个组合. 注意: (1)取出的 m 个元素不讲究顺序,也就是说元素没有位置的要求,无 序性是组合的本质。 (2)组合与排列的异同:组合与排列的相同点是“从 n 个不同元素中任意 取出 m 个不同元素” ;不同点是组合“不管元素的顺序并成一组” ,而排列要求元 素“按照一定的顺序排成一列” ,因此区分某一问题是组合还是排列,关键是看 取出的元素有无顺序。 10、组合数与组合数公式 从 n 个不同元素中取出 m(m≤n)个元素的所有组合的个数,叫做从 n 个不 同元素中取出 m 个元素的组合数,用符号表示。组合数公式:

n! Anm n(n ? 1)(n ? 2)? (n ? m ? 1) m 或 C n? (n, m ? N ? , 且m ? n) C ? m? m!(n ? m)! Am m!
m n

规定:=1。

注意: (1)组合与组合数是两个不同的概念。 (2)在公式中,我们规定 0!=1,因而有= =1,同样=1. 11、组合数的两个性质
m n?m 性质 1: C n ? Cn

一般地,从 n 个不同元素中取出 m 个元素后,剩下 n ? m 个元素.因为从 n 个不同元素中取出 m 个元素的每一个组合,与剩下的 n ? m 个元素的每一个组合 一一对应, 所以从 n 个不同元素中取出 m 个元素的组合数,等于从这 n 个元素中
m n?m 取出 n ? m 个元素的组合数,即: C n .在这里,主要体现: “取法”与 ? Cn

“剩法”是“一一对应”的思想 注意: (1)该性质反映了组合数的对称性。 (2)若 m>,通常不直接计算,而改为计算。
m m m ?1 性质 2: C n ?1 = C n + C n

一般地,从 a1 , a 2 , ? , a n ?1 这 n+1 个不同元素中取出 m 个元素的组合数是
m Cn ?1 ,这些组合可以分为两类:一类含有元素 a1 ,一类不含有 a1 .含有 a1 的组 m ?1 合是从 a 2 , a3 , ? , a n ?1 这 n 个元素中取出 m ?1 个元素与 a1 组成的,共有 C n 个; m 不含有 a1 的组合是从 a 2 , a3 , ? , a n ?1 这 n 个元素中取出 m 个元素组成的,共有 C n

个.根据分类计数原理,可以得到组合数的另一个性质.在这里,主要体现从特 殊到一般的归纳思想, “含与不含其元素”的分类思想. 注意: (1)左端下标为 n+1,右端下标都为 n,相差 1;上标左端与右端的 一个一样,右端的另一个比它们少 1.
m m m ?1 (2)要注意性质 C n 的顺用、逆用、变形应用,顺用是将一个 ?1 = C n + C n

组合数拆成两个,逆用则是“合二为一” 。
m ?1 m m (3)变形: C n = Cn ?1 - C n 。

12、几个常用组合数公式
0 1 2 n Cn ?C n ?C n ? ?C n n ?2

0 2 4 1 3 5 Cn ?C n ?C n ? ? ?C n ?C n ?C n ? ? ?2 n?1 m m m m ?1 Cm n ?C m ?1 ?C m ? 2 ?C m ? n ?C m ? n ?1 k ?1 kC k n ? nC n ?1

1 k 1 k ?1 C n? C n?1 k ?1 n ?1
13、组合的应用 13.1 有限制条件的组合应用题 (1)有限制条件的组合问题的限制条件主要表现在取出的元素中“含”或 “不含”某些元素,通常用直接法或间接法。解决该类问题用“直接法”时,要 注意合理分类,用“间接法”时,要注意“至少” “最多” “恰好”等词语的含义,

做到既不重复又不遗漏。 (2)有关排列、组合的混合问题,应遵循先选后排的原则。 (3)解答排列组合应用题的总体思路是:①整体分类;②局部分布;③辩 证地看待元素的位置;④一些具体问题有时需要把它抽象成组合模型。 13.2 几何中的组合应用问题 (1)解决几何图形中的组合问题,首先应注意运用处理组合问题的常规方 法分析、解决问题,其次要从不同类型的几何问题中抽象出组合问题,往往寻找 一个组合的模型加以处理。 (2)图形多少的问题通常是组合问题,要注意共点、共线、共面、异面等 情形,防止多算。常用直接法,也可采用排除法。 (3)在处理几何问题中的组合问题时,应将几何问题抽象成组合问题来解 决。 13.3 分组、分配问题 分组问题和分配问题是有区别的:在分组问题中,组与组之间只要元素个数 相同即可;而在分配问题中,即使两个组元素个数相同,但因人不同,仍然是可 区分的。对于这类问题,必须遵循先分组后排列,若平均分 m 组,则分法=. 13.4 若干集合中选取元素问题 对比较复杂的在若干集合中选取元素的问题,一般需分类求解。只要能运用 分类思想正确地对待所选法分类,又能正确地根据题目要求合理地考察步骤,就 可以顺利地求得答案。在分类时,要注意做到既不重复又不遗漏。 14、解决排列组合综合题常用的方法与技巧 14.1 关于排列组合问题的一些解题技巧: ①特殊元素优先安排;②合理分类与准确分步;③排列、组合混合问题先选 后排;④相邻问题捆绑处理;⑤不相邻问题插空处理;⑥定序问题除法处理;⑦ 分排问题直排处理;⑧“小集团”排列问题先整体后局部;⑨构造模型;⑩正难 则反、等价转化。 对于无限制条件的排列组合问题应遵循两个原则:一是按元素的性质分类, 二是按时间发生的过程进行分步。对于有限制条件的排列组合问题,通常从以下 三个途径考虑: ①以元素为主考虑, 即先满足特殊元素的要求, 再考虑其他元素; ②以位置为主考虑,即先满足特殊位置的要求,再考虑其他位置;③先不考虑限 制条件,计算出排列或组合数,再减去不符合要求的排列或组合数。 14.2 排列、组合问题几大解题方法: (1)直接法; (2)排除法; (3)捆绑法:在特定要求的条件下,将几个相关元素当作一个元素来考虑, 待整体排好之后再考虑它们“局部”的排列。它主要用于解决“元素相邻问题” ; (4)插空法:先把一般元素排列好,然后把待定元素插排在它们之间或两 端的空档中,此法主要解决“元素不相邻问题” ; (5)占位法:从元素的特殊性上讲,对问题中的特殊元素应优先排列,然 后再排其他一般元素;从位置的特殊性上讲,对问题中的特殊位置应优先考虑, 然后再排其他剩余位置。即采用“先特殊后一般”的解题原则; (6)调序法:当某些元素次序一定时,可用此法; ( 7 )平均法:若把 kn 个不同元素平均分成 k 组,每组 n 个,共有

n n C kn ?C ( k ?1)n n ?C n

Ak k



(8)隔板法:常用于解正整数解组数的问题; (9)定位问题:从 n 个不同元素中每次取出 k 个不同元素作排列规定某 r 个元素都包含在内,并且都排在某 r 个指定位置则有 A r A n ? r ; (10)指定元素排列组合问题: ①从 n 个不同元素中每次取出 k 个不同的元素作排列(或组合) ,规定某 r 个元素都包含在内。先 C 后 A 策略,排列 C r C n ? r A k ;组合 C r C n ? r ; ②从 n 个不同元素中每次取出 k 个不同元素作排列(或组合) ,规定某 r 个 元素都不包含在内。先 C 后 A 策略,排列 C n ? r A k ;组合 C n ? r ; ③从 n 个不同元素中每次取出 k 个不同元素作排列(或组合) ,规定每个排 列 (或组合) 都只包含某 r 个元素中的 s 个元素。 先 C 后 A 策略, 排列 C r C n ? r A k ; 组合 C r C n ? r 。 15.二项式定理 一般地,对于任意正整数 n,都有
0 n 1 n r n?r r n n ( a ? b ) n ? Cn a ? Cn a b ? ? ? Cn a b ? ? ? Cn b (n ? N ? )

r

k ?r

r

k ?r

k

r

k ?r

k

k

k

s

k ?s

k

s

k ?s

这个公式就叫做二项式定理,右边的多项式叫做 (a ? b) 的二项展开式。其
n
r 中各项的系数 C n (r ? 0,1,2,? ? ?, n) 叫做二项式系数。

注意: (1)二项展开式有 n+1 项; (2)二项式系数与二项展开式系数是两个不同的概念; (3)每一项的次数是一样的,即为 n 次,展开式依 a 的降幕排列,b 的升 幕排列展开; (4)二项式定理通常有如下变形:
n 0 n 1 n ?1 r r n?r r n n n ① (a ? b) ? C n a ? C n a b ? ? ? ? ? (?1) C n a b ? ? ? ? ? (?1) C n b ;

② (1 ? x) ? 1 ? C n x ? C n x ? ? ? ? ? C n x ? ? ? ? ? x ;
n 1 1 2 2 r r n

(5)要注意逆用二项式定理来分析问题、解决问题。 16、二项展开式的通项公式 二项展开式的第 n+1 项 Tr ?1 = C n a
r n?r

r C (r ? 0,1,2,? ? ?, n) 叫做二项展开式的 b rn

通项公式。它体现了二项展开式的项数、系数、次数的变化规律,是二项式定理 的核心,它在求展开式的某些特定的项及其系数方面有着广泛的应用。 注意: (1)通项公式表示二项展开式的第 r+1 项,该项的二项式系数是,而 不是;

(2)字母 b 的次数和组合数的上标相同; (3)a 与 b 的次数之和为 n。 17、二项式系数的性质 (1) 对称性: 与首末两端 “等距离” 的两个二项式系数相等, 即 =, =, =, ?,

=。
(2)增减性与最大值:当 k<时,二项式系数是逐渐增大的。由对称性知, 它的后半部分是逐渐减小的,且在中间取最大值。当 n 为偶数时,则中间一项的 二项式系数最大;当 n 为奇数时,则中间的二项式系数与相等,且同时取得最大 值。 求展开式系数的最大问题,首先要区分“展开式系数最大” “二项式系数最 大”以及“最大项”等;其次要注意展开式系数是离散型变量,因此在系数均为 正数的前提下, 它们的最大值只需比较相邻两个的大小,根据通项公式正确地列 出不等式组即可。
0 1 2 r n (1 ? 1) n ? C n ? Cn ? Cn ? ? ? ? ? Cn ? ? ? ? ? Cn (3)各二项式系数的和: = 2 。奇数项

n

Cn ? Cn ? ? ? ? ? Cn ? Cn ? ? ? ? ? 2 的二项式系数之和与偶数项的二项式系数之和相等且都等于
0 2 1 3

n ?1



注意: (1)求二项式所有项的系数和,可以采用“特殊值取代法” ,通常令
0 1 2 r n 字母变量的值为 1,即 (1 ? 1) n ? C n = 2n 。 ? Cn ? Cn ? ? ? ? ? Cn ? ? ? ? ? Cn

一般地,多项式 f(x)=+x+x? +…+的各项系数和为 f(1),奇次方系数和为 [f(1)-f(-1)] ,偶次项系数和为[f(1)+f(-1)] 。 (2)关于组合恒等式的证明,常采用“构造法”——构造函数或构造同一 问题的两种算法。 18、二项式定理的应用 (1)要注意二项式定理的双向功能:一方面可将二项式 (a ? b) n 展开,另一 方面可将展开式合并为二项式 (a ? b) n ,即二项式定理从左到右使用为展开,从 右到左使用可以化简、求和或证明,这种公式的逆用不可忽视。 (2)由于二项式定理是一个恒等式,因此通过对 a、b 取不同的特殊值,可 得到一些给解决某些问题带来方便的特例恒等式。


计数原理与排列组合

计数原理与排列组合_高一数学_数学_高中教育_教育专区。计数原理与排列组合计数原理一、知识导学 1.分类计数原理: 完成一件事n类办法, 那么完成这件事共有 N= ...

计数原理与排列组合

11.1 分类加法计数原理与分步乘法计数原理考情分析两个原理是解决排列、组合和概率的基础,贯穿始终,在高考中一般不单独考 察,而是作为一种思想方法用在排列组合...

计数原理、排列组合题型与方法

计数原理排列组合题型与方法_高三数学_数学_高中教育_教育专区。计数原理、排列...第一个项目有 6 种选法,第 二个项目有 5 种选法,第三个项目只有 4 种...

4-17计数原理排列组合专题

4-17计数原理排列组合专题_数学_高中教育_教育专区。4-17 计数原理排列组合...第三 层有 8 本不同的英语书,现从中任取一本书,共有( )种不同的取法...

45计数原理和排列组合

45计数原理和排列组合_数学_高中教育_教育专区。2011...4 本,另两人每人得 1 本; 规律方法总结: 二、...如果将这两个新节 目插入原节目单中,那么不同插...

分类计数原理与分步计数原理、排列组合

分类计数原理与分步计数原理、排列组合_数学_高中教育...=1 n 4 考点 3 组合 1. 组合的定义:从 n 个...12 ,共有选 法 36 种,选 A. 【总结与反思】...

计数原理与排列组合

计数原理与排列组合_高二数学_数学_高中教育_教育专区。计数原理与排列组合 1.(...第三道工序有 4 人,从中 选 3 人每人做一道工序,则选法有___种. 13.(...

46计数原理和排列组合

计数原理与排列组合编制人:丁建萍 李智 卜彦玲 孙衍常 审核: 审批: 【使用...4 本,另两人每人得 1 本; 二、总结提升 1.知识方面 2.数学思想方法: 2011...

2011-2015计数原理排列组合

2011-2015计数原理排列组合_数学_高中教育_教育专区。1. 如图, 用四种不同的...60种方法;第三类是取个奇数,即 C4 F B C B.63 种 C.65 种 D.66 ...