Ordinary Generating Functions

Combinatorics · Axiom Academy

LESSON Ordinary Generating Functions Learn how sequences can be encoded as power series and unlock powerful combinatorial techniques Given a sequence (a₀, a₁, a₂, a₃, ...), the ordinary generating function (OGF) is defined as the formal power series: Each coefficient aₙ in the sequence becomes the coefficient of xⁿ in the power series. We don't worry about convergence—this is a formal power series where x is just a placeholder. Consider the constant sequence (1, 1, 1, 1, ...). Its generating function is: This infinite series has a beautiful closed form that you may recognize from calculus: This closed form is valid when |x| < 1, but we use it formally without worrying about convergence. 3. Example: Powers and Products We can modify the geometric series to encode different sequences. For instance, starting from index 1: Or consider the sequence (1, 2, 3, 4, ...). By differentiating the geometric series and manipulating: The binomial theorem gives us another important generating function. For a fixed n: The coefficients encode binomial coefficients! This connects generating functions directly to combinatorics.

This is the written version of the interactive lesson above. See the full Combinatorics course.