(完整版)计数原理、排列组合题型与方法
萌到你眼炸
713次浏览
2021年01月28日 06:05
最佳经验
本文由作者推荐
快乐六一作文-职业素质培养
实用标准文案
计数原理、排列组合题型与方法
☆基本思路：大的方向分类，类中可能有步或类
例
1
：架子上有不 同的
2
个红球，不同的
3
个白球，不同的
4
个黑球
.
若从中取
2
个不同
色的球，则取法种数为
________.
解：先分类、再分步，共有取法
2
×
3
＋
2
×
4
＋
3
×
4
＝
26
种
.
故填
26
.
☆基本思路：大的方向分步，步中可能有类或步
例
1
：
如 图所示，
使电路接通，
开关不同的开闭方式有
( )
A
．
11
种
C
．
21
种
B
．
20
种
D
．
12
种
解：分两步，第一部分接通，则可 能有一个接通或者两个都接通，有
3
种可能；第二部
分接通，
则可能恰有一个 接通或恰有两个接通或者都接通，
有
7
种可能。
从而总共有
3
7=21
种方式。
☆基本思路：排除法间接求解
例
1
：
(
2013
·济南模拟
)
电路如图 所示，
在
A
，
B
间有四个开关，
若发现
A
，
B
之间电路不通，则这四个开关打开或闭合的方式有
(
)
A.3
种
B.8
种
C.13
种
D.16
种
解：各 个开关打开或闭合有
2
种情形，故四个开关共有
2
4
种可能，其中能 使电路通的情
形有：
1
，
4
都闭合且
2
和
3
中至少有一个闭合，共有
3
种可能，故开关打开或闭合的不同情
形共有2
4
－
3
＝
13(
种
)
.
故 选
C.
☆剔除重复元素
例
1
：(
2013
·四川
)
从
1
，
3
，5
，
7
，
9
这五个数中，每次取出两个不同的数分别记为
a
，
b
，共可得到
lg
a
－
lg
b的不同值的个数是
(
)
A.9 B.10 C.18 D.20
a
1
3
3
9
解：
lg
a
－
lg
b
＝
lg
，而
＝
，
＝
， 故所求为
A
2
5
－
2
＝
18
个，故选C.
b
3
9
1
3
☆投信问题
例
1
：将
5
封信投入
3个邮筒，不同的投法共有
(
)
A.5
3
种
B.3
5
种
C.3
种
D.15
种
解：第
1
封信，可以投 入第
1
个邮筒，可以投入第
2
个邮筒，也可以投入第
3
个邮 筒，
共有
3
种投法；同理，后面的
4
封信也都各有
3
种投法
.
所以，
5
封信投入
3
个邮筒，不同的
文 档
实用标准文案
投法共有
3
5
种
.
故选
B.
例
2
：
有六名同学报名参加三个智力竞赛项目，
在下列情况下各有多少种不同的 报名方法？
(
不一定六名同学都能参加
)
(1)
每人恰好参加一项，每项人数不限；
(2)
每项限报一人，且每人至多参加一项；
(3)
每项限报一人，但每人参加的项目不限．
解
(1 )
每人都可以从这三个比赛项目中选报一项，各有
3
种不同选法，由分步乘法计数原理，知共有选法
3
6
＝
729(
种
)
．
(2)
每项限报一人，且每人至多参加一项，因此可由项目选人，第一个项目有
6
种选法，
第二个项目有
5
种选法，第三个项目只有
4
种选 法，由分步乘法计数原理，得共有报名方
法
6
×
5
×
4＝
120(
种
)
．
(3)
由于每人参加的项 目不限，因此每一个项目都可以从这六人中选出一人参赛，由分步
乘法计数原理，得共有不同的报名方法
6
3
＝
216(
种
)
．
☆数字排列问题
例
1
：用数字
0
，< br>1
，
2
，
3
，
4
，
5
组成 没有重复数字的四位数
.
(1)
可组成多少个不同的四位数？
(2)
可组成多少个不同的四位偶数？
3
4
3
解 ：
(1)
直接法：
A
1
5
A
5
＝
300
；
间接法：
A
6
－
A
5＝
300
.
(2)
由题意知四位数的个位上必须是偶数，同时 暗含了千位不能是
0
，因此该四位数的个
位和千位是“特殊位置”
，应优先处 理；另一方面，
0
既是偶数，又不能排在千位，属“特殊
元素”
，应重点对待
.
解法一：
(
直接法
)0
在个位的四位偶数有< br>A
3
5
个；
0
不在个位时，先从
2
，
4
中选一个放在
1
2
个位，再从余下的四个数
(
不包括< br>0)
中选一个放在千位，应有
A
1
2
A
4
A
4
个
.
1
1
2
综上所述，共有
A
3
5
＋
A
2
A
4
A
4
＝
156(
个
)
.
3
解法二：
(
间接法
)
从这六个数字中任取四个数字组成最后一位是偶数的排法，有
A
1
3
A
5
个，
2
1
3
1
2
其中千位是
0
的有
A
1
2
A
4
个，故适合 题意的数有
A
3
A
5
－
A
2
A
4
＝
156(
个
)
.
点拨：
本例是有限制条件的排列问题，先满足特殊元素或特殊位置的要求，再考虑其他元素或
位置，同 时注意题中隐含条件
0
不能在首位
.
例
2
：< br>用数字
2
，
3
组成四位数，
且数字
2
，3
至少都出现一次，
这样的四位数共有
________
个
(
用数字作答
)
．
解析
数字
2
，
3
至少都出现一次，包括以下情况：
文档
实用标准文案
“
2
”出现
1次，
“
3
”出现
3
次，共可组成
C
1
4
＝
4(
个
)
四位数．
“
2
” 出现
2
次，
“
3
”出现
2
次，共可组成
C
2
4
＝
6(
个
)
四位数．
“< br>2
”出现
3
次，
“
3
”出现
1
次， 共可组成
C
3
4
＝
4(
个
)
四位数．
综上所述，共可组成
14
个这样的四位数．
例< br>3
：
(
2014
·武汉模拟
)
如果正整数
M
的各位数字均不为
4
，且各位数字之和为
6
，则称
M
为“幸运数”
，则三位正整数中的“幸运数”共有
____________
个.
解：不含
4
，且和为
6
的三个自然数可能为
(1
，
2
，
3)
，
(1
，
5
，
0)
，
(2
，
2
，
2)
，
(3< br>，
3
，
2
2
0)
，
(6
，
0
，
0)
.
因此三位正整数中的“幸运数”有
A
3
3
＋
2
A
2
＋
1
＋
A
2
＋
1
＝
14(
个
)
.
故填
14
.
☆错位排列
例
1
：将数字
1
，
2
，
3
，
4
填入标号为
1
，
2
，
3
，
4
的四个方格中，每格填一个数，则每个
方格的标 号与所填数字均不相同的填法有
________
种．
解析
编号为
1
的方格内填数字
2
，共有
3
种不同填法；编号 为
1
的方格内填数字
3
，共
有
3
种不同填法；编号 为
1
的方格内填数字
4
，共有
3
种不同填法．于是由分类加 法计数
原理，得共有
3
＋
3
＋
3
＝
9(< br>种
)
不同的填法．
例
2
：
(
20 13
·成都模拟
)
用
6
个字母
A
，
B，
C
，
a
，
b
，
c
编拟某种信号程序
(
大小写有区
别
)
.
把这
6
个字母全部排 到如图所示的表格中，每个字母必须使用且只使用一次，不同的排
列方式表示不同的信号，
如果 恰有一对字母
(
同一个字母的大小写
)
排到同一列的上下格位置，
那 么称此信号为“微错号”
，则不同的“微错号”总个数为
(
)
A.432
B.288
C.96 D.48
解：根据题意 ，分
3
步进行：①先确定排到同一列的上下格位置的一对字母，有
C
1
3
＝
3
2
种情况，将其放进表格中，有
C
1
3< br>＝
3
种情况，考虑这一对字母的顺序，有
A
2
＝
2< br>种不同顺序；
②再分析第二对字母，其不能排到同一列的上下格位置，假设①选定的一对大小写字 母为
A
文档
实用标准文案
和
a
，则分 析
B
与
b
：
B
有
4
种情况，
b< br>的可选位置有
2
个；③最后一对字母放入最后两个位
置，有
A
2
2
＝
2
种放法
.
则共有
3
×
3
×
2
×
4
×
2
×
2
＝
2 88
个“微错号”
.
故选
B.
☆选派分配问题
例
1
：
2010< br>年广州亚运会组委会要从小张、小赵、小李、小罗、小王五名志愿者中选派
四人分别从事翻译、导 游、礼仪、司机四项不同工作，若其中小张和小赵只能从事前两项工
作，其余三人均能从事这四项工作， 则不同的选派方案共有
( )
A
．
36
种
B
．
12
种
C
．
18
种
D
．
48
种
解：根据题意分
2
种情况讨 论，①若小张或小赵入选，则有选法
C
2
1
C
2
1
A
3
3
=24
；
②若小张、小赵都入选，则有选法
A
2
2
A
3
2
=12
，共有选法
12+ 24=36
种，故选
A
．
例
2
：
201 5
年开春之际，六中食堂的伙食在百升老师的带领下进行了全面升级．某日
5
名同学去 食堂就餐，有米饭，花卷，包子和面条四种主食．每种主食均至少有一名同学选择
且每人只能选择其中一 种．花卷数量不足仅够一人食用，甲同学因肠胃不好不能吃米饭，则
不同的食物搭配方案种数为（
）
A
．
96 B
．
120 C
．
132 D
．
240
解 ：分类讨论：甲选花卷，则有
2
人选同一种主食，方法为
方法为
=2
，共有方法
18
×
2=36
种；
=18
，剩下< br>2
人选其余主食，
甲不选花卷，其余
4
人中
1
人选花 卷，方法为
4
种，甲包子或面条，方法为
2
种，其余
3
人，
若有
1
人选甲选的主食，剩下
2
人选其余主食，方法为
3< br>法为
=6
，共有
4
×
2
×（
6+6
）
=96
种，
=6
；若没有人选甲选的主食，方
故共有< br>36+96=132
种，故选：
C
．
☆分堆与分配问题
例
1
：现有
6
本不同的书：
(1)
甲、乙、丙三人每人两本，有多少种不同的分配方法？
(2)
分成三堆，每堆
2
本，有多少种分堆方法？
文档
实用标准文案
(3)
分成三堆，一堆
1< br>本，一堆
2
本，一堆
3
本，有多少种不同的分堆方法？
(4)
分给甲、乙、丙三人，一人
1
本，一人
2
本，一人
3
本，有多少种不同的分配方法？
(5)
甲、乙、丙三人中，一人分4
本，另两人每人分
1
本，有多少种不同的分配方法？
解：< br>(1)
在
6
本书中，先取
2
本给甲，再从剩下的
4< br>本书中取
2
本给乙，最后两本给丙，
2
2
共有
C2
6
C
4
C
2
＝
90(
种
)
分配方法；
2
C
2
6
C
4
(2 )6
本书平均分成
3
堆，用上述分法重了
A
倍，故共有
3< br>＝
15(
种
)
分堆方法；
A
3
3
3
(3)
从
6
本书中，先取
1
本作为一堆，再在剩 下的
5
本中取
2
本作为一堆，最后
3
本作为
23
一堆，共有
C
1
6
C
5
C
3
＝
60(
种
)
分堆方法；
2
3
3(4)
在
(3)
的分堆中，甲、乙、丙三人任取一堆，共有
C
1
6
C
5
C
3
A
3
＝
360(种
)
分配方法
.
1
1
C
4
6
C
2
C
1
(5)
先分堆、再分配，共有
2
·
A
3
3
＝
90(
种
)
分配方法
.
A
2
点拨：
平均分配给不同人的分法等 于平均分堆的分法乘以堆数的全排列
.
分堆到位相当于分堆
平均分堆到指定位置
后各堆再全排列，平均分堆不到指定位置，其分法数为：
.
对于分堆与分
堆数的阶乘
配问题应注意：①处理分配问题要注意先分堆再分配
.
②被分配的元素是不同的
(
像“名额”
等则是相同元素，不适用
)
，位置也应是不同的
(< br>如不同的“盒子”
)
.
③分堆时要注意是否均
匀
.
如
6
分成
(2
，
2
，
2)
为均匀分组，分成
(1
，
2
，
3)
为非均匀分组，分成
(4
，
1
，
1)
为部分均
匀分组
.
例2
：
4
个不同的球，
4
个不同的盒子，把球全部放入盒内
.
(1)
恰有
1
个盒不放球，共有多少种放法？
(2)
恰有
2
个盒不放球，共有多少种放法？
解：
(1)
为保证“恰有
1
个盒不放球”
，先从
4
个盒子中任 意取出去一个，问题转化为“
4
个球，
3
个盒子，每个盒子都要放入球，共有 多少种放法？”即把
4
个球分成
2
，
1
，
1
的三
1
1
C
2
4
C
2
C
1组，然后进行全排列，共有
C
·
2
·
A
3
3< br>＝
144(
种
)
放法
.
A
2(2)
确定
2
个空盒有
C
2
4
种方法
.
4
个球放进
2
个盒子可分成
(3
，
1)
，
(2
，
2)
两类，第一类
2
C
2
4C
2
3
1
2
为有序不均匀分组，有
C
4
C
1
A
2
种放法；第二类为有序均匀分组，有
2
·
A
2
2
种放法，故共有
A
2
2
2
3
1
2
C
4
C
2
2
C
4
C
1
A
2
＋
2
·
A2
C
2
4
＝
84(
种
)
.
A
2
1
4
☆相邻捆绑，不邻插空
例
1
：
3
名女生和
5
名男生排成一排
(1)
如果女生全排在一起，有多少种不同排法？
(2)
如果女生都不相邻，有多少种排法？
(3)
如果女生不站两端，有多少种排法？
(4)
其中甲必须排在 乙前面
(
可不邻
)
，有多少种排法？
文档
实用标准文案
(5)
其中甲不站左端，乙不站右端，有多少种排法？
解
(1)(
捆绑法
)
由于女生排在一起，可把她们看成一个整体，这样同五个男生合在 一起
3
有
6
个元素，排成一排有
A
6
6
种 排法，而其中每一种排法中，三个女生间又有
A
3
种排法，因
3
此共 有
A
6
6
·
A
3
＝
4 320(
种
)
不同排法．
(2)(
插空法
)先排
5
个男生，
有
A
5
这
5
个男生之 间和两端有
6
个位置，
从中选取
3
5
种排法，
5< br>3
个位置排女生，有
A
3
6
种排法，因此共有
A5
·
A
6
＝
14 400(
种
)
不同排法．
(3)
法一
(
位置分析法
)
因为两端不排女生，只能从< br>5
个男生中选
2
人排列，有
A
2
5
种排法，
2
6
剩余的位置没有特殊要求，有
A
6
6
种排法， 因此共有
A
5
·
A
6
＝
14 400(
种
)
不同排法．
法二
(
元素分析法
)
从中间
6
个位置选
3
个安排女生，有
A
3
6
种排法，其余位置无限制，有
3< br>5
A
5
5
种排法，因此共有
A
6
·
A
5
＝
14 400(
种
)
不同排法．
1
(4)8
名学生的所有排列共
A
8
8
种，其中甲在乙前面 与乙在甲前面的各占其中
，∴符合要求
2
1
8
的排法种数为
A
8
＝
20 160(
种
)
．
2
(5)
甲、乙为特殊元素，左、右两边为特殊位置．
法一
(
特殊元素法
)
甲在最右边时，其他的可全排，有
A
7
7
种；甲不在最右边时，可从余下
6
个位置中任选一个，有
A
6
种．而乙可排在除去最右边位置后剩余的
6
个中的任一个上，
1
1
6
有
A
1
6
种，其余人全排列，共有
A
6
·
A
6
·
A
6
种．
1
1
6
由分类加法计数原理，共有
A
7
7
＋A
6
·
A
6
·
A
6
＝
30 960(
种
)
．
7
法二
(
特殊位置法
)
先排最左边，除去甲外，有
A
1
7
种，余下
7
个位置全排，有
A
7
种，但应
6
1
7
1
6
剔除乙在最右边时的排法
A< br>1
6
·
A
6
种，因此共有
A
7
·< br>A
7
－
A
6
·
A
6
＝
30 960(
种
)
．
7
法三
(
间接法
)
8
个人全排，共
A< br>8
8
种，其中，不合条件的有甲在最左边时，有
A
7
种，乙在
6
最右边时，有
A
7
7
种，其中都包含了甲在最左边，同时 乙在最右边的情形，有
A
6
种．因此共
7
6
有
A< br>8
8
－
2A
7
＋
A
6
＝
3 0 960(
种
)
．
1
规律方法
(1 )
对于有限制条件的排列问题，分析问题时有位置分析法、元素分析法，在
实际进行排列时一般 采用特殊元素优先原则，
即先安排有限制条件的元素或有限制条件的
位置，对于分类过多的问题 可以采用间接法．
(2)
对相邻问题采用捆绑法、不相邻问题采用插空法、定序问题 采用倍缩法是解决有限制
条件的排列问题的常用方法．
文档
实用标准文案
例
2
：有
5
盆菊花，其中黄菊花< br>2
盆、白菊花
2
盆、红菊花
1
盆，现把它们摆放成一排，要求
2
盆黄菊花必须相邻，
2
盆白菊花不能相邻，则这
5
盆花不同的摆放种数是
( )
A
．
12
B
．
24
C
．
36
D
．
48
解：由题意，第一步将黄
1
与黄
2
绑定，两者的站法有
2< br>种，第二步将此两菊花看作一
个整体，与除白
1
，白
2
之外的 一菊花看作两个元素做一个全排列有
A
2
2
种站法，此时隔开了
三个 空，第三步将白
1
，白
2
两菊花插入三个空，排法种数为
A
3
2
，则不同的排法种数为
2
×
A
2
2
×
A
3
2
=2
×
2
×
6=24
．故 选
B
．
例
3
：编号为
1
、< br>2
、
3
、
4
、
5
、
6
、< br>7
的七盏路灯，晚
上用时只亮三盏灯，且任意两盏亮
灯不相邻，则不同的开灯方 案有
(
)
A
．
60
种
B
．
8
种
C
．
20
种
D
．
10
种
解：四盏不亮灯有
5
个空位，再安排
3
亮灯，总有
C
5
3
10
种方案。
例
4
：
某班元旦晚会已经排好
4
个节目的顺序，
先临时要增加
2
个节目进来，
要求不打乱
原来节目的顺序，则晚会节目的安排方案有
______种。
解：原来
4
个节目有
5
个空位，先安排第一个节 目，有
5
种方案；这时有
6
个空位，再
安排第二个节目，有
6
种方案，所以总共有
30
种方案。
☆最短路走法问题
例
1
：
A
,
B< br>两地街道如图所示，某人要从
A
地前往
B
地，则路程最
短的走 法有
种（用数字作答）
．
解：< br>3
右
2
上，
共
5
步，
从中选
3步来右走余下则上走，
走法有
C
5
3
10
种 。
☆无区别元素分配的隔板法
例
1.
求方程
X+Y+Z=10
的正整数解的个数。
解：将
10
个球排成一排，球与球之间形成
9
个空隙，将两个隔板插入这些空隙中（每空
至多插一块隔板）
，
规定由隔板分成的左、
中、
右三部分的球数分别为
x
、
y
、
z
之值
（如下图）
。
则隔法与 解的个数之间建立了一一对立关系，故解的个数为
C
9
2
=36
（个 ）
。
○
○
○∣○
○
○∣○
○
○
○
文档
实用标准文案
例
2
：求方程
X+Y+Z=10
的非负整数解的个数。
< br>解：
注意到
x
、
y
、
z
可以为零，
故上题解法中的限定
“每空至多插一块隔板”
就不成立了，
怎么办呢？只要添加三个球 ，给
x
、
y
、
z
各一个球。这样原问题就转化为求
X+Y+Z=13
的正整
数解的个数了，故解的个数为
C
12
2=66
（个）
。
例
3
：将
20
个相 同的小球放入编号分别为
1
，
2
，
3
，
4
的四个盒子中，要求每个盒子中
的球数不少于它的编号数，求放法总数。
解法
1
：先在编号
1
，
2
，
3
，
4
的四个盒子内分别放
0
，
1
，
2
，
3
个球 ，剩下
14
个球，有
1
种方法；再把剩下的球分成
4
组，每 组至少
1
个，由例
1
知方法有
C
13
3
= 286
（种）
。
解法
2
：第一步先在编号
1，
2
，
3
，
4
的四个盒子内分别放
1
，
2
，
3
，
4
个球，剩下
10
个
球，有
1
种方法；第二步把剩下的
10
个相同的球放入编号为
1，
2
，
3
，
4
的盒子里，由例
2
知方 法有
C
13
3
=286
（种）
。
☆涂色问题
例
1
：有一个圆被两相交弦分成四块，现用
5
种不同的颜料给这四块涂色，要求相邻的
两块颜色不同，每块只涂一种颜色，共有多少种涂色方 法？
解：如图，分别用
A
，
B
，
C
，< br>D
记这四个部分，
A
与
C
，
B
与
D
不相邻，因此，它们可以
同色，也可以不同色
.
首先分两类，即
A< br>，
C
涂相同颜色和
A
，
C
涂不同颜色：
类型一，分三步：第一步，给
A
，
C
涂相同的颜色，有< br>5
种涂法；第二步，给
B
涂色有
4
种涂法；第三步，给
D
涂色，由于
D
与
B
可以涂相同的颜色，所以有
4
种涂法
.
由分步计数原
理知，共有
5
×
4
×4
＝
80
种不同的涂法
.
类型二，分四步：第一步， 给
A
涂色，有
5
种涂法；第二步，给
C
涂色，有
4
种涂法；
第三步，给
B
涂色有
3
种涂法；第四步，给
D
涂色有
3
种涂法
.
由分步计数原理知，共有
5
×
4
×
3
×
3
＝
180
种不同的涂法.
综上，由分类计数原理可知，共有
80
＋
180
＝
260
种不同的涂法
.
点拨：
本题 也可以在分四步的基础上再分类来完成：
A
有
5
种涂法，
B
有
4
种涂法，若
C
与
A
相
同，则
D
有
4
种涂法，若
C
与
A
不同，则
C
有< br>3
种涂法，且
D
有
3
种涂法，故有
5
×4
×
(4
＋
3
×
3)
＝
260
种涂法
.
涂色问题多以平面、空间为背景，涂色对象以平面区域居多，也有以点
或线 为对象的涂色问题
.
此类问题往往需要多次分类、
分步
(
也有用穷举 法解决的题目
)
，
常用
分类依据有：①所涂颜色种类
(
如本 题，可依用
4
种、
3
种、
2
种色来分类
)
；②可涂同色的区
文档