Ordinary Generating Function

An ordinary generating function (OGF) of a sequence (aₙ) is the formal power series A(z) = Σ aₙ zⁿ. It is the simplest and most widely used type of generating function, and it is the natural tool for counting unlabeled combinatorial structures.

The OGF encodes the sequence as the coefficients of a power series, and combinatorial operations on the structures correspond to algebraic operations on the series. The disjoint union of two classes corresponds to addition of their OGFs. The Cartesian product corresponds to multiplication. The sequence class corresponds to the geometric series 1/(1-z). These correspondences make the OGF a powerful tool for deriving closed-form expressions and asymptotic estimates for combinatorial sequences.

The OGF is particularly useful for sequences defined by linear recurrence relations with constant coefficients. Such recurrences can be solved by rewriting them as algebraic equations for the OGF, which can then be solved by partial fraction decomposition to extract the coefficients. This method is the discrete analogue of the Laplace transform method for solving linear differential equations.