数学冬令营——组合计数.doc

组合计数
一、基本知识
1. 加法原理与乘法原理
如果完成一件事情的方法可分成n个互不相交的类，且第一类中有种方法，第二类中有种方法，…，第n类中有种方法，那么完成这件事情一共有++…+种方法.这就是加法原理，简称为分类相加.
如果完成一件事情要分n步，且第一步有种方法，第二步有种方法，…，第n步有种方法，那么完成这件事情一共有…种方法.这就是乘法原理，简称为分步相乘.
2. 无重复的排列与组合
2.1． 无重复的排列
从n个不同的元素中，任取m（≤n）个不同元素，按照一定的顺序排成一列（或者从n个不同的元素中，有序地任取m（≤n）个不同元素），叫做从n个不同的元素中取出m个不同元素的一个排列.
从n个不同的元素中取出m（≤n）个不同元素的排列的个数，叫做从n个不同的元素中取出m个不同元素的排列数，用符号或表示.由乘法原理得
==
==
2.2．无重复的组合
从n个不同的元素中，任取m（≤n）个不同元素并成一组（或者从n个不同的元素中，无序地任取m（≤n）个不同元素），叫做从n个不同的元素中任取m个不同元素的组合.
从n个不同的元素中取m（≤n）个不同元素的所有组合的个数，叫做从n个不同的元素中取m个不同元素的组合数，用符号表示，其计算公式为
===
事实上，对于每一个从n个不同的元素中任取m个不同元素的组合，将其元素作全排列可产生个不同的排列.显然不同的组合产生的排列互不相同，且每个排列都可以分2步得到.由乘法原理可得=•，于是=.
3. 可重复的排列与组合
3.1. 可重复的排列
从n个不同的元素中，任取（允许重复）m（≥1）个元素，按照一定的顺序排成一列，叫做从n个不同的元素中取出m个元素的可重复排列.
由乘法原理可得，从n个不同的元素中，取m（≥1）个元素的所有可重复排列个数为（选第1位元素有n种方法，选第2位元素也有n种方法，…，最后，选第m位元素也有n种方法）.
3.2. 有限个重复元素的全排列
设n个元素由k个不同的元素，，…，组成，其中有个，有个，…，有个（++…+=n），那么这n个元素的全排列称为有限个重复元素的全排列，其排列数为.
事实上，若n个元素互不相同，则全排列为，但其中有个，它们之间任意交换顺序（共有种交换顺序的方法），得到的是同一排列（=1，2，…，k）.故不同的排列个数为.
3.3. 可重复的组合
从个不同的元素中，任意可重复地选取（≥1）个元素，叫做从个不同的元素中取出个元素的可重复的组合，其不同组合的个数为.
事实上，不妨设个元素为1，2，…，，设取出的个元素为
（1≤）≤≤…≤（≤），
显然（1≤）+0＜＋１＜…＜＋－１（≤＋－１）．
将（，，…，）与（+0，＋１，…，＋－１）建立一一对应，后者为从＋－１个不同元素1，2，…，＋－１中取个不同元素的组合，且不同的（，，…，）对应的（+0，＋１，…，＋－１）是不同的．反过来，从1，2，…，＋－１中任取个不同的数的组合
（1≤）＜＜…＜（≤＋－1）．
也恰好对应于一个从个元素1，2，…，中取个可重复元素的组合
（1≤）－0≤－1≤…≤－＋1（≤）．
因此，上面所说的对应是一一对应，故所求组合数等于从＋－1个不同的元素1，2，…，＋－1中取个不同元素的组合数，即．
4．圆排列与项链数
从个不同的元素中，取个不同元素排在一个圆周上，叫做从个不同的元素中取出个不同元素的圆周排列，其排列数为
=.
事实上，对每一个固定的个元素的圆排列，在任意两个元素之间将圆周剪开，沿顺时针方向拉直恰产生个直线排列，且不同的圆排列所产生的直线排列互不相同.又易见从个不同的元素取个不同元素的排列都可以这样从圆排列中得到，所以，所求圆排列数的倍恰好是从个不同的元素中取个不同元素的排列数，由此得出上述结论.
将个不同的元素排成一个圆周的圆排列数为=.
将粒不同的珍珠，用线串成一根项链的不同发数记为，则=（≥3），=1（=1或2）.
5．容斥原理
对于有限集合，我们用表示中元素的个数，若是的子集，则=\表示在中的补集.
定理1（容斥原理）设是有限集合，，，，是的子集，则
||＝－＋－…＋＋…＋.　　　　　　　　（＃）
证明　只要对任意，证明（＃）式两边计算的次数是相同的即可.
若不属于，，，中任何集合，则在（＃）式左边计算了１次，在（＃）式右边第１项中计算了１次，而在（＃）式右边其余各个和式项中计算的次数为０，故在（＃）式右边计算的总次数也为１.
若恰属于，，，中个集合，这里≥１，则在（＃）式左边计算的次数为０，而在右边的第１项，第２项，…，第＋１项，…，最后一项中计算的次数分别为１，，，…，，０，０，…，０.在（＃）式右边计算的总次数为
１－＋－…＋＋０＋…＋０＝＝０
综合上面的讨论，我们知道对任意，（＃）式两边计算的次数（即对等式两边所作的贡献）相等.故（＃）式成立.
定理2（容斥原理的对偶形式）对任意有限集合，，，，我们有
=-+…＋＋…＋.
二、基本方法与策略
1. 枚举法
所谓枚举法，就是把要计数的集合中的元素逐一列举出来，不重复不遗漏，从而计算出中的元素的个数.在枚举的过程中，常常要适当地分类和分步枚举，这就要用到加法原理与乘法原理以及记数的基本公式.
例1-1 方程+++++++++=3的非负整数解共有 组
（1985年全国高中联赛题）
解 0≤≤3且为非负整数，=0或1，下面分两种情形.
（1）若=1，则必有某=1（2≤≤10），其余=0（≠1，），这样的解有=9组.
（2）若=0，则又分为三种情形.
（i）有某一个=3（2≤≤10），其余=0（≠1，），这样的解有=9组.
（ii）有某一个=2（2≤≤10），则必还有一个=1（≠1，），其余=0（≠1，，），这样的解有=72组.
（iii）所有≠2或3（2≤≤10），则，，，，，，，，中必有3个等于1，其余6个等于0，这样的解有=84组.
于是，原方程共有9+9+72+84=174组.
例1-2 将一个四棱锥的每一个顶点染上一种颜色，并使同一棱的两端点异色，如果只有5种颜色可供使用，那么不同的染色方法总数是 .
（1995年全国高中联赛题）
解 依题意，四棱锥的顶点，，互不同色，题目有=60种染色方法.
当，，的颜色染好后，不妨设其颜色分别为1色，2色，3色，则只可染2，4，5色中的一色.
（1）若染2色，则可染3，4，5色中的一色，有=3种方法.
（2）若染4色，则可染3，5色中的一色，有=2种方法.
（3）若染5色，则可染2，4色中的一色，有=2种方法.
故总的染色方法为60（3+2+2）=420种.
2．映射方法
定义 设是从集合到集合的映射.若对任意，，当≠时有（）≠（），则称为到的单射；若对任意的，存在，使得（）=，则称为到的满射；若既是单射又是满射，则称为到的双射，又称为与之间的一一映射.
定理1 对于两个有限集合与，若存在从到的单射，则||≤||；若存在从到的满射，则||≥||；若存在从到的双射，则||=||.
当计算有限集合中的元素个数比较困难时，我们设法建立到另一个有限集合上的双射，如果中的元素个数||容易算出，于是由||=||，得出中的元素个数，这种计数方法称为映射方法，或者称为配对法.
例2-1 设凸边形的任意3条对角线不相交于形内一点，求它的对角线在形内的交点总数.
解 依题意，一个交点由两条对角线与相交而得，反之，两条相交的对角线与，确定一个交点，而与（，）可建立一一对应.
又因两条相交的对角线与分别由凸边形中两对顶点，和，连接而成，故（，）又可与4顶点组（，，，）建立一一对应，即有
（，）（，，，）
因此，形内对角线的交点总数=凸边形的4顶点组的组数=.
例2-2 将三角形每边等分，过分点作其余两边的平行线，在已知三角形内所形成的平行四边形的个数记为，求的表达式.
解 延长到使，延长到使.设将等分的分点（包括，共个）依次记为0，1，2，…，，于是平行四边形每边所在直线恰与交与4点，，，（0≤＜＜＜≤）反之，从上的个等分点中任意取4个等分点，，，（0≤＜＜＜≤），过，作的平行线，过，作的平行线，便可得到一个平行四边形，这种对应是一一对应，所以图中边不平行与的平行四边形有个，从而平行四边形的总个数=3个.
3．递推法
例3-1 将圆分成（≥2）个扇形，，…，.现用种颜色给这些扇形染色，每个扇形恰染一种颜色且要求相邻的扇形的颜色互不相同.问有多少种不同的染色方法？
解 设染色方法数为.
（1）求初始值.
=2时，给染色有种方法，继而给染色有（-1）种方法，所以，=（-1）.
（2）求递推关系.
因有种染色方法，有（-1）种染色方法，有（-1）种染色方法，…，有（-1）种染色方法，仍有（-1）种染色方法（不保证与不同色）.这样共有种染色方法，但这种染色方法可分为两类：
一类是与不同色，此时的染色方法有种；另一类是与同色，则将与合并为一个扇形，并注意到此时与不同色，故这时的的染色方法有种，由加法原理得
+=（≥2）
（3）求.
令=，由+=，有－1=－（－１），即－1为首项为－1＝，公比为－的等比数列的第项.
－1＝（）（－）＝，
即＝１＋，
＝
例3-2 将周长为24的圆周等分为24段，从24个分点中选取8个点，使得其中任何两点所夹的弧长都不等于3和8.问满足要求的8点组的不同取法有多少种？
（2001年CMO题）
解： 设24个分点依次为1，2，…，24，将24个数列成下表：
1
4
7
10
13
16
19
22
9
12
15
18
21
24
3
6
17
20
23
2
5
8
11
14
表中每行相邻两数所代表的点所夹弧长为3，每列相邻两数所代表的点所夹弧长为8，故每列至多取一个数，8列至多取8个数，但一共要取8个数，故每列恰取一个数且相邻两列所取的数不同行.
若将每列看作一个扇形，每列中第一、而、三行看作三种颜色，则由上面例题知，
＝=258种.
例3-3 如图在1个正六边形的6个区域栽种观赏植物，要求同1区域中种同一种植物，相邻的2区域中种不同的植物.现有4种不同的植物可供选择，则有 种栽种方案. （2001年全国高中联赛题）
解： 在上述命题中，取=6，=4，即得
＝=732种.
例3-4 用红、黄、蓝、绿四种颜色给图中的A、B、C、D四个小方格涂色（允许只用其中几种），使邻区（有公共边的小格）不同色，则不同的涂色方式种数为（ ）.
、； 、； 、； 、.
解：选两色有种，一色选择对角有种选法，共计种；选三色有种，其中一色重复有种选法，该色选择对角有种选法，另两色选位有种，共计种；四色全用有种（因为固定位置），合计种.
D
B
C
A
变例：（2008全国一）如图，一环形花坛分成四块，现有4种不同的花供选种，要求在每块里种1种花，且相邻的2块种不同的花，则不同的种法总数为（ B ）
A．96 B．84 C．60 D．48
例3-5 有人要上楼，此人每步能向上走1阶或2阶，如果一层楼有18阶，他上一层楼有多少种不同的走法？
解法1： 此人上楼最多走18步，最少走9步.这里用分别表示此人上楼走18步，17步，16步，…，9步时走法（对于任意前后两者的步数，因后者少走2步1阶，而多走1步2阶，计后者少走1步）的计数结果.考虑步子中的每步2阶情形，易得，，，…，.
综上，他上一层楼共有种不同的走法.
解法2： 设表示上n阶的走法的计数结果.
显然，，（2步1阶；1步2阶）．对于起步只有两种不同走法：上1阶或上2阶.
因此对于，第1步上1阶的情形，还剩阶，计种不同的走法；对于第1步上2阶的情形，还剩阶，计种不同的走法.总计.
同理，，，…，.
4．容斥原理
例4-1 由数字1，2，3组成n位数，且在这个n位数中，1，2，3的每一个至少出现一次，问这样的n位数有多少个？
解 设U是由1，2，3组成的n位数的集合，是U中不含数字1的n位数的集合，是U中不含数字2的n位数的集合，是U中不含数字3的n位数的集合，则
；；；．
因此
．
即符合题意的n位数的个数为．
例4-2 参加大型团体表演的学生共240名，他们面对教练站成一行，自左至右按1，2，3，4，5，…依次报数．教练要求全体学生牢记各自所报的数，并做下列动作：先让报的数是3的倍数的全体同学向后转；接着让报的数是5的倍数的全体同学向后转；最后让报的数是7的倍数的全体同学向后转．问：
（1）此时还有多少名同学面对教练？
（2）面对教练的同学中，自左至右第66位同学所报的数是几？
解（1）设，表示由U中所有i的倍数组成的集合．则
；，，；
，，；．
从而此时有名同学面对教练．
如果我们借助维恩图进行分析，利用上面所得数据分别填入图1，注意按从内到外的顺序填．
如图1，此时面对教练的同学一目了然，应有109+14+4+9=136名．
（2）用上面类似的方法可算得自左至右第1号至第105号同学中面对教练的有60名．
考虑所报的数不是3，5，7的倍数的同学没有转动，他们面对教练；所报的数是3，5，7中的两个数的倍数的同学经过两次转动，他们仍面对教练；其余同学转动了一次或三次，都背对教练．
从106开始，考虑是3、5、7的倍数：
3的倍数（由105依次加3）：108，111，114，117，120，…
5的倍数（由105依次加5）：110，115，120，…
7的倍数（由105依次加7）：112，119，…
因此，从106号开始，自左至右，面对教练的同学所报的数依次是：106，107，109，113，116，118，120，…
由此可知面对教练的第66位同学所报的数是118．
例4-3 将与105互素的正整数从小到大排成数列，求出这个数列的第1000项.
（1994年全国高中联赛题）
解 首先，求出={1，2，…，105}内与105=345互素的正整数的个数，令={|∈且被整除}（=3，5，7）.于是中与105互素的正整数的个数为
||
=||-||-||-||+||+||+||-||
=105－－－+++－
=105-35-21-15+7+5+3-1=48
其次，设所有正整数中与105互素的正整数从小到大排成数列为{}，于是有，=1，=2，=4，…，=101，=103，=104，并记={，，…，}.
一方面，数列{}中每一项可表示成为=（，为非负整数，0≤≤104），于是由（，105）=（，105）=（，105）=1，知∈，即数列{}中每一项可表示成为=（为非负整数，∈）的形式.
另一方面，对任意非负整数及任意∈，由（，105）=（，105）=1，知数列{}中必有某一项=.
可见，数列{}有且仅有形如（为非负整数，∈）的数组成，因对每一个固定的，取遍中的数时，形如的数有48个，得到数列中的48个项，因为1000=+40，所以，=+.
而=104，=103，=101，=97，=94，=92，=89，=88，=86，所以=+86=2186.
例4-4 五人站成一列，重新站队时，各人都不站在原来的位置上，有多少种站法？
解：设原来站在第i个位置的人是（i=1，2，3，4，5）.重新站队时，站在第2个位置的站法有种，其中不符合要求的有：站第3位的种，站第4位的种，但有的站法在考虑的情形时已经减去了，故只应再算（）种，同理，站第5位的应再算[]种.站在第3，4，5位的情形与站在第2位的情形时对等的，故所有符合要求的站法有：
=44（种）.
5. 构造不定方程
在某些排列组合问题中,我们可以利用不定方程的正整数（或整数）解的组数来确定排列组合数的多少.
引理：不定方程 （）的正整数解有 组.
证明:用 “隔板法” 证明引理.
由于， , …, ,把n 分成n个1 ,这n个 1 共有n - 1个空档.插入m - 1块“隔板”,把n个1分成m个部分,则
每一种情况对应不定方程的一组解.所以，原不定方程共有组解.
推论:不定方程（）非负整数解有组.
例5-1　已知两个实数集合与.若从A 到B的映射f 使得B 中每个2元素都有原像,且…≤,则这样的映射共有 ( D ).
(A) 　(B) 　(C) 　(D)
(2002 ,全国高中数学联赛)
解:不妨设 .因为 中每个元素都有原像,设原像的集合为 ,其元素个数为；原像的集合为 ,其元素个数为; ……; 原像的集合为 ,其元素个数为则
+ + …+ = 100. ①
于是,问题转化为求不定方程 ①的正整数解的组数,共有组解.
例5-2 8个女孩，25个男孩围成一个圆周，每两个女孩之间至少站有2个男孩，共有 种不同的排列方法.（只把圆旋转一下就重合的排法认为是相同的）
（1990年全国高中联赛题）
解 以8个女孩为组长，将25个男孩分入该8个组，各组内男孩数记为，，，，，，，，则++…+=25（）①
令=-2，则++…+=9（）②
于是，①的正整数解组的组数等于②的非负整数解组的个数=，即25个男孩分入该8个组，每组至少两人的分组方法有种.8个组排成每组以女孩为头的圆排列有=种排列方法，再25个男孩站入的方法数为，所以总的排列方法为•••••
例5-3　 如果从数1 ,2 , …,14中，按由小到大的顺序取出、、 ,使得同时满足与.那么，所有符合要求的不同取法有多少种.
(1989 ,全国高中数学联赛)
解:由,, ,
令 , , ，，则
.
于是,问题转化为求不定方程在
，，，下的整数解的组数.
将方程转化为

令，，，
而的正整数解的组数是.所以 ,符合条件的、、的不同取法有种.
6．配对法
求解某些数学间题时，针对问题中一个式子(或集合)的结构特征，配一个与具有内在联系的式子(或集合)，即的配对式(或配对集合)，然后借助 (表示某种数学运算，如加、减、乘、除等)，促进问题的转化和解决.我们把这种解决数学何题的思想称为配对思想.
例6-1 一次乒乓球比赛中，是n个运动员，每两人正好比赛一次，没有平局.若记胜的次数为，负的次数为，证明:
=
证明 首先，对于任意一个，他与其余个人都赛过，共赛过次.因无平局，所以的胜、负次数之和为 (定数)，即
+=
其次，因无平局，所以每场比赛后，有人胜必有对应一人负.全部比赛结束后，胜的总次数等于负的总次数，即
=
于是 -=
==
例6-2 对于及其每一个非空子集，定义“交替和”如下：按照递减的顺序重新排列元素，然后从最大的数开始交替的减、加后续的数.例如(1，2，4，6，9}，排列成(9，6，4，2，1)，交替和是9-6+4-2+l=6.{5}的交替和就是5.对，求所有交替和的总和.
解 不妨规定空集中元素交替和为0，将的个子集分成两类：一类含的有个子集，另一类不含的，也是个子集.将含的子集与不含的子集配对，显然这个配对是一一对应的，且其中一对中的两个子集的交替和之和为，于是的所有元素的交替和.因此当时，交替和的总和为448.
7．排列组合题的求解策略
（1）排除：对有限条件的问题，先从总体考虑，再把不符合条件的所有情况排除，这是解决排列组合题的常用策略.
（2）分类与分步
有些问题的处理可分成若干类，用加法原理，要注意每两类的交集为空集，所有各类的并集是全集；有些问题的处理分成几个步骤，把各个步骤的方法数相乘，即得总的方法数，这是乘法原理.
（3）对称思想：两类情形出现的机会均等，可用总数取半得每种情形的方法数.
（4）插空：某些元素不能相邻或某些元素在特殊位置时可采用插空法．即先安排好没有限制条件的元素，然后将有限制条件的元素按要求插入到排好的元素之间.
（5）捆绑：把相邻的若干特殊元素“捆绑”为一个“大元素”，然后与其它“普通元素”全排列，然后再“松绑”，将这些特殊元素在这些位置上全排列.
（6）隔板模型：对于将不可辨的球装入可辨的盒子中，求装的方法数，常用隔板模型．如将12个完全相同的球排成一列，在它们之间形成的11个缝隙中任意插入3块隔板，把球分成4堆，分别装入4个不同的盒子中的方法数应为，这也就是方程的正整数解的个数.
例7-1．有3名男生，4名女生，在下列不同要求下，求不同的排列方法总数.
(1)全体排成一行，其中甲只能在中间或者两边位置.
(2)全体排成一行，其中甲不在最左边，乙不在最右边.
(3)全体排成一行，其中男生必须排在一起.
(4)全体排成一行，男、女各不相邻.
(5)全体排成一行，男生不能排在一起.
(6)全体排成一行，其中甲、乙、丙三人从左至右的顺序不变.
(7)排成前后二排，前排3人，后排4人.
(8)全体排成一行，甲、乙两人中间必须有3人.
解：(1)利用元素分析法，甲为特殊元素，故先安排甲左、右、中共三个位置可供甲选择.有A种，其余6人全排列，有A种.由乘法原理得AA=2160种.
(2)位置分析法.先排最右边，除去甲外，有A种，余下的6个位置全排有A种，但应剔除乙在最右边的排法数AA种.则符合条件的排法共有AA－AA=3720种.
(3)捆绑法.将男生看成一个整体，进行全排列.再与其他元素进行全排列.共有AA=720种.
(4)插空法.先排好男生，然后将女生插入其中的四个空位，共有AA=144种.
(5)插空法.先排女生，然后在空位中插入男生，共有AA=1440种.
(6)定序排列.第一步，设固定甲、乙、丙从左至右顺序的排列总数为N，第二步，对甲、乙、丙进行全排列，则为七个人的全排列，因此A=N×A，∴N== 840种.
(7)与无任何限制的排列相同，有A=5040种.
(8)从除甲、乙以外的5人中选3人排在甲、乙中间的排法有A种，甲、乙和其余2人排成一排且甲、乙相邻的排法有AA.最后再把选出的3人的排列插入到甲、乙之间即可.共有A×A×A=720种.
例7-2 四名优等生保送到三所学校去，每所学校至少得一名，则不同的保送方案的总数是_________.
思路分析 解法一，采用处理分堆问题的方法. 解法二，分两次安排优等生，但是进入同一所学校的两名优等生是不考虑顺序的.
解：（法一）分两步 先将四名优等生分成2，1，1三组，共有C种；而后，对三组学生安排三所学校，即进行全排列，有A33种. 依乘法原理，共有N=C =36(种).
（法二）分两步 从每个学校至少有一名学生，每人进一所学校，共有A种；而后，再将剩余的一名学生送到三所学校中的一所学校，有3种.值得注意的是，同在一所学校的两名学生是不考虑进入的前后顺序的.因此，共有N=A·3=36(种).
例7-3 有五张卡片，它们的正、反面分别写0与1，2与3，4与5，6与7，8与9，将其中任意三张并排放在一起组成三位数，共可组成多少个不同的三位数？
解：(间接法)：任取三张卡片可以组成不同三位数C·23·A(个)，其中0在百位的有C·22·A (个)，这是不合题意的，故共有不同三位数：C·23·A－C·22·A=432(个).
例7-4一个口袋内装有4个不同的红球，6个不同的白球，若取出一个红球记2分，取出一个白球记1分，从口袋中取5个球，使总分不小于7分的取法有多少种？
解：设取个红球，个白球，于是：
，其中，

因此所求的取法种数是：=186（种）.
例7-5 从集合{0，1，2，3，5，7，11}中任取3个元素分别作为直线方程Ax+By+C=0中的A、B、C，所得的经过坐标原点的直线有_________条(用数值表示).
解：因为直线过原点，所以C=0，从1，2，3，5，7，11这6个数中任取2个作为A、B两数的顺序不同，表示的直线不同，所以直线的条数为A=30.
例7-6．二次函数y=ax2+bx+c的系数a、b、c，在集合{－3，－2，－1，0，1，2，3，4}中选取3个不同的值，则可确定坐标原点在抛物线内部的抛物线多少条？
解：由图形特征分析，a＞0,开口向上，坐标原点在内部f(0)=c＜0;a＜0,开口向下，原点在内部f(0)=c＞0,所以对于抛物线y=ax2+bx+c来讲，原点在其内部af(0)=ac＜0,则确定抛物线时，可先定一正一负的a和c，再确定b,故满足题设的抛物线共有CCAA=144条.
例7-7．20个不加区别的小球放入编号为1、2、3的三个盒子中，要求每个盒内的球数不小于它的编号数，求不同的放法种数.
解：首先按每个盒子的编号放入1个、2个、3个小球，然后将剩余的14个小球排成一排，如图，|O|O|O|O|O|O|O|O|O|O|O|O|O|O|，有15个空档，其中“O”表示小球，“|”表示空档.将求小球装入盒中的方案数，可转化为将三个小盒插入15个空档的排列数.对应关系是：以插入两个空档的小盒之间的“O”个数，表示右侧空档上的小盒所装有小球数.最左侧的空档可以同时插入两个小盒.而其余空档只可插入一个小盒，最右侧空档必插入小盒，于是，若有两个小盒插入最左侧空档，有C种；若恰有一个小盒插入最左侧空档，有种；若没有小盒插入最左侧空档，有C种.由加法原理，有N==120种排列方案，即有120种放法.
例7-8．甲、乙、丙三人值周一至周六的班，每人值两天班，若甲不值周一、乙不值周六，则可排出不同的值班表数为多少？
解：每人随意值两天，共有CCC个；甲必值周一，有CCC个；乙必值周六，有CCC个；甲必值周一且乙必值周六，有CCC个.所以每人值两天，且甲必不值周一、乙必不值周六的值班表数，有N=CCC－2CCC+ CCC=90－2×5×6+12=42个.
例7-9．将名学生分配到甲、乙两个宿舍中，每个宿舍至少安排名学生，那么互不相同的分配方法共有多少种？
解：根据宿舍的人数，可分为三类：“”型不同的分配方法有种；“”型不同的分配方法有种；“”型不同的分配方法有种.则由加法原理得，不同的分配方法共有种.
本题体现了“先选后排”通法的应用，属于排列组合混合问题.要注意（不）平均分配与（不）平均分堆的联系与区别.
例7-10．（2005，天津）将A、B、C、D、E五种不同的文件放入一排编号依次为1，2，3，4，5，6，7的七个抽屉内，每个抽屉至多放一种文件.若文件A、B必须放入相邻的抽屉内，文件C、D也必须放入相邻的抽屉内，则文件放入抽屉内的满足条件的所有不同的方法有( C )种.
(A)60 (B)120 (C)240 (D)480
解：将AB、CD、E及两个空抽屉视为5个元素，全排列为.由于AB、CD的排列数均为，而两个空抽屉为相同元素，故共有=240种.
例7-11．从中任取个数字，从中任取个数字，组成没有重复数字的四位数，其中能被整除的不同四位数共有 个.
解：由已知，此四位数的末位只能是或，且不能在首位，故为特殊元素，而且二者中至少要选一个.根据题意，可分三类：有无，不同的四位数有个；有无，不同的四位数有个；同时存在，当在末位时，不同的四位数有个，当在末位时，不同的四位数有个.所以满足条件的不同的四位数共有个.
[小结] 本题考查有两个受条件限制的特殊元素的排列组合混合问题，基本解题模型为：分为三类.第一类，两个中一个都不考虑；第二类，两个中考虑一个；第三类，两个都考虑.
注意在具体求解中其中“先选后排”“位置分析法”等通法的运用.
例7-12．6名考生坐在两侧各有通道的同一排座位上应考，考生答完试卷先后次序不定，且每人答完后立即交卷离开座位，则其中一人交卷时为到达通道而打扰其余尚在考试的考生的概率为 .
解：
不妨设如上图就坐.
一
二
三
四
五
六
上面表格中,第一个格子排第一个交卷的人，第二个格子排第二个交卷的人，依次类推.
现在计算不出现打扰他人的交卷的总数.
如果坐在最左边的A第一个交卷，不会打扰其他人；如果坐在最右边的F第一个交卷，也不会打扰其他人，因此第一个格子有2种排法；第一个人交完卷且没打扰他人，则剩下的5人中，坐在最左边或最右边的人第二个交卷，也不打扰他人，因此第二个格子也有2种排法；……第五个格子也有2种排法.
因此，不出现打扰他人的交卷的总数为种.
所有的交卷的总数为
因此，出现打扰他人的交卷的总数为种
因此，出现打扰他人的交卷的概率为
1.（2008，安徽）12名同学合影，站成前排4人后排8人，现摄影师要从后排8人中抽2人调整到前排，若其他人的相对顺序不变，则不同调整方法的总数是( C ).
A． B． C． D．
2.（2008，湖北）将5名志愿者分配到3个不同的奥运场馆参加接待工作，每个场馆至少分配一名志愿者的方案种数为（D）.
A. 540 B. 300 C. 180 D. 150
3.（2008，福建）某班级要从4名男生、2名女生中选派4人参加某次社区服务，如果要求至少有1名女生，那么不同的选派方案种数为（A）.
A.14 B.24 C.28 D.48
4.（2008，陕西）某地奥运火炬接力传递路线共分6段，传递活动分别由6名火炬手完成.如果第一棒火炬手只能从甲、乙、丙三人中产生，最后一棒火炬手只能从甲、乙两人中产生，则不同的传递方案共有 96 种.
5.（2008，天津）有4张分别标有数字1，2，3，4的红色卡片和4张分别标有数字1，2，3，4的蓝色卡片，从这8张卡片中取出4张卡片排成一行.如果取出的4张卡片所标数字之和等于10，则不同的排法共有__432__种.
6．（2007，全国Ⅱ）从5位同学中选派4位同学在星期五、星期六、星期日参加公益活动，每人一天，要求星期五有2人参加，星期六、星期日各有1人参加，则不同的选派方法共有（ B ）.
A．40种 B．60种 C．100种 D．120种
7．（2007，四川）用数字0，1，2，3，4，5可以组成没有重复数字，并且比20000大的五位偶数共有（ B ）.
（A）288个 （B）240个 （C）144个 （D）126个
8．（2007，江苏）某校开设9门课程供学生选修，其中三门由于上课时间相同，至多选一门，学校规定每位同学选修4门，共有　75种不同选修方案.
9．（2007，辽宁）将数字1，2，3，4，5，6拼成一列，记第个数为，若，，，，则不同的排列方法有 30 种.
10．（2009，复旦）设有个不同颜色的球，放入个不同的盒子中，要求每个盒子至少有一个球，则不同的放法有（D）种.
（A） （B） （C） （D）
11．（2008，复旦）5个不同元素排成一列，规定不许排第一，不许排第二，不同的排法共有（C）种.
（A）64 （B）72 （C）78 （D）84
19 / 19