“捆绑”法－妙解排列组合题.doc

期末教学工作总结巧用“捆绑”、“插空”、“分组”法－妙 解 排 列 组 合 题曾祥红　　　　　　 　 在求解排列组合问题时，经常遇到有关几个元素必须相邻、几个元素互不相邻、将ｎ个元素分成ｍ组的问题现将此类问题的解法通过例题介绍如下　 例１ 由数字１、２、３、４、５、６、７组成无重复数字的七位数1）求三个偶数必相邻的七位数的个数；（2）求三个偶数互不相邻的七位数的个数　 解 (1)：因为三个偶数２、４、６必须相邻，所以要得到一个符合条件的七位数可以分为如下三步：第一步将１、３、５、７四个数字排好有Ｐ44 种不同的排法；第二步将２、４、６三个数字“捆绑”在一起有Ｐ3 3 种不同的“捆绑”方法; 第三步将第二步“捆绑”的这个整体“插入”到第一步所排的四个不同数字的五个“间隙”(包括两端的两个位置)中的其中一个位置上,有Ｐ5 1种不同的“插入”方法根据乘法原理共有Ｐ4 4 Ｐ3 3 Ｐ5 1 ＝720种不同的排法所以共有720个符合条件的七位数　 解（2）：因为三个偶数２、４、６ 互不相邻，所、以要得到符合条件的七位数可以分为如下两步：第一步、将１、３、５、７四个数字排好，有Ｐ4 4 种不同的排法；第二步将２、４、６分别“插入”到第一步排的四个数字的五个“间隙”（包括两端的两个位置）中的三个位置上，有Ｐ5 3 种“插入”方法。

根据乘法原理共有Ｐ4 4 Ｐ5 3 ＝1440种不同的排法所以共有1440个符合条件的七位数　 例２ 将Ａ、Ｂ、Ｃ、Ｄ、Ｅ、Ｆ分成三组，共有多少种不同的分法？　 解：要将Ａ、Ｂ、Ｃ、Ｄ、Ｅ、Ｆ分成三组，可以分为三类办法：（１－１－４）分法、（１－２－３）分法、（２－２－２）分法下面分别计算每一类的方法数：　 第一类（１－１－４）分法，这是一类整体不等分局部等分的问题，可以采用两种解法解法一：从六个元素中取出四个不同的元素构成一个组，余下的两个元素各作为一个组，有Ｃ6 4 种不同的分法解法二：从六个元素中先取出一个元素作为一个组有Ｃ6 1 种选法，再从余下的五个元素中取出一个元素作为一个组有Ｃ5 1 种选法，最后余下的四个元素自然作为一个组，由于第一步和第二步各选取出一个元素分别作为一个组有先后之分，产生了重复计算，应除以Ｐ2 2 所以共有Ｃ6 1 Ｃ5 1 Ｐ2 2 ＝15种不同的分组方法　 第二类（１－２－３）分法，这是一类整体和局部均不等分的问题，首先从六个不同的元素中选取出一个元素作为一个组有Ｃ6 1 种不同的选法，再从余下的五个不同元素中选取出两个不同的元素作为一个组有Ｃ5 2 种不同的选法，余下的最后三个元素自然作为一个组，根据乘法原理共有Ｃ6 1 Ｃ5 2 ＝60种不同的分组方法。

　 第三类（２－２－２）分法，这是一类整体“等分”的问题，首先从六个不同元素中选取出两个不同元素作为一个组有Ｃ6 2 种不同的取法，再从余下的四个元素中取出两个不同的元素作为一个组有Ｃ4 2 种不同的取法，最后余下的两个元素自然作为一个组由于三组等分存在先后选取的不同的顺序，所以应除以Ｐ3 3 ，因此共有Ｃ6 2 Ｃ4 2 Ｐ3 3 ＝15种不同的分组方法 根据加法原理，将Ａ、Ｂ、Ｃ、Ｄ、Ｅ、Ｆ六个元素分成三组共有：15＋60＋15＝90种不同的方法　 例３ 一排九个坐位有六个人坐，若每个空位两边都坐有人，共有多少种不同的坐法？　 解：九个坐位六个人坐，空了三个坐位，每个空位两边都有人，等价于三个空位互不相邻，可以看做将六个人先依次坐好有Ｐ6 6 种不同的坐法，再将三个空坐位“插入”到坐好的六个人之间的五个“间隙”（不包括两端）之中的三个不同的位置上有Ｃ5 3 种不同的“插入”方法根据乘法原理共有Ｐ6 6 Ｃ5 3 ＝7200种不同的坐法　 小结：（１）ｍ个不同的元素必须相邻，有Ｐm m 种“捆绑”方法　 （２）ｍ个不同元素互不相邻，分别“插入”到ｎ个“间隙”中的ｍ个位置有Ｐn m 种不同的“插入”方法。

　 （３）ｍ个相同的元素互不相邻，分别“插入”到ｎ个“间隙”中的ｍ个位置，有Ｃn m 种不同的“插入”方法　 （４）若干个不同的元素“等分”为 ｍ个组,要将选取出每一个组的组合数的乘积除以Ｐm m 。