排列组合经典题型

1 排 列

一、优先法

例1（1）7位同学站成一排，共有多少种不同的排法？

解：问题可以看作：7个元素的全排列77A＝5040．

（2）7位同学站成两排（前3后4），共有多少种不同的排法？

解：根据分步计数原理：7×6×5×4×3×2×1＝7！＝5040．

（3）7位同学站成一排，其中甲站在中间的位置，共有多少种不同的排法？

解：问题可以看作：余下的6个元素的全排列——66A=720．

（4）7位同学站成一排，甲、乙只能站在两端的排法共有多少种？

解：根据分步计数原理：第一步 甲、乙站在两端有22A种；

第二步 余下的5名同学进行全排列有55A种，所以，共有22A55A=240种排列方法

（5）7位同学站成一排，甲、乙不能站在排头和排尾的排法共有多少种？

解法1（直接法）：第一步从（除去甲、乙）其余的5位同学中选2位同学站在排头和排尾有25A种方法；第二步从余下的5位同学中选5位进行排列（全排列）有55A种方法，所以一共有25A55A＝2400种排列方法

解法2：（排除法）若甲站在排头有66A种方法；若乙站在排尾有66A种方法；若甲站在排头且乙站在排尾则有55A种方法，所以，甲不能站在排头，乙不能排在排尾的排法共有77A－662A＋55A=2400种．

说明：对于“在”与“不在”的问题，常常使用“直接法”或“排除法”，对某些特殊元素可以优先考虑

二、捆绑法：

例2． 7位同学站成一排，

（1）甲、乙两同学必须相邻的排法共有多少种？

解：先将甲、乙两位同学“捆绑”在一起看成一个元素与其余的5个元素（同学）一起进行全排列有66A种方法；再将甲、乙两个同学“松绑”进行排列有22A种方法．所以这样的排法一共有62621440AA种

（2）甲、乙和丙三个同学都相邻的排法共有多少种？

解：方法同上，一共有55A33A＝720种

（3）甲、乙两同学必须相邻，而且丙不能站在排头和排尾的排法有多少种？

解法一：将甲、乙两同学“捆绑”在一起看成一个元素，此时一共有6个元素，因为丙不能站在排头和排尾，所以可以从其余的5个元素中选取2个元素放在排头和排尾，有25A种方法；将剩下的4个元素进行全排列有44A种方法；最后将甲、乙两个同学“松绑”进行排列有22A种方法．所以这样的排法一共有 2 25A44A22A＝960种方法

解法二：将甲、乙两同学“捆绑”在一起看成一个元素，此时一共有6个元素，若丙站在排头或排尾有255A种方法，

所以，丙不能站在排头和排尾的排法有960)2(225566AAA种方法

解法三：将甲、乙两同学“捆绑”在一起看成一个元素，此时一共有6个元素，因为丙不能站在排头和排尾，所以可以从其余的四个位置选择共有14A种方法，再将其余的5个元素进行全排列共有55A种方法，最后将甲、乙两同学“松绑”，所以，这样的排法一共有14A55A22A＝960种方法．

（4）甲、乙、丙三个同学必须站在一起，另外四个人也必须站在一起

解：将甲、乙、丙三个同学“捆绑”在一起看成一个元素，另外四个人“捆绑”在一起看成一个元素，时一共有2个元素，∴一共有排法种数：342342288AAA（种）

说明：对于相邻问题，常用“捆绑法”（先捆后松）．

三、插空法

例3．7位同学站成一排，

（1）甲、乙两同学不能相邻的排法共有多少种？

解法一：（排除法）3600226677AAA；

解法二：（插空法）先将其余五个同学排好有55A种方法，此时他们留下六个位置（就称为“空”吧），再将甲、乙同学分别插入这六个位置（空）有26A种方法，所以一共有36002655AA种方法．

（2）甲、乙和丙三个同学都不能相邻的排法共有多少种？

解：先将其余四个同学排好有44A种方法，此时他们留下五个“空”，再将甲、乙和丙三个同学分别插入这五个“空”有35A种方法，所以一共有44A35A＝1440种．

说明：对于不相邻问题，常用“插空法”（特殊元素后考虑）．

四、倍除法

5男5女排成一排，按下列要求各有多少种排法：（1）男女相间；（2）女生按指定顺序排列

解：（1）先将男生排好，有55A种排法；再将5名女生插在男生之间的6个“空挡”（包括两端）中，

（2）方法1：10510105530240ANAA；

方法2：设想有10个位置，先将男生排在其中的任意5个位置上，有510A种排法；余下的5个位置排女生，因为女生的位置已经指定，所以她们只有一种排法

故本题的结论为510130240NA（种） 3 强化练习

1．（2007年天津卷）如图，用6种不同的颜色给图中的4个格子涂色，每个格子涂一种颜色，要求最多使用3种颜色且相邻的两个格子颜色不同，则不同的涂色方法共有 种（用数字作答）．

用2色涂格子有C62×2=30种方法，

用3色涂格子，第一步选色有C63，第二步涂色，共有3×2（1×1+1×2）=18种，

所以涂色方法18×C63=360种方法，

故总共有390种方法．

故答案为：390

2．（2007年江苏卷）某校开设9门课程供学生选修，其中,,ABC三门由于上课时间相同，至多选一门，学校规定每位同学选修4门，共有 75

种不同选修方案。（用数值作答）

3．（2007年北京卷）记者要为5名志愿都和他们帮助的2位老人拍照，要求排成一排，2位老人相邻但不排在两端，不同的排法共有（ Ｂ ）

Ａ．1440种 Ｂ．960种 Ｃ．720种 Ｄ．480种

4．（2007年全国卷I）从班委会5名成员中选出3名，分别担任班级学习委员、文娱委员与体育委员，其中甲、乙二人不能担任文娱委员，则不同的选法共有 36 种．（用数字作答）

∵先从其余3人中选出1人担任文娱委员，

再从4人中选2人担任学习委员和体育委员，

∴不同的选法共有C31•A42=3×4×3=36种

5．（2007年全国卷Ⅱ）从5位同学中选派4位同学在星期五、星期六、星期日参加公益活动，每人一天，要求星期五有2人参加，星期六、星期日各有1人参加，则不同的选派方法共有（ B ）

A．40种 B．60种 C．100种 D．120种

6. （2007年陕西卷）安排3名支教老师去6所学校任教，每校至多2人，则不同的分配方案共有 210 种.（用数字作答）

设3名老师分别为甲，乙，丙；6所学校分别为A,B,C,D,E,F;先分配甲，甲可以去这6所学校中的任一所，故有6种可能；再分配乙，由条件每校至多2人，故当乙和甲去同一所学校，则丙去剩余5所学校中一所，这种情况下有6*5=30种方案；若乙不和甲去同一所学校，则乙可以有5种选择，而丙可以去这6所学校中任一所，故有6*5*6=180种分配情况，两种情况相加共有210种方案。。。

7．（2007年四川卷）用数字0，1，2，3，4，5可以组成没有重复数字，并且比20000大的五位偶数共有（ ）

（A）288个 （B）240个 （C）144个 （D）126个

解析：选B．对个位是0和个位不是0两类情形分类计数；对每一类情形按“个位－最高位－中间三位”分步计数：①个位是0并且比20000大的五位偶数有341496A个；②个位不是0并且比20000大的五位偶数有3423144A个；故共有96144240个．本题考查两个基本原理，是典型的源于教材的题目．

8.．（2007年辽宁卷）将数字1，2，3，4，5，6拼成一列，记第i个数为i(i126)a，，，，若11a，33a，55a，135aaa，则不同的排列方法有 种（用数字作答）．

解析：分两步：（1）先排531,,aaa，1a=2，有2种；1a=3有2种；1a=4有1种，共有5种；（2） 4 再排642,,aaa，共有633A种，故不同的排列方法种数为5×6=30，填30．

组 合

1.组合数的性质1：mnnmnCC．

2．组合数的性质2：mnC1＝mnC+1mnC．

一般地，从121,,,naaa这n+1个不同元素中取出m个元素的组合数是mnC1，这些组合可以分为两类：一类含有元素1a，一类不含有1a．含有1a的组合是从132,,,naaa这n个元素中取出m 1个元素与1a组成的，共有1mnC个；不含有1a的组合是从132,,,naaa这n个元素中取出m个元素组成的，共有mnC个．根据分类计数原理，可以得到组合数的另一个性质．在这里，主要体现从特殊到一般的归纳思想，“含与不含其元素”的分类思想．

证明：)]!1([)!1(!)!(!!1mnmnmnmnCCmnmn )!1(!!)1(!mnmmnmnn

)!1(!!)1(mnmnmmn)!1(!)!1(mnmnmnC1

∴mnC1＝mnC+1mnC．

说明：①公式特征：下标相同而上标差1的两个组合数之和，等于下标比原下标多1而上标与大的相同的一个组合数；

②此性质的作用：恒等变形，简化运算

例1．（1）计算：69584737CCCC；

（2）求证：nmC2＝nmC+12nmC+2nmC．

解：（1）原式4565664889991010210CCCCCCC；

证明：（2）右边1121112()()nnnnnnnmmmmmmmCCCCCCC左边

例2．证明：pnpmpmpnnmCCCC。

证明：原式左端可看成一个班有m个同学，从中选出n个同学组成兴趣小组，在选出的n个同学中，p个同学参加数学兴趣小组，余下的pn个同学参加物理兴趣小组的选法数。原式右端可看成直接在m个同学中选出p个同学参加数学兴趣小组，在余下的pm个同学中选出pn个同学参加物理兴趣小组的选法数。显然，两种选法是一致的，故左边=右边，等式成立。

例3．证明：110mmnmmnCCCC…mnmmmnCCC0（其中mn）。

证明：设某班有n个男同学、m个女同学，从中选出m个同学组成兴趣小组，可分为1m类： 5 男同学0个，1个，„，m个，则女同学分别为m个，1m个，„，0个，共有选法数为110mmnmmnCCCC„0mmnCC。又由组合定义知选法数为mnmC，故等式成立。

例4．证明：32132nnnCCC…12nnnnnC。

证明：左边=32132nnnCCC„nnnC=313212111nnnCCCCCC„nnnCC1，

其中iniCC1可表示先在n个元素里选i个，再从i个元素里选一个的组合数。设某班有n个同学，选出若干人（至少1人）组成兴趣小组，并指定一人为组长。把这种选法按取到的人数i分类（，，21i„n，），则选法总数即为原式左边。现换一种选法，先选组长，有n种选法，再决定剩下的1n人是否参加，每人都有两种可能，所以组员的选法有12n种，所以选法总数为12nn种。显然，两种选法是一致的，故左边=右边，等式成立。