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

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


第四课时
教学目标:

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

掌握几类特殊的排列问题的解决技巧. 教学重点:掌握“递推法”等问题的解题技巧. 教学难点:如何应用“技巧”解题. 教学过程: 十.穷举法: 对于一些不能直接用两个原理, 且类别不多的问题, 通常采用穷举法.即列举所有情况. 例 19 将五个市级三好学生名额和八个区级优秀学生干

部名额全部分配到辖区的两所

中学,每所学校至少有一个名额,有多少种不同的分配方案? 解: 分配情况用有序数组 ( x, y ) 表示: (1,12) , (2,11) , (3,10) , (4,9) , (5,8) , (6,7) . 然后两校交换.所以共有分配方案数为 2 ?( 2 ? 3 ? 4 ? 5 ? 6 ? 6 ) ? 52 种. 例 20 .

十一.递推法: 对于一些较复杂的排列问题, 可以建立排法之间的一个递推关系, 通过递推关系求出排 法种数. 例 19 一个楼梯共 10 个台阶,如果规定一步登一个台阶或登两个台阶,一共有多少种

不同的走法? 解:设上 n 级台阶的走法为 an 种,易知 a1 ? 1 , a2 ? 2 ,当 n ? 2 时,上 n 级台阶的走 法可分两类:第一类是最后一步跨一级,有 an ?1 种走法,第二类是最后一步跨二级,有 an?2 种走法.由加法原理可知 an ? an?1 ? an?2 ,据此可得 a10 ? 89 种不同的走法. 例 20 同排法? 解:我们考虑人数为 n 的情况,即 n 个人排成一列,重新站队时,各人都不站在原来的 位置上.设满足这样的站队方式有 an 种, 现在我们来通过合理分步, 恰当分类找出递推关系: 第一步:第一个人不站在原来的第一个位置,有 n ? 1 种站法. 第二步:假设第一个人站在第 2 个位置,则第二个人的站法又可以分为两类: 有五个人排成一列,现在要重新排列,要求都不能站在原来的位置,有几种不

第一类,第二个人恰好站在第一个位置,则余下的 n ? 2 个人有 an?2 种站队方式; 第二类,第二个人不站在第一个位置,则就是第二个人不站在第一个位置,第三个人不 站在第三个位置,第四个人不站在第四个位置,??,第 n 个人不站在第 n 个位置,所以有

an ?1 种站队方式.
由分步计数原理和分类计数原理,我们便得到了数列 an 的递推关系式:

an ? (n ?1)(an?1 ? an?2 ) ,显然, a1 ? 0 , a2 ? 1 ,?, a5 ? 44 .故有 44 种不同排法.
注意: n 个人排成一排后,解散后重新排队,自己不站原来的位置的排法种数可由以 下公式推导得到: (1) a1 ? 0 , a2 ? 1 , an ? (n ?1)(an?1 ? an?2 ) ( n ? 3 ) ; (2) an ? n ![1 ?

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

n 1 n?1 2 n ?2 3 n?3 n 0 (3) an ? An ? Cn An?1 ? Cn An?2 ? Cn An?3 ???? ? (?1)n Cn A0 .

例 21

在 n ? m 的网格中,从 (0, 0) 点到 (n, m) 点,只能沿网格的边向 x 轴正方向或 y

轴正方向前进,问共有多少种不同的前进路线? 解:对任意一个非 x 轴、 y 轴上的点 ( x, y ) ,可以从点 ( x , y ? 1) 走来,也可以从点

( x ? 1, y) 走来.因此,设 ( x, y ) 处的路线条数为 f ( x, y) ,则有递推公式: f ( x, y) ? f ( x, y ?1) ? f ( x ? 1, y) .
x 下面的推理很重要:根据上述递推公式,可得 f ( x, y) ? Cx? y ,即从 x ? y 件物品中选

出无顺序的 x 件(或 y 件)的总方案数.即 f ( x, y ) ?

( x ? y )! . x! y!
?

小结: 上述问题中把每个 f ( x, y) 指标在对应的坐标点处, 再将坐标系顺时针旋转 135 , 你发现了什么?这是杨辉三角, f ( x, y) ? Cx? y .而我们知道, Cxy ? Cxy?1 ? Cxy ?1 .这就是通
x

项公式的来源. 另解:记网格横向的 x 条线段从左至右依次为 a1 、 a2 、?、 ax ,网格纵向的 y 条线段

从下至上依次为 b1 、b2 、?、by .从 (0, 0) 到 ( x, y ) 的走法种数,就是 a1 、a2 、?、ax 及 b1 、

b2 、?、 by 这 x ? y 个元素的一个定序排列.于是有
例 22

?y Axx? y

A A

x x

y y

(或

( x ? y )! )种不同走法. x! y!

某地决定在一个大型广场建一个同心圆形花坛,花坛分为两部分,中间小圆部

分种植草坪,周围的圆环分为 n ( n ? 3, n ? N )等份种植红、黄、蓝三色不同的花. 要求 相邻两部分种植不同颜色的花. 如图①,圆环分成的 3 等份分别为 a1 , a2 , a3 ,有 6 种不 同的种植方法.如图②,圆环分成的 4 等份分别为 a1 , a2 , a3 , a4 ,有 18 种不同的种植 方法;则在图③中,圆环分成的 n ( n ? 3 , n ? N ) 等份分别为 a1 , a2 , a3 , ? , an , 有 种不同的种植方法.

a1

a1 a2


a2
??

a1

a2
a3
? ③

a3

a4


a3

an

第 18 题图 解:对于 n 的情形,总的涂法数为 3 ? 2
n ?1

,但是最后一块与第一块有两种情况:不同色

(满足题意)与同色,同色时就是 n ? 1 的情形,于是得出递推公式: an ? 3 ? 2n?1 ? an?1

an a 1 a ?1 3 1 a ?1 ?? ? n ? ,即 n ?1 ? ? ( n ? 1) n n ?1 n 2 2 2 2 2n ?1 2 2 a F ( n) 6 1 1 1 ? 1 ? ? 1 ? ? ,所以 n ? 1 ? ? ? (? ) n ?3 ,即 F (n) ? 2n ? 2 ? (?1)n?1 . 因为 3 3 8 4 4 2 2 2
(n ? 4) ,变形得 例 23 有甲乙两队,各有 7 名队员,分别编号 1~7,首先两队编号为 1 的队员对抗比

赛,负者淘汰,胜者与负方的 2 号队员比赛,?,依次类推.直到某队全部淘汰为止.问最后 有多少种不同比赛方式? 解:设 f ( x, y) 表示甲乙两队分别由 x , y 名队员组成时的方式数.由于上次可能是甲、 乙两队中某个被淘汰,故递推公式为: f ( x, y) ? f ( x, y ? 1) ? f ( x ? 1, y) .故转化为与上题 相同的数学模型.即 f ( x, y ) ?

( x ? y )! x! y!

另解:记甲队 7 人分别为 a1 、 a2 、?、 a7 ,乙队 7 人分别为 b1 、 b2 、?、 b7 .比赛结 束时的方案数就是 a1 、 a2 、?、 a7 及 b1 、 b2 、?、 b7 这 14 个元素的一个定序排列.于是有
14 14! A14 (或 )种不同方案数. 7 7 7!7! A7 A7

小结:求排列组合递推问题时,一定要注意以下几个方面: ①初始条件;②递推关系中 ?1 , ?1 的问题;③递推终止条件. 例 24 有甲、乙、丙三人踢毽子,互相传递,每人每次只能踢一下,由甲开始踢,经

过 5 次传递后,毽子又被踢回给甲,问有多少种不同的传递方式? 解:设 k ( k ? 2 )个人传递 n ( n ? 2 )次后回到甲处的不同传递方法数为 an . 则 a2 ? k ?1 .下面考查 an ?1 与 an 的关系.(如图)

甲 ? ① ? ② ? ③ ? ④ ? ??? ? ? ?甲
则甲 ? ① 有 k ? 1 种不同方法, ① ? ② 有 k ? 1 种不同方法, ② ? ③ 有 k ? 1 种不 同方法,??, ??? ? ? k ? 1 种不同方法. 而第 n 次接毽子的人 ? 可能不是甲,也可能是甲,所以 an ? an?1 ? (k ?1)n?1 对于本题,令 k ? 3 ,则 a2 ? 2 ,由递推公式得 a3 ? 2 , a4 ? 6 , a5 ? 10 . 注意:由 an ? an?1 ? (k ?1)n?1 得

an an ?1 1 1 ?? ? n n ?1 (k ? 1) k ? 1 (k ? 1) k ?1



an an ?1 1 1 1 ? ?? [ ? ], n n ?1 (k ? 1) k k ? 1 (k ? 1) k an 1 1 n?2 a2 1 ? ? (? ) [ ? ], n 2 (k ? 1) k k ?1 (k ? 1) k

由等比数列的通项公式知



an 1 1 n?2 1 1 ? ? (? ) ( ? ), n (k ? 1) k k ?1 k ?1 k
k ?1 [(?1)n ? (k ? 1) n ?1 ] .显然,当 k ? 3 时, a5 ? 10 . k

化简 an ?


相关文章:
第四课时 排列组合问题的解题方法(四)
第四课时 排列组合问题的解题方法(四)_数学_高中教育_教育专区。第四课时教学目标: 排列组合问题的解题方法(四) 掌握几类特殊的排列问题的解决技巧. 教学重点:...
排列组合问题的解题方法(共4课时)
Cm m Am 种分法; 第四课时教学目标: 排列组合问题的解题方法(四) 掌握几类特殊的排列问题的解决技巧. 教学重点:掌握“递推法”等问题的解题技巧. 教学难点:...
第三课时 排列组合问题的解题方法(三)
第三课时 排列组合问题的解题方法(三)_数学_高中教育_教育专区。第三课时教学...60 种方法. 1 2 3 3 (4)在(3)的基础上再进行全排列,所以一共有 C6 ...
排列组合问题基本类型及解题方法
排列组合问题基本类型及解题方法_数学_高中教育_教育...(四) 、元素交叉问题集合法(二元否定问题,依次分类...如果甲不跑第一棒,乙不跑第四棒,共 有多少种不...
排列组合问题的解题方法与技巧的总结(完整版)
尊重·乐学·博识 学员授课时间 学员年级 课时总数 教学目标 共 数学 科目第 ...4.解决排列组合综合性问题,往往类与步交叉,因此必须掌握一些常用的解题策略 排列...
排列组合问题的解题技巧
排列组合问题的解题技巧_初三理化生_理化生_初中教育_教育专区。排列组合问题的解题...100米接力赛,如果甲不跑第一棒,乙 不跑第四棒,共有多少种不同的参赛方法?...
第4课时 排列与组合的综合问题
对一些复杂的带有附加条件的问题,需掌握以下几种常用的解题方法: 特殊优先法: 特殊优先法: 对于存在特殊元素或者特殊位置的排列组合问题,我们可以从这些特殊的 东西...
第一课时 排列组合问题的解题方法(一)
Cm m Am 种分法; 第四课时排列组合问题的解题方法(四)教学目标: 掌握几类特殊的排列问题的解决技巧. 教学重点:掌握“递推法”等问题的解题技巧. 教学难点:...
第4课时 排列与组合的综合问题
第4课时 排列与组合的综合问题_数学_高中教育_教育专区。§10.4 排列与组合的...常用的解题方法: 特殊优先法: 对于存在特殊元素或者特殊位置的排列组合问题,我们...
第二课时 排列组合问题的解题方法(二)
第二课时 排列组合问题的解题方法(二)_数学_高中教育_教育专区。第二课时教学...教学难点:如何应用“技巧”解题. 教学过程: 【例析技巧】 四.错位排列问题 n...
更多相关标签:
排列组合解题方法 | 小学排列组合解题方法 | 排列组合解题技巧 | 奥数排列组合解题技巧 | 排列与组合解题技巧 | 排列组合解题策略 | 排列组合解题思路 | 排列组合的解题技巧 |