O'Reilly logo

Concrete Mathematics: A Foundation for Computer Science, Second Edition by Oren Patashnik, Donald E. Knuth, Ronald L. Graham

Stay ahead with the world's most comprehensive technology and business learning platform.

With Safari, you learn the way you learn best. Get unlimited access to videos, live online training, learning paths, books, tutorials, and more.

Start Free Trial

No credit card required

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

With Safari, you learn the way you learn best. Get unlimited access to videos, live online training, learning paths, books, interactive tutorials, and more.

Start Free Trial

No credit card required