浙江大学：《离散数学》课程教学资源（PPT课件讲稿）第四章 计数原理（4.1-4.2-4.3）

计数 4、计数原理 Counting 41基本计数原理 he Basic of Counting 42包含与排斥原理 The Inclusion-Exclusion Principle 43鸽洞原理 The Pigeonhole Principl 2/24/202111:38PM Deren Chen, Zhejiang UniV

计数原理 2/24/2021 11:38 PM Deren Chen, Zhejiang Univ. 1 4、计数原理/Counting 4.1 基本计数原理 The Basic of Counting 4.2 包含与排斥原理 The Inclusion-Exclusion Principle 4.3 鸽洞原理 The Pigeonhole Principle

计数原廷 求和规则/ he 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. 1A1∪A2|=1A1+A2其中A1A2= 2/24/202111:38PM Deren Chen, Zhejiang UniV 2

计数原理 2/24/2021 11:38 PM 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 = 

Example 1 计数原廷 例3单循环程序 2/24/202111:38PM Deren Chen, Zhejiang UniV 3

计数原理 2/24/2021 11:38 PM Deren Chen, Zhejiang Univ. 3 例3 单循环程序 Example 1

计数原廷 求和规则的推广 1A1∪A2U.∪An=|4A1+|A2+..+An 其中A0A;=团 2/24/202111:38PM Deren Chen, Zhejiang UniV

计数原理 2/24/2021 11:38 PM Deren Chen, Zhejiang Univ. 4 求和规则的推广 |A1  A2  … An | = |A1 | + |A2 | +… + |An | 其中A i  A j =  ij, i,j =1,2,…,n

计数原廷 求积规则/ he 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 1×A2|=A1 2/24/202111:38PM Deren Chen, Zhejiang UniV

计数原理 2/24/2021 11:38 PM 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 |

example2 计数原廷 How many functions are there from a set with m elements to one with n elements nn。。n=nm 2/24/202111:38PM Deren Chen, Zhejiang UniV

计数原理 2/24/2021 11:38 PM Deren Chen, Zhejiang Univ. 6 How many functions are there from a set with m elements to one with n elements ? example2 nn…n = nm

example3 计数原廷 How many one-to-one functions are there firom a set with m elements to one with n elements n(n-1)(n-2)(n-m+1) 2/24/202111:38PM Deren Chen, Zhejiang UniV

计数原理 2/24/2021 11:38 PM 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)

Example 4 计数原廷 例11多重循环程序 2/24/202111:38PM Deren Chen, Zhejiang UniV

计数原理 2/24/2021 11:38 PM Deren Chen, Zhejiang Univ. 8 例11 多重循环程序 Example 4

计数原廷 求积规则的推广 1A1×A2×,×An=|A1A2|∴|An 2/24/202111:38PM Deren Chen, Zhejiang UniV

计数原理 2/24/2021 11:38 PM Deren Chen, Zhejiang Univ. 9 求积规则的推广 |A1  A2  … An | = |A1 | |A2 | … |An |

计数 4、计数原理 Counting 41基本计数原理 The Basic of Counting 42包含与排斥原理/容斥原理 The Inclusion-Exclusion Principle 43鸽洞原理 The Pigeonhole Principl 2/24/202111:38PM Deren Chen, Zhejiang UniV

计数原理 2/24/2021 11:38 PM Deren Chen, Zhejiang Univ. 10 4、计数原理/Counting 4.1 基本计数原理 The Basic of Counting 4.2 包含与排斥原理/容斥原理 The Inclusion-Exclusion Principle 4.3 鸽洞原理 The Pigeonhole Principle