1.2.3排列组合问题的常用方法.ppt

解排列组合问题的常用策略
分房问题
又名:住店法,重排问题求幂策略
住店法
解决“允许重复排列问题”要注意区分两类元素:
一类元素可以重复,另一类不能重复,把不能重复的元素看作“客”,能重复的元素看作“店”,再利用乘法原理直接求解。
例七名学生争夺五项冠军,每项冠军只能由一人获得,获得冠军的可能的种数有( )
A. B. C. D.
分析:因同一学生可以同时夺得n项冠军,故学生可重复排列,将七名学生看作7家“店”,五项冠军看作5名“客”,每个“客”有7种住宿法,由乘法原理得种。
注:对此类问题,常有疑惑,为什么不是呢?
用分步计数原理看,5是步骤数,自然是指数。
回目录
A
重排问题求幂策略
,共有
多少种不同的分法
解:完成此事共分六步:把第一名实习生分配
到车间有种分法。
7
把第二名实习生分配
到车间也有7种分法,
依此类推,由分步计
数原理共有种不同的排法
回目录
环排问题和多排问题
环排问题线排策略
例. 5人围桌而坐,共有多少种坐法?
解:围桌而坐与坐成一排的不同点在于,坐成
圆形没有首尾之分,所以固定一人A并从
此位置把圆形展成直线其余4人共有____
种排法即
A
B
C
E
D
D
A
A
B
C
E
(5-1)!
回目录
练习题
6颗颜色不同的钻石,可穿成几种钻石圈?
120
一般地,n个不同元素作圆形排列,共有(n-1)!
出m个元素作圆形排列共有种。
多排问题直排策略(特殊元素先分析)
,每排4人,其中甲乙在前排,丁在后排,共有多少排法
解:8人排前后两排,相当于8人坐8把椅子,可以把椅子排成一排.
先在前4个位置排甲乙两个特殊元素有____种,
再排后4个位置上的特殊元素有_____种,
其余的5人在5个位置上任意排列有_____种,
则共有____________种.
前排
后排
一般地,元素分成多排的排列问题,
可归结为一排考虑,再分段研究。
回目录
小团体问题(捆绑法)
小团体问题:先整体后局部(捆绑法)
,2,3,4,5组成没有重复数字的五位数,其中恰有两个
偶数夹在1和5两个奇数之间,这样的五位数有多少个?
解:把1,5,2,4当作一个小集团与3排队
共有____种排法,再排小集团内部共有
_______种排法,由分步计数原理共有
_______种排法.
3
1245
小集团
小集团排列问题中,先整体后局部,再结合其它策略进行处理。
回目录