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

排列组合问题的解题方法(共4课时)


第一课时
教学目标:

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

掌握几类特殊的排列问题的解决技巧. 教学重点:掌握“条件排列” 、 “集团排列” 、 “间隔排列” 、 “部分顺序排列”问题的解题 技巧. 教学难点:如何应用“技巧”解题. 教学过程: 【例析技巧】 一.集团排列问题:部分元素必须安排在一起(相邻)的排列问题,称之为“集团排列” 问题.解决这类问题,常用“捆绑法” ,其方法是先排“集团”内部的元素,再把这个大“元 素”与其它元素一起排列即可. 例1 若 7 位同学站成一排

(1)甲、乙两同学必须相邻的排法共有多少种? (2)甲、乙和丙三个同学都相邻的排法共有多少种? (3)甲、乙两同学必须相邻,而且丙不能站在排头和排尾的排法有多少种? (4) 甲、 乙、 丙三个同学必须站在一起, 另外四个人也必须站在一起的排法有多少种? 解: (1)先将甲、乙两位同学“捆绑”在一起看成一个元素与其余的 5 个元素(同学)
6 一起进行全排列有 A6 种方法;再将甲、乙两个同学“松绑”进行排列有 A2 种方法.所以这
6 2 样的排法一共有 A6 ? A2 ? 1440 种.

2

5 3 (2)方法同上,一共有 A5 ? 720 种. A3

(3)解法一:将甲、乙两同学“捆绑”在一起看成一个元素,此时一共有 6 个元素, 因为丙不能站在排头和排尾,所以可以从其余的 5 个元素中选取 2 个元素放在排头和排尾,
2 有 A5 种方法;将剩下的 4 个元素进行全排列有 A4 种方法;最后将甲、乙两个同学“松绑” 2 进行排列有 A2 种方法.所以这样的排法一共有 A5 A4 A2 ? 960 种方法.
2 4 2 4

解法二:将甲、乙两同学“捆绑”在一起看成一个元素,此时一共有 6 个元素,若丙站
5 在排头或排尾有 2 A5 种方法, 所以, 丙不能站在排头和排尾的排法有 ( A6 ? 2 A5 ) ? A2 ? 960 6 5 2

种方法.

解法三:将甲、乙两同学“捆绑”在一起看成一个元素,此时一共有 6 个元素,因为丙
1 不能站在排头和排尾,所以可以从其余的四个位置选择共有 A4 种方法,再将其余的 5 个元

5 素进行全排列共有 A5 种方法,最后将甲、乙两同学“松绑” ,所以,这样的排法一共有
1 2 5 ? 960 种方法. A4 A2 A5

(4)将甲、乙、丙三个同学“捆绑”在一起看成一个元素,另外四个人“捆绑”在一
3 4 2 起看成一个元素,时一共有 2 个元素,∴一共有排法种数: A3 A4 A2 ? 288 (种)

说明:对于相邻问题,常用“捆绑法” (先捆后松) . 二. 间隔排列问题: 部分元素不能安排在一起 (间隔)的排列问题, 称之为“间隔排列” 问题.解决这类问题,常用“插空法” ,其方法是先排不需要间隔的元素,再将需要间隔的元 素通过插空的方式插进来即可. 例2 在一条南北方向的步行街同侧有 8 块广告牌,牌的底色可选用红、蓝两种颜色. )

若只要求相邻两块牌的底色不都为红色,则不同的配色方案共有( A.55. B.56. C.46. D.45.

1 解:没有红牌,一种方法;有一块红牌,让其插空,有 C8 种方法;有二块红牌,让其 2 3 4 插空,有 C7 种方法;有三块红牌,让其插空,有 C6 种方法;有四块红牌,让其插空,有 C5 1 2 3 4 种方法;共有方法 1 ? C8 ? C7 ? C6 ? C5 ? 55 种.

说明:对于不相邻问题,常用“插空法”(特殊元素后考虑) . 例 3 某仪表显示屏上一排有 7 个小孔,每个小孔可显示出 0 或 1,若每次显示其中三 个孔,但相邻的两孔不能同时显示,则这显示屏可以显示的不同信号的种数有 种. 解:四个孔不亮,三个孔亮,相当于三个亮着的孔在四个不亮的孔之间插空,故有
3 C5 ? 2 ? 2 ? 2 ? 80 种方法.

三. 部分不同元素定序与部分相同元素排列问题: 部分不同元素在排列前后的顺序固定不变(不一定相邻)的排列问题,称之为“定序排 列”问题.解决这类问题的基本方法有三种. (1) “消序法” (有些地方叫“整体法” ) ,即若有 m ? n 个元素排成一列,其中有 m 个
m? n 元素之间的排列顺序不变,将这 m ? n 个元素任意排成一列,共有 Am ? n 种不同的排法,其

m 中未定序的 n 个元素排在某一特定位置的排列的个数有 Am 种排法,但只有一个排列是我们
m?n Am ?n 种不同的排法 . 类似地还可推广到一般情形,如有有 m Am

所需要的排列,因而共有

m ? n ? k个元素排成一列,其中有 m 个元素之间的排列顺序不变,且另外 k 个元素之间的
排列顺序也不变,则共有
m?n?k Am ?n?k 中不同的算法. m k Am Ak

(2)逐一插空法:先将定序的元素进行排列,再将其它元素逐一插入这组元素两端及 中间. (3)优序法:先将所有位置中按“特殊元素”个数选出若干位置,并把这些特殊元素 按规定顺序排上去,再将普通元素在其余位置上全排列. 例4 若 5 男 5 女排成一排,按下列要求各有多少种排法

(1)男女相间; (2)女生按指定顺序排列.
5 解: (1)先将男生排好,有 A5 种排法;再将 5 名女生插在男生之间的 6 个“空挡” (包 5 5 5 括两端)中,有 2 A5 种排法.故本题的排法有 N ? 2 A5 ; ? A5 ? 28800 (种)
10 A10 5 ? A10 ? 30240 ; 5 A5

(2)方法 1(消序法) :N ?

方法 2 (逐一插空法) : 5 个女生按序排列, 有 1 中方法, 5 个男生逐个插空, 有 6,7,8,9,10 种方法,共有 6 ? 7 ? 8 ? 9 ?10 ? 30240 种方法.
5 方法 3(优序法) :设想有 10 个位置,先将男生排在其中的任意 5 个位置上,有 A10 种

排法;余下的 5 个位置排女生,因为女生的顺序已经指定,所以她们只有一种排法.
5 故本题的结论为 N ? A 10 ?1 ? 30240 (种).

例5

今有 2 本相同的语文书,3 本相同的数学书,4 本相同的英语书排成一排,有多

少种不同的排法? 解: (消序法)有 例6
9 A9 ? 1260 种. 2 3 4 A2 A3 A4

一个楼梯共 18 个台阶,12 步登完,可一步登一个台阶,也可一步登两个台阶,

一共有多少种不同的走法? 解:根据题意,要想 12 步登完,只能 6 个一步登一个台阶,6 个一步登二个台阶.因此,

把问题转化为“相同元素”的排列问题.因此有

12 A12 ? 924 (种). 6 6 A6 A6

点评:对于部分不同元素定序排列以及相同元素的排列问题,可用优序法. 【随堂练习】 1.从 5 位同学中选派 4 位同学在星期五、星期六、星期日参加公益活动,每人一天, 要求星期五有 2 人参加,星期六、星期日各有 1 人参加,则不同的选派方法共有( B ) A.40 种 B.60 种 C.100 种 D.120 种

2.安排 3 名支教老师去 6 所学校任教,每校至多 2 人,则不同的分配方案共有 210 种. (用数字作答) 3.用数字 0,1,2,3,4,5 组成没有重复数字,且比 20000 大的五位偶数有( A.288 个 B.240 个 C.144 个 D.126 个 )

4.如图,用 6 种不同的颜色给图中的 4 个格子涂色,每个格 子涂一种颜色,要求最多使用 3 种颜色且相邻的两个格子颜色不同, 则不同的涂色方法共有 390 种(用数字作答) . 5.某校开设 9 门课程供学生选修,其中 A, B, C 三门由于上课时间相同,至多选一门, 学校规定每位同学选修 4 门,共有 75 种不同选修方案.(用数值作答) 6.从班委会 5 名成员中选出 3 名,分别担任班级学习委员、文娱委员与体育委员,其 中甲、乙二人不能担任文娱委员,则不同的选法共有 36 种. (用数字作答) 【课后作业】 1.某校安排 5 个班到 4 个工厂进行社会实践,每个班去一个工厂,每个工厂至少安排 一个班,不同的安排方法共有 240 种. (用数字作答) 2.将数字 1,2,3,4,5,6 拼成一列,记第 i 个数为 ai ( i ? 1,2,?,6) ,若 a1 ? 1 , . a3 ? 3 , a5 ? 5 , a1 ? a3 ? a5 ,则不同的排列方法有 30 种(用数字作答) 解:分两步: (1)先排 a1 , a3 ,a5 ,当 a1 =2 时,有 2 种;当 a1 =3 时,有 2 种;当 a1 =4 时,有 1 种,共有 5 种; (2)再排 a2 , a4 , a6 ,共有 A3 ? 6 种,故不同的排列方法种数
3

为 5×6=30,填 30. 3.中韩两支围棋队各由 8 人组成,按事先排好的次序出场进行围棋擂台赛,双方先由 1 号队员比赛,负者被淘汰,胜者再与负方 2 号队员比赛,??,直到有一方全部被淘汰为

止,另一方获胜,形成一个比赛过程. (1)已知中方动用了 5 名队员,取得了胜利,问这样的比赛过程有多少种? (2)求由中方第 8 位选手获得最后胜利的概率. 解: (1)中方胜利时,双方共有 8 ? 5 ? 13 名队员参加了比赛,将他们按淘汰的顺序从 左向右排列,则最右为中方 5 号,右第二个为韩方 8 号,从右第三个至最左,共 11 个位置 上,有 4 个位置排中方队员,其余排韩方队员,每一种排法,对应一种比赛结果,故共有
4 C11 ? 330 种.
7 C14 4 ? . 8 C16 15

(2) p ?

4. 若 7 位同学站成一排 (1)甲、乙两同学不能相邻的排法共有多少种? (2)甲、乙和丙三个同学都不能相邻的排法共有多少种?
7 6 2 解: (1)解法一: (排除法) A7 ? A6 ? A2 ? 3600; 5 解法二: (插空法)先将其余五个同学排好有 A5 种方法,此时他们留下六个位置(就称 2 为“空”吧) ,再将甲、乙同学分别插入这六个位置(空)有 A6 种方法,所以一共有 5 2 A5 A6 ? 3600种方法.

(2)先将其余四个同学排好有 A4 种方法,此时他们留下五个“空” ,再将甲、乙和丙
3 3 三个同学分别插入这五个“空”有 A5 种方法,所以一共有 A4 A5 =1440 种.
4

4

【课后记】

第二课时
教学目标:

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

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

四.错位排列问题

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)] 错排公式 3: An ? Cm An?1 ? Cm An?2 ? Cm An?3 ???? ? (?1) Cm An?m
n 1 2 3 m m n?1 n ?2 n?3 n ?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) 这种情况可以分为两类 一类是 Sn 与 S1 不同色,此时的染色方法种数是 an ;另一类是 Sn 与 S1 同色,Sn 与 S1 可 以合并为一个扇形, Sn ?1 与 S1 不同色,染色方法种数为 an ?1 .由加法原理,得到
n ?1

种方法.

an ? an?1 ? m(m ?1)n?1 ( n ? 2 ).
(3)求 an .构造等比数列.结论:共有 an ? (m ?1) ? (?1) (m ?1) 种染色方法.
n n

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

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

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

第三课时
教学目标:

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

掌握几类特殊的排列问题的解决技巧. 教学重点:掌握“容斥原理” 、 “错位排列” 、 “圆桌排列”等问题的解题技巧. 教学难点:如何应用“技巧”解题. 教学过程: 【例析技巧】 七. 用容斥原理解排列问题 有些排列组合问题可转化为求集合的元素的个数来求.充分应用容斥原理:

n( A ? B) ? n( A) ? n( B) ? n( A ? B)

n( A?B?C ) ? n( A) ? n( B) ? n(C ) ? n( A?B) ? n( B?C ) ? n( A?B) ? n( A?B? C ) .
例 14 五人站成一排,其中甲不站第一位,乙不站第二位,共有多少种不同的站法.

解:这个问题在高中很多参考书上都有,有几种解法,其中一解法是用排除法:先考虑
5 4 4 5 个有的全排列,有 A5 种不同的排法,然后除去甲排第一(有 A4 种)与乙排第二(也有 A4

种) ,但两种又有重复部分,因此多减,必须加上多减部分,这样得到共有:
5 4 3 A5 ? 2 A4 ? A3 ? 78 种.

例 15

有 5 个人站成一排,其中甲不站第一位,乙不站第二位,丙不站第三位,共

有多少种不同的站法.
5 4 3 2 仿上分析可得: A5 ? 3A4 ? 3A3 ? A2 ? 64 种.

八.均匀分组问题. 一般地: 将 mn 个不同元素均匀分成 n 组 (每组 m 个元素) , 共有 方法. 例 16 有 6 本不同的书,按下列要求各有多少种不同的选法:
m m m Cmn ? Cmn ? m ?? ? Cm 种 n An

(1)分给甲、乙、丙三人,每人 2 本; (2)分为三份,每份 2 本; (3)分为三份,一份 1 本,一份 2 本,一份 3 本; (4)分给甲、乙、丙三人,一人 1 本,一人 2 本,一人 3 本; (5)分给甲、乙、丙三人,每人至少 1 本.
2 2 2 解: (1)根据分步计数原理得到: C6 C4 C2 ? 90种; 2 2 2 (2)分给甲、乙、丙三人,每人两本有 C6 C4 C2 种方法,这个过程可以分两步完成:

第一步分为三份,每份两本,设有 x 种方法;第二步再将这三份分给甲、乙、丙三名同学有

A

3 3 种方法.根据分步计数原理可得:

C C C ? xC
2 6 2 4 2 2

3 3 ,所以

2 2 2 C6 C4 C2 x? ? 15 .因此, 3 A3

分为三份,每份两本一共有 15 种方法. (3)这是“不均匀分组”问题,一共有 C6 C5 C3 ? 60 种方法.
1 2 3

(4)在(3)的基础上再进行全排列,所以一共有 C6 C5 C3 A3 ? 360种方法.
1 2 3 3

(5)可以分为三类情况:
2 2 2 ①“2、2、2 型”即(1)中的分配情况,有 C6 C4 C2 ? 90种方法; 1 2 3 3 ②“1、2、3 型”即(4)中的分配情况,有 C6 C5 C3 A3 ? 360种方法; 4 3 ③“1、1、4 型” ,有 C6 A3 ? 90 种方法;

所以,一共有 90+360+90=540 种方法. 点评:本题第(3)种类型为部分均匀分组再分配,其分组总数为
1 1 C64C2 C1 . 2 A2

题型变换:8 名球员住 A 、 B 、 C 三个房间,每个房间最多住 3 人,有多少种住宿方 法?
3 3 2 C8 C5 C2 3 解: ? A3 . 2 A2

例 17

若 3 名飞行员和 6 名特勤人员分别上 3 架不同型号的直升飞机执行任务,每机一

名飞行员和两名特勤人员,有多少种分配方法? 解:先分组,再分配,
2 2 2 1 1 1 C6 C4 C2 C3 C2C1 3 3 2 2 2 1 1 1 ? ? A3 ? A3 ,或者 C6 C4 C2 ? C3 C2C1 . 3 3 A3 A3

类题:20 名同学分两组,每组 10 人去某地社会实践,其中 6 名干部,每组 3 人,不同
3 7 C6 C14 2 分法总数是多少?答案: 2 ? 2 ? A2 . A2 A2

九. 隔板法:将 n 个相同元素,分成 k ( n ? k , n , k ? N )组,可以看成是在 n 个
*

k ?1 元素之间的 n ? 1 个空隙间插入 k ? 1 块隔板.共有 Cn ?1 种方法.

例 18

将六本相同的书全部发给甲、乙、丙三人.

(1)每人至少分到一本书,问有多少种不同的分法? (2)每人不一定都分到一本书,问有多少种不同的分法?
2 解: (1)用“隔板法”处理,六本书之间有五个空,插入两块隔板,有 C5 种分法;

用“隔板站位法”处理,六本书之间有五个空,需插入两块隔板,但由于有人可能没有 书,所以两块隔板站着两个位置,加上六本书,可以看着是 6 ? 2 ? 8 本书,分成 3 分,所
2 2 以有 C6 ?2 ? C8 ? 28 种分法.

点评: 〖类题〗求不定方程 x1 ? x2 ? x3 ? 6 的非负整数解的个数? 题型变换一:四本不同的书,分给三个人,每人至少一本,全部分完,有几种分法?
2 3 解:先分组,再分配有 C4 A3 种.

题型变换二:n 本不同的书,分给 n ? 1 个人,每人至少 1 本,全部分完,有几种分法?
2 n ?1 解:先分组,再分配有 Cn An?1 种.

题型变换三: n 本相同的书,全部分给 m ( m ? n )个人. (1)每人至少分到一本书,问有多少种不同的分法? (2)每人不一定都分到一本书,问有多少种不同的分法? 解: (1)解法一(隔板站位法) :每人先分一本书,还剩下 n ? m 本书,加上 m ? 1 块隔
m?1 板,可视为 (n ? m) ? (m ? 1) ? n ? 1 本书,分给 m 个人,所以有 Cn ?1 种方法. m?1 解法二(隔板法) :n 本书之间有 n ? 1 个空,需插入 m ? 1 块隔板,所以有 Cn ?1 种方法.

(2) (隔板站位法) : n 本书之间,需插入 m ? 1 块隔板,但是,由于有人分不到书,所 以 m ? 1 块隔板站着 m ? 1 个位置,加上 n 本书,可视为 n ? m ? 1 本书,用 m ? 1 块隔板分成
m?1 m 分,所以有 Cn ? m?1 种方法(这也是一个公式).

【随堂练习】 1.(1) 四个不同的小球放入四个不同的盒中,一共有多少种不同的放法? (2) 四个不同的小球放入四个不同的盒中且恰有一个空盒的放法有多少种? 解: (1)根据分步计数原理:一共有 4 ? 256 种方法;
4

(2) (捆绑法)第一步:从四个不同的小球中任取两个“捆绑”在一起看成一个元素有
2 3 2 3 种方法; 第二步: 从四个不同的盒中任取三个将球放入有 A4 种方法, 所以, 一共有 C 4 A4 C4

=144 种方法. 说明:先组合,再排列是解决问题的关键.本题亦可先将 4 个小球分成三组,每组分别 有 1 / 1 / 2 个,共再放入四个盒子中的三个,共有
2 1 1 C4 C2C1 3 ? A4 ? 144 种. 2 A2

思考: (1)四个相同的小球放入四个不同的盒子中,一共有多少种不同的放法? 解: (隔板站位法)共 C4?3 ? C7 ? 35.
3 3

(2)10 个相同的小球放入编号为 1、2、3 的盒子中,球数不少于编号数的放法有多少

种?
2 2 解:按要求放 6 个,其余 4 个按隔板站位法有 C4 ? 2 ? C6 ? 15 种方法.

另解: (隔板法)设 1,2,3 号盒子所放的球数分别为 a , b , c .则有 a ? b ? c ? 10 . 设 x ? a , y ? b ? 1 , z ? c ? 2 ,则方程 x ? y ? z ? 7 的正整数解的组数,就是放球的
2 2 方法数.所以共有 C4 ? 2 ? C6 ? 15 种方法.

注意:这种利用“先换元,再用隔板技巧”的方法对于求有限制条件的不定方程的非 负整数解的问题很有效! 【总结提炼】 均匀分组(不计组的顺序)问题不是简单的组合问题,如:将 3 个人分成 3 组,每组
1 1 1 一个人,显然只有 1 种分法,而不是 C3 ? C2 ? C1 ? 6 种
王新敞
奎屯 新疆

一般地,将 m ? n 个不同元素均匀分成 n 组,有 【课后作业】 【板书设计】 (略) 【教学后记】

m m Cmn C(m n ?1) m ?Cm m Am

种分法;

第四课时
教学目标:

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

掌握几类特殊的排列问题的解决技巧. 教学重点:掌握“递推法”等问题的解题技巧. 教学难点:如何应用“技巧”解题. 教学过程: 十.穷举法: 对于一些不能直接用两个原理, 且类别不多的问题, 通常采用穷举法.即列举所有情况. 例 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 ?


赞助商链接
相关文章:
第9讲应用问题的题型与方法(4课时)
第9讲应用问题的题型与方法(4课时)_高三数学_数学_高中教育_教育专区。高三数学...9.排列组合、二项式定理: ⑴掌握分类计数原理与分步计数原理,并能用它们分析...
选修5-4-1-油脂(共两课时)
选修5-4-1-油脂(共课时)_理化生_高中教育_教育...油脂中三个不同烃基有排列组合问题,可运用数学公式...(提示:关键在于解题思路的掌握,要知道饱和脂肪酸甘油...
第4课时 解决问题(例4)-人教三下优质课教学设计精品
4课时 解决问题(例4)-人教三下优质课教学设计...提问:(1)解答正确吗? (2)你能用其他的方法进行 ...列式计算。 满载时共重 8.7 吨。 巩固练习 2....
...单元《图形的运动(二)》教学设计(共4课时)
新人教版数学四年级下册第七单元《图形的运动(二)》教学设计(共4课时)_数学_...教学重点 教学难点 教学准备 运用平移的方法解决简单不规则图形的面积问题。 在...
解决问题的策略(4课时)
解决问题的策略(4课时)_数学_小学教育_教育专区。...不管哪种方法,都要注意把条件对应排列起来整理,这样...(3)运用策略,探寻思路。 启发:这题的解题思路是...
人教版二年级数学上册1《长度单位》教案(共4课时)
教学反思: 第四课时 解决问题 确定长度单位 教学内容:课本第 7 页 教学目标:1、掌握合适的确定长度单位的方法; 2、在确定长度单位的过程中学会思考、学会比较。...
排列组合上课教案(杨亚玲)_图文
排列组合上课教案(杨亚玲)_四年级数学_数学_小学教育...二年级数学组教师 课时:第一课时 上课班级:二(6)...活动 一.猜一猜,说一说: 学生根据预习回答问题。...
...四年级下册第十单元《总复习》教学设计(共4课时)
(共 4 课时) 教材第 109 页的第 2 题及第 111 页练习二十五的第 4、...(学生自由回 答) 师:在解答过程中,你运用了数学的哪些思想方法?(学生自由回答...
3.4 实际问题与一元一次方程(共4课时) -
3.4 实际问题与一元一次方程(共4课时) -_初一数学_数学_初中教育_教育专区...解答过程见教材第 100 页例 1 的解答过程. 探究点二 工程问题 活动二:阅读...
第5讲解析几何问题的题型与方法(4课时)
第5讲解析几何问题的题型与方法(4课时)_高三数学_数学_高中教育_教育专区。...(2 个选择题, 1 个填空题, 1 个解答题), 共计 30 分左右, 考查的知识...
更多相关标签: