Discrete Math · Undergraduate

Generating Functions: Counting with Power Series

Quick answer

A generating function stores a whole sequence a₀, a₁, a₂, … as one power series a₀ + a₁x + a₂x² + ⋯. Multiplying generating functions combines choices: the coefficient of xⁿ in a product counts the ways to make a total of n. So making change, distributing objects and rolling dice become questions about coefficients. A recurrence turns into an equation for the generating function, and solving it gives a closed form, such as x/(1 − x − x²) for the Fibonacci numbers.

What you'll learn

  • Write the generating function of a simple sequence
  • Count combinations as coefficients of a product
  • Count solutions of a + b + c = n with and without upper limits
  • Turn a recurrence into an equation for its generating function

A sequence as one function

The generating function of a sequence a0,a1,a2,…a_0, a_1, a_2, \ldots is the power series

G(x)=a0+a1x+a2x2+⋯=∑n=0∞anxnG(x) = a_0 + a_1x + a_2x^2 + \cdots = \sum_{n=0}^{\infty} a_nx^n

The xx only holds places: ana_n sits on xnx^n. Some standard ones:

SequenceGenerating function
1,1,1,…1, 1, 1, \ldots11−x\tfrac{1}{1 - x}
1,c,c2,…1, c, c^2, \ldots11−cx\tfrac{1}{1 - cx}
(n0),(n1),…,(nn)\binom{n}{0}, \binom{n}{1}, \ldots, \binom{n}{n}(1+x)n(1 + x)^n
(k+22)\binom{k + 2}{2}, for k=0,1,2,…k = 0, 1, 2, \ldots1(1−x)3\tfrac{1}{(1 - x)^3}

Why multiplying counts combinations

Suppose A(x)A(x) lists the ways to pick some of item A and B(x)B(x) the ways for item B. In the product, xi⋅xj=xi+jx^i \cdot x^j = x^{i+j}. The coefficient of xnx^n in A(x)B(x)A(x)B(x) collects every pairing whose amounts add to nn, which is exactly the number of ways to make a total of nn. Exponents add while coefficients multiply, so counting turns into algebra. The same rule underlies the binomial theorem: (1+x)n(1 + x)^n chooses, for each of nn items, either 11 (leave it) or xx (take it).

Worked examples

Common mistakes

Practice problems

  1. Write the generating function of 1,2,4,8,…1, 2, 4, 8, \ldots.

    Answer

    11−2x\tfrac{1}{1 - 2x}

    Full solution

    A geometric series with ratio 2x2x.

  2. Find the coefficient of x3x^3 in (1+x+x2)3(1 + x + x^2)^3.

    Answer

    77

    Full solution

    Count (a,b,c)(a, b, c) from {0,1,2}\{0, 1, 2\} with sum 33: the 66 orders of (0,1,2)(0, 1, 2) and (1,1,1)(1, 1, 1).

  3. How many nonnegative solutions does a+b+c=7a + b + c = 7 have?

    Answer

    3636

    Full solution

    (7+22)=(92)=36\binom{7 + 2}{2} = \binom{9}{2} = 36.

  4. In how many ways can you pay 1515 cents with nickels and dimes?

    Answer

    22

    Full solution

    Three nickels, or one dime and one nickel: the coefficient of x15x^{15} in 1(1−x5)(1−x10)\tfrac{1}{(1 - x^5)(1 - x^{10})}.

  5. Two dice: what generating function counts the totals, and how many ways give 77?

    Answer

    (x+x2+⋯+x6)2(x + x^2 + \cdots + x^6)^2; 66 ways

    Full solution

    The coefficient of x7x^7 counts pairs (1,6),(2,5),…,(6,1)(1,6), (2,5), \ldots, (6,1).

  6. Which sequence has generating function (1+x)5(1 + x)^5?

    Answer

    1,5,10,10,5,1,0,0,…1, 5, 10, 10, 5, 1, 0, 0, \ldots

    Full solution

    The binomial coefficients (5k)\binom{5}{k}.

  7. Find the generating function of a0=1a_0 = 1, an=3an−1a_n = 3a_{n-1}.

    Answer

    11−3x\tfrac{1}{1 - 3x}

    Full solution

    A(x)−3xA(x)=a0=1A(x) - 3xA(x) = a_0 = 1, so an=3na_n = 3^n.

  8. A student counts solutions of a+b+c=10a + b + c = 10 with each at most 44 as (122)=66\binom{12}{2} = 66. What went wrong?

    Answer

    The upper limits were ignored; the answer is 66.

    Full solution

    6666 counts all nonnegative solutions. Inclusion–exclusion, or the factor (1−x5)3(1 - x^5)^3, removes those with a value above 44.

Frequently asked questions

What is a generating function?

The power series G(x) = a₀ + a₁x + a₂x² + ⋯ whose coefficients are the terms of a sequence. The x is a placeholder; the coefficients carry the information.

Why does multiplying generating functions count combinations?

When two series are multiplied, the coefficient of xⁿ collects every way to pick xⁱ from one and xʲ from the other with i + j = n.

What is the generating function of 1, 1, 1, …?

1/(1 − x) = 1 + x + x² + ⋯, the geometric series.

How many nonnegative solutions does a + b + c = n have?

C(n + 2, 2), the coefficient of xⁿ in 1/(1 − x)³.

What is the generating function of the Fibonacci numbers?

x/(1 − x − x²), found by using Fₙ = Fₙ₋₁ + Fₙ₋₂ to relate F(x) to xF(x) and x²F(x).