当前位置:首页 >> 数学 >>

第二课时 排列组合问题的解题方法(二)


第二课时
教学目标:

排列组合问题的解题方法(二)

掌握几类特殊的排列问题的解决技巧. 教学重点:掌握“错位排列” 、 “圆桌排列” 、 “转化命题”等问题的解题技巧. 教学难点:如何应用“技巧”解题. 教学过程: 【例析技巧】 四.错位排列问题

n 个不同元素排成一排,有 m 个元素( m ? n )不

排在相应位置的排列种数共有:
n 1 n?1 2 n ?2 3 n?3 m n ?m An ? Cm An?1 ? Cm An?2 ? Cm An?3 ???? ? (?1)m Cm An?m . 0 当 n ? m 时,规定 A0 ? 0! ? 1 ,这个公式亦成立.

例7

五封标号为 1~5 的信放进 5 个编号为 1~5 的信笺里面, 若信的编号与信笺的编

号都不相同,一共有多少种不同放法. 解:这是著名的信封问题,很多著名数学家都研究过.瑞士数学家欧拉按一般情况给出 了一个递推公式: 用 A 、 B 、 C ??表示写着 n 位友人名字的信封, a 、 b 、 c ??表示 n 份相应的写 好的信.把错装的总数记为 f ( n) .假设把 a 错装进 B 里了,包含着这个错误的一切错装法分 两类: (1)b 错装进 A 里, 这时每种错装的其余部分都与 a 、b 、 A 、B 无关, 应有 f (n ? 2) 种错装法. (2) b 错装进 A 、 B 之外的信封,这时的装信工作实际是把(除 a 之外的)信纸 b 、

c ??装入(除 B 之外的) n ? 1 个信封 A 、 C ??,显然这种错装方法有 f (n ? 1) 种.
错装的其余部分都与 a 、 b 、 A 、 B 无关,应有 f (n ? 2) 种错装法. 总之在 a 错装入 B 的错误之下,共有错装法 f (n ? 1) ? f (n ? 2) 种. 装入 D ??的 n ? 2 种错误之下,同样都有 f (n ? 1) ? f (n ? 2) 种错装法. 因此 f (n) ? (n ? 1)[ f (n ? 1) ? f (n ? 2)] ,显然 f (1) ? 0 , f (2) ? 1 .

由此可得 f (5) ? 44 . 注意:用容斥原理亦可解决此题. 普遍结论为错排公式 1: f (n) ? n ![1 ?

1 1 1 1 ? ? ? ??? ? (?1) n ] . 1! 2! 3! n!

错排递推公式 2: f (n) ? (n ? 1)[ f (n ? 1) ? f (n ? 2)]
n 1 n?1 2 n ?2 3 n?3 m n ?m 错排公式 3: An ? Cm An?1 ? Cm An?2 ? Cm An?3 ???? ? (?1)m Cm An?m

例8

有 5 个人站成一排,其中 A 不站第一位,B 不站第二位,C 不站第三位,D 不站

第四位,E 不站第五位,共有多少种不同的站法. 解析:上面两例实际上可以看成 n 个不同元素中有 m ( m ? n )错位排列的问题. 而这个问题是其特殊情况,即全错位排列问题.
5 1 4 2 3 3 2 4 1 5 0 0 共有 A5 ? C5 A4 ? C5 A3 ? C5 A2 ? C5 A1 ? C5 A0 ? 44 种(注意 A0 ? 0! ? 1 )

例9

同室四人各写一张贺年卡,先集中起来.然后每人从中拿一张别人送出的贺年卡.

则四张贺年卡不同的分配方式有 A.6 种 B.9 种 C.11 种 D.23 种

解析:由上面公式得:
4 1 3 2 2 3 1 4 0 A4 ? C4 A3 ? C4 A2 ? C4 A1 ? C4 A0 ? 9 种,∴选择 B 答案.

因此可得到全错位排列的公式:

n 个不同元素排成一排,第一个元素不在第一位,第二个元素不在第二位,??,第 n
个元素不在第 n 位的排列数为:
n 1 n?1 2 n ?2 3 n?3 n 0 An ? Cn An?1 ? Cn An?2 ? Cn An?3 ???? ? (?1)n Cn A0 n n?1 2 n? 2 3 n? 3 m n? m 这实际上是公式 An ? C1 (? 1) m Cm An? m的特殊情况 . 这 mA n?1 ? Cm A n?2 ? Cm A n ?3 ? ??? ?

个公式很有用,只要有特殊元素不站特殊位置的问题,都可以用这个公式很快得到解决,希 望这个公式对大家有所帮助. 五. 圆桌排列 从 n 个不同元素中不重复的取出 m ( 1 ? m ? n )个元素排在一个圆周上,叫做这 n 个 不同元素的圆排列.如果一个 m -圆排列旋转可以得到另一个 m -圆排列, 则认为这两个圆排 列是相同的. 特别的,当 m ? n 时, n 个不同元素作成的圆排列总数为 (n ? 1)! .

证明: 在圆周上任选一个位置排 a1 有 n 种排法, 再选一个位置排 a2 有 n ? 1 种排法,?, 最后一个位置排 an 有 1 种排法.而这 n 个人顺时针(或逆时针)挪动 n 次位置都是同一种排 列.所以共有

n! ? (n ? 1)! 种排法. n

例 10 有 5 对夫妇参加一场婚宴,他们被安排在一张 10 个座位的圆桌就餐,但是婚礼 操办者并不知道他们彼此之间的关系, 只是随机安排座位。 问 5 对夫妇恰好都被安排在一起 相邻而坐的概率是多少?( A. 在 1‰到 5‰之间 ) B. 在 5‰到 1%之间 C. 超过 1% D. 不超过 1‰

解:5 对夫妇相邻而座,可以看做是五个大元素为桌而坐,所以有 4! 种坐法,而夫妇间 又可以换位置,所以共有 例 11

4!? 2 ? 2 ? 2 ? 2 ? 2 2 ? ? 0.002 . 故选:A. 9! 945

博杰学习网竞赛小组“先进人物评比”最终圈定了 n 个人,需要确定最终的三

个“先进人物”人选.方法是:这 n 个人排成一行,从第一名开始,1 至 3 循环报数,凡报 出 3 的就退出,余下的向前靠拢,按此规律重复进行.直到第 p 次报数后,只剩下 3 个人为 止.试问:这剩下的三个人,分别在队伍最初的什么位置? 解:设 n 个人的编号依次为 1,2,?, n .最后剩下的三个人中,第三人的编号为 bn .

n n 个人,还剩 n ? 个人. bn 向前移 3 3 b 3b ? rn n 动了 bn ? bk ( k ? n ? )个人,前面淘汰了 n ? bn ? rn ( rn ? 1,2)个人.故 bn ? k . 3 3 2 1 其中当 bk 为奇数时, rn ? 1 ;否则, rn ? 2 ,每报一次号,人数减少 (除不尽时取整). 3
因 bn 未被淘汰,故不是 3 的倍数.第一次报数后淘汰了 计算 bn 逐步归纳为减小的数列, 最终划归到小情况.例如 n ? 1000 时, 第三个人的初始位置 是 712. 例 12 将圆分成 n ( n ? 2 )个扇形,现用 m ( m ? 2 )种颜色给这些扇形染色,每个

扇形恰染一种颜色且要求相邻的扇形不同色.问有多少种不同的染色方法? 解:设染色方法数为 an . (1)求初始值.当 n ? 2 时,给 S1 染色有 m 种方法,给 S2 染色有 m ? 1 种方法. 所以 a2 ? m(m ?1) ; (2) 求递推关系. 给 S1 染色有 m 种方法, 给 S2 染色有 m ? 1 种方法, 给 S3 染色有 m ? 1

种方法,??,给 Sn 染色有 m ? 1 种方法.共有 m(m ?1) n?1 种方法. 这种情况可以分为两类 一类是 Sn 与 S1 不同色,此时的染色方法种数是 an ;另一类是 Sn 与 S1 同色,Sn 与 S1 可 以合并为一个扇形, Sn ?1 与 S1 不同色,染色方法种数为 an ?1 .由加法原理,得到

an ? an?1 ? m(m ?1)n?1 ( n ? 2 ).
(3)求 an .构造等比数列.结论:共有 an ? (m ?1)n ? (?1)n (m ?1) 种染色方法. 六.转化命题 对于一些较难的排列组合问题,通常采用转化命题的方法来解决.比如圆内弦的交点个 数可转化为圆内接四边形的个数;异面直线的对数可转化为 3 倍的四面体的个数等. 例 13 有多少个? 分析: 若两弦有交点, 则两弦应是圆内接四边形的对角线, 即一个四边形对应一个交点.
4 所以共有 C15 ? 1365 个交点.

圆周上共有 15 个不同的点,过其中任意两点连一弦,这些弦在圆内的交点最多

小结: 1.“在”与“不在”可以相互转化.解决某些元素在某些位置上用“定位法” ,解决某些 元素不在某些位置上一般用“间接法”或转化为“在”的问题求解. 2.排列组合应用题极易出现“重” 、 “漏”现象,而“重” 、 “漏”错误常发生在该不该分 类、有无顺序的问题上.为了更好地防“重”堵“漏” ,在做题时需认真分析自己做题思路, 也可改变解题角度,利用一题多解核对答案. 【作业】 1.今有 8 个人坐圆桌,有多少种坐法? 2.有 5 个男孩,3 个女孩围成一圆,其中 3 个女孩不相邻,有多少种站法? 3.一圆型餐桌依次有 A 、 B 、 C 、 D 、 E 、 F 六个座位,现让 3 个大人和 3 个孩子入 座进餐,要求任何两个小孩都不能坐在一起,则不同的作法总数为 72 .


相关文章:
第二课时 排列组合问题的解题方法(二)
第二课时 排列组合问题的解题方法(二)_数学_高中教育_教育专区。第二课时教学目标: 排列组合问题的解题方法(二) 掌握几类特殊的排列问题的解决技巧. 教学重点:...
排列组合问题的解题方法与技巧的总结(完整版)
排列组合问题的解题策略 学管 教师姓名 高二课时 课题名称 教育顾问 邱老师 1...1 类办法中有 m1 种不同的方法,在第 2办法中有 m2 种不同的 方法,...
第一课时 排列组合问题的解题方法(一)
第一课时 排列组合问题的解题方法(一)_教学反思/汇报_教学研究_教育专区。第一...第二课时排列组合问题的解题方法(二)教学目标: 掌握几类特殊的排列问题的解决...
排列组合问题的解题技巧
下面介绍几种常用的解题方法和策略。 一.特殊元素(位置)的 “优先安排法 ”:对于特殊元素(位置)的排列组合 问题,一般先考虑特殊,再考虑其他。 例 1. 用 0,2...
排列组合问题的解题方法(共4课时)
三个同学分别插入这五个“空”有 A5 种方法,所以一共有 A4 A5 =1440 种. 4 4 【课后记】 第二课时教学目标: 排列组合问题的解题方法(二) 掌握几类特殊...
第三课时 排列组合问题的解题方法(三)
第三课时 排列组合问题的解题方法(三)_数学_高中教育_教育专区。第三课时教学目标: 排列组合问题的解题方法(三) 掌握几类特殊的排列问题的解决技巧. 教学重点:...
第一课时 排列组合问题的解题方法(一)
第一课时 排列组合问题的解题方法(一)_数学_高中教育_教育专区。第一课时教学...乙两个同学“松绑”进行排列有 A2 种方法.所以这 6 2 样的排法一共有 A6 ...
高三复习:排列组合问题的解题方法
高三复习:排列组合问题的解题方法_数学_高中教育_教育专区。排列组合问题的解题方法...解 2: (位置优先法)根据所求四位数对首末两位置的特殊要求可分三步:第一步...
排列组合问题基本类型及解题方法
排列组合问题基本类型及解题方法_数学_高中教育_教育专区。排列组合问题的基本模型...1 ?10 ? 55 2 种方法.同样甲、乙可互换位置, (二) 、定序问题缩倍法 ...
更多相关标签:
排列组合解题方法 | 小学排列组合解题方法 | 排列组合解题技巧 | 排列与组合解题技巧 | 排列组合解题策略 | 排列组合解题思路 | 排列组合的解题技巧 | 排列组合c的计算方法 |