当前位置:首页 >> 其它课程 >> 信息学竞赛中问题求解常见题分析(排列组合)

信息学竞赛中问题求解常见题分析(排列组合)


信息学竞赛中问题求解常见题分析 排列组合问题 排列组合问题
一,知识点: 知识点:
1. 分类计数原理 分类计数原理:做一件事情,完成它可以有 n 类办法,在第一类办法中有 m1 种不同的方法,在 第二类办法中有 m2 种不同的方法,……,在第 n 类办法中有 mn.种不同的方法,那么完成 这件事共有 N=m1+m2+…+mn.种不同的方法. 2. 分步计数原

理 分步计数原理:做一件事情,完成它需要分成 n 个步骤,做第一步有 m1 种不同的方法,做第二 步有 m2 种不同的方法, ……, 做第 n 步有 mn 种不同的方法, 那么完成这件事有 N=m1*m2*… mn.种不同的方法. 3. 排列的概念:从 n 个不同元素中,任取 m(m≤n)个元素(这里的被取元素各不相同),按照一定的 排列的概念 顺序排成一列,叫做从 n 个不同元素中取出 m 个元素的一个排列. 4. 排列数的定义 从 n 个不同元素中, 排列数的定义: 任取 m(m≤n)个元素的所有排列的个数叫做从 n 个元素中取 出 m 个元素的排列数,用符号 An 表示. 5. 排列数公式 An =n(n-1)(n-2)…(n-m+1)(m,n∈N,m≤n) 排列数公式 数公式: 6. 阶乘 阶乘:n!表示正整数 l 到 n 的连乘积,叫做 n 的阶乘规定 0!=l. 7. 排列数的另一个计算公式 An = 排列数的另一个计算公式: m
m m

n! (n m)!

8. 组合的概念 组合的概念:一般地,从 n 个不同元素中取出 m(m≤n)个元素并成一组,叫做从 n 个不同元素中 取出 m 个元素的一个组合. 9. 组合数的概念 从 n 个不同元素中取出 m(m≤n)个元素的所有组合的个数, 组合数的概念: 叫做从 n 个不同元素 中取出 m 个元素的组合数.用符号 C n 表示.
m An n(n 1)(n 2)...(n m + 1) n! m 组合数公式: ,或 C n = (n,m∈N, 组合数公式 C = m = m! m!(n m)! Am m n m

10.

且 m≤n) 11. 组合数的性质 1: C n = C n
m nm

,规定: C n :=1; 2: C n +1 = C n + C n
0

m

m

m 1

.

12. 圆排列 . (1) 由 A{a1,a2,a3. n}的 n 个元素中,每次取出 r 个元素排在一个圆环上,叫做一个圆排 .a 列(或叫环状排列). (2) 圆排列有三个特点:(i)无头无尾;(ii)按照同一方向转换后仍是同一排列;(iii)两个圆排 列只有在元素不同或者元素虽然相同,但元素之间的顺序不同时,才是不同的圆排列. (3) 定理:在 A={a1,a2,a3. an}的 n 个元素中,每次取出 r 个不同的元素进行圆排列,圆 .

Pnr 排列数为 . r
13. 可重排列 允许元素重复出现的排列,叫做有重复的排列. 在 m 个不同的元素中,每次取出 n 个元素,元素可以重复出现,按照一定的顺序那么第一, 第二……第 n 位是的选取元素的方法都是 m 种,所以从 m 个不同的元素中,每次取出 n 个

14.

元素的可重复的排列数为时 mn. 不尽相异元素的全排列 如果 n 个元素中,有 p1 个元素相同,又有 p2 个元素相同,…,又有 ps 个元素相同(p1+p2+… +ps ≤n),这 n 个元素全部取的排列叫做不尽相异的 n 个元素的全排列,它的排列数是

n! ! . p1! p 2 !... p s !
二,解题思路: 排列组合题的求解策略 解题思路: 1. 排除 排除:对有限条件的问题,先从总体考虑,再把不符合条件的所有情况排除,这是解决排列组 合题的常用策略. 2. 分类与分步:有些问题的处理可分成若干类,用加法原理,要注意每两类的交集为空集,所有 分类与分步: 各类的并集是全集;有些问题的处理分成几个步骤,把各个步骤的方法数相乘,即得总的方法 数,这是乘法原理. 3. 对称思想 对称思想:两类情形出现的机会均等,可用总数取半得每种情形的方法数. 4. 插空:某些元素不能相邻或某些元素在特殊位置时可采用插空法.即先安排好没有限制条件的 插空: 元素,然后将有限制条件的元素按要求插入到排好的元素之间. 5. 捆绑 捆绑:把相邻的若干特殊元素"捆绑"为一个"大元素" ,然后与其他"普通元素"全排列, 然后再"松绑" ,将这些特殊元素在这些位置上全排列. 6. 隔板模型 隔板模型:对于将不可辨的球装入可辨的盒子中,求装的方法数,常用隔板模型.如将 12 个 完全相同的球排成一列,在它们之间形成的 11 个缝隙中任意插入 3 块隔板,把球分成 4 堆,
3 分别装入 4 个不同的盒子中的方法数应为 C11 .这也就是方程 a+b+c+d=12 的正整数解的个数. ,

解排列组合问题:首先要弄清一件事是"分类"还是"分步"完成,对于元素之间的关系,还要考虑 解排列组合问题 是"有序的"还是"无序的" ,也就是会正确使用分类计数原理和分步计数原理,排列定义和组合定义, 其次,对一些复杂的带有附加条件的问题,需掌握以下几种常用的解题方法. 讲解范例: 三,讲解范例: 1.相邻问题——整体捆绑法 ——整体捆绑法 .相邻问题—— 例 1. 7 名学生站成一排,甲,乙必须站在一起,有多少不同排法? 解:两个元素排在一起的问题可用"捆绑"法解决,先将甲乙二人看作一个元素与其他五人进行排列, 并考虑甲乙二人的顺序,所以共有 A6 A2 =1440 种.
6 2

捆绑法:要求某几个元素必须排在一起的问题,可以用捆绑法来解决问题.即将需要相邻的元素合 并为一个元素,再与其他元素一起作排列,同时要注意合并元素内部也可以作排列.一般地:n 个人站成 一排,其中某 m 个人相邻,可用捆绑法解决,共有 An m +1 . Am 种排法. 练习: 练习:5 个男生 3 个女生排成一排,3 个女生要排在一起,有多少种不同的排法? 分析:此题涉及到的是排队问题,对于女生有特殊的限制,因此,女生是特殊元素,并且要求她们要 相邻,因此可以将她们看成是一个元素来解决问题. 解:因为女生要排在一起,所以可以将 3 个女生看成是一个人,与 5 个男生作全排列,有 P6 种排法, 其中女生内部也有 P3 种排法,根据乘法原理,共有 P6 P3 种不同的排法. 2.不相邻问题——选空插入法 .不相邻问题——选空插入法 —— 例 2.7 名学生站成一排,甲乙互不相邻,有多少不同排法?
3 6 3 6 n m +1 m

A 解: 乙二人不相邻的排法一般应用 甲, "插空" 所以甲, 法, 乙二人不相邻的排法总数应为: 5 A6 =3600
5 2

种. 插入法:对于某两个元素或者几个元素要求不相邻的问题,可以用插入法.即先排好没有限制条件的 插入法 元素,然后将有限制条件的元素按要求插入排好元素的空档之中即可.若个人站成一排,其中 m 个人不相 邻,可用插空法解决,共有 An m An m +1 种排法.
m nm

练习: 练习:学校组织老师学生一起看电影,同一排电影票 12 张,8 个学生,4 个老师,要求老师在学生中 间,且老师互不相邻,共有多少种不同的坐法? 分析:此题涉及到的是不相邻问题,并且是对老师有特殊的要求,因此老师是特殊元素,在解决时就 要特殊对待,所涉及问题是排列问题. 解:先排学生共有 P8 种排法,然后把老师插入学生之间的空档,共有 7 个空档可插,选其中的 4 个 空档,共有 P7 种选法.根据乘法原理,共有 P7 的不同坐法为 P8 * P7 种. 3.复杂问题——总体排除法或排异法 .复杂问题——总体排除法或排异法 —— 有些问题直接法考虑比较难比较复杂, 或分类不清或多种时, 而它的反面往往比较简捷, 可考虑用 "排 除法" ,先求出它的反面,再从整体中排除.解决几何问题必须注意几何图形本身对其构成元素的限制. 个. 例 3.正六边形的中心和顶点共 7 个点,以其中 3 个点为顶点的三角形共有 解:从 7 个点中取 3 个点的取法有 C 7 种,但其中正六边形的对角线所含的中心和顶点三点共线不能 组成三角形,有 3 条,所以满足条件的三角形共有 C 7 -3=32 个. 例 4.从 43 人中任抽 5 人,正,副班长,团支部书记至少有一人在内的抽法有多少种? 分析:此题若是直接去考虑的话,就要将问题分成好几种情况,这样解题的话,容易造成各种情况 遗漏或者重复的情况.而如果从此问题相反的方面去考虑的话,不但容易理解,而且在计算中也是非常地 简便. 解:43 人中任抽 5 人的方法 C 43 种,正副班长,团支部书记都不在内的抽法有 C 40 乙种,所以正副班 长,团支部书记至少有 1 人在内的抽法有 C 43 - C 40 种. 4.特殊元素——优先考虑法 特殊元素——优先考虑法 特殊元素—— 对于含有限定条件的排列组合应用题,可以考虑优先安排特殊位置,然后再考虑其他位置的安排. 例 4. 1 名老师和 4 名获奖学生排成一排照相留念,若老师不排在两端,则共有不同的排法 种. . 解:先考虑特殊元素(老师)的排法,因老师不排在两端,故可在中问三个位置上任选一个位置,有 A3 种,
4 4 而其余学生的排法有 A4 :种,所以共有 A3 A4 :=72 种不同的排法. 1
1 5 5 5 5 3 3 4 4 8 4 8

例 5.乒乓球队的 10 名队员中有 3 名主力队员,派 5 名队员参加比赛,3 名主力队员要安排在第一, 三,五位置,其余 7 名队员选 2 名安排在第二,四位置,那么不同的出场安排共有 种. 解:由于第一,三,五位置特殊,只能安排主力队员,有 A3 种排法,而其余 7 名队员选出 2 名安排 在第二,四位置,有 A7 种排法,所以不同的出场安排共有 A3 . A7 =252 种. 5.多元问题——分类讨论法 .多元问题——分类讨论法 —— 对于元素多,选取情况多的问题,可按要求进行分类讨论,最后总计. 例 6.某班新年联欢会原定的 5 个节目已排成节目单,开演前又增加了两个新节目.如果将这两个节 目插入原节目单中,那么不同插法的种数为 ( )
2 3 2 3

A.

42

B.

30

C. 20

D.

12
2

解:增加的两个新节目,可分为相邻与不相邻两种情况:1.不相邻:共有 A6 :种;2.相邻:共有
1 2 1 2 2 A2 A6 :种.故不同插法的种数为: A6 + A2 A6 =42,故选 A.

6.混合问题——先选后排法 .混合问题——先选后排法 —— 对于排列组合的混合应用题,可采取先选取元素,后进行排列的策略. 若每个路口 4 人, 则不同的分配方案共有( ) 例 7. 12 名同学分别到三个不同的路口进行车流量的调查, A. C12 C8 C 4
4 4 4

B.3 C12 C8 C 4

4

4

4

C. C12 C8 P3

4

4

3

D.

4 4 C12 C84 C 4 3 A3

解:本试题属于均分组问题.则 12 名同学均分成 3 组共有

4 4 C12 C84 C 4 种方法,分配到三个不同的路口 3 A3

的不同的分配方案共有 C12 C8 C8 种,故选 A. 例 8.从黄瓜,白菜,油菜,扁豆 4 种蔬菜品种中选出 3 种,分别种在不同土质的三块土地上,其中 黄瓜必须种植,不同的种植方法共有() A.24 种 B.1 8 种 c.1 2 种 D.6 种 解:先选后排,分步实施.由题意,不同的选法有 C 3 种,不同的排法有 A3 A2 故不同的种植方法共
2 1 2

4

4

4

有 C 3 . A3 A2 =18,故应选 B.
2 1 2

7.相同元素分配——档板分隔法 .相同元素分配——档板分隔法 —— 例 9.把 10 本相同的书发给编号为 1,2,3 的三个学生阅览室,每个阅览室分得的书的本数不小于 其编号数,试求不同分法的种数.请用尽可能多的方法求解,并思考这些方法是否适合更一般的情况?本 题考查组合问题. 解:先让 2,3 号阅览室依次分得 1 本书,2 本书;再对余下的 7 本书进行分配,保证每个阅览室至少 得一本书,这相当于在 7 本相同书之间的 6 个"空档"内插入两个相同"I"(一般可视为"隔板"),共有

C 62 种插法,即有 l 5 种分法.
8.转化法 . 对于某些较复杂的或较抽象的排列组合问题,可以利用转化思想,将其化归为简单的,具体的问题来 求解. 例 10. 高二年级 8 个班,组织一个 12 个人的年级学生分会,每班要求至少 1 人,名额分配方案有多 少种? 分析:此题若直接去考虑的话,就会比较复杂.但如果我们将其转化为等价的其他问题,就会显得比 较清楚,方法简单,结果容易理解. 解:此题可以转化为:将 12 个相同的白球分成 8 份,有多少种不同的分法问题.因此须把这 12 个白
7 球排成一排, 11 个空档中放上 7 个相同的黑球, 在 每个空档最多放一个, 即可将白球分成 8 份, 显然有 C11 7 种不同的放法,所以名额分配方案有 C11 种.

总之,排列,组合应用题的解题思路可总结为:排组分清,加乘明确;有序排列,无序组合;分类为 加,分步为乘. 具体说,解排列组合的应用题,通常有以下途径:

(1)以元素为主体,即先满足特殊元素的要求,再考虑其他元素. (2)以位置为主体,即先满足特殊位置的要求,再考虑其他位置. (3)先不考虑附加条件,计算出排列或组合数,再减去不合要求的排列组合数. 1.(NOIP 2002)在书架上放有编号为 1,2,…,n 的 n 本书.现将 n 本书全部取下然后再放回去,当 . 本书. 本书全部取下然后再放回去, 在书架上放有编号为 , , 放回去时要求每本书都不能放在原来的位置上. 放回去时要求每本书都不能放在原来的位置上. 例如:n=3 时: 原来位置为:1 2 3 放回去时只能为:3 l 2 或 2 3 1 这两种 问题:求当 n=5 时满足以上条件的放法共有多少种?(不用列出每种放法) 解析: 这是一道排列组合中的计数问题, 有关这方面的基础知识在前几期已经有老师阐述得比较明确, 笔者在此不再赘述,只想对本题谈一下笔者的拙见,希望能对初学者有点帮助. 因为书是有编号的,故书是 5 本不同的书,我们分别记为 1,2,3,4,5,有 5 个空位供放这 5 本书, 只要我们将这 5 本书放到这 5 个空位,我们的任务就算完成了.由于这 5 本书放回去的时候每本书不能放 回原来的位置,我们可以将这 5 个位置分别记为 1,2,3,4,5 号位,因此我们放书的时候就有一个先后 顺序问题: ①步我们可以从这 5 本不同的书中任意选出一本书(不妨选 2 号书),放到除了 2 号位之外的四个位置
1 中的任何一个位置,有 C 4 种放置方法,不妨设放到 3 号位上如图所示:

2 号书 1 号位 2 号位 3 号位 4 号位 5 号位 ②步接下来我们该放 3 号书,这时候有两类情况: I 类:3 号书恰好放到 2 号位置上,这样剩下的 3 本书的排列方法就如同题干上所说的 n=3 的情况,
1 有 C 2 种放法,如图所示:

3 号书 l 号位 2 号位

2 号书 3 号位 4 号付 5 号位
1

Ⅱ类:3 号书不放在 2 号位,而是放在除 2 号位之外的三个位置中的任意一个位置上有 C 3 种放法,不 妨设放到 1 号位,接下来该放 1 号书,我们从剩余的 3 个空位中选一个放 1 号书,有 C 3 种排法,不妨设 放到 4 号位,则剩余的两本书只有一种排法. 3 号书 l 号位 2 号位 2 号书 3 号位 1 号书 4 号付 5 号位
1 1 1 1 1

综上两步将 5 本书放到符合条件的 5 个空位的排列种数有: C 4 (C 2 + C 3 C 3 ) =4×(2+3×3)=44(种) 此题的难点就在于第②步的分类上,如果搞清这一点,问题就好解决了. 2.(NOIP 2004)由 3 个 a,5 个 b 和 2 个 c 构成的所有字符串中,包含子串"abc"的共有 构成的所有字符串中,包含子串" 的共有( )个. . 由 , 的共有 个 A.40320 B.39600 C.840 D.780 E.60 . . . . . 解析:3 个 a,5 个 b,2 个 c 共 10 个字符,将"a""b""c"组成一个原子团(特殊字符)"abc"与剩 , , 下的 7 个字符看成共 8 个字符的排列,这样有 8 个空位置可供它们选择,如果这 8 个字符都放到这 8 个位 置,任务就算完成.具体放法如下: ① 步先放"ahc" :从 8 个位置中任选一个放"abc"有 C8 种放法; ② 步再放"a": ,从剩余的 7 个位置中选 2 个放"a"有 C 7 :种放法; ③ 步接着放"b" :从剩下的 5 个位置中选 4 个放"b"有 C 5 种放法;
4 2 1

④ 步最后放"c" :有一种放法. 综上共有= C8 C 7 C 5 =8×2 1×5=840(种) 上述放法中有包含两个"ahc"字符的情况,这些情况都有重复 计算,应该除去. 这种情况有: 从 10 个字符抽出两组"ahc"后还剩余 4 个字符,与这两个原子团(特殊字符)共同组成 6 个 元素,有 6 个空位置可供选择,将这 6 个元素放到这 6 个空位置就算完成任务.具体做法如下: ⑤ 步放"abc" :从 6 个位置中选 2 个放"abe"有 C 6 :种放法;
1 ⑥ 步放"a":从剩下的 4 个位置中选一个放"a"有 C 4 :种放法;
2 1 2 4

⑦ 步放"b" :从剩下的 3 个空位放"c"有 C 3 :种放法; 综上共有 C 6 C 4 C 3 =6×5/(2×1)×4×1=1 5×4=60(种). 由上知,符合条件的包含子串"ahc"的个数有 C8 C 7 C 5 C 6 C 4 C 3 ;=840—60=780(个),故答案选 D
1 1 4 2 1 3 2 1 3

3

说明:对这一类题目来说,字符(串)"abc""a", , "b""c"它们在放的时候没有先后顺序,先放谁,后放 , 谁都一样,计算结果都是一样的,并非一定按上面顺序,有兴趣的同学不妨试一试. 3.(NOIP 2007)给定 n 个有标号的球,标号依次为 1,2,3,…,n.将这 n 个球放入 r 个相同的盒子中, . 不允许有空盒子,其不同的放置方法总数记为 S(n,r) . 例如:S(4,2)=7,这 7 种不同的放置方法依次为: {(1),(234)} {(2),(134)} {(3),(124)} {(4),(123)} {(12),(34)} {(13),(24)} {(14),(23)} 问当 n=7,r=4 时,S(7,4)=? 解法一:递推公式 S(x,y)=S(x-1,y)*y+S(x-1,y-1).因为把 X 个球放入 Y 个箱子,相当于先把 X-1 个球放好 再放最后一个. 最后一个有两种放法: 放入前面已经有球的箱子或者独占一个箱子. 前者对应 S(x-1,y)*y (放 入每一个不同的箱子都是一种不同的放法,因为箱子内原来的球不同),后者对应 S(x-1,y-1). 解法二:将这 n 个球放入 r 个相同的盒子里,不允许有空盒,因为是"相同的盒子",所以是一个组合问题. 既将 n 个球分成 r 份.这样当 n=7,r=4 时,将 7 个球分成 4 份,有三种分法:(1)分为 4,1,1,1(2)分为 3,2,1,1(3) 分为 2,2,2,1 第一种分法有 C(7,4)=35 种 第二种分法有 C(7*3)*C(4,2)=210 种 第三种分法有 C(7,2)*C(5,2)*C(3,2)/A(3,3)=105 种 S(7,4)= C(7,4)+C(7,3)*C(4,2)+C(7,2)*C(5,2)*C(3,2)/A(3,3)=350 C(n,m)表示从 n 个不同元素中取出 m 个元素的组合数 A(n,m)表示从 n 个不同元素中取出 m 个元素的排列数

更多相关文档:

信息学竞赛中问题求解常见题分析(排列组合)

初​中​信​息​学​竞​赛​资​料信息学竞赛中问题求解常见题分析 排列组合问题 排列组合问题一,知识点: 知识点: 1. 分类计数原理 分类计数原...

信息学竞赛中问题求解常见题分析(综合打印)

信息学竞赛中问题求解常见题分析( 信息学竞赛中问题求解常见题分析(一)逻辑推理...诸如寻找假币、博弈原理、抽屉原理、容斥问题、排列组合、逻辑推理、递推关系等 ...

信息学竞赛中问题求解题常见考查题型分析

-1一、 二、 信息学竞赛中问题求解题常见考查题型分析 信息学竞赛中问题求解题...诸如寻找假币、博弈原理、抽屉原理、容斥问题、 排列组合问题、逻辑推理、递推...

信息学竞赛中问题求解题常见考查题型分析

信息学竞赛中问题求解信息学竞赛中问题求解题常见考查题型分析 问题求解 问题...诸如寻找假币、博弈原理、抽屉原理、容斥问题、排列组合问题、逻辑推理、 递推...

探究noip初赛——“问题求解”中的排列组合问题

探究noip初赛——“问题求解”中的排列组合问题_学科竞赛_初中教育_教育专区。排列组合问题练习 信息学竞赛中问题求解常见题分析 排列组合问题 一、知识点: 1. ...

问题求解试题及答案

信息学竞赛中问题求解常见... 22页 2财富值 VC常见数据类型转换 3页 1财富值...试题及其答案 第1 题(14 分)以下程序是将一组整数按从小到大的顺序 排列。...

排列组合常见题型及解题策略答案

-1排列组合常见题型及解题策略 一.可重复的排列求幂法:重复排列问题要区分两类...注:题中*表示元素,○表示空. :某个或几个元素要排在指定位置 四.元素分析...

排列组合常见题型及解题策略答案

排列组合常见题型及解题策略答案_高二数学_数学_高中...如填空模型,排队模型, 装盒模型可使问题容易解决. ...5040 种 【解析】 : 先从 10 人中选出 2 人...

排列组合常见题型及解题策略(详解)

高中排列组合常见题型及解题策略,题目有详细分析解答 ...(1)有 4 名学生报名参加数学、物理、化学竞赛,...如填空模型,排队模型,装盒模 型可使问题容易解决....

NOIP中排列组合问题的十种解题策略

NOIP中排列组合问题的十种解题策略_计算机软件及应用_...(NOIP2002) 解:此题属于不全相异元素的全排列,...解法 1: (元素分析法)因为甲不能站左右两端,故第...
更多相关标签:
排列组合常见题型 | 常见排列组合数 | 分治法求解全排列问题 | 最优资产组合求解推导 | 组合求解 | 组合优化问题求解 | 组合优化求解补集 | 排列组合 |
网站地图

文档资料共享网 nexoncn.com copyright ©right 2010-2020。
文档资料共享网内容来自网络,如有侵犯请联系客服。email:zhit325@126.com