六.转化命题

对于一些较难的排列组合问题，通常采用转化命题的方法来解决.比如圆内弦的交点个数可转化为圆内接四边形的个数；异面直线的对数可转化为3倍的四面体的个数等.

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

分析：若两弦有交点，则两弦应是圆内接四边形的对角线，即一个四边形对应一个交点.

4所以共有C15?1365个交点.

小结：

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 五人站成一排，其中甲不站第一位，乙不站第二位，共有多少种不同的站法. 解：这个问题在高中很多参考书上都有，有几种解法，其中一解法是用排除法：先考虑

5445个有的全排列，有A5种不同的排法，然后除去甲排第一（有A4种）与乙排第二（也有A4种），但两种又有重复部分，因此多减，必须加上多减部分，这样得到共有：

543A5?2A4?A3?78种.

例15 有5个人站成一排，其中甲不站第一位，乙不站第二位，丙不站第三位，共有多少种不同的站法.

5432仿上分析可得：A5?3A4?3A3?A2?64种.

八.均匀分组问题．

mmmC?C???Cmnmn?mm一般地：将mn个不同元素均匀分成n组（每组m个元素），共有种nAn方法．

例16 有6本不同的书，按下列要求各有多少种不同的选法： （1）分给甲、乙、丙三人，每人2本； （2）分为三份，每份2本；

（3）分为三份，一份1本，一份2本，一份3本；

（4）分给甲、乙、丙三人，一人1本，一人2本，一人3本； （5）分给甲、乙、丙三人，每人至少1本.

222解：（1）根据分步计数原理得到：C6C4C2?90种；

222（2）分给甲、乙、丙三人，每人两本有C6C4C2种方法，这个过程可以分两步完成：

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

A33种方法．根据分步计数原理可得：

CCC?xC26242233，所以

222C6C4C2x??15．因此，3A3分为三份，每份两本一共有15种方法．

（3）这是“不均匀分组”问题，一共有C6C5C3?60种方法．

（4）在（3）的基础上再进行全排列，所以一共有C6C5C3A3?360种方法．

1233123（5）可以分为三类情况：

222①“2、2、2型”即（1）中的分配情况，有C6C4C2?90种方法； 1233②“1、2、3型”即（4）中的分配情况，有C6C5C3A3?360种方法； 43③“1、1、4型”，有C6A3?90种方法；

所以，一共有90+360+90＝540种方法．

11C64C2C1点评：本题第（3）种类型为部分均匀分组再分配，其分组总数为． 2A2题型变换：8名球员住A、B、C三个房间，每个房间最多住3人，有多少种住宿方法？

332C8C5C23解：?A3． 2A2例17 若3名飞行员和6名特勤人员分别上3架不同型号的直升飞机执行任务,每机一名飞行员和两名特勤人员，有多少种分配方法？

222111C6C4C2C3C2C133222111解：先分组，再分配，，或者??A?ACCC?C336423C2C1． 33A3A3类题：20名同学分两组，每组10人去某地社会实践，其中6名干部，每组3人，不同

37C6C142分法总数是多少？答案：2?2?A2．

A2A2九. 隔板法：将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分，所

22以有C6?C?28?28种分法．

点评：〖类题〗求不定方程x1?x2?x3?6的非负整数解的个数？

题型变换一：四本不同的书，分给三个人，每人至少一本，全部分完，有几种分法？

23解：先分组，再分配有C4A3种．

题型变换二：n本不同的书，分给n?1个人，每人至少1本，全部分完，有几种分法？

2n?1解：先分组，再分配有CnAn?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?1m分，所以有Cn?m?1种方法（这也是一个公式）.

【随堂练习】

1.（1） 四个不同的小球放入四个不同的盒中，一共有多少种不同的放法？ （2） 四个不同的小球放入四个不同的盒中且恰有一个空盒的放法有多少种？ 解：（1）根据分步计数原理：一共有4?256种方法；

（2）（捆绑法）第一步：从四个不同的小球中任取两个“捆绑”在一起看成一个元素有

2323种方法；第二步：从四个不同的盒中任取三个将球放入有A4种方法，所以，一共有C4A4C44＝144种方法．

说明：先组合，再排列是解决问题的关键．本题亦可先将4个小球分成三组，每组分别

211C4C2C13有1/1/2个，共再放入四个盒子中的三个，共有?A4?144种． 2A2思考：（1）四个相同的小球放入四个不同的盒子中，一共有多少种不同的放法？ 解：（隔板站位法）共C4?3?C7?35．

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

33