ABSTRACT
Given that generating functions are an important tool in our analysis, how do we
derive them in the first place? We have seen a few examples in Chapter 2, mostly
from recurrences, which often correspond to the way in which data structures are
built, or algorithms progress and modify their state. In this chapter, we describe other
approaches based on tightening the bond between generating functions and combi-
natorial entities, to use a general term. In order to enumerate a set, we first construct
it by a recursive definition, using well-defined intuitive operations on primitive com-
ponents. We are then led directly to suitable generating functions, avoiding the need
for recurrences. We show a mechanical way based on symbolic calculus, which can
often guide us to such a construction, when intuition alone is an insufficient guide.
The basic concepts in this calculus are the combinatorial class and the combinato-
rial operation. A combinatorial class is essentially a set consisting of combinatorial
objects, such as points, lines, graphs and symbols, alone or in any combination. A
combinatorial operation is used to create complex classes from simple ones, such as
letters to strings or words, or nodes and edges to graphs, or words to books.
