具体数学 计算机科学基础 英文版PDF电子书下载

1 Recurrent Problems 1

1.1 The Tower of Hanoi 1

1.2 Lines in the Plane 4

1.3 The Josephus Problem 8

Exercises 17

2 Sums 21

2.1 Notation 21

2.2 Sums and Recurrences 25

2.3 Manipulation of Sums 30

2.4 Multiple Sums 34

2.5 General Methods 41

2.6 Finite and Infinite Calculus 47

2.7 Infinite Sums 56

Exercises 62

3 Integer Functions 67

3.1 Floors and Ceilings 67

3.2 Floor/Ceiling Applications 70

3.3 Floor/Ceiling Recurrences 78

3.4 'mod':The Binary Operation 81

3.5 Floor/Ceiling Sums 86

Exercises 95

4 Number Theory 102

4.1 Divisibility 102

4.2 Primes 105

4.3 Prime Examples 107

4.4 Factorial Factors 111

4.5 Relative Primality 115

4.6 'mod':The Congruence Relation 123

4.7 Independent Residues 126

4.8 Additional Applications 129

4.9 Phi and Mu 133

Exercises 144

5 Binomial Coefficients 153

5.1 Basic Identities 153

5.2 Basic Practice 172

5.3 Tricks of the Trade 186

5.4 Generating Functions 196

5.5 Hypergeometric Functions 204

5.6 Hypergeometric Transformations 216

5.7 Partial Hypergeometric Sums 223

5.8 Mechanical Summation 229

Exercises 242

6 Special Numbers 257

6.1 Stirling Numbers 257

6.2 Eulerian Numbers 267

6.3 Harmonic Numbers 272

6.4 Harmonic Summation 279

6.5 Bernoulli Numbers 283

6.6 Fibonacci Numbers 290

6.7 Continuants 301

Exercises 309

7 Generating Functions 320

7.1 Domino Theory and Change 320

7.2 Basic Maneuvers 331

7.3 Solving Recurrences 337

7.4 Special Generating Functions 350

7.5 Convolutions 353

7.6 Exponential Generating Functions 364

7.7 Dirichlet Generating Functions 370

Exercises 371

8 Discrete Probability 381

8.1 Definitions 381

8.2 Mean and Variance 387

8.3 Probability Generating Functions 394

8.4 Flipping Coins 401

8.5 Hashing 411

Exercises 427

9 Asymptotics 439

9.1 A Hierarchy 440

9.2 O Notation 443

9.3 O Manipulation 450

9.4 Two Asymptotic Tricks 463

9.5 Euler's Summation Formula 469

9.6 Final Summations 476

Exercises 489

A Answers to Exercises 497

B Bibliography 604

C Credits for Exercises 632

Index 637

List of Tables 657