文档文本内容
1
高中数学·竞赛一试·第46 讲
一、计数原理
加法原理:
完成一件事的方法可分成n 个互不相交的类,在第1类到第n 类分别有
1
2
,
,...,
n
m m
m 种方法,
则总共完成这件事有
1
2
...
n
m
m
m
+
+
+
种方法.
应用加法原理的关键在于通过适当的分类,使得每一类都相对易于计数.
乘法原理:
完成一件事的方法有n 个步骤,从第1步到第n 步分别有
1
2
,
,...,
n
m m
m 种方法,则总共完成
这件事有
1
2 ...
n
m m
m
种方法.
应用乘法原理的关键在于通过适当的分步,使得每一步都相对易于计数.
由上可见,加法原理与乘法原理也是化归思想的应用,通过这两个原理以及它们的组合,可以将
一个复杂的组合计数问题分解成若干个便于计数的小问题.
二、常见的排列与组合数
(1) 无重排列与组合
无重排列:从n 个不同元素中任取m 个不同元素排成一列,不同的排列种数称为排列数,记为
m
n
A .
(部分书中记为
m
nP ),由乘法原理得到
!
(
1) ... (
1)
(
)!
m
n
n
A
n
n
n
m
n
m
=
−
−
+
=
−
.
无重组合:从n 个不同元素中任取m 个元素并为一组,不同的组合种数称为组合数,记为
m
n
C
.
其公式为
(
1) ... (
1)
!
!
!
!(
)!
m
m
n
n
A
n
n
n
m
n
C
m
m
m n
m
−
−
+
=
=
=
−
.
本讲概述
第46 讲 计数原理与排列组合
2
高中数学·竞赛一试·第46 讲
(2) 可重排列与组合
可重排列:从n 个不同元素中可重复地任取m 个元素排成一列,不同的排列种数有
m
n
种.
有限个重复元素的全排列:设n 个元素由k 个不同元素
1
2
,
,...,
k
a a
a 组成,分别有
1
2
,
,...,
k
n n
n
个(
1
2
...
k
n
n
n
n
+
+
+
=
),那么这n 个元素的全排列数为
1
2
!
!
!...
!
k
n
n n
n
.
可重组合:从n 个不同元素中,任意可重复地选取m 个元素,称为n 个不同元素中取m 个元素的
可重组合,其种数为
1
m
n m
C +
−.
多元线性不定方程的正整数解个数:方程
1
2
...
k
x
x
x
n
+
+
+
=
(,k n 为正整数)的正整数解个数
为
1
1
k
n
C −
−.
(3) 圆排列
在n 个不同元素中,每次取出m 个元素排在一个圆环上,叫做一个圆排列(或叫环状排列).
圆排列有三个特点:①无头无尾;②按照同一方向转换后仍是同一排列;③两个圆排列只有在元
素不同或者元素虽然相同,但元素之间的顺序不同,才是不同的圆排列.
在n 个元素中,每次取出m 个不同的元素进行圆排列,圆排列数为
m
n
A
m
.
三、容斥原理
设
1
2
,
,...,
n
A A
A 为有限集合,用|
|
iA 表示集合
iA 中的元素个数,那么
1
2
1
2
1
1
1
|
...
|
|
|
|
|
|
| ... ( 1) |
...
|
n
n
n
i
i
j
i
j
k
n
i
i
j n
i
j k n
A
A
A
A
A
A
A
A
A
A
A
A
=
=
−
+
−
+ −
联赛一试的填空题中出现的计数问题有接近一半的问题不需要用到很高深的技巧,而是直接利用
最基本的加法、乘法原理,以及枚举方法来计数. 从往年的联赛试题来看,枚举法解决计数问题是最
主要的题型之一,其难点在于做到“不重不漏”,这是加法原理的一个简单的应用. 枚举过程中,采用
恰当的分类、分步形式,往往会收到化难为易的效果.
3
高中数学·竞赛一试·第46 讲
【例1】 (1) 等腰三角形的三边均为正整数,它们周长不大于10 ,这样不同的三角形的种数为 ;
(2) 有两排座位,前排11个座位,后排12 个座位,现安排2 人就座,规定前排中间的3 个座
位不能坐,并且这2 人不左右相邻,那么不同排法的种数是 .
【例2】 (1)设三位数n
abc
=
,若以, ,
a b c 为三条边的长可以构成一个等腰(含等边)三角形,则
这样的三位数n 有 个.
(2)有长为
(
)
3
0
1006
n
n
≤≤
的线段各两条.则由2014 条线段能构成__________个不同形状
的三角形(全等视为相同)
例题精讲
4
高中数学·竞赛一试·第46 讲
【例3】 将2 个a 和2 个b 共4 个字母填在4 4
方格表内,每个小方格内至多填1个字母,若使相同字
母既不同行也不同列,则不同的填法共有 种.(用数字作答)
【例4】 从给定的6 种不同颜色中选用若干种颜色,将一个正方体的六个面染色,每面恰染一种颜色,
每两个具有公共棱的面染成不同的颜色. 那么不同的染色方法共有 种.
(注:如果我们对两个相同的正方体染色后,可以通过适当的翻转,使得两个正方体的上、
下、左、右、前、后六个对应面的染色都相同,那么我们就说这两个正方体的染色方案相同.)
5
高中数学·竞赛一试·第46 讲
【例5】 年度星际数学竞赛的委员会有5 名火星人,5 名金星人和5 名地球人.会议上,委员们坐在一
张圆桌上,椅子顺时针编号为1到15 .委员会规定,1号座位必须坐火星人,15 号座位必须坐
地球人.另外,地球人不能坐在火星人紧邻的左侧,火星人不能坐在金星人紧邻的左侧,金
星人不能坐在地球人紧邻的左侧.委员会的就座方法数目为
3
(5!)
N
.求N .
【例6】 (1)由数字1,2 和3 组成的n 位数,要求n 位数中1,2 和3 的每一个至少出现一次。求所
有这种n 位数的个数。
(2)在所有的n 位数中,包含数字3、8、9 但不包含数字0、4 的数有多少个?
6
高中数学·竞赛一试·第46 讲
【例7】 将24 个志愿者名额分配给3 个学校,则每校至少有一个名额且各校名额互不相同的分配方法
共有 种.
【例8】 在世界杯足球赛前,F 国教练为了考察
1
2
7
,
,...,
A A
A 这七名队员,准备让他们在三场训练比赛
(每场90 分钟)都上场,假设在比赛的任何时刻,这些队员中有且仅有一人在场上,并且
1
2
3
4
,
,
,
A A A A 每人上场的总时间(以分钟为单位)均被7 整除,
5
6
7
,
,
A A A 每人上场的总时间
(以分钟为单位)均被13整除,如果每场换人次数不限,那么按每名队员上场的总时间计算,
共有多少种不同的情况.