计数原理.ppt

4、计数原理/Counting
基本计数原理
The Basic of Counting
包含与排斥原理
The Inclusion-Exclusion Principle
鸽洞原理
The Pigeonhole Principle
11/11/2017
1
Deren Chen, Zhejiang Univ.
求和规则/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 = 
11/11/2017
2
Deren Chen, Zhejiang Univ.
例3 单循环程序
Example 1
11/11/2017
3
Deren Chen, Zhejiang Univ.
求和规则的推广
|A1  A2 … An | = |A1| + |A2| +…+ |An|
其中A i  A j = 
ij, i,j =1,2,…,n
11/11/2017
4
Deren Chen, Zhejiang Univ.
求积规则/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|
11/11/2017
5
Deren Chen, Zhejiang Univ.
How many functions are there from a set with m elements to one with n elements ?
example2
nn…n = nm
11/11/2017
6
Deren Chen, Zhejiang Univ.
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)
11/11/2017
7
Deren Chen, Zhejiang Univ.
例11 多重循环程序
Example 4
11/11/2017
8
Deren Chen, Zhejiang Univ.
求积规则的推广
|A1  A2 … An | = |A1| |A2| …|An|
11/11/2017
9
Deren Chen, Zhejiang Univ.
4、计数原理/Counting
基本计数原理
The Basic of Counting
包含与排斥原理/容斥原理
The Inclusion-Exclusion Principle
鸽洞原理
The Pigeonhole Principle
11/11/2017
10
Deren Chen, Zhejiang Univ.