CONTENTS xiii 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 Exercises 230 6 Special Numbers 243 6.1 Stirling Numbers 243 6.2 Eulerian Numbers 253 6.3 Harmonic Numbers 258 6.4 Harmonic Summation 265 6.5 Bernoulli Numbers 269 6.6 Fibonacci Numbers 276 6.7 Continuants 287 Exercises 295 7 Generating Functions 306 7.1 Domino Theory and Change 306 7.2 Basic Maneuvers 317 7.3 Solving Recurrences 323 7.4 Special Generating Functions 336 7.5 Convolutions 339 7.6 Exponential Generating Functions 350 7.7 Dirichlet Generating Functions 356 Exercises 357 8 Discrete Probability 367 8.1 Definitions 367 8.2 Mean and Variance 373 8.3 Probability Generating Functions 380 8.4 Flipping Coins 387 8.5 Hashing 397 Exercises 413 9 Asymptotics 425 9.1 A Hierarchy 426 9.2 0 Notation 429 9.3 0 Manipulation 436 9.4 Two Asymptotic Tricks 449 9.5 Euler's Summation Formula 455 9.6 Final Summations 462 Exercises 475 A Answers to Exercises 483 B Bibliography 578 C Credits for Exercises 601 Index 606 List of Tables 624CONTENTS xiii 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 Exercises 230 6 Special Numbers 243 6.1 Stirling Numbers 243 6.2 Eulerian Numbers 253 6.3 Harmonic Numbers 258 6.4 Harmonic Summation 265 6.5 Bernoulli Numbers 269 6.6 Fibonacci Numbers 276 6.7 Continuants 287 Exercises 295 7 Generating Functions 306 7.1 Domino Theory and Change 306 7.2 Basic Maneuvers 317 7.3 Solving Recurrences 323 7.4 Special Generating Functions 336 7.5 Convolutions 339 7.6 Exponential Generating Functions 350 7.7 Dirichlet Generating Functions 356 Exercises 357 8 Discrete Probability 367 8.1 Definitions 367 8.2 Mean and Variance 373 8.3 Probability Generating Functions 380 8.4 Flipping Coins 387 8.5 Hashing 397 Exercises 413 9 Asymptotics 425 9.1 A Hierarchy 426 9.2 0 Notation 429 9.3 0 Manipulation 436 9.4 Two Asymptotic Tricks 449 9.5 Euler’s Summation Formula 455 9.6 Final Summations 462 Exercises 475 A Answers to Exercises 483 B Bibliography 578 C Credits for Exercises 601 Index 606 List of Tables 624