计数原理
7/31/2009 11:28 AM Deren Chen,Zhejiang Univ,1
4、计数原理 /Counting
4.1 基本计数原理
The Basic of Counting
4.2 包含与排斥原理
The Inclusion-Exclusion Principle
4.3 鸽洞原理
The Pigeonhole Principle
计数原理
7/31/2009 11:28 AM Deren Chen,Zhejiang Univ,2
求和规则 /The Sum Rule
If a first task can be done in n ways and a
second task in m ways,and if there these tasks
cannot be done at the same time,then there are
n+m ways to be either task.
|A1? A2| = |A1| + |A2| 其中 A1? A2 =?
计数原理
7/31/2009 11:28 AM Deren Chen,Zhejiang Univ,3
例 3 单循环程序
Example 1
计数原理
7/31/2009 11:28 AM Deren Chen,Zhejiang Univ,4
求和规则的推广
|A1? A2?…?An | = |A1| + |A2| +… + |A n|
其中 A i? A j =?
i?j,i,j =1,2,…,n
计数原理
7/31/2009 11:28 AM Deren Chen,Zhejiang Univ,5
求积规则 /The Product Rule
Suppose that a procedure can be broken down into two
tasks,If there are n ways to do the first task and m ways to
do the second task after the first task has been done,then
there are nm ways to do the procedure.
|A1? A2 | = |A1| |A2|
计数原理
7/31/2009 11:28 AM Deren Chen,Zhejiang Univ,6
How many functions are there from a set
with m elements to one with n elements?
example2
nn…n = n m
计数原理
7/31/2009 11:28 AM Deren Chen,Zhejiang Univ,7
How many one-to-one functions are there
from a set with m elements to one with n
elements?
example3
n(n-1)(n-2)…(n -m+1)
计数原理
7/31/2009 11:28 AM Deren Chen,Zhejiang Univ,8
例 11 多重循环程序
Example 4
计数原理
7/31/2009 11:28 AM Deren Chen,Zhejiang Univ,9
求积规则的推广
|A1? A2?…?An | = |A1| |A2| … |A n|
计数原理
7/31/2009 11:28 AM Deren Chen,Zhejiang Univ,10
4、计数原理 /Counting
4.1 基本计数原理
The Basic of Counting
4.2 包含与排斥原理 /容斥原理
The Inclusion-Exclusion Principle
4.3 鸽洞原理
The Pigeonhole Principle
计数原理
7/31/2009 11:28 AM Deren Chen,Zhejiang Univ,11
讨论范围：有限集 A及其 A的基 |A|
对任意有限集 A1,A2，
(1) |A1? A2|? |A1| + |A2|
(2) |A1?A2|? min(|A1|,|A2| )
(3) |A1 - A2|? |A1| - |A2|
计数原理
7/31/2009 11:28 AM Deren Chen,Zhejiang Univ,12
Theorem
对任意有限集 A1,A2,成立
|A1? A2| = |A1| + |A2| - |A1?A2|
推广,|A1? A2?…?An | =
计数原理
7/31/2009 11:28 AM Deren Chen,Zhejiang Univ,13
EXAMPLE 1
例 1,10个球迷,已知 5个青年,7个男性,3个男青年,问有几个非青年女性球迷？
计数原理
7/31/2009 11:28 AM Deren Chen,Zhejiang Univ,14
EXAMPLE 2
例 2,30户居民,有洗衣机,大屏幕彩电和高级音响的分别有 15,8,6户,有 3户有全部 3大件 。
问至少有几户没有三大件中的任何一件？
计数原理
7/31/2009 11:28 AM Deren Chen,Zhejiang Univ,15
EXAMPLE 3
例 3,1到 250个数中有多少个能被 2,3,5、
7的至少其中之一所整除？
计数原理
7/31/2009 11:28 AM Deren Chen,Zhejiang Univ,16
4、计数原理 /Counting
4.1 基本计数原理
The Basic of Counting
4.2 包含与排斥原理
The Inclusion-Exclusion Principle
4.3 鸽洞原理
The Pigeonhole Principle
计数原理
7/31/2009 11:28 AM Deren Chen,Zhejiang Univ,17
鸽洞原理的出处：
The Pigeons and The Pigeonhole
抽屉原理：
Dirichlet Drawer Principle
计数原理
7/31/2009 11:28 AM Deren Chen,Zhejiang Univ,18
The Pigeonhole Principle
If k+1 or more objects are placed into k boxes,
then there is at least one box containing two or
more of the objects.
对任意有限集 A,B,若 |A|>|B|，则对任意从 A到
B的函数 f，至少存在两个元素 a,b?A且 a?b，使得 f(a)=f(b)
计数原理
7/31/2009 11:28 AM Deren Chen,Zhejiang Univ,19
EXAMPLE 1
例 1,Show that among any n+1 positive
integers not exceeding 2n there must be an
integer that divides one of the other integers.
计数原理
7/31/2009 11:28 AM Deren Chen,Zhejiang Univ,20
The Generalized Pigeonhole Principle
If N objects are placed into k boxes,then
there is at least one box containing at least
N/k?objects.
计数原理
7/31/2009 11:28 AM Deren Chen,Zhejiang Univ,21
EXAMPLE 2
例 2,132个球放入 77个盒子内,盒子排成一行,每盒至少放一个 。 证明无论如何怎样放,
一定存在相邻的某几个盒子内放有 21个球 。
计数原理
7/31/2009 11:28 AM Deren Chen,Zhejiang Univ,22
EXAMPLE 3
例 3,证明在任意 6个人中,要么有 3个人互相认识,要么有 3个人互相不认识 。
计数原理
7/31/2009 11:28 AM Deren Chen,Zhejiang Univ,23
建立小 结
1、加法原理和乘法原理
2、容斥原理,有限集的基的运算
3、鸽洞原理,有限集的基的比较计数原理
7/31/2009 11:28 AM Deren Chen,Zhejiang Univ,24
进一步的思考
1、容斥原理：
有限集的基的运算,有限集的运算
2、鸽洞原理：
有限集的基的比较,函数建立两个集合间的关系
3,应用问题计数原理
7/31/2009 11:28 AM Deren Chen,Zhejiang Univ,25
练 习
pp.242 1,3,33,45
pp.248 12,23