Concrete Mathematics: A Foundation for Computer Science (2nd Edition)

Description

Cover......Page 1 Concrete Mathematics (Second edition)......Page 4 Copyright......Page 5 Preface......Page 6 A Note on Notation......Page 11 Contents......Page 13 1.1 The Tower of Hanoi�����������������������������......Page 15 1.2 Lines in the Plane�����������������������������......Page 18 1.3 The Josephus Problem�������������������������������......Page 22 Exercises����������������......Page 31 2.1 Notation�������������������......Page 35 2.2 Sums and Recurrences�������������������������������......Page 39 2.3 Manipulation of Sums�������������������������������......Page 44 2.4 Multiple Sums������������������������......Page 48 2.5 General Methods��������������������������......Page 55 2.6 Finite and Infinite Calculus���������������������������������������......Page 61 2.7 Infinite Sums������������������������......Page 70 Exercises����������������......Page 76 3.1 Floors and Ceilings������������������������������......Page 81 3.2 Floor/Ceiling Applications�������������������������������������......Page 84 3.3 Floor/Ceiling Recurrences������������������������������������......Page 92 3.4 'mod': The Binary Operation��������������������������������������......Page 95 3.5 Floor/Ceiling Sums�����������������������������......Page 100 Exercises����������������......Page 109 4.1 Divisibility�����������������������......Page 116 4.2 Primes�����������������......Page 119 4.3 Prime Examples�������������������������......Page 121 4.4 Factorial Factors����������������������������......Page 125 4.5 Relative Primality�����������������������������......Page 129 4.6 'mod': The Congruence Relation�����������������������������������������......Page 137 4.7 Independent Residues�������������������������������......Page 140 4.8 Additional Applications����������������������������������......Page 143 4.9 Phi and Mu���������������������......Page 147 Exercises����������������......Page 158 5.1 Basic Identities���������������������������......Page 167 5.2 Basic Practice�������������������������......Page 186 5.3 Tricks of the Trade������������������������������......Page 200 5.4 Generating Functions�������������������������������......Page 210 5.5 Hypergeometric Functions�����������������������������������......Page 218 5.6 Hypergeometric Transformations�����������������������������������������......Page 230 5.7 Partial Hypergeometric Sums��������������������������������������......Page 237 5.8 Mechanical Summation�������������������������������......Page 243 Exercises����������������......Page 256 6.1 Stirling Numbers���������������������������......Page 271 6.2 Eulerian Numbers���������������������������......Page 281 6.3 Harmonic Numbers���������������������������......Page 286 6.4 Harmonic Summation�����������������������������......Page 293 6.5 Bernoulli Numbers����������������������������......Page 297 6.6 Fibonacci Numbers����������������������������......Page 304 6.7 Continuants����������������������......Page 315 Exercises����������������......Page 323 7.1 Domino Theory and Change�����������������������������������......Page 334 7.2 Basic Maneuvers��������������������������......Page 345 7.3 Solving Recurrences������������������������������......Page 351 7.4 Special Generating Functions���������������������������������������......Page 364 7.5 Convolutions�����������������������......Page 367 7.6 Exponential Generating Functions�������������������������������������������......Page 378 7.7 Dirichlet Generating Functions�����������������������������������������......Page 384 Exercises����������������......Page 385 8.1 Definitions����������������������......Page 395 8.2 Mean and Variance����������������������������......Page 401 8.3 Probability Generating Functions�������������������������������������������......Page 408 8.4 Flipping Coins�������������������������......Page 415 8.5 Hashing������������������......Page 425 Exercises����������������......Page 441 9 Asymptotics��������������������......Page 453 9.1 A Hierarchy����������������������......Page 454 9.2 O Notation���������������������......Page 457 9.3 O Manipulation�������������������������......Page 464 9.4 Two Asymptotic Tricks��������������������������������......Page 477 9.5 Euler's Summation Formula������������������������������������......Page 483 9.6 Final Summations���������������������������......Page 490 Exercises����������������......Page 503 A. Answers to Exercises......Page 511 B. Bibliography......Page 618 C. Credits for Exercises......Page 646 Index������������......Page 651 List of Tables���������������������......Page 671 Errata, 1994–1997......Page 673