排列组合问题解法--LJ.ppt

排列组合问题的解法
李 骏
概述
排列组合问题联系实际生动有趣，但题型多样，思路灵活，
首先要认真审题，弄清楚是排列问题、组合问题还是排列与组合综合问题；
其次要抓住问题的本质特征，采用合理恰当的方法来处理．
没有改变，不计顺逆方向，这种排列和直线排列是不同的，这就是环形排列的问题．
一个m个元素的环形排列，相当于一个有m个顶点的多边形，沿相邻两个点的弧线剪断，再拉直就是形成一个直线排列，即一个m个元素的环形排列对应着m个直线排列。
设从n个元素中取出m个元素组成的环形排列数为N个，则对应的直线排列数为mN个，又因为从n个元素中取出m个元素的排成一排的排列数为 个，
所以 ，所以
即从n个元素中取出m个元素组成的环形排列数为 ．
n个元素的环形排列数为
例6. 8人围桌而坐,共有多少种坐法?
解：围桌而坐与坐成一排的不同点在于，坐成圆形没有首尾之分，所以固定一人并从此位置把圆形展成直线其余7人共有
种排法，即840种
练习6：
6颗颜色不同的钻石，可穿成几种钻石圈 ?
5!=120
，直排策略
例7. 8人排成前后两排,每排4人,其中甲乙在前排,丙在后排,共有多少排法？
解:8人排前后两排,相当于8人坐8把椅子,可以把椅子排成一排.
先排前４个位置，２个特殊元素有 种排法
再排后4个位置上的特殊元素丙有 种,
其余的5人在5个位置上任意排列有 种,
则共有 种排法．（排好后，按前４个为前排，后４人为后排分成两排即可）
练习7：
有两排座位，前排11个座位，后排12个座位，现安排2人就座：规定前排中间的3个座位不能坐，并且这2人不左右相邻，那么不同排法的种数是 ？
解：由于甲乙二人不相邻，所以当前排第1,4,8,11四个位置和后排第１,12两个位置是甲乙中之一时，与它相邻的位置只能排除一个，
而其它位置要排除３个，所以共有排列
，先选后排策略
例8. 有5个不同的小球,装入4个不同的盒内,每盒至少装一个球,共有多少不同的装法.
解:第一步从5个球中选出2个组成复合元素，共有 种方法.
再把4个元素(包含一个复合元素)装入4个不同的盒内，有 种方法，
根据分步计数原理装球的方法共有
练习8：
一个班有6名战士,其中正副班长各1人。现从中选4人完成四种不同的任务,每人完成一种任务,且正、副班长有且只有1人参加,则不同的选法有 ？ 种
，先整体后局部策略
例9. 用1,2,3,4,5组成没有重复数字的五位数，其中在1、５之间恰好只有两个偶数,这样的五位数有多少个？
解：把１,５,２,４当作一个小集团与３排队共有 种排法，
再排小集团内部，共有 种排法
由分步计数原理，共有 种排法.
练习9：
1. 计划展出10幅不同的画,其中1幅水彩画,４幅油画,５幅国画, 排成一行陈列。要求同一品种的必须连在一起，并且水彩画不在两端，那么共有陈列方式的种数为？
2. 5男生和５女生站成一排照像,男生相邻,女生也相邻的排法有 ？ 种
，隔板策略
，分给7个班，每班至少一个,有多少种分配方案？
解：因为10个名额没有差别，把它们排成一排．相邻名额之间形成９个空隙．在９个空档中选６个位置插个隔板，可把名额分成７份，对应地分给７个班级，每一种插板方法对应一种分法，共有 种分法．
注：这和投信问题是不同的。投信问题的关键是信不同，邮筒也不同；而这里的问题是邮筒不同，但信是相同的。即班级不同，但名额都是一样的．
两个条件：
1、元素相同
2、各部分至少含有一个元素
练习10：
1. 10个相同的球装5个盒中,每盒至少一有多少装法？
2. 求 x+y+z+w=100 这个方程的自然数解的组数
，总体排除策略
,1,2,3,4,5,6,7,8,9这十个数字中取出三个数，使其和为不小于10的偶数,不同的取法有多少种？
解：这问题中如果直接求不小于10的偶数很困难,可用总体排除法．
这十个数字中有5个偶数5个奇数。
所取的三个数，含有3个偶数的取法有 ，只含有1个偶数的取法有
则和为偶数的取法共有
再淘汰和小于10的偶数共9种，符合条件的取法共有60-9=51
练习11：
班里有43位同学,从中任