Chapter 21 of 30

Generating Functions

Suppose you want to know how many ways there are to pay ₹10 using ₹1, ₹2 and ₹5 coins, or how many ways 10 chocolates can be shared among three children when one child must get at least two and another may get only an even number. You could list every case, but the lists grow quickly and it is easy to miss one. Generating functions turn such counting problems into algebra: you write down a polynomial or power series for each choice, multiply, and read off a coefficient.

The same tool also solves recurrence relations. In Solving Linear Recurrences we used characteristic roots; in this chapter you will see a second method that works directly from the recurrence and handles initial conditions automatically. Generating functions are part of the GATE CS syllabus (under combinatorics), and GATE questions on them are usually short coefficient-extraction problems once you know the standard series.

The (ordinary) generating function of a sequence a0, a1, a2, … is the power series G(x) = a0 + a1x + a2x² + ⋯ = ∑n≥0 anxn. The term an is the coefficient of xn, written [xn] G(x).


The Big Idea: A Sequence on a Clothesline

A generating function is a way to store an infinite sequence in one expression. Think of the powers x0, x1, x2, … as pegs on a clothesline, and hang an on peg xn. The variable x is never given a numerical value; it only marks the position. Because of this we treat G(x) as a formal power series: we add and multiply series term by term and never worry about whether the series converges.

Why is this useful? Because multiplying series corresponds to combining choices. When you multiply (xi)(xj) the exponents add: xi+j. So if one series lists "ways to choose i items from group 1" and another lists "ways to choose j items from group 2", the coefficient of xn in the product counts all ways to choose n items in total. Exponents keep track of the count for us.

First example: all ones

The sequence 1, 1, 1, 1, … has generating function 1 + x + x² + x³ + ⋯. Multiply it by (1 − x):

(1 − x)(1 + x + x² + x³ + ⋯) = (1 + x + x² + ⋯) − (x + x² + x³ + ⋯) = 1

Everything except the 1 cancels. So, as formal power series,

1 + x + x² + x³ + ⋯ = 1 / (1 − x)

This one identity (the geometric series) is the source of almost every other formula in this chapter. Replacing x by ax gives 1/(1 − ax) = ∑ anxn, the generating function of 1, a, a², a³, ….


A Table of Standard Generating Functions

Learn this table. Nearly every exam question reduces to it.

Sequence an

First terms

Generating function

1

1, 1, 1, 1, …

1/(1 − x)

an

1, a, a², a³, …

1/(1 − ax)

(−1)n

1, −1, 1, −1, …

1/(1 + x)

1 if n is even, else 0

1, 0, 1, 0, …

1/(1 − x²)

n + 1

1, 2, 3, 4, …

1/(1 − x)²

n

0, 1, 2, 3, …

x/(1 − x)²

n²

0, 1, 4, 9, …

x(1 + x)/(1 − x)³

C(m, n) (m fixed)

1, m, C(m,2), …, 1, 0, 0, …

(1 + x)m

C(n + k − 1, n) (k fixed)

1, k, C(k+1,2), …

1/(1 − x)k

1 for n ≤ m, else 0

1, 1, …, 1 (m + 1 ones), 0, …

(1 − xm+1)/(1 − x)

1/n!

1, 1, 1/2, 1/6, …

ex

The last-but-one row is a finite geometric sum: 1 + x + ⋯ + xm = (1 − xm+1)/(1 − x). It is how we encode "at most m" in counting problems.


Operations on Generating Functions

Let A(x) = ∑ anxn and B(x) = ∑ bnxn. Each operation on series matches an operation on sequences.

Operation on the series

Effect on the sequence

A(x) + B(x)

an + bn

c · A(x)

c · an

xk A(x)

shift right by k: 0, …, 0 (k zeros), a0, a1, …

(A(x) − a0)/x

shift left: a1, a2, a3, …

A(cx)

cn an

x A′(x)

n · an

A(x) B(x)

cn = ∑k=0n ak bn−k (convolution)

A(x)/(1 − x)

partial sums a0 + a1 + ⋯ + an

The product rule is the important one. The coefficient of xn in A(x)B(x) collects every pair of terms akxk · bn−kxn−k whose exponents add up to n. The partial-sum rule is just a special case: 1/(1 − x) has every bj = 1, so cn = a0 + ⋯ + an.

Deriving new series from old

Example. Find the generating function of 1, 2, 3, 4, ….

The partial sums of 1, 1, 1, … are 1, 2, 3, …. So the answer is (1/(1 − x)) · (1/(1 − x)) = 1/(1 − x)². Shifting right once gives 0, 1, 2, 3, …, which is x/(1 − x)².

Example. Find the generating function of n².

Apply x · d/dx to x/(1 − x)². The derivative of x/(1 − x)² is (1 + x)/(1 − x)³, so x times it is x(1 + x)/(1 − x)³. Expanding gives 0, 1, 4, 9, 16, 25, 36, …, as expected.

Example. Which sequence has generating function 5/(1 − 2x) − 3/(1 − x)?

Read each piece from the table: 5 · 2n − 3 · 1 = 5 · 2n − 3. The terms are 2, 7, 17, 37, ….


The Extended Binomial Theorem

For a positive integer m, (1 + x)m = ∑ C(m, k)xk, a finite sum. To handle negative or fractional powers we extend the binomial coefficient to any real number u:

C(u, k) = u(u − 1)(u − 2)⋯(u − k + 1) / k! for k ≥ 1, and C(u, 0) = 1. Then (1 + x)u = ∑k≥0 C(u, k) xk.

When u is a positive integer the factor (u − u) eventually appears in the numerator, so the series stops and we get the ordinary binomial theorem. For u = −k (a negative integer) it never stops. Work it out:

C(−k, n) = (−k)(−k − 1)⋯(−k − n + 1) / n!
         = (−1)ⁿ · k(k + 1)⋯(k + n − 1) / n!
         = (−1)ⁿ · C(k + n − 1, n)

Substituting −x for x cancels the sign (−1)n, which gives the most useful formula in this chapter:

1/(1 − x)k = ∑n≥0 C(n + k − 1, n) xn.

This is no accident. C(n + k − 1, n) is the number of ways to pick n items from k types with repetition allowed (stars and bars, from Permutations & Combinations). And 1/(1 − x)k is the product of k copies of 1 + x + x² + ⋯, one copy per type, each saying "take any number of this type". The algebra and the counting agree.

For example, [x10] 1/(1 − x)³ = C(12, 10) = C(12, 2) = 66.


Counting with Generating Functions

The recipe:

  1. For each object, type or person, write a series whose exponents are the allowed amounts for it.

  2. Multiply the series.

  3. The answer for a total of n is the coefficient of xn.

Worked Example 1: sharing chocolates

In how many ways can 10 identical chocolates be given to children A, B and C if A gets at least 2, B gets at most 3, and C gets an even number?

A : x² + x³ + x⁴ + ⋯        = x² / (1 − x)
B : 1 + x + x² + x³          = (1 − x⁴) / (1 − x)
C : 1 + x² + x⁴ + x⁶ + ⋯    = 1 / (1 − x²)

Answer = [x¹⁰]  x² · (1 + x + x² + x³) / ((1 − x)(1 − x²))

Pull out the x²: we need the coefficient of x8 in (1 + x + x² + x³) · 1/(1 − x) · 1/(1 − x²). Choose B's term xb first; then C takes an even c ≤ 8 − b and A takes the rest (exactly one way). Count the choices of c:

B gets b

Even values of c with c ≤ 8 − b

Count

0

0, 2, 4, 6, 8

5

1

0, 2, 4, 6

4

2

0, 2, 4, 6

4

3

0, 2, 4

3

Total: 5 + 4 + 4 + 3 = 16. A brute-force check over all (a, b, c) also gives 16.

Worked Example 2: making change

How many ways can you pay ₹10 using ₹1, ₹2 and ₹5 coins (order does not matter)?

Using c1 one-rupee coins contributes 1·c1 to the total, so its series has exponents 0, 1, 2, …. Two-rupee coins contribute 0, 2, 4, …, and five-rupee coins 0, 5, 10, …:

G(x) = 1/(1 − x) · 1/(1 − x²) · 1/(1 − x⁵)

The coefficient of x10 is 10. Here they are, written as (number of ₹1, ₹2, ₹5 coins):

(10,0,0) (8,1,0) (6,2,0) (4,3,0) (2,4,0) (0,5,0)
(5,0,1)  (3,1,1) (1,2,1)
(0,0,2)

Notice the difference from Example 1: there each child received identical units (exponents 0, 1, 2, …), here each coin type adds its value (exponents are multiples of the value).

Worked Example 3: a theorem of Euler about partitions

A partition of n writes n as an unordered sum of positive integers. Claim: the number of partitions of n into distinct parts equals the number of partitions of n into odd parts. For n = 6: distinct parts give 6, 5+1, 4+2, 3+2+1 (4 ways); odd parts give 5+1, 3+3, 3+1+1+1, 1+1+1+1+1+1 (4 ways).

Proof. In a partition into distinct parts each k is used 0 or 1 times, so the generating function is (1 + x)(1 + x²)(1 + x³)⋯. Using 1 + xk = (1 − x2k)/(1 − xk):

∏ (1 + xᵏ) = (1 − x²)(1 − x⁴)(1 − x⁶)⋯  /  (1 − x)(1 − x²)(1 − x³)(1 − x⁴)⋯
           = 1 / ((1 − x)(1 − x³)(1 − x⁵)⋯)

Every even factor in the numerator cancels the matching factor in the denominator, leaving only odd k. And 1/(1 − xk) for odd k means "use part k any number of times", which is exactly the generating function for partitions into odd parts. Equal generating functions mean equal coefficients. ∎

(A program confirms both counts agree for every n up to 20; for n = 20 both are 64.)


Solving Recurrences with Generating Functions

The method:

  1. Let A(x) = ∑ anxn.

  2. Multiply the recurrence by xn and sum over every n for which it holds.

  3. Rewrite each sum in terms of A(x) (using shifts), and solve the resulting equation for A(x).

  4. Split A(x) into partial fractions and read an from the table.

Example 1: Tower of Hanoi

an = 2an−1 + 1 for n ≥ 1, with a0 = 0.

∑ₙ≥₁ aₙ xⁿ = 2 ∑ₙ≥₁ aₙ₋₁ xⁿ + ∑ₙ≥₁ xⁿ

A(x) − a₀  = 2x A(x)       + x/(1 − x)

A(x)(1 − 2x) = x/(1 − x)          (a₀ = 0)

A(x) = x / ((1 − x)(1 − 2x)) = 1/(1 − 2x) − 1/(1 − x)

Check the partial fractions: 1/(1 − 2x) − 1/(1 − x) = ((1 − x) − (1 − 2x))/((1 − x)(1 − 2x)) = x/((1 − x)(1 − 2x)). ✓ Reading from the table: an = 2n − 1. The sequence is 0, 1, 3, 7, 15, 31, ….

Example 2: Fibonacci numbers

Fn = Fn−1 + Fn−2 for n ≥ 2, F0 = 0, F1 = 1.

∑ₙ≥₂ Fₙ xⁿ = ∑ₙ≥₂ Fₙ₋₁ xⁿ + ∑ₙ≥₂ Fₙ₋₂ xⁿ
F(x) − 0 − x = x (F(x) − 0)  + x² F(x)
F(x) = x / (1 − x − x²)

Factor 1 − x − x² = (1 − φx)(1 − ψx) where φ = (1 + √5)/2 and ψ = (1 − √5)/2 (they satisfy φ + ψ = 1 and φψ = −1). Since φ − ψ = √5,

x / ((1 − φx)(1 − ψx)) = (1/√5) · ( 1/(1 − φx) − 1/(1 − ψx) )

so Fn = (φn − ψn)/√5, the famous Binet formula, the same answer the characteristic-root method gives.

Example 3: a repeated root

an = 4an−1 − 4an−2 for n ≥ 2, a0 = 1, a1 = 4.

A(x) − 1 − 4x = 4x(A(x) − 1) − 4x² A(x)
A(x)(1 − 4x + 4x²) = 1 + 4x − 4x = 1
A(x) = 1 / (1 − 2x)²

Using 1/(1 − y)² = ∑ (n + 1)yn with y = 2x: an = (n + 1)2n, giving 1, 4, 12, 32, 80, 192, …. The square in the denominator is how a repeated characteristic root shows up.

A general fact: a linear homogeneous recurrence an = c1an−1 + ⋯ + ckan−k always has a rational generating function P(x)/Q(x), with Q(x) = 1 − c1x − c2x² − ⋯ − ckxk and a numerator P(x) of degree less than k that carries the initial conditions. The same stays true when a forcing term with a rational generating function (a polynomial in n, or sn) is added, as in the Tower of Hanoi example.

A non-linear example: Catalan numbers

The Catalan numbers satisfy C0 = 1 and Cn+1 = ∑k=0n CkCn−k. The right side is a convolution, so it is the coefficient of xn in C(x)². This gives C(x) = 1 + x · C(x)², a quadratic in C(x). Taking the root that stays finite at x = 0:

C(x) = (1 − √(1 − 4x)) / (2x) = 1 + x + 2x² + 5x³ + 14x⁴ + 42x⁵ + 132x⁶ + ⋯

Expanding √(1 − 4x) with the extended binomial theorem leads to Cn = C(2n, n)/(n + 1). Convolution recurrences like this one are where generating functions really beat the characteristic-root method, which cannot handle them at all.


Exponential Generating Functions

Ordinary generating functions suit selections where order does not matter. For arrangements (strings, permutations) we use

The exponential generating function (EGF) of a0, a1, … is E(x) = ∑n≥0 an xn/n!.

Why the n!? When two EGFs are multiplied, the coefficient works out as ∑ C(n, k) akbn−k. The binomial factor C(n, k) chooses which positions of the arrangement go to the first part, which is exactly what counting strings needs.

Example. How many strings of length n over {A, B, C} contain an even number of A's?

The EGF for "the letter A used an even number of times" is 1 + x²/2! + x⁴/4! + ⋯ = (ex + e−x)/2. B and C may be used any number of times, each giving ex. Multiply:

E(x) = (eˣ + e⁻ˣ)/2 · eˣ · eˣ = (e³ˣ + eˣ) / 2

Since eax = ∑ anxn/n!, the answer is (3n + 1)/2: 1, 2, 5, 14, 41, 122, … for n = 0, 1, 2, …. (For n = 2: AA, BB, BC, CB, CC, so 5. ✓)

Ordinary GF

Exponential GF

Form

∑ anxn

∑ anxn/n!

Counts

Selections, distributions of identical items, partitions

Arrangements, strings, labelled structures

Product means

∑ akbn−k

∑ C(n,k) akbn−k

All-ones sequence

1/(1 − x)

ex


Computing Coefficients with a Program

A power series truncated after xN is just a list of N + 1 numbers, and multiplying series is a double loop. This short program checks three results from this chapter.

N = 12  # keep coefficients of x^0 .. x^N

def mul(p, q):
    """Multiply two power series, truncated after x^N."""
    r = [0] * (N + 1)
    for i, a in enumerate(p):
        if a == 0:
            continue
        for j, b in enumerate(q):
            if i + j > N:
                break
            r[i + j] += a * b
    return r

def poly(exponents):
    """Series with coefficient 1 at each listed exponent."""
    s = [0] * (N + 1)
    for e in exponents:
        if e <= N:
            s[e] = 1
    return s

# 1. Coins of value 1, 2, 5: ways to make each amount
coins = poly([0])
for c in (1, 2, 5):
    coins = mul(coins, poly(range(0, N + 1, c)))
print("coin ways   :", coins)

# 2. 10 chocolates: A >= 2, B <= 3, C even
A = poly(range(2, N + 1))
B = poly(range(0, 4))
C = poly(range(0, N + 1, 2))
print("chocolates  :", mul(mul(A, B), C)[10])

# 3. Recurrence a(n) = 2a(n-1) + 1, a(0) = 0, from A(x) = x / ((1-x)(1-2x))
geo1 = [1] * (N + 1)                    # 1/(1-x)
geo2 = [2 ** k for k in range(N + 1)]   # 1/(1-2x)
hanoi = [0] + mul(geo1, geo2)[:N]       # multiply by x = shift right
print("Hanoi moves :", hanoi)

Output:

coin ways   : [1, 1, 2, 2, 3, 4, 5, 6, 7, 8, 10, 11, 13]
chocolates  : 16
Hanoi moves : [0, 1, 3, 7, 15, 31, 63, 127, 255, 511, 1023, 2047, 4095]

The coin list shows 10 ways for ₹10, as found by hand. This truncated-product idea is exactly the classic "coin change" dynamic-programming algorithm that appears in coding interviews: the DP table is the coefficient list of the generating function.


Common Mistakes

  • Off-by-one in 1/(1 − x)k. The coefficient of xn is C(n + k − 1, n), not C(n + k, n) or C(n + k − 1, k).

  • Forgetting to shift. If the series starts at x3 (each person gets at least 3), factor out x3 and look for a smaller coefficient.

  • Summing the recurrence over the wrong range. If an = … holds only for n ≥ 2, sum from n = 2 and subtract the first two terms (a0 + a1x) from A(x).

  • Using an ordinary GF for an ordered problem. Strings and arrangements need EGFs (or another method); the ordinary product counts unordered selections.

  • Treating x as a number. We never substitute values or worry about convergence; 1/(1 − x) just means "the series whose product with 1 − x is 1".

  • Sign errors with (1 + x)−k. 1/(1 + x)k has coefficients (−1)nC(n + k − 1, n); the signs alternate.


Interview and GATE-Style Questions

Q1. What is the coefficient of x12 in (x³ + x⁴ + x⁵ + x⁶ + ⋯)³?

(x³ + x⁴ + ⋯)³ = x⁹ · (1/(1 − x))³. We need [x³] 1/(1 − x)³ = C(3 + 2, 3) = C(5, 2) = 10. (Counting view: three people share 12 items, each at least 3; give each 3 first and share the remaining 3 freely.)

Q2. A sequence has ordinary generating function (1 + x)/(1 − x)³. Find a3 − a0.

1/(1 − x)³ has coefficients C(n + 2, 2). Multiplying by (1 + x) gives an = C(n + 2, 2) + C(n + 1, 2) = (n + 1)². So a3 = 16, a0 = 1, and a3 − a0 = 15.

Q3. Give the generating function of an = 3 · 2n + 4.

3/(1 − 2x) + 4/(1 − x). Combined: (7 − 11x)/((1 − x)(1 − 2x)).

Q4. Using generating functions, how many solutions does x1 + x2 + x3 + x4 = 10 have in non-negative integers?

[x10] 1/(1 − x)⁴ = C(10 + 3, 10) = C(13, 3) = 286, the same as stars and bars.

Q5. Which sequence has generating function 1/(1 − x − 2x²)?

1 − x − 2x² = (1 − 2x)(1 + x). Partial fractions: 1/((1 − 2x)(1 + x)) = (2/3)/(1 − 2x) + (1/3)/(1 + x). So an = (2n+1 + (−1)n)/3: 1, 1, 3, 5, 11, 21, …. It satisfies an = an−1 + 2an−2.

Q6. Why does the coefficient of xn in A(x)/(1 − x) equal a0 + ⋯ + an?

1/(1 − x) has every coefficient equal to 1, so the convolution cn = ∑ ak · 1 = a0 + a1 + ⋯ + an.


Summary

  • A generating function ∑ anxn stores a sequence as a formal power series; x is only a position marker.

  • Everything grows from 1/(1 − x) = ∑ xn; the key derived formula is 1/(1 − x)k = ∑ C(n + k − 1, n)xn.

  • Product of series = convolution of sequences = combining independent choices. For counting, write one factor per type with the allowed amounts as exponents, multiply, and read a coefficient.

  • To solve a recurrence: multiply by xn, sum, solve for A(x), use partial fractions. Initial conditions are built in.

  • Exponential generating functions ∑ anxn/n! count arrangements; ex plays the role of 1/(1 − x).

Generating functions turn counting into multiplying polynomials. The next chapter, Discrete Probability, puts those counts to work: once you can count outcomes, you can compute chances.