When is an exponential generating function preferred?

When the objects being counted carry distinguishable labels, such as labeled trees or permutations, the factorial weighting of exponential generating functions makes their products count correctly.

Does the variable in a generating function have a meaning?

In the formal setting it is a placeholder marking size; only when analytic methods are applied is it treated as a complex variable with numerical value.

Ordinary and Exponential Generating Functions

Ordinary generating functions encode sequences for unlabeled counting, while exponential generating functions handle labeled structures, and both translate combinatorial constructions into algebra.

Definition

The ordinary generating function of a sequence is the power series with that sequence as coefficients; the exponential generating function divides each coefficient by a factorial, the form suited to counting labeled objects.

Scope

This topic introduces the two principal kinds of generating function, the formal power series framework, and the symbolic method that maps combinatorial constructions - disjoint union, product, sequence, set, and cycle - directly to operations on series. It develops the product formulas that distinguish the ordinary and exponential settings.

Core questions

When should one use an ordinary versus an exponential generating function?
How do combinatorial operations correspond to algebraic operations on series?
Why does multiplication of exponential generating functions count labeled merges?
How does the symbolic method automate the derivation of counting formulas?

Key concepts

Ordinary generating function
Exponential generating function
Formal power series
Convolution and product rule
Symbolic method
Labeled versus unlabeled structures

Key theories

Symbolic method: Flajolet and Sedgewick's symbolic method gives a systematic dictionary translating combinatorial constructions on classes of objects into operations on their generating functions, so counting formulas can be read off structural descriptions.
Product rule for generating functions: The product of two ordinary generating functions enumerates ordered pairs by total size, while the product of exponential generating functions enumerates labeled merges, the distinction that governs which form to use.

Clinical relevance

The symbolic method automates the enumeration and average-case analysis of data structures and algorithms, and exponential generating functions are the natural tool for counting labeled trees, permutations, and set partitions that arise in computer science.

History

The systematic correspondence between combinatorial constructions and generating-function operations, foreshadowed by Euler and Polya, was developed into the formal symbolic method by Flajolet and Sedgewick.

Key figures

Philippe Flajolet
Robert Sedgewick
Richard P. Stanley

Seminal works

flajolet2009
stanley2011

Frequently asked questions

When is an exponential generating function preferred?: When the objects being counted carry distinguishable labels, such as labeled trees or permutations, the factorial weighting of exponential generating functions makes their products count correctly.
Does the variable in a generating function have a meaning?: In the formal setting it is a placeholder marking size; only when analytic methods are applied is it treated as a complex variable with numerical value.