book

Concrete Mathematics: A Foundation for Computer Science, 2nd Edition

by Ronald L. Graham, Donald E. Knuth, Oren Patashnik

February 1994

Intermediate to advanced

672 pages

18h 51m

English

Addison-Wesley Professional

Read now

Unlock full access

1.1 The Tower of Hanoi1.2 Lines in the Plane1.3 The Josephus ProblemExercises

2.1 Notation2.2 Sums and Recurrences2.3 Manipulation of Sums2.4 Multiple Sums2.5 General Methods2.6 Finite and Infinite Calculus2.7 Infinite SumsExercises
3.1 Floors and Ceilings3.2 Floor/Ceiling Applications3.3 Floor/Ceiling Recurrences3.4 ‘MOD’: The Binary Operation3.5 Floor/Ceiling SumsExercises
4.1 Divisibility4.2 Primes4.3 Prime Examples4.4 Factorial Factors4.5 Relative Primality4.6 ‘MOD’: The Congruence Relation4.7 Independent Residues4.8 Additional Applications4.9 PHI and MUExercises
5.1 Basic Identities5.2 Basic Practice5.3 Tricks of the Trade5.4 Generating Functions5.5 Hypergeometric Functions5.6 Hypergeometric Transformations5.7 Partial Hypergeometric Sums5.8 Mechanical SummationExercises
6.1 Stirling Numbers6.2 Eulerian Numbers6.3 Harmonic Numbers6.4 Harmonic Summation6.5 Bernoulli Numbers6.6 Fibonacci Numbers6.7 ContinuantsExercises
7.1 Domino Theory and Change7.2 Basic Maneuvers7.3 Solving Recurrences7.4 Special Generating Functions7.5 Convolutions7.6 Exponential gf’s7.7 Dirichlet Generating FunctionsExercises
8.1 Definitions8.2 Mean and Variance8.3 Probability Generating Functions8.4 Flipping Coins8.5 HashingExercises
9.1 A Hierarchy9.2 O Notation9.3 O Manipulation9.4 Two Asymptotic Tricks9.5 Euler’s Summation Formula9.6 Final SummationsExercises

Content preview from Concrete Mathematics: A Foundation for Computer Science, 2nd Edition

7 Generating Functions

The most powerful way to deal with sequences of numbers, as far as anybody knows, is to manipulate infinite series that “generate” those sequences. We’ve learned a lot of sequences and we’ve seen a few generating functions; now we’re ready to explore generating functions in depth, and to see how remarkably useful they are.

7.1 Domino Theory and Change

Generating functions are important enough, and for many of us new enough, to justify a relaxed approach as we begin to look at them more closely. So let’s start this chapter with some fun and games as we try to develop our intuitions about generating functions. We will study two applications of the ideas, one involving dominoes and the other involving coins.

How many ways ...