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