A topic in the Open Knowledge Graph — a free, open map of 15,290 topics and the order to learn them in.
A generating function encodes a sequence (a₀, a₁, a₂, …) as coefficients of the formal power series A(x) = a₀ + a₁x + a₂x² + ⋯. Multiplying generating functions corresponds to convolution of sequences, making them a powerful algebraic tool for counting. The generating function for binomial coefficients C(n,k) is (1+x)ⁿ, and 1/(1−x)ⁿ generates combinations with repetition. Generating functions provide a unified algebraic framework that can solve recurrences, count restricted compositions, and derive combinatorial identities.
Start with 1/(1−x) = 1 + x + x² + ⋯ as the simplest example, then explore 1/(1−x)² and 1/(1−x)ⁿ. Practice extracting a specific coefficient as the answer to a counting question. Solve a recurrence both by characteristic equations and by generating functions to compare methods.
A generating function is a way to package an infinite sequence of numbers into a single algebraic object. Given a sequence a₀, a₁, a₂, …, you form the formal power series A(x) = a₀ + a₁x + a₂x² + a₃x³ + ⋯. The sequence lives in the coefficients; x is just a placeholder. You already know from geometric series that 1/(1−x) = 1 + x + x² + x³ + ⋯, so 1/(1−x) is the generating function for the sequence (1, 1, 1, …). This one fact, combined with algebraic manipulations, unlocks an enormous range of counting problems.
The power comes from what algebraic operations do to sequences. Multiplication of generating functions corresponds to convolution of sequences: if A(x) encodes (aₙ) and B(x) encodes (bₙ), then A(x)B(x) encodes the sequence cₙ = Σₖ aₖbₙ₋ₖ. This is exactly the counting structure of "choose k items of type A and n−k items of type B." Squaring 1/(1−x) gives 1/(1−x)² = 1 + 2x + 3x² + 4x³ + ⋯, and its nth coefficient is n+1 — which counts the number of ways to write n as an ordered sum of two non-negative integers. More generally, 1/(1−x)ⁿ has [xᵏ]-coefficient C(n+k−1, k), which is precisely the stars-and-bars count you already know: placing k identical items into n bins.
To solve a counting problem with generating functions, you encode your constraints as algebraic operations and then extract a coefficient. For example, "how many ways to make change for n cents using pennies, nickels, and dimes?" becomes [xⁿ] in 1/((1−x)(1−x⁵)(1−x¹⁰)), because each factor generates the choices for one coin type. Recurrences yield to the same tool: if aₙ = aₙ₋₁ + aₙ₋₂ (Fibonacci), multiply the generating function A(x) by the equation, collect terms, and solve for A(x) as a closed-form rational function. Partial fractions then let you read off the coefficients explicitly.
The key philosophical shift is treating the power series as a formal algebraic object, not a function you evaluate at x = 0.5. Convergence is irrelevant — the machinery is purely symbolic. This frees you to use 1/(1−2) = −1 without panic, because you never actually substitute 2; you only manipulate the series symbolically and read coefficients. Once this mindset clicks, generating functions feel less like a trick and more like a language: every combinatorial identity is an algebraic identity in disguise, and algebraic identities between generating functions are often much easier to prove than their combinatorial equivalents.