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

2-3 Counting Hengfeng Wei hfwei@nju.edu.cn March 12,2020 4口·1①，43，t夏，里)Q0 Hengfeng Wei (hfweixinju.edu.cn) 2-3 Counting farch12.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 4口·1①，43，t夏，里)Q0 Hengfeng Wei (hfweixinju.edu.cn) 2-3 Counting farch12.20202/34

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

AN INTRODUCTION TO THE ANALYSIS ALGORITHMS S E CO N DE D I T I O N ROBE食T5ED0 EWICK PHILIPPE FLAJOLET 2 Θ d 4口·1①，43，t夏，里)Q0 Hengfeng Wei (hfweixinju.edu.cn) 2-3 Counting farch12.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 ~ 4口·1①，43，t夏，里)Q0 Hengfeng Wei (hfweixinju.edu.cn) 2-3 Counting farch12.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. 4口·￥①，43，t夏，3)Q0 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 4口·1①，43，t夏，里)Q0 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

Counting Sums Σ 4口·￥①，43，t夏，3)Q0 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

Counting Sums ∑ Binomials 4口·1①，43，t夏，里)Q0 Hengfeng Wei (hfweixinju.edu.cn) 2-3 Counting farch12.20205/34

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

PRELIMINARY 4口·￥①，43，t夏，3)Q0 Hengfeng Wei (hfweixinju.edu.cn) 2-3 Counting March12,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! 4口·1①，43，t夏，里)Q0 Hengfeng Wei (hfweixinju.edu.cn) 2-3 Counting farch12.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 = 1 n¯ m n ! = mn n! Hengfeng Wei (hfwei@nju.edu.cn) 2-3 Counting March 12, 2020 7 / 34