MGU Mathematics Series — Combinatorics
Part IV: Recurrence, Generating Functions, and Algebraic Methods
Formal Series · Coefficients · Selection Encoding · Recurrence Solving · Partitions
Chapter 11 of 14
MGU Mathematics Series  ·  Combinatorics  ·  Library Textbook Edition

Chapter 11:
Generating
Functions

Encoding sequences algebraically, extracting coefficients, multiplying to model independent selection, solving recurrences, and counting partitions — all without calculus

■ Math Level: Post-Algebra II ■

■ 14 Sections  •  Part IV of 5 ■

Follows Chapter 10: Recurrence Relations  ·  Prepares students for Chapter 12: Graph Counting and Network Structures

Chapter 11 — Front Matter

Purpose and Overview

This chapter introduces one of the most elegant tools in combinatorics: the generating function. A generating function is not a function in the ordinary sense — it is an algebraic object, a formal power series, whose coefficients carry counting information. Instead of asking "how many ways can I do this?" and immediately reaching for a formula, you can encode an entire sequence of answers into a single algebraic expression, then manipulate that expression using the rules of algebra.

This approach transforms counting problems into algebra problems. It unifies many techniques from earlier chapters — combinations, repetition, recurrences, restrictions — into a single framework. Students who understand generating functions are equipped for advanced combinatorics, discrete probability, algorithm analysis, and computer science at a level that pure formula memorization cannot reach.

This chapter introduces generating functions at an accessible, algebra-based level. No calculus is required. No convergence theory is needed. No complex analysis appears. The central idea is simple and powerful: coefficients carry counting information.

Opening Question

Suppose you want to know in how many ways you can make exactly \(n\) cents using pennies (1¢), nickels (5¢), and dimes (10¢), for every value of \(n\) simultaneously. You could solve this for each \(n\) separately, grinding through cases. Or you could encode the problem into a product of algebraic expressions and read off all the answers at once from the coefficients.

That is what generating functions do. They store an entire family of counting answers in one algebraic object and let you extract whichever answer you need.

14Sections
10Objectives
13Key Terms
7+Worked Examples

Learning Objectives

  1. 1Define a generating function and explain what its coefficients represent.
  2. 2Write the ordinary generating function for a given sequence.
  3. 3Extract specific coefficients from a generating function using algebraic reasoning.
  4. 4Add, subtract, and scale generating functions.
  5. 5Multiply generating functions and interpret the result combinatorially.
  6. 6Construct generating functions for selection problems, with and without restrictions.
  7. 7Use generating functions to solve first- and second-order linear recurrences.
  8. 8Recognize partition problems and understand how generating functions approach them.
  9. 9Connect generating functions to algebraic and probabilistic reasoning.
  10. 10Avoid common generating function errors.
Chapter 11 — Contents

Sections at a Glance

Sections 11.1 – 11.5
What Generating Functions Are and How They Work
Motivation · Sequences as Coefficients · Ordinary GFs · Coefficient Notation · Basic Forms
Section 11.1

Why Generating Functions Are Useful

Throughout this textbook, counting has meant answering one question at a time: how many arrangements exist? How many selections? How many ways to distribute objects? Each problem produced a single number.

But many counting problems form families. You might want to know not just how many ways to choose exactly 3 items, but how many ways to choose 0, 1, 2, 3, 4, and 5 items, all at once. Or you might have a recurrence relation that describes a sequence and want a formula for the general term. Or you might need to count arrangements satisfying multiple simultaneous restrictions.

In all of these situations, the same organizing idea appears: instead of computing answers one by one, encode the entire family of answers into a single algebraic expression, then extract the answer you need.

This is what generating functions do. They transform a sequence of numbers into an algebraic object. They let you use the rules of algebra — addition, multiplication, substitution, factoring — to answer counting questions that would be much harder to solve directly.

The Central Idea

The coefficient of \(x^n\) in a generating function counts the number of ways to achieve the value \(n\) in the problem the sequence encodes.

Generating functions do not require calculus. They do not require convergence analysis. They do not require complex numbers. They are formal algebraic objects: expressions that follow the rules of polynomial arithmetic, extended to allow infinitely many terms. You never substitute a real number for \(x\) and ask whether the series converges. You treat \(x\) as a formal placeholder whose powers track which value of \(n\) you are counting.

This algebraic treatment is called the formal power series approach. It is the right framework for combinatorics.

Section 11.2

Sequences as Coefficients

A sequence is an ordered list of numbers: \(a_0, a_1, a_2, a_3, \ldots\) where \(a_n\) is the term at position \(n\). In combinatorics, sequences often count things. The idea behind generating functions is to encode the sequence \(a_0, a_1, a_2, \ldots\) by placing \(a_n\) as the coefficient of \(x^n\):

$$G(x) = a_0 + a_1 x + a_2 x^2 + a_3 x^3 + \cdots = \sum_{n \geq 0} a_n x^n$$

This expression is called the ordinary generating function of the sequence \((a_n)\). The variable \(x\) is not a number. It is a formal symbol, a placeholder that tracks position in the sequence. When you see \(x^n\), you are looking at position \(n\). When you see the coefficient in front of \(x^n\), you are seeing the count for position \(n\).

Position \(n\)Count \(a_n\)Term in \(G(x)\)
0\(a_0\)\(a_0 \cdot x^0 = a_0\)
1\(a_1\)\(a_1 x\)
2\(a_2\)\(a_2 x^2\)
3\(a_3\)\(a_3 x^3\)
\(n\)\(a_n\)\(a_n x^n\)
Section 11.3

Ordinary Generating Functions

Definition — Ordinary Generating Function

Let \((a_n)_{n \geq 0} = a_0, a_1, a_2, \ldots\) be a sequence. The ordinary generating function (OGF) of this sequence is the formal power series:

\(G(x) = \displaystyle\sum_{n=0}^{\infty} a_n x^n = a_0 + a_1 x + a_2 x^2 + a_3 x^3 + \cdots\)

This is a formal expression. It is treated purely algebraically, like a polynomial with infinitely many terms. Two generating functions are equal if and only if their coefficients agree at every position.

Why "ordinary"? There are other types of generating functions, such as exponential generating functions (used in permutation problems), Dirichlet series (used in number theory), and probability generating functions (used in probability). This chapter focuses exclusively on ordinary generating functions, which are the most natural starting point and the most useful for the selection and distribution problems studied so far.

Key Fact

To prove two generating functions are equal, prove that their coefficients match at every position. This principle is used repeatedly in generating function proofs.

Section 11.4

Coefficient Notation

When working with generating functions, it is useful to have compact notation for extracting coefficients. The symbol \([x^n]\, G(x)\) means: "the coefficient of \(x^n\) in \(G(x)\)."

Example 11.0
Reading coefficients with bracket notation
  • GivenLet \(G(x) = 3 + 5x + 2x^2 + 7x^3 + \cdots\)
  • Extract \([x^0]\, G(x) = 3\)   \([x^1]\, G(x) = 5\)   \([x^2]\, G(x) = 2\)   \([x^3]\, G(x) = 7\)
The bracket notation selects exactly one coefficient at a time. This is the final step in most generating function problems.

The coefficient extraction operation \([x^n]\) is linear: \([x^n](G(x) + H(x)) = [x^n]\, G(x) + [x^n]\, H(x)\), and \([x^n](c \cdot G(x)) = c \cdot [x^n]\, G(x)\) for any constant \(c\).

Section 11.5

Basic Generating Functions

Before solving counting problems, students should know the generating functions for several fundamental sequences. These appear repeatedly throughout the chapter and beyond.

The Constant Sequence \(1, 1, 1, 1, \ldots\)

The generating function is the geometric series, with closed form:

$$G(x) = 1 + x + x^2 + x^3 + \cdots = \sum_{n \geq 0} x^n = \frac{1}{1-x}$$

The closed form is algebraically equivalent to the series: multiplying \((1-x)(1 + x + x^2 + \cdots)\) gives \(1\), which confirms the identity. The closed form is simply a compact way to write the series without infinite notation.

The Finite Geometric Series (At Most \(k\) Items)

$$G(x) = 1 + x + x^2 + \cdots + x^k = \frac{1 - x^{k+1}}{1 - x}$$

The coefficient of \(x^n\) is 1 if \(0 \leq n \leq k\) and 0 otherwise. This generating function represents choosing at most \(k\) of something.

Binomial Coefficients

From the Binomial Theorem (Chapter 5): \((1+x)^n = \sum_{k=0}^{n} \binom{n}{k} x^k\). This generating function stores all the binomial coefficients for a fixed \(n\).

Sequence \(a_n\)Generating Function \(G(x)\)
\(1, 1, 1, 1, \ldots\)\(\dfrac{1}{1-x}\)
\(1, 1, \ldots, 1, 0, 0, \ldots\) (first \(k{+}1\) terms)\(\dfrac{1 - x^{k+1}}{1-x}\)
\(1, r, r^2, r^3, \ldots\)\(\dfrac{1}{1-rx}\)
\(\binom{n}{0}, \binom{n}{1}, \ldots, \binom{n}{n}\)\((1+x)^n\)
\(0, 1, 2, 3, 4, \ldots\)\(\dfrac{x}{(1-x)^2}\)
Study Strategy

Memorize this table. These five forms — the full geometric series, the finite truncation, the scaled geometric series, the binomial expansion, and the linear sequence — appear in almost every generating function problem.

Sections 11.6 – 11.7
Operations on Generating Functions
Addition · Scaling · Shifting · Multiplication and Convolution
Section 11.6

Adding and Scaling Generating Functions

One of the great advantages of the generating function framework is that basic algebraic operations on generating functions correspond to simple operations on the sequences they encode.

Three Basic Operations

Addition: \((F+G)(x) = \sum_{n \geq 0}(a_n + b_n)x^n\) — adds coefficients termwise; combines two separate counting problems.

Scaling: \((c \cdot G)(x) = \sum_{n \geq 0}(c \cdot a_n)x^n\) — multiplies every coefficient by \(c\).

Shifting: \(x \cdot G(x) = \sum_{n \geq 1} a_{n-1} x^n\) — shifts every term one position to the right; essential for recurrence manipulation.

Example 11.1
Adding generating functions
  • ProblemItem A can be bought in 0, 1, 2, or 3 units. Item B can be bought in 0, 1, or 2 units. Find the coefficient of \(x^2\) in their combined generating function (treating this as a union: all units from one type only).
  • Represent\(F(x) = 1 + x + x^2 + x^3\) for item A; \(G(x) = 1 + x + x^2\) for item B.
  • Analyze F(x) + G(x) = (1 + x + x²+ x³) + (1 + x + x²) = 2 + 2x + 2x² + x³
  • CheckThe coefficient of \(x^2\) is 2: two ways to have exactly 2 total units (buy 2 of A, or buy 2 of B). ✓
Answer: \([x^2](F(x)+G(x)) = 2\)
Section 11.7

Multiplying Generating Functions

Multiplication is the most important operation on generating functions, and it directly models one of the most common combinatorial situations: making independent choices from separate sources and combining the results.

The Product Rule for Generating Functions

If \(F(x) = \sum_{n \geq 0} a_n x^n\) and \(G(x) = \sum_{n \geq 0} b_n x^n\), then:

\(F(x) \cdot G(x) = \sum_{n \geq 0} c_n x^n \quad \text{where} \quad c_n = \sum_{k=0}^{n} a_k\, b_{n-k}\)

This formula is called the convolution of the sequences. The coefficient \(c_n\) counts the number of ways to split \(n\) into two parts \(k\) and \(n-k\), choosing \(k\) from the first source and \(n-k\) from the second.

Why does multiplication model independent selection? Suppose you are choosing a total of \(n\) objects from two independent sources A and B. For each way to take \(k\) from A and \(n-k\) from B, you get one combined selection of size \(n\). Summing over all valid splits gives the convolution formula. Multiplication of generating functions encodes this structure automatically.

Example 11.2
Multiplying two generating functions
  • ProblemA student can choose 0, 1, or 2 chocolate candies, and independently choose 0, 1, 2, or 3 gummy candies. In how many ways can the student choose exactly 3 candies total?
  • Represent\(F(x) = 1 + x + x^2\) (chocolate)    \(G(x) = 1 + x + x^2 + x^3\) (gummy)
  • Analyze F(x)·G(x) = (1 + x + x²)(1 + x + x² + x³) = (1 + x + x² + x³) + (x + x² + x³ + x⁴) + (x² + x³ + x⁴ + x⁵) = 1 + 2x + 3x² + 3x³ + 2x⁴ + x⁵
  • CheckThe three ways to get 3 total: (0 choc, 3 gummy), (1 choc, 2 gummy), (2 choc, 1 gummy). That is 3 ways. ✓
  • InterpretThere are 3 ways to choose exactly 3 candies with these restrictions.
Answer: \([x^3](F(x)\cdot G(x)) = 3\)
Student Warning — Addition vs. Multiplication

Addition of generating functions combines alternative choices from separate cases (the sum rule). Multiplication combines independent choices that are made simultaneously (the product rule). A common error is multiplying when you should add, or adding when you should multiply. Always ask: are the two selections made independently (multiply) or are they alternatives (add)?

Sections 11.8 – 11.9
Selections and Restrictions
Unrestricted Selection · Multi-Type Products · Stars and Bars · Restrictions
Section 11.8

Generating Functions for Selections

One of the most natural applications of generating functions is encoding selection problems: counting the number of ways to choose objects from a set, possibly with restrictions on how many of each type you may take.

Selection RuleGenerating Function Factor
Any number from an unlimited supply\(\dfrac{1}{1-x}\)
At most \(k\) items\(1 + x + x^2 + \cdots + x^k = \dfrac{1-x^{k+1}}{1-x}\)
Unlimited supply of \(m\) types combined\(\left(\dfrac{1}{1-x}\right)^m\)
Connection to Stars and Bars (Chapter 6)

The coefficient of \(x^n\) in \(\frac{1}{(1-x)^k}\) is \(\binom{n+k-1}{k-1}\), precisely the stars-and-bars count for choosing \(n\) objects from \(k\) types with unlimited repetition. Generating functions unify the Chapter 6 formula with an algebraic identity.

Example 11.3
Setting up a selection generating function
  • ProblemA baker can use up to 3 cups of flour, up to 2 cups of sugar, and any number of cups of oats. How many ways can the baker choose exactly 4 cups of ingredients total?
  • Represent Flour (0–3): \(F(x) = 1 + x + x^2 + x^3 = \dfrac{1-x^4}{1-x}\)
    Sugar (0–2): \(S(x) = 1 + x + x^2 = \dfrac{1-x^3}{1-x}\)
    Oats (unlimited): \(O(x) = \dfrac{1}{1-x}\)
  • Analyze G(x) = F(x)·S(x)·O(x) = (1-x⁴)(1-x³) / (1-x)³ Numerator: (1-x³-x⁴+x⁷) [x⁴] G(x) = C(6,2) - C(3,2) - C(2,2) = 15 - 3 - 1 = 11 (using \([x^n]\frac{1}{(1-x)^3} = \binom{n+2}{2}\))
  • CheckThe last numerator term \(x^7\) contributes 0 to \([x^4]\) since \(7 > 4\). ✓
  • InterpretThere are 11 ways for the baker to use exactly 4 cups of ingredients under these restrictions.
Answer: 11 ways
Section 11.9

Generating Functions with Restrictions

To impose a restriction on one type of object, change its factor in the product. The coefficient of \(x^n\) in the full product then automatically accounts for all the restrictions.

Restriction on One TypeGenerating Function Factor
At least \(m\) items\(\dfrac{x^m}{1-x} = x^m + x^{m+1} + x^{m+2} + \cdots\)
Even quantities only (0, 2, 4, …)\(\dfrac{1}{1-x^2} = 1 + x^2 + x^4 + \cdots\)
Odd quantities only (1, 3, 5, …)\(\dfrac{x}{1-x^2} = x + x^3 + x^5 + \cdots\)
Multiples of \(k\) only\(\dfrac{1}{1-x^k} = 1 + x^k + x^{2k} + \cdots\)
Example 11.4
Counting with restrictions — direct enumeration
  • ProblemHow many ways are there to select exactly 7 objects from three types, where type A uses an even number, type B uses an odd number, and type C uses any amount?
  • Represent\(A(x) = \dfrac{1}{1-x^2}\), \(\quad B(x) = \dfrac{x}{1-x^2}\), \(\quad C(x) = \dfrac{1}{1-x}\)
  • Analyze Enumerate all \((a,b,c)\) with \(a\) even, \(b\) odd, \(a+b+c = 7\): a b c 0 1 6 0 3 4 0 5 2 0 7 0 2 1 4 2 3 2 2 5 0 4 1 2 4 3 0 6 1 0
  • CheckAll entries have \(a\) even, \(b\) odd, \(c \geq 0\), and \(a+b+c = 7\). Ten rows total. ✓
  • InterpretThere are 10 ways to select exactly 7 objects under these restrictions.
Answer: 10 ways
Practical Note

For more complex restriction products, extracting coefficients may require partial fractions or a computer algebra system. At this level, either direct enumeration (as above) or careful polynomial multiplication is always a valid verification strategy.

Section 11.10
Solving Recurrences with Generating Functions
The Algebraic Strategy · First-Order Example · Fibonacci Recurrence
Section 11.10

Solving Recurrences with Generating Functions

In Chapter 10, recurrence relations were solved using characteristic equations and pattern recognition. Generating functions offer an alternative algebraic approach: translate the recurrence into an equation involving \(G(x)\), solve for \(G(x)\) in closed form, then extract the coefficient of \(x^n\).

The General Strategy

1. Let \(G(x) = \sum_{n \geq 0} a_n x^n\).

2. Multiply the recurrence by \(x^n\) and sum over the valid range of \(n\).

3. Express each sum in terms of \(G(x)\) using shift operations.

4. Solve the resulting algebraic equation for \(G(x)\).

5. Write \(G(x)\) in a recognizable form (geometric series, partial fractions).

6. Extract the coefficient of \(x^n\) to read off the closed form.

Example 11.5
Solving a first-order recurrence
  • ProblemSolve the recurrence \(a_n = 3a_{n-1}\) with \(a_0 = 2\).
  • RepresentLet \(G(x) = \sum_{n \geq 0} a_n x^n\). Multiply \(a_n = 3a_{n-1}\) by \(x^n\) and sum for \(n \geq 1\).
  • Analyze Left side: Σ aₙxⁿ = G(x) - a₀ = G(x) - 2 (n≥1) Right side: 3 Σ aₙ₋₁xⁿ = 3x Σ aₘxᵐ = 3x·G(x) (n≥1) (m≥0) So: G(x) - 2 = 3x·G(x) G(x)(1 - 3x) = 2 G(x) = 2/(1 - 3x) Since \(\frac{1}{1-3x} = \sum_{n \geq 0} 3^n x^n\), we get \(G(x) = \sum_{n \geq 0} 2\cdot 3^n x^n\).
  • Check\(a_0 = 2\cdot 3^0 = 2\) ✓,   \(a_1 = 2\cdot 3^1 = 6 = 3\cdot 2\) ✓,   \(a_2 = 18 = 3\cdot 6\) ✓.
  • InterpretThe sequence is \(a_n = 2 \cdot 3^n\).
Answer: \(a_n = 2 \cdot 3^n\)
Example 11.6
Solving the Fibonacci recurrence
  • ProblemLet \(F_0 = 0\), \(F_1 = 1\), and \(F_n = F_{n-1} + F_{n-2}\) for \(n \geq 2\). Find the generating function for \((F_n)\).
  • Represent\(G(x) = \sum_{n \geq 0} F_n x^n = 0 + x + x^2 + 2x^3 + 3x^4 + 5x^5 + \cdots\)
  • Analyze Multiply \(F_n = F_{n-1} + F_{n-2}\) by \(x^n\) and sum for \(n \geq 2\): Left: G(x) - F₀ - F₁x = G(x) - x Right: x·G(x) + x²·G(x) So: G(x) - x = xG(x) + x²G(x) G(x)(1 - x - x²) = x G(x) = x / (1 - x - x²)
  • CheckExpanding gives \(x(1 + x + 2x^2 + 3x^3 + 5x^4 + \cdots)\) — matches the Fibonacci sequence. ✓
  • InterpretThe compact expression \(\frac{x}{1-x-x^2}\) encodes all Fibonacci numbers simultaneously as coefficients.
Answer: \(G(x) = \dfrac{x}{1 - x - x^2}\)
MGU Library Connection
  • The Fibonacci generating function appears in Discrete Mathematics, Chapter 8: Sequences and Recurrences
  • Probability generating functions for random variables are developed in the Probability and Statistics textbook, Chapter 7
  • Algorithm analysis using generating functions is covered in the MGU Algorithms course
  • The Binet formula, derived from partial fractions applied to the Fibonacci GF, appears in the MGU Advanced Combinatorics preview
Section 11.11
Partition Problems
Definition · Partition Generating Function · Restricted Partitions
Section 11.11

Partition Problems as an Introduction

A partition of a positive integer \(n\) is a way of writing \(n\) as a sum of positive integers, where the order of the summands does not matter. For example, the partitions of 4 are:

\(4\)   ·   \(3+1\)   ·   \(2+2\)   ·   \(2+1+1\)   ·   \(1+1+1+1\)

So the number of partitions of 4 is \(p(4) = 5\). Partition problems are counting problems where order does not matter and repetition is allowed — making them naturally suited to generating functions.

The Generating Function for Unrestricted Partitions

A partition of \(n\) uses some number of 1s, some number of 2s, some number of 3s, and so on. The generating function for the number of times \(k\) may appear is \(\frac{1}{1-x^k}\). The full generating function for all partitions is the infinite product:

$$P(x) = \prod_{k=1}^{\infty} \frac{1}{1-x^k} = \frac{1}{(1-x)(1-x^2)(1-x^3)(1-x^4)\cdots}$$

The coefficient of \(x^n\) in \(P(x)\) is \(p(n)\), the number of partitions of \(n\). To compute \(p(n)\) for a specific value, you only need factors up to \(k = n\), making the computation finite.

Partition vs. Composition

A partition treats \(2+3\) and \(3+2\) as the same. A composition treats them as different. Generating functions for partitions use factors \(\frac{1}{1-x^k}\) (unlimited copies of each part). Generating functions for compositions use a different setup. Always identify which type of problem you have before building the product.

Example 11.7
Counting partitions using a partial product
  • ProblemFind the number of ways to partition 5 using only parts of size 1, 2, or 3.
  • Represent\(G(x) = \dfrac{1}{1-x} \cdot \dfrac{1}{1-x^2} \cdot \dfrac{1}{1-x^3}\)
  • Analyze Expand each factor to degree 5 and multiply step by step: Step 1: 1/(1-x) · 1/(1-x²) — collect coefficients bₙ up to n=5: n=0: 1 n=1: 1 n=2: 1+1=2 n=3: 1+1=2 n=4: 1+1+1=3 n=5: 1+1+1=3 Step 2: multiply by 1/(1-x³) = 1 + x³ + x⁶ + ... [x⁵]: b₅ + b₂ = 3 + 2 = 5
  • CheckList directly: \(3+2,\ 3+1+1,\ 2+2+1,\ 2+1+1+1,\ 1+1+1+1+1\). Five partitions. ✓
  • InterpretThere are 5 ways to write 5 as a sum of positive integers using only 1s, 2s, and 3s.
Answer: 5 partitions
Section 11.12

Generating Functions in Algebra and Probability

Connection to algebra. When the sequence \((a_n)\) has only finitely many nonzero terms, the generating function is a polynomial. The Binomial Theorem is an example: the generating function for \(\binom{n}{0}, \binom{n}{1}, \ldots, \binom{n}{n}\) is \((1+x)^n\), a polynomial of degree \(n\). When the sequence is infinite, the generating function is a formal power series, but algebraic operations still work exactly as for polynomials.

Connection to probability. Probability generating functions (PGFs) encode the distribution of a discrete random variable. If \(X\) takes values \(0, 1, 2, \ldots\) with probabilities \(p_0, p_1, p_2, \ldots\), then \(G_X(x) = \sum_{n \geq 0} p_n x^n\). Operations on PGFs — multiplication for independent sums, shifting for shifted random variables — parallel exactly the operations in this chapter.

Connection to algorithm analysis. Generating functions appear in counting paths in recursive structures, computing expected values of algorithm complexity, and analyzing data structures. The Fibonacci generating function, for instance, appears in the analysis of certain recursive algorithms.

MGU Library Connection
  • Probability generating functions: MGU Probability and Statistics, Chapter 7
  • Algorithm analysis with generating functions: MGU Algorithms course
  • Partition generating functions and the function \(p(n)\): MGU Number Theory and Cryptography preview
Sections 11.13 – 11.14
Mistakes to Avoid and the Road Ahead
Seven Common Errors · Readiness Checklist · Bridge to Part V
Section 11.13

Common Generating Function Mistakes

Mistake 1 — Treating generating functions as calculus functions
Substitute x = 2 into G(x) to find a specific value

Correct approach: Generating functions are formal algebraic objects. Never substitute a real number and check convergence. Extract coefficients algebraically using \([x^n]\).

Mistake 2 — Forgetting the coefficient extraction step
"The generating function is the answer."

Correct approach: The generating function stores the answers. The answer to a specific question is the coefficient \([x^n]\, G(x)\). Always complete this final extraction step.

Mistake 3 — Using the wrong factor for a restriction
Using 1/(1-x) when the restriction says "at most 3" or "even numbers only"

Correct approach: Each restriction requires its own factor. State explicitly what values of \(n\) are allowed, then write the corresponding series. Consult the restriction table in Section 11.9.

Mistake 4 — Confusing multiplication with addition
Adding generating functions for two independent simultaneous selections

Correct approach: Independent choices → multiply. Alternative cases → add. Always identify the structure before choosing the operation.

Mistake 5 — Incorrect convolution
[x^n](F·G) = [x^n]F · [x^n]G

Correct: \([x^n](F \cdot G) = \sum_{k=0}^n a_k b_{n-k}\). Coefficients are not multiplied pointwise — they are convolved. Always expand the product term by term to verify small cases.

Mistake 6 — Premature truncation
Expanding to degree n-1 when looking for the coefficient of x^n

Correct approach: Always expand to at least degree \(n\) when extracting \([x^n]\). Higher-degree numerator terms may shift down and contribute to lower-order coefficients.

Mistake 7 — Confusing partitions with compositions
Using the partition generating function when order matters (compositions)

Correct approach: Partitions ignore order (\(2+3\) and \(3+2\) are the same). Compositions count order. These require different generating function setups. Always determine whether order matters before building the product.

Section 11.14

Preparing for Graphs and Designs

Chapter 11 concludes Part IV. The three algebraic methods of Part IV — recurrence relations (Chapter 10), generating functions (Chapter 11), and the combinatorial proofs from Chapter 9 — form the algebraic backbone of combinatorics at the post-Algebra II level.

Part V now moves into combinatorial structures: graphs (Chapter 12), designs and symmetry (Chapter 13), and the capstone (Chapter 14). These chapters apply counting tools — including generating functions — to finite relationship structures, symmetric arrangements, and integrated modeling problems.

Chapter 11 Readiness Checklist

Before moving to Chapter 12, confirm you can do all of the following:

☐   Read and write generating functions for sequences using correct notation

☐   Extract coefficients using \([x^n]\) notation

☐   Multiply generating functions to model independent selections

☐   Choose the correct factor for common restrictions (at most \(k\), even, odd, at least \(m\))

☐   Use the generating function method to solve a first-order linear recurrence

☐   Connect the generating function framework to partition problems

☐   Explain clearly that generating functions are formal algebraic objects, not calculus functions

MGU Library Connection
  • Generating functions for graph counting (Tutte polynomial, chromatic polynomials): MGU Graph Theory reference
  • Generating functions for coding theory and cryptography: MGU Cryptography and Coding Theory course
  • Generating functions for machine learning model evaluation: MGU Machine Learning Mathematics course
Chapter 11 — Back Matter

Chapter Summary

Key Terms Review

generating function
A formal power series \(G(x) = \sum a_n x^n\) whose coefficients encode a sequence of numbers, typically counting information.
formal power series
An algebraic expression \(\sum_{n \geq 0} a_n x^n\) treated purely algebraically, with no reference to convergence or limits.
coefficient
The number \(a_n\) in front of \(x^n\) in a power series. In a generating function, it carries the counting information for value \(n\).
ordinary GF (OGF)
The standard generating function \(G(x) = \sum_{n \geq 0} a_n x^n\), as opposed to exponential, Dirichlet, or probability generating functions.
coefficient extraction
The operation \([x^n]\, G(x)\), which selects the coefficient of \(x^n\) from a generating function \(G(x)\).
convolution
The formula \(c_n = \sum_{k=0}^n a_k b_{n-k}\), giving the coefficient of \(x^n\) in the product \(F(x) \cdot G(x)\).
closed form
A compact algebraic expression for a generating function, such as \(\frac{1}{1-x}\) instead of \(1 + x + x^2 + \cdots\)
geometric series
The series \(1 + x + x^2 + \cdots = \frac{1}{1-x}\); the generating function for the constant sequence \(1, 1, 1, \ldots\)
recurrence (via GF)
A recurrence relation translated into a generating function equation; solving the equation gives the closed form for the sequence.
partition
A way of writing a positive integer as an unordered sum of positive integers. Order does not matter: \(2+3\) and \(3+2\) are the same partition.
partition number \(p(n)\)
The number of partitions of \(n\); the coefficient of \(x^n\) in the generating function \(\prod_{k \geq 1} \frac{1}{1-x^k}\).
restricted GF factor
A generating function factor chosen to reflect a constraint: even quantities, minimum required, multiples of \(k\), etc.
product of GFs
The generating function formed by multiplying two or more series, modeling independent selection from each corresponding source.

Concept Review Questions

  1. What is a generating function, and why is it described as a "formal" power series? What does this mean in practice?
  2. What does the coefficient of \(x^n\) in a generating function represent in a counting problem?
  3. Why does multiplying two generating functions correspond to counting independent selections? Use a small example to explain the convolution.
  4. Explain why \(\frac{1}{1-x^2} = 1 + x^2 + x^4 + \cdots\) is the generating function for "an even number of items."
  5. What is the generating function for the sequence \(1, 1, 1, 1, \ldots\)? For the sequence \(1, 2, 4, 8, \ldots\)?
  6. What is a partition? How is it different from a composition (an ordered sum)?
  7. How does the generating function approach to recurrences compare to the characteristic equation approach from Chapter 10?
  8. Explain the error in the following claim: "Since \(\frac{1}{1-x} = 1 + x + x^2 + \cdots\), substituting \(x = 2\) gives \(\frac{1}{1-2} = -1\), so \(1 + 2 + 4 + 8 + \cdots = -1\)." What is wrong with this reasoning for generating functions?

Skill Practice

Part AIdentifying and Reading Coefficients
  1. Write the first five terms of \(\frac{1}{1-2x}\) and identify the coefficient pattern.
  2. Write the first six terms of \((1+x)^5\) and verify the coefficients are \(\binom{5}{k}\).
  3. What is the generating function for the sequence \(3, 3, 3, 3, \ldots\)?
  4. What is the generating function for \(1, 0, 1, 0, 1, 0, \ldots\) (1 at even positions, 0 at odd)?
  5. \([x^0]\, G(x)\), \([x^2]\, G(x)\), \([x^4]\, G(x)\) where \(G(x) = 2 + 3x - x^2 + 5x^3 + 7x^5\)
  6. Write the generating function for \(0, 1, 0, 1, 0, 1, \ldots\) (1 at odd positions, 0 at even).
Part BSetting Up Generating Functions
  1. Write the GF for choosing at most 5 objects of one type.
  2. Write the GF for choosing an even number of objects (unlimited supply).
  3. Write the GF for choosing at least 2 objects (unlimited supply).
  4. Write the GF for choosing a quantity that is a multiple of 3.
  5. Write the product GF for: type A at most 4, type B even (unlimited), type C any amount.
  6. Find \([x^4](1 + x + x^2 + x^3 + x^4)^2\).
Part CCoefficient Extraction
  1. \([x^3]\,\frac{1}{(1-x)^2}\)   (recall \([x^n]\frac{1}{(1-x)^2} = n+1\))
  2. \([x^5]\,\frac{1}{(1-x)^3}\)   (recall \([x^n]\frac{1}{(1-x)^3} = \binom{n+2}{2}\))
  3. \([x^4](1+x)^6\)
  4. \([x^5](1+x+x^2)^3\) by expansion
  5. \([x^6](1+x+x^2+x^3)^2\)
  6. \([x^5]\,\frac{1}{(1-x)(1-x^2)}\) — interpret as a partition count

Applications

  1. Coin change. Using pennies (1¢), nickels (5¢), and dimes (10¢), write the generating function that encodes the number of ways to make exactly \(n\) cents. Find the coefficient of \(x^8\) (how many ways to make 8¢).
  2. Quiz scoring. A quiz has 10 questions. A student scores 0, 1, or 2 on each question. How many ways are there to score exactly 12 points total? Set up the generating function and find \([x^{12}]\).
  3. Bookshelf. Fill a shelf with exactly 6 books from two types (A and B). You must use an even number of type A and at least 1 of type B. Write the generating function and find the count.
  4. Scheduling. A manager needs exactly 10 workers: Group A (at least 2, at most 5), Group B (0 to 4), Group C (0 to 6). Write the generating function and find the number of valid assignments.
  5. Partition identification. List all partitions of 6 using parts of size 1, 2, or 3. Verify using \([x^6]\frac{1}{(1-x)(1-x^2)(1-x^3)}\).
  6. Algorithm analysis preview. A recursive algorithm has \(T(n) = T(n-1) + 1\), \(T(0) = 0\). Solve using a generating function and interpret the result.
RecurrenceGenerating Function Approach
  1. Solve \(a_n = 2a_{n-1}\), \(a_0 = 5\) using a generating function.
  2. Set up the generating function equation for \(a_n = a_{n-1} + 2a_{n-2}\), \(a_0 = 0\), \(a_1 = 1\). Find \(G(x)\) in closed form.
  3. Verify that the Fibonacci generating function \(G(x) = \frac{x}{1-x-x^2}\) gives \(F_5 = 5\) by expanding the series to the \(x^5\) term.
  4. Show algebraically that \([x^n]\frac{1}{(1-x)^2} = n+1\) by writing \((1-x)^2 \cdot G(x) = 1\) and solving for the coefficients.

Error Analysis

Each problem shows a student's work. Identify the error and write the correct approach.

Problem 1
"To count selections of exactly 5 from type A (0–3 times) and type B (0–4 times), I used G(x) = (1+x+x²+x³) + (1+x+x²+x³+x⁴)."

What is wrong? What is the correct generating function and how should the coefficient of \(x^5\) be found?

Problem 2
"The coefficient of x³ in 1/(1-x) is 3, because the third term of the sequence is 3."

Identify the error. What is the generating function \(\frac{1}{1-x}\) and what are its coefficients?

Problem 3
"To solve aₙ = 3aₙ₋₁ with a₀ = 1, I substituted x = 3 into G(x) = 1/(1-3x) and got G(3) = -1/8."

What is the fundamental error here? How should generating functions be used to find \(a_n\)?

Problem 4
"The generating function for partitions into parts of size at most 3 is (1+x¹)(1+x²)(1+x³)."

What does this expression actually count? Write the correct generating function for unrestricted use of parts of size 1, 2, or 3.

Problem 5
"The coefficient of x⁴ in (1+x+x²)² is 1·1 = 1."

Apply the convolution formula correctly to find \([x^4](1+x+x^2)^2\).

Chapter 11 Checkpoint

Chapter 11 Checkpoint
Complete without assistance — assesses all key skills and concepts from Chapter 11
Part A — Concepts
  1. Define a formal power series generating function in your own words. What does the coefficient of \(x^n\) represent?
  2. Explain why multiplying two generating functions models independent selection from two sources. Give a concrete example.
  3. What is the difference between a partition of \(n\) and a composition of \(n\)? How does this affect the generating function setup?
Part B — Skills
  1. Write the generating function for the sequence \(0, 1, 0, 1, 0, 1, \ldots\) (1 at odd positions, 0 at even).
  2. Find \([x^4](1 + x + x^2)^3\).
  3. Using \((1 + x + x^2 + x^3)(1 + x + x^2 + x^3 + x^4)\), find the coefficient of \(x^5\).
  4. Solve the recurrence \(a_n = 5a_{n-1}\), \(a_0 = 3\), using a generating function.
Part C — Applications and Modeling
  1. A store sells three types of candy: chocolate (at least 1, at most 4), gummy (any even number from 0 to 6), and lollipops (any amount). Write the generating function that counts the ways to buy exactly \(n\) total candies.
  2. Find the number of partitions of 7 using only parts of size 1 and 2. Set up the generating function and extract the coefficient of \(x^7\).
  3. A student scores heights as S = 1, A = 2, T = 3. Two children's heights are chosen independently. In how many ways does the combined score equal exactly 4? Write the generating function product and find the count.
Part D — Reasoning
  1. Explain the error: "Since \(\frac{1}{1-x} = 1 + x + x^2 + \cdots\), substituting \(x = 2\) gives \(1 + 2 + 4 + \cdots = -1\)." What is wrong with this in the context of generating functions?
  2. Explain why the generating function for partitions into distinct parts is \((1+x)(1+x^2)(1+x^3)\cdots\), while the generating function for unrestricted partitions is \(\frac{1}{(1-x)(1-x^2)(1-x^3)\cdots}\). What structural difference leads to these two product forms?
Looking Ahead
Part V: Graphs, Designs, and Capstone Applications

Chapter 11 completes the algebraic toolkit of Part IV. The next section of the book — Part V — applies all of the counting tools developed so far to combinatorial structures. Chapter 12 studies graph counting: vertices, edges, degrees, trees, paths, and cycles viewed as finite combinatorial objects. Chapter 13 introduces designs, Latin squares, symmetry, and Burnside's Lemma. Chapter 14 is the capstone, integrating every method — direct counting, recurrences, generating functions, graphs, and designs — into modeling problems. The generating function ideas from this chapter will reappear in Chapter 14 as part of the complete combinatorial modeling toolkit.

MGU Library Connection
  • Generating Function Reference — Appendix N of this textbook
  • Recurrence Relation Reference — Appendix M of this textbook
  • Binomial Coefficient Reference — Appendix C of this textbook
  • MGU Discrete Mathematics, Chapter 8: Sequences and Recurrences
  • MGU Probability and Statistics, Chapter 7: Probability Generating Functions
  • MGU Algorithms: Analysis of Recursive Algorithms
  • MGU Number Theory and Cryptography: The Partition Function
  • MGU Dictionary entries: generating function, formal power series, coefficient, partition, convolution