Skip to content
Tutorials Center
My learning

Topics

Lesson 30 of 68 · Sequences, Sums and Recurrences

Generating Functions

Use ordinary generating functions to count selections, dice sums and partitions, and to solve linear recurrences like Fibonacci, with Python series code.

A sequence a0, a1, a2, ... is just a list of numbers. A generating function hangs that list on a clothesline: it is the power series a0 + a1·x + a2·x² + a3·x³ + .... The variable x is a placeholder, and you never plug in a value. What you gain is that algebra on the series (adding, multiplying, dividing) performs counting and recurrence-solving for you.

Advanced Counting gave a short taste. This lesson builds the toolkit properly: series arithmetic, the shapes you should recognize, counting problems solved by multiplication, and linear recurrences solved by division.

Series as lists of coefficients

Represent a series by its first few coefficients as a Python list. Then:

  • Addition adds coefficients position by position.
  • Multiplication is convolution: the coefficient of xⁿ in A·B is Σ a_k · b_{n-k}. That sum counts the ways to split n into a part from A and a part from B, which is why products model independent choices.
  • Shifting by xᵏ slides the list right by k places.
Python Series arithmetic

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.

The square of 1 + x + x² + ... has coefficients 1, 2, 3, 4, ...: the number of ways to write n as an ordered sum of two non-negative integers is n + 1.

Recognize these series

Closed form Sequence it generates
1 / (1 - x) 1, 1, 1, 1, ...
1 / (1 - a·x) 1, a, a², a³, ...
1 / (1 - x)² 1, 2, 3, 4, ...
(1 + x)ⁿ binomial coefficients C(n, k)
x / (1 - x - x²) the Fibonacci numbers 0, 1, 1, 2, 3, 5, ...

The identity 1 / (1 - x) = 1 + x + x² + ... is the geometric series, and almost every row follows from it by substitution or multiplication. For example, (1 + x)ⁿ is the binomial theorem, see Binomial Theorem and Pascal's Triangle.

A generating function in three steps

List Write the sequence a0, a1, a2.
Encode Make them coefficients of x to the n.
Calculate Add, multiply or divide the series.

The coefficient of x to the n is the answer for size n.

1 / 2

Counting with products

Each independent choice contributes one factor; the exponent of x tracks the total.

Dice sums. One six-sided die contributes x + x² + x³ + x⁴ + x⁵ + x⁶. The sum of two dice is the square, and the coefficient of xˢ is the number of ways to roll s.

Coins. Using any number of 1-cent coins gives 1 / (1 - x); any number of 5-cent coins gives 1 / (1 - x⁵); of 10-cent coins 1 / (1 - x¹⁰). Multiply them and read the coefficient of xⁿ to count the ways to pay n cents.

Partitions. A partition of n is a way to write n as an unordered sum of positive integers. Parts of size k contribute 1 / (1 - xᵏ), so the partition numbers come from Π 1 / (1 - xᵏ).

Python Dice, coins and partitions

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.

The dice row 1, 2, 3, 4, 5, 6, 5, 4, 3, 2, 1 is the familiar triangle. The partition list starts 1, 1, 2, 3, 5, 7, 11, 15, 22, 30, and p(20) = 627.

Solving a recurrence with a generating function

Division by a polynomial is where the method shines. Take the Fibonacci recurrence F(n) = F(n-1) + F(n-2) with F(0) = 0 and F(1) = 1. Let G(x) = Σ F(n)xⁿ. Multiplying the recurrence by xⁿ and summing:

G(x) - x = x·G(x) + x²·G(x), which gives G(x) = x / (1 - x - x²).

The recurrence became a single equation, solved by ordinary algebra. To get the coefficients, divide the series: if Q(x)·G(x) = P(x) with Q(0) = 1, then each coefficient follows from the earlier ones. Splitting 1 - x - x² into linear factors and using partial fractions then yields Binet's closed form; the code below does the long division numerically instead.

Python Expanding a rational generating function

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.

The second recurrence has 1 - 3x + 2x² = (1 - x)(1 - 2x). Partial fractions split x / ((1 - x)(1 - 2x)) into 1/(1 - 2x) - 1/(1 - x), whose coefficients are 2ⁿ - 1, matching the printed sequence. This is the same closed form that Solving Recurrences finds with the characteristic equation, so the two methods agree.

Use generating functions when a problem says "count the number of ways with constraints on each part" or when a recurrence has a non-standard right-hand side. For plain linear recurrences with constant coefficients, the characteristic-equation method is usually quicker.

Three more kinds of generating function

The series you met above, Σ a_n x^n, are called ordinary generating functions (OGFs). They count selections where order does not matter. Changing what sits next to x^n gives other kinds, each suited to a different job.

Exponential generating functions (EGFs)

The exponential generating function of a sequence a_n is

TEXT
A(x) = Σ a_n · x^n / n!

The extra n! makes products count arrangements, where order matters. If one kind of object can be used in a_i ways in a group of size i, and another in b_j ways, then the number of ways to build an ordered arrangement of size n from both is the coefficient of x^n/n! in the product A(x) · B(x). The binomial coefficient C(n, i) (which positions the first kind takes) is built into the product automatically.

Example: how many strings of length n can you make from the letters a, b, c if each letter may appear at most twice? Each letter contributes the factor 1 + x + x²/2!, one term per allowed repeat count, and n! · (coefficient of x^n) in the cube of that factor is the answer.

Probability generating functions (PGFs)

For a random variable X taking values 0, 1, 2, ..., the probability generating function is G(x) = Σ P(X = k) x^k. It packs the whole distribution into one polynomial. Three facts make it useful:

  • G(1) = 1, because probabilities sum to 1.
  • The mean is G'(1) and the variance is G''(1) + G'(1) - G'(1)².
  • If X and Y are independent, the PGF of X + Y is the product G_X(x) · G_Y(x). (This is just polynomial multiplication of the two distributions, a convolution.)

Dirichlet generating functions

A Dirichlet series of a sequence is Σ a_n / n^s. It suits number-theoretic sequences because multiplying two Dirichlet series convolves their coefficients (the Dirichlet convolution): (a * b)_n = Σ_{d | n} a_d · b_{n/d}. The series for the constant sequence 1, 1, 1, ... is the Riemann zeta function ζ(s). Squaring it gives the series of d(n), the number of divisors of n, because Σ_{d|n} 1 · 1 counts divisors.

Python EGF arrangements, a dice PGF and a divisor convolution

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.

The first two lines match, confirming the EGF recipe, and the dice variance comes out as 35/6, twice the variance 35/12 of one die, which agrees with the rule that variances of independent variables add.

Check your understanding

Quick check · 4 questions

of 4 answered You scored / 4 · perfect!

  1. 1. What sequence does 1 / (1 - x) generate?

    The geometric series 1 + x + x^2 + ... has every coefficient equal to 1.
  2. 2. In a product of generating functions, what does the coefficient of x^n count?

    Multiplying series convolves their coefficients, adding the exponents of independent choices.
  3. 3. Which generating function counts partitions of n?

    Each part size k can be used any number of times, which contributes the factor 1/(1 - x^k).
  4. 4. The recurrence F(n) = F(n-1) + F(n-2) leads to which denominator?

    Moving the terms of the recurrence to the left gives the polynomial 1 - x - x^2 as the denominator.

Summary

  • A generating function stores a sequence as the coefficients of a power series; the variable is only a placeholder.
  • Sums of series mean "either/or", products mean "and then", so counting with constraints becomes multiplication.
  • Geometric series 1 / (1 - x) and its variants are the main building blocks.
  • Dice sums, coin change and integer partitions are all products of simple series.
  • A linear recurrence turns into a rational generating function, which you can expand by long division or split with partial fractions.

Continue with Counting Principles.