Power Series for Counting

Combinatorics · Axiom Academy

INTRO Power Series for Counting Discover how sequences become algebraic tools through generating functions. Let's start with a simple sequence. Use the slider to choose how many terms you want to see: Now let's try a different sequence. Adjust the slider to see how the sequence 0, 1, 2, 3, 4, ... becomes a generating function: Suppose we have 3 different coins. Click each coin to decide whether to include it (0 or 1 of each coin). Watch how the generating function builds: The real power: we can solve counting problems by reading coefficients! A generating function is a power series where the coefficients encode a sequence. For sequence a₀, a₁, a₂, ... , the generating function is G(x) = a₀ + a₁x + a₂x² + a₃x³ + ... Generating functions turn counting problems into algebra problems. We can use polynomial multiplication, factoring, and other algebraic techniques to solve combinatorial questions. Encode your problem as a generating function, manipulate it algebraically, then extract the coefficient of x n to get the answer to your counting question. You'll learn closed forms for common generating functions (like 1/(1-x) = 1 + x + x² + ...), operations on generating functions, and how to solve recurrence relations using this powerful tool.

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