翻身道情-中教数据库论文

排列组合的常见模型
一、基础知识：
（一）处理排列组合问题的常用思路：
1、特殊优先：对于题目中有特殊要求的元素，在考虑步骤时优先安排，然后再去处理无要
求的 元素。
例如：用
0,1,2,3,4
组成无重复数字的五位数，共有多少种排法？
解：五位数意味着首位不能是0，所以先处理首位，共有4种选择，而其余数位没有要求，
4< br>只需将剩下的元素全排列即可，所以排法总数为
N4A
4
96
种
2、寻找对立事件：如果一件事从正面入手，考虑的情况较多，则可以考虑该事的对立面，
再用 全部可能的总数减去对立面的个数即可。
例如：在10件产品中，有7件合格品，3件次品。从这10 件产品中任意抽出3件，至少有
一件次品的情况有多少种
解：如果从正面考虑，则“至少1件 次品”包含1件，2件，3件次品的情况，需要进行分
类讨论，但如果从对立面想，则只需用所有抽取情 况减去全是正品的情况即可，列式较为简
33
单。
NC
10
C< br>7
85
（种）
3、先取再排（先分组再排列）：排列数
A
n
是指从
n
个元素中取出
m
个元素，再将这
m
个元
素进行排列。但有时会出现所需排列的元素并非前一步选出的元素，所以此时就要将过程拆
分成 两个阶段，可先将所需元素取出，然后再进行排列。
例如：从4名男生和3名女生中选3人，分别从事 3项不同的工作，若这3人中只有一名女
生，则选派方案有多少种。
解：本题由于需要先确定 人数的选取，再能进行分配（排列），所以将方案分为两步，第一
步：确定选哪些学生，共有
C
4
C
3
种可能，然后将选出的三个人进行排列：
A
3
。所以共有
213
C
4
C
3
A
3
10 8
种方案
m
213
（二）排列组合的常见模型
1、捆绑法（整体 法）：当题目中有“相邻元素”时，则可将相邻元素视为一个整体，与其他
元素进行排列，然后再考虑相 邻元素之间的顺序即可。
例如：5个人排队，其中甲乙相邻，共有多少种不同的排法

解：考虑第一步将甲乙视为一个整体，与其余3个元素排列，则共有
A
4< br>种位置，第二步考
42
2
虑甲乙自身顺序，有
A
2
种 位置，所以排法的总数为
NA
4
A
2
48
种
4
2、插空法：当题目中有“不相邻元素”时，则可考虑用剩余元素“搭台”，不相邻元素进行
“插空”，然后再进行各自的排序
注：（1）要注意在插空的过程中是否可以插在两边
（2）要从题目中判断是否需要各自排序
例如：有6名同学排队，其中甲乙不相邻，则共有多少种不同的排法
解：考虑剩下四名同学“ 搭台”，甲乙不相邻，则需要从5个空中选择2个插入进去，即有
C
5
242
种选择，然后四名同学排序，甲乙排序。所以
NC
5
A
4
A< br>2
480
种
2
3、错位排列：排列好的
n
个元素 ，经过一次再排序后，每个元素都不在原先的位置上，则
称为这
n
个元素的一个错位排 列。例如对于
a,b,c,d
，则
d,c,a,b
是其中一个错位排列。3< br>个元素的错位排列有2种，4个元素的错位排列有9种，5个元素的错位排列有44种。以上
三种 情况可作为结论记住
例如：安排6个班的班主任监考这六个班，则其中恰好有两个班主任监考自己班的 安排总数
有多少种？
解：第一步先确定那两个班班主任监考自己班，共有
C
6
种选法，然后剩下4个班主任均不
2
监考自己班，则为4个元素的错位排列，共9种 。所以安排总数为
NC
6
9135

2
4、依次插 空：如果在
n
个元素的排列中有
m
个元素保持相对位置不变，则可以考虑先将 这
m
个元素排好位置，再将
nm
个元素一个个插入到队伍当中（注意每插入 一个元素，下
一个元素可选择的空
1
）
例如：已知
A,B,C, D,E,F
6个人排队，其中
A,B,C
相对位置不变，则不同的排法有多少
种
解：考虑先将
A,B,C
排好，则
D
有4个空可以选择，
D
进入队伍后，
E
有5个空可以选择，
以此类推，
F
有6 种选择，所以方法的总数为
N456120
种
5、不同元素分组：将
n
个不同元素放入
m
个不同的盒中
6、相同元素分组：将
n
个相同元素放入
m
个不同的盒内，且每盒不空，则不 同的方法共有
m1
C
n
，因为元素相同，所以只需考虑每个盒子里
1
种。解决此类问题常用的方法是“挡板法”

所含元素个数，则可 将这
n
个元素排成一列，共有

n1

个空，使用

m1

个“挡板”进
入空档处，则可将这
n
个元素划 分为
m
个区域，刚好对应那
m
个盒子。例如：将6个相同
的小球放入 到4个不同的盒子里，那么6个小球5个空档，选择3个位置放“挡板”，共有
3
C
5
20
种可能
7、涂色问题：涂色的规则是“相邻区域涂不同的颜色”，在处理涂色 问题时，可按照选择颜
色的总数进行分类讨论，每减少一种颜色的使用，便意味着多出一对不相邻的区域 涂相同的
颜色（还要注意两两不相邻的情况），先列举出所有不相邻区域搭配的可能，再进行涂色即可。例如：最多使用四种颜色涂图中四个区域，不同的涂色方案有多少种？
解：可根据使用颜色的种数进行分类讨论
4
（1）使用4种颜色，则每个区域涂一种 颜色即可：
N
1
A
4

（2）使用3种颜色，则有一对不 相邻的区域涂同一种颜色，首
先要选择不相邻的区域：用列举法可得：

I,IV
不相邻
3
所以涂色方案有：
N
2
A
4

（3）使用2种颜色，则无法找到符合条件的情况，所以讨论终止
43
总计
SA
4
A
4
48
种
二、典型例题：
例1：某电视台邀请了6位同学的父母共12人，请12位家长中的4位介绍 对子女的教育情
况，如果这4位中恰有一对是夫妻，则不同选择的方法种数有多少
思路：本题解决的方案可以是：先挑选出一对夫妻，然后在挑选出两个不是夫妻的即可。
第一步：先挑出一对夫妻：
C
6

2
第二步：在剩下的10 个人中选出两个不是夫妻的，使用间接法：
C
10
5

1
所以选择的方法总数为
NC
6
C
10
5240
（种）
答案：
240
种
例2：某教师一天上3个班级的课，每班上1节，如果一天 共9节课，上午5节，下午4节，
并且教师不能连上3节课（第5节和第6节不算连上），那么这位教师 一天的课表的所有不
同排法有（ ）
A.
474
种 B.
77
种 C.
462
种 D.
79
种

1

2


思路：本题如果用直接法考虑，则在安排的过程中还要考虑两节连堂，并且会受到第5,6
节课连堂 的影响，分类讨论的情形较多，不易求解。如果使用间接法则更为容易。首先在无
任何特殊要求下，安排 的总数为
A
9
。不符合要求的情况为上午连上3节：
A
4
和 下午连上三
333
3
节：
A
3
，所以不同排法的总数为：< br>A
9
A
4
A
3
474
（种）
33
答案：A
例3：2位男生和3位女生共5位同学站成一排，若男生甲不站两端， 3位女生中有且只有
两位女生相邻，则不同排法的种数是（ ）
A.
60
B.
48
C.
42
D.
36

思路：首 先考虑从3位女生中先选中相邻的两位女生，从而相邻的女生要与另一女生不相邻，
则可插空，让男生搭 架子，因为男生甲不站两端，所以在插空的过程中需有人站在甲的边上，
再从剩下的两个空中选一个空插 入即可。
第一步：从三位女生中选出要相邻的两位女生：
C
3

第 二步：两位男生搭出三个空，其中甲的边上要进入女生，另外两个空中要选一个空进女生，
所以共有C
2
种选法。
第三步：排列男生甲，乙的位置：
A
2
，排列相邻女生和单个女生的位置：
A
2
，排列相邻女
生相互的位置：
A
2

21222
所以共有
NC
3
C
2
A
2
A
2
A
2
48
种
2
1
22
2
答案：B
例4：某班班会准备从甲，乙等7名 学生中选派4名学生发言，要求甲，乙两名同学至少有
一人参加，且若甲乙同时参加，则他们发言时不能 相邻，那么不同的发言顺序种数为（ ）
A. 360 B. 520 C. 600 D. 720
思路：因 为选人的结果不同会导致安排顺序的不同，所以考虑“先取再排”，分为“甲乙”
同时选中和“甲乙只有 一人选中”两种情况讨论：若甲乙同时被选中，则只需再从剩下5
22
C
5
2
，人中选取2人即可：在安排顺序时，甲乙不相邻则“插空”，所以安排的方式有：
A
3
A
2
，
222
从而第一种情况的总数为：
N
1
C
5
A
3
A
2
120
（种），若 甲乙只有一人选中，则首先先
从甲乙中选一人，有
C
2
，再从剩下5人中选取 三人，有
C
5
，安排顺序时则无要求，所以第
13

134
二种情况的总数为：
N
2
C
2
C
5
A
4
480
（种），从而总计600种
答案：C
例5：从单词“equation”中选取5个不同的字母排成一排，含有“qu”（其中“qu”相连
且顺序不变）的不同排列共有________种
思路：从题意上看，解决的策略要分为两步：第一 步要先取出元素，因为“qu”必须取出，
所以另外3个元素需从剩下的6个元素中取出，即
C
6
种，然后在排列时，因为要求“qu”
相连，所以采用“捆绑法”，将qu视为一个 元素与其它三个元素进行排列：
A
4
，因为“qu”
34
顺序不变， 所以不需要再对qu进行排列。综上，共有：
C
6
A
4
480< br>种
4
3
答案：
480

例6：设有编号
1 ,2,3,4,5
的五个茶杯和编号为
1,2,3,4,5
的五个杯盖，将五个杯盖盖 在五个
茶杯上，至少有两个杯盖和茶杯的编号相同的盖法有（ ）
A. 30种 B. 31种 C. 32种 D. 36种 < br>思路：本题可按照相同编号的个数进行分类讨论，有两个相同时，要先从5个里选出哪两个
22
相同，有
C
5
种选法，则剩下三个为错位排列，有2种情况，所以N
1
C
5
2
，有三个相同
3
时，同理，剩 下两个错位排列只有一种情况（交换位置），所以
N
2
C
5
1< br>，有四个相同时
23
则最后一个也只能相同，所以
N
3
1< br>，从而
SC
5
2C
5
1131
（种）
答案：B
例7：某人上10级台阶，他一步可能跨1级台阶，称为一阶步，也可能跨2级台阶 ，称为
二阶步；最多能跨3级台阶，称为三阶步，若他总共跨了6步，而且任何相邻两步均不同阶，则此人所有可能的不同过程的种数为（ ）
A. 6 B. 8 C. 10 D. 12
答案：A
思路：首先要确定在这6步中，一阶步，二阶步，三阶步各有几步，分别设为
x,y,zN
，


x4

x3

x2
xyz6


则有

，解得：

y0,

y2,

y4
，因为相邻两步不同阶，所 以符合

x2y3z10

z2

z1

z0



x3

要求 的只有

y2
，下面开始安排顺序，可以让一阶步搭架子，则二阶步与三阶步必须插

z1

入一阶步里面的两个空中，所以共有2种插法，二阶步与三阶步的 前后安排共有3种（三二
二，三二三，二三三），所以过程总数为
N236

答案：A
例8：某旅行社有导游9人，其中3人只会英语，2人只会日语，其余4人既会英语 又会日
语，现要从中选6人，其中3人负责英语导游，另外三人负责日语导游，则不同的选择方法
有_______种
思路：在步骤上可以考虑先选定英语导游，再选定日语导游。英语导游的组成可 按只会英语
的和会双语的人数组成进行分类讨论，然后再在剩下的人里选出日语导游即可。第一种情况：
没有会双语的人加入英语导游队伍，则英语导游选择数为
C
3
，日语导游从剩 下6个人中选
333
择，有
C
6
中，从而
N
0C
3
C
6
，第二种情况：有一个会双语的人加入英语导游队伍，从< br>3
123
而可得
N
1
C
4
，依次类推，第 三种情况。两个会双语的加入英语导游队伍，则
C
3
C
5
21N
2


C
4
C
3

C
4
3
，第四种情况，英语导游均为会双语的。则
N
3
C< br>4
3
C
3
3
，综上所述，
3312321333< br>不同的选择方法总数为
SC
3
C
6
C
4
C
3
C
5
C
4
C
3
C
4
C
4
C
3
216
(种)


答案：216种
例9：如图，用四种不同颜色给图中
A,B,C,D,E,F
六个点涂色，要求每个点涂一种颜色，
且图中每条线段的两个端点涂不 同颜色，则不同的涂色方法有（ ）
A.
288
种 B.
264
种 C.
240
种
D.
168
种
思路：如果用四种颜色涂六个点，则需要有两对不相邻的 点涂相同的
颜色。所以考虑列举出不相邻的两对点。列举的情况如下：

A,C

B,D

，

A,C

B,E

，

A,C

D,F

，

A ,F

B,D

，

A,F

B,E

，

A,F

C,E

，

B,D

C,E

，

B,E
D,F

，

C,E

D,F

共 九组，
4
所以涂色方法共有
9A
4
216

如果用三种颜色涂六个点，则需要有三对不相邻的点涂相同的颜色，列举情况如下：


A,C

B,E

D,F

，

A,F

C,E

B,D

共 两组，所以涂色方法共有
2A
4
3
48

综上所述，总计
264
种
答案：B
例10：有8张卡片分别标有 数字
1,2,3,4,5,6,7,8
，从中取出6张卡片排成3行2列，要求
3行中 仅有中间行的两张卡片上的数字之和为5，则不同的排法共有（ ）
A. 1344种 B. 1248种 C. 1056种 D. 960种
思路：中间行数字和为5只有两种情况，即
1,4
和
2,3
，但这两 组不能同时占据两行，若按
题意思考，以
1,4
占中间行为例，则在安排时既要考虑另 一组
2,3
是否同时被选中，还要考
虑同时被选中时不能呆在同一行，情况比较复杂。 所以考虑间接法，先求出中间和为5的所
有情况，再减去两行和为5的情形
解：先考虑中间和为5的所有情况：
第一步：先将中间行放入
1,4
或2,3
：
C
2

第二步：中间行数字的左右顺序：
A
2

第三步：从剩下6个数字中选择4个，填入到剩余的四个位置并排序：
A
6

124
所以中间和为5的情况总数为
SC
2
A
2
A
4
1440

1
2
4
在考虑两行和为5的情况：
第一步：
1,4
，
2,3
两组中哪组占用中间行：
C
2

第二步：另一组可选择的行数：
C
2

第三步：
1,4，
2,3
在本行中的左右顺序：
A
2
A
2

第四步：从剩下4个数中选取2个填入所剩位置并排序：
A
4

11 222
所以两行和为5的情况：
NC
2
C
2
A
2
A
2
A
4
192

1
1
22
2
从而仅有中间行为5的情况为
SN1248
（种）
答案：B