3
Generating functions
CONTENTS
3.1 Power series .. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 117
3.1.1 Generalized binomial coefficients .. . . . . . . . . . . . . . . . . . . . . . . 118
3.1.2 Formal power series . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 119
3.2 Warming up: Solving recurrence relations . . . . . . . . . . . . . . . . . . . . . . . 122
3.2.1 Ordinary generating functions . . . . . . . . . . . . . . . . . . . . . . . . . . . 122
3.2.2 Exponential generating functions . . . . . . . . . . . . . . . . . . . . . . . 128
3.3 Products of generating functions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 131
3.3.1 Ordinary generating functions . . . . . . . . . . . . . . . . . . . . . . . . . . . 131
3.3.2 Exponential generating functions . . . . . . . . . . . . . . . . . . . . . . . 142
3.4 Compositions of generating functions . . . . . . . . . . . . . . . . . . . . . . . . . . . . 147
3.4.1 Ordinary generating functions . . . . . . . . . . . . . . . . . . . . . . . . . . . 147
3.4.2 Exponential generating functions . . . . . . . . . . . . . . . . . . . . . . . 153
3.4.2.1 The exponential formula . . . . . . . . . . . . . . . . . . . . . 153
3.4.2.2 The compositional formula . . . . . . . . . . . . . . . . . . . 157
3.5 A different type of generating functions . . . . . . . . . . . . . . . . . . . . . . . . . 160
3.6 Notes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 161
3.7 Chapter review . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 162
3.8 Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 164
3.9 Solutions to exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 166
3.10 Supplementary exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 176
In this chapter, we will learn our most advanced counting technique so far.
We will learn how to encode all elements of a possibly infinite sequence by one
single function, the generating function of the sequence. Often, we will first
obtain the generating function of a sequence and then decode it, that is, we will
then compute the elements of the sequence from the generating function. This
idea is a powerful example of using continuous objects in discrete mathematics.
Let us start with a very short review of the type of functions we will use.
Rest assured that the book will return to discussing combinatorics very soon.
117

Get Introduction to Enumerative and Analytic Combinatorics, 2nd Edition now with O’Reilly online learning.

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