南京大学：《计算机问题求解》课程教学资源（课件讲稿）组合与计数 Counting（简版）

2-3 Counting Hengfeng Wei hfwei@nju.edu.cn March 12,2020 L Hengfeng Wei (hfweixinju.edu.cn) 2-3 Counting March12,20201/34

2-3 Counting Hengfeng Wei hfwei@nju.edu.cn March 12, 2020 Hengfeng Wei (hfwei@nju.edu.cn) 2-3 Counting March 12, 2020 1 / 34

AN INTRODUCTION TO THE ANALYSIS ALGORITHMS S E CO N DE D I T I O N ROBE食T5ED0 EWICK PHILIPPE FLAJOLET 2 Θ 0 以 Hengfeng Wei (hfweixinju.edu.cn) 2-3 Counting March12,20202/34

O Ω Θ o ω Hengfeng Wei (hfwei@nju.edu.cn) 2-3 Counting March 12, 2020 2 / 34

"People who analyze algorithms have double happiness..." Donald E.Knuth (1938~) Hengfeng Wei (hfweixinju.edu.cn) 2-3 Counting March12,20203/34

“People who analyze algorithms have double happiness . . .” Donald E. Knuth (1938 ∼) Hengfeng Wei (hfwei@nju.edu.cn) 2-3 Counting March 12, 2020 3 / 34

Unfortunately,you have to master some mathematics. Hengfeng Wei (hfweixinju.edu.cn) 2-3 Counting March12,20204/34

Unfortunately, you have to master some mathematics. Hengfeng Wei (hfwei@nju.edu.cn) 2-3 Counting March 12, 2020 4 / 34

Counting Sums ∑ Binomials () Hengfeng Wei (hfweixinju.edu.cn) 2-3 Counting March12,20205/34

Counting Sums P Binomials ￾n k
Hengfeng Wei (hfwei@nju.edu.cn) 2-3 Counting March 12, 2020 5 / 34

PRELIMINARY Hengfeng Wei (hfweiinju.edu.cn) 2-3 Counting arch12,20206/34

Hengfeng Wei (hfwei@nju.edu.cn) 2-3 Counting March 12, 2020 6 / 34

Falling and Rising Factorials m2=mn=m(m-1)m-2)(m-n+1）=m-m m! m元=mm=m(m+1)(m+2）)…(m+n-1) n!=n2=1n m n n! Hengfeng Wei (hfweixinju.edu.cn) 2-3 Counting March12,20207/34

Falling and Rising Factorials mn = (m)n = m(m − 1)(m − 2)· · ·(m − n + 1) = m! (m − n)! mn¯ = m(n) = m(m + 1)(m + 2)· · ·(m + n − 1) n! = n n = 1n¯ m n ! = mn n! Hengfeng Wei (hfwei@nju.edu.cn) 2-3 Counting March 12, 2020 7 / 34

Iverson Bracket [P] 1 if P is true; 10 otherwise n≤网= ∫1， ifn≤m ifn>m Kenneth Eugene Iverson (1920~2004) Hengfeng Wei (hfweignju.edu.cn) 2-3 Counting March12,20208/34

Iverson Bracket Kenneth Eugene Iverson (1920 ∼ 2004) [P] = ( 1, if P is true; 0, otherwise [n ≤ m] = ( 1, if n ≤ m; 0, if n > m Hengfeng Wei (hfwei@nju.edu.cn) 2-3 Counting March 12, 2020 8 / 34

Theorem(Sum Principle) SnT=0→ISUT=S1+1Tl Theorem (Product Principle) IS×T=IS×T Holds for finite sets S and T. Hengfeng Wei (hfweixinju.edu.cn) 2-3 Counting March12,20209/34

Theorem (Sum Principle) S ∩ T = ∅ =⇒ |S ∪ T| = |S| + |T| Theorem (Product Principle) |S × T| = |S| × |T| Holds for finite sets S and T. Hengfeng Wei (hfwei@nju.edu.cn) 2-3 Counting March 12, 2020 9 / 34

先学习下加法，1+1，就是 +- 所以1+1=2，这很好理解 那我们趁热打铁学习下一个重要公式吧： EwEw(-1)det(w)w(ex+) ePΠa>o(1-e-a) Hengfeng Wei (hfweixinju.edu.cn) 2-3 Counting March12,202010/34

Hengfeng Wei (hfwei@nju.edu.cn) 2-3 Counting March 12, 2020 10 / 34