Skip to content
Tutorials Center
My learning

Topics

Lesson 21 of 36 ยท Recurrences and Generating Functions

Generating Functions

Learn ordinary generating functions: encode a counting sequence as a power series, multiply series to combine choices, and solve dice, coin change and Fibonacci problems.

A generating function is a clothesline for a sequence: you hang the terms a_0, a_1, a_2, ... on the powers of x and treat the result as a single object:

A(x) = a_0 + a_1 x + a_2 x^2 + ...

The x is never evaluated; it is only a marker for position. The magic is that algebra on A(x) (adding, multiplying, dividing) corresponds to counting operations on the sequence. Multiplying two series is exactly the product rule over all ways to split the total.

Two basic series

  • 1/(1-x) = 1 + x + x^2 + x^3 + ... : the constant sequence 1, 1, 1, ....
  • (1+x)^n = sum C(n,k) x^k : the binomial theorem; the coefficient of x^k counts k-subsets of an n-set.

Each factor (1 + x) says "this object is either not chosen (1) or chosen (x)". A product of such factors lists the choices for all objects at once.

Python Series in sympy

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

1/(1-x)^2 has coefficients 1, 2, 3, 4, ... because squaring 1/(1-x) convolves the all-ones sequence with itself. The list die is the polynomial x + x^2 + ... + x^6, one die. Multiplying two dice gives the familiar sum distribution 1, 2, 3, 4, 5, 6, 5, 4, 3, 2, 1 for totals 2 to 12. Three dice have 6^3 = 216 outcomes in total (the sum of all coefficients), and the coefficient of x^10 (the 8th printed number, 27) counts the ways to roll 10.

The product rule becomes polynomial multiplication

If A(x) counts ways to build part 1 of a structure with total size n, and B(x) does the same for part 2, then the coefficient of x^n in A(x) B(x) is a_0 b_n + a_1 b_{n-1} + ... + a_n b_0: choose how much size goes to each part, then multiply. This operation is called convolution.

Recipe: distributing items

To count solutions of e_1 + e_2 + e_3 = n where each e_i lies in some allowed set S_i, multiply the polynomials sum_{e in S_i} x^e and read the coefficient of x^n. For example, "at least 1 and at most 4 of each of three flavors" is (x + x^2 + x^3 + x^4)^3.

Counting with unlimited choices: coins

Paying 100 cents using coins 1, 5, 10 and 25: each coin type contributes a factor 1/(1 - x^c) = 1 + x^c + x^{2c} + ... (use 0, 1, 2, ... coins of that value). The answer is the coefficient of x^100 in 1/((1-x)(1-x^5)(1-x^10)(1-x^25)). In code, multiplying by 1/(1-x^c) is the simple loop ways[s] += ways[s - c].

Python Fibonacci and coin change

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

There are 242 ways to make 100 cents. The first line shows that the series of x/(1 - x - x^2) is x + x^2 + 2x^3 + 3x^4 + 5x^5 + ...: the Fibonacci numbers again.

From a recurrence to a generating function

Take F_n = F_{n-1} + F_{n-2}, F_0 = 0, F_1 = 1, and let F(x) = sum F_n x^n. Multiply the recurrence by x^n and sum over n >= 2:

F(x) - x = x F(x) + x^2 F(x), so F(x) = x / (1 - x - x^2).

Factor the denominator, use partial fractions, expand each piece as a geometric series, and you obtain Binet's formula. This is the second method for linear recurrences, and it also handles recurrences whose coefficients are not constant, where the characteristic equation fails.

flowchart LR
    A["Counting problem"] --> B["Build one factor per choice"]
    B --> C["Multiply the factors"]
    C --> D["Read coefficient of x^n"]
    D --> E["Closed form or program"]

The generating function workflow: model, multiply, extract.

Useful rules

  • A(x) + B(x): add sequences term by term.
  • x A(x): shift right (insert a leading 0).
  • A(x) B(x): convolution.
  • A(x)/(1-x): partial sums a_0 + ... + a_n.
  • Differentiate: A'(x) = sum n a_n x^{n-1}, which brings down the index.

Series are formal: you never plug in a number or worry about convergence. 1/(1-x) simply means "the series whose product with 1 - x is 1".

Check your understanding

Quick check ยท 4 questions

of 4 answered You scored / 4 ยท perfect!

  1. 1. Which generating function counts how many ways to choose a subset of a 6-element set by size?

    Each element contributes the factor (1 + x): not chosen or chosen. The coefficient of x^k is C(6,k).
  2. 2. What does the product A(x)B(x) compute at the coefficient of x^n?

    Choosing how much size goes to each part and multiplying counts (convolution).
  3. 3. Which factor models an unlimited supply of coins of value 5?

    1/(1 - x^5) = 1 + x^5 + x^10 + ..., meaning 0, 1, 2, ... coins.
  4. 4. From F(n) = F(n-1) + F(n-2) with F(0)=0, F(1)=1, what is F(x)?

    F(x) - x = x F(x) + x^2 F(x), so F(x) = x/(1 - x - x^2).

Summary

  • A(x) = sum a_n x^n packages a sequence; operations on series mirror counting operations.
  • Each independent choice becomes a factor; multiply them and read the needed coefficient.
  • Unlimited repeats use 1/(1 - x^c); bounded choices use polynomials; subsets use (1 + x).
  • A recurrence turns into an equation for A(x), solved by partial fractions.

Next: Exponential Generating Functions