定序问题倍缩空位插入策略
例47人排队其中甲乙丙3人顺序一定共有多少不同
的排法
解倍缩法对于某几个元素顺序一定的排列问题可先把
这几个元素与其他元素一起进行排列然后用
总排列数除以这几个元素之间的全排列数则
共有不同排法种数是:
A
77
A33
空位法设想有7把椅子让除甲乙丙以外的四人就坐
共有
A
47
种方法,其余的三个位置甲乙丙共有
1
种坐法,则共有A74种方法。
思考可以先让甲乙丙就坐吗
(插入法先排甲乙丙三个人共有1种排法再把其余4
四人依次插入共有
方法
定序问题可以用倍缩法,还可转化为占位插空模型处理
练习题10人身高各不相等排成前后排,每排5人要求
从左至右身高逐渐增加,共有多少排法?
C150
五重排问题求幂策略例5把6名实习生分配到7个车间实习共有多少种不同的分法解完成此事共分六步把第一名实习生分配到车间有7
种分法把第二名实习生分配到车间也有7种分依此类推由分步计数原理共有76种不同的排法
允许重复的排列问题的特点是以元素为研究对象,元素不受位置的约束,可以逐一安排各个元素的位置,一般地
不
同的元素没有限制地安排在m个位置上的排列数为m
种
f练习题:1.某班新年联欢会原定的5个节目已排成节目单,开演
前又增加了两个新节目如果将这两个节目插入原节目单中,那么不同插法的种数为422某8层大楼一楼电梯上来8名乘客人他们到各自的一层下电梯下电梯的方法78
六环排问题线排策略
例68人围桌而坐共有多少种坐法
解:围桌而坐与坐成一排的不同点在于,坐成圆形没有首
尾之分,所以固定一人
A
44
并从此位置把圆形展成直线
其余7人共有(81)!种排法即7!
C
D
B
E
A
F
H
G
ABCDEFGHA
一般地
个不同元素作圆形排列共有
1种排法如果从
个不同元素中取出
m
个元素作圆形排列共有
1
A
m
练习题:6颗颜色不同的钻石,可穿成几种钻石圈120
七多排问题直排策略
例78人排成前后两排每排4人其中甲乙在前排丙在后
排共有多少排法
解8人排前后两排相当于8人坐8把椅子可以把椅子
排成一排个特殊元素有
A
24
种再排后
4
个位置上的特
殊元素丙有A14种其余的5人在5个位置上任意排列
f有种则共有种A55
A
24
A14
A55
前排
后排
一般地元素分成多排的排列问题可归结为一排考虑再分段研究
练习题:有两排座位,前排11个座位,后排12个座位,现安排2人就座规定前排中间的3个座位不能坐,并且这2人不左右相邻,那么不同排法的种数r