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

2-3 Counting Jun Ma majun@nju.edu.cn March 9,2022 4口·￥①，4三，t更，里)Q0 Jun Ma (majunainju.edu.cn) 2-3 Counting March 9.2022 1/35

2-3 Counting Jun Ma majun@nju.edu.cn March 9, 2022 Jun Ma (majun@nju.edu.cn) 2-3 Counting March 9, 2022 1 / 35

AN INTRODUCTION TO THE ANALYSIS ALGORITHMS S E CO N DE D I T I O N ROBERT SEDOEWICK PHILIPPE FLAJOLET 4口·￥①，4三，t更，里)Q0 Jun Ma (majunainju.edu.cn) 2-3 Counting March 9.2022 2/35

O Ω Θ o ω Jun Ma (majun@nju.edu.cn) 2-3 Counting March 9, 2022 2 / 35

AN INTRODUCTION TO THE ANALYSIS ALGORITHMS S E CO N DE D I T I O N ROBERT SEDOEWICK PHILIPPE FLAJOLET 2 Θ 0 d 4口·￥①，4三，t更，里)Q0 Jun Ma (majunainju.edu.cn) 2-3 Counting March 9.2022 2/35

O Ω Θ o ω Jun Ma (majun@nju.edu.cn) 2-3 Counting March 9, 2022 2 / 35

"People who analyze algorithms have double happiness..." Donald E.Knuth (1938~) 4口·￥①，4三，t更，里)Q0 Jun Ma (majunainju.edu.cn) 2-3 Counting March 9.2022 3/35

“People who analyze algorithms have double happiness . . .” Donald E. Knuth (1938 ∼) Jun Ma (majun@nju.edu.cn) 2-3 Counting March 9, 2022 3 / 35

Unfortunately,you have to master some mathematics. 4口·￥①，43，t夏，3Q0 Jun Ma (majunainju.edu.cn) 2-3 Counting March 9.2022 4/35

Unfortunately, you have to master some mathematics. Jun Ma (majun@nju.edu.cn) 2-3 Counting March 9, 2022 4 / 35

Counting 4口·￥①，4三，t更，里)Q0 Jun Ma (majunainju.edu.cn) 2-3 Counting March 9.2022 5/35

Counting Sums P Binomials ￾n k
Jun Ma (majun@nju.edu.cn) 2-3 Counting March 9, 2022 5 / 35

Counting Sums Σ 4口·￥①，4三，t更，里)Q0 Jun Ma (majunainju.edu.cn) 2-3 Counting March 9.2022 5/35

Counting Sums P Binomials ￾n k
Jun Ma (majun@nju.edu.cn) 2-3 Counting March 9, 2022 5 / 35

Counting Sums ∑ Binomials 4口·￥①，4三，t更，里)Q0 Jun Ma (majunainju.edu.cn) 2-3 Counting March 9.2022 5/35

Counting Sums P Binomials ￾n k
Jun Ma (majun@nju.edu.cn) 2-3 Counting March 9, 2022 5 / 35

PRELIMINARY 4日·1①，4子，t夏，里)Q0 Jun Ma (majunainju.edu.cn) 2-3 Counting March 9.2022 6/35

Jun Ma (majun@nju.edu.cn) 2-3 Counting March 9, 2022 6 / 35

Falling and Rising Factorials n=(mm=n(n-1)n-2)m-m+1)=m-m n! 4口·￥①，4三，t更，里)Q0 Jun Ma (majunainju.edu.cn) 2-3 Counting March 9.2022 7/35

Falling and Rising Factorials n m = (n)m = n(n − 1)(n − 2)· · ·(n − m + 1) = n! (n − m)! n m¯ = n (m) = n(n + 1)(n + 2)· · ·(n + m − 1) n! = n n = 1 n¯ n m ! = n! (n − m)!m! = n m m! Jun Ma (majun@nju.edu.cn) 2-3 Counting March 9, 2022 7 / 35