This entry is about the generating functions in the sense of algebraic combinatorics. For another notion see generating function in classical mechanics.
A generating function is an element of , the rig of formal power series over the rig (which is often taken to be the natural numbers or the rational numbers), used for purposes of combinatorics. A general element takes the form
If is taken to be the real numbers or the complex numbers (or any subrig), then we can ask whether the power series has a radius of convergence and if there’s an analytic continuation; if so, then we also say that the continuation is the generating function.
Multiplying generating functions in the same variable gives
which effectively says to split up the set into two parts, put the structure on the first part and the structure on the second part.
Ordinary generating functions (OGFs) describe structures on totally ordered sets, while exponential generating functions (EGFs) apply to unordered sets (whose elements may be distinguished by having different labels). For example, the generating function for being an unordered finite set is
while the generating function for being a finite ordered set is
If we assume that the zeroth term is , then multiplying generating functions in different variables gives
If we take the product of countably many generating functions and then set where is the th prime, then we get
which is called the Dirichlet generating function for the family
The product of two Dirichlet generating functions gives
which effectively says to factor the term into two dimensions, apply to the first and to the second.
Sometimes we take the exponents on to be in a rig other than the natural numbers. For example, we might set and such a system lets us talk about the cost of operations done in parallel (max) or sequentially (+). Similarly, we could take the exponents to be binary string?s when considering instantaneous codes, or finite field elements when considering structures on a finite collection of objects.
The OGF for binary trees (rooted in the plane, counted by number of internal nodes) satisfies , which can be solved as . The coefficient of in is the th Catalan number .