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 ...

Get Concrete Mathematics: A Foundation for Computer Science, Second Edition now with O’Reilly online learning.

O’Reilly members experience live online training, plus books, videos, and digital content from 200+ publishers.