26-08 — Generating Functions

Phase: Combinatorics | Subject: 26-08 Prerequisites: 26-07-recurrence-relations.md, 03-07-sequences-and-series.md Next subject: 26-09-graph-theory-basics.md

Learning Objectives

By the end of this subject, you will be able to:

1. Define ordinary generating functions (OGFs) and exponential generating functions (EGFs)
2. Derive generating functions for common sequences
3. Solve recurrence relations using generating functions
4. Extract coefficients from generating functions
5. Apply generating functions to partition problems

Core Content

Ordinary Generating Functions (OGF)

The ordinary generating function of a sequence ${a_n}_{n=0}^{\infty}$ is:

$$A(x) = \sum_{n=0}^{\infty} a_n x^n$$

The coefficient $a_n = [x^n]A(x)$.

Key Idea: Operations on sequences correspond to algebraic operations on generating functions. This turns combinatorial problems into algebraic ones.

Common OGFs

Operations on OGFs

Let $A(x) = \sum a_n x^n$, $B(x) = \sum b_n x^n$.

• Addition: $A(x) + B(x) \longleftrightarrow a_n + b_n$
• Multiplication (Convolution): $A(x)B(x) \longleftrightarrow \sum_{k=0}^n a_k b_{n-k}$
• Scaling: $A(cx) \longleftrightarrow c^n a_n$
• Differentiation: $A'(x) \longleftrightarrow (n+1)a_{n+1}$
• Integration: $\int_0^x A(t) dt \longleftrightarrow a_{n-1}/n$ (for $n \geq 1$)

Solving Recurrences with Generating Functions

Recipe: 1. Write the recurrence for all $n \geq$ something 2. Multiply both sides by $x^n$ and sum from $n$ to $\infty$ 3. Express sums in terms of $A(x)$ and known series 4. Solve for $A(x)$ as a rational function 5. Partial fraction decomposition + coefficient extraction

Example (Fibonacci): $F_{n+2} = F_{n+1} + F_n, F_0 = 0, F_1 = 1$. $\sum F_{n+2} x^n = \sum F_{n+1} x^n + \sum F_n x^n$ $(F(x) - x)/x^2 = (F(x))/x + F(x)$ $F(x) = \frac{x}{1 - x - x^2}$.

Exponential Generating Functions (EGF)

$$E(x) = \sum_{n=0}^{\infty} a_n \frac{x^n}{n!}$$

EGFs are useful when the recurrence involves binomial coefficients or when counting labeled structures (e.g., permutations, set partitions).

Example: Bell numbers $B_n$ (partitions of an $n$-element set) have EGF: $B(x) = e^{e^x - 1}$.

Integer Partitions

Let $p(n)$ = number of partitions of $n$ (ways to write $n$ as sum of positive integers, order irrelevant).

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

Key Terms

• Ordinary Generating Function (OGF)
• Exponential Generating Function (EGF)
• Convolution
• Coefficient Extraction
• Integer Partitions

Worked Examples

Example 1: Solve $a_n = 2a_{n-1} + 1, a_0 = 0$ using OGF

Solution: $a_n = 2a_{n-1} + 1$ for $n \geq 1$, $a_0 = 0$. Multiply by $x^n$, sum $n \geq 1$: $\sum_{n \geq 1} a_n x^n = 2\sum_{n \geq 1} a_{n-1} x^n + \sum_{n \geq 1} x^n$ $A(x) - 0 = 2x A(x) + \frac{x}{1-x}$ $A(x)(1 - 2x) = \frac{x}{1-x}$ $A(x) = \frac{x}{(1-x)(1-2x)} = \frac{1}{1-2x} - \frac{1}{1-x}$ $a_n = 2^n - 1$.

Example 2: Coefficient Extraction

Find $[x^5]$ in $\frac{1}{(1-x)^3}$.

Solution: $\frac{1}{(1-x)^3} = \sum_{n=0}^{\infty} \binom{n+2}{2} x^n$. $[x^5] = \binom{7}{2} = 21$.

Example 3: Convolution

Find the generating function for partial sums: $b_n = \sum_{k=0}^n a_k$.

Solution: $b_n = \sum_{k=0}^n a_k \cdot 1$. This is convolution of ${a_n}$ with ${1}$. $B(x) = A(x) \cdot \frac{1}{1-x}$.

Quiz

Q1: What does the concept of Ordinary Generating Function (OGF) primarily refer to in this subject?

A) A computational error related to Ordinary Generating Function (OGF) B) A visual representation of Ordinary Generating Function (OGF) C) A historical anecdote about Ordinary Generating Function (OGF) D) The definition and application of Ordinary Generating Function (OGF)

Correct: D)

• If you chose A: This is incorrect. Ordinary Generating Function (OGF) is defined as: the definition and application of ordinary generating function (ogf). The other options describe different aspects that are not the primary focus.
• If you chose B: This is incorrect. Ordinary Generating Function (OGF) is defined as: the definition and application of ordinary generating function (ogf). The other options describe different aspects that are not the primary focus.
• If you chose C: This is incorrect. Ordinary Generating Function (OGF) is defined as: the definition and application of ordinary generating function (ogf). The other options describe different aspects that are not the primary focus.
• If you chose D: Ordinary Generating Function (OGF) is defined as: the definition and application of ordinary generating function (ogf). The other options describe different aspects that are not the primary focus. Correct!

Q2: Which of the following is the key formula discussed in this subject?

A) \{a_n\}{n=0}^{\infty} B) The inverse operation of the formula in question C) A simplified version of \{a_n\}{n=0}^{\infty}... D) An unrelated formula from a different topic

Correct: A)

• If you chose A: The formula \{a_n\}_{n=0}^{\infty} is central to this subject. The other options are either simplified versions or unrelated. Correct!
• If you chose B: This is incorrect. The formula \{a_n\}_{n=0}^{\infty} is central to this subject. The other options are either simplified versions or unrelated.
• If you chose C: This is incorrect. The formula \{a_n\}_{n=0}^{\infty} is central to this subject. The other options are either simplified versions or unrelated.
• If you chose D: This is incorrect. The formula \{a_n\}_{n=0}^{\infty} is central to this subject. The other options are either simplified versions or unrelated.

Q3: What is the primary purpose of Exponential Generating Function (EGF)?

A) It is primarily a historical notation system B) It is used only in advanced research contexts C) It is used to exponential generating function (egf) in mathematical analysis D) It replaces all other methods in this domain

Correct: C)

• If you chose A: This is incorrect. Exponential Generating Function (EGF) serves the purpose described in the correct answer. The other options misrepresent its role.
• If you chose B: This is incorrect. Exponential Generating Function (EGF) serves the purpose described in the correct answer. The other options misrepresent its role.
• If you chose C: Exponential Generating Function (EGF) serves the purpose described in the correct answer. The other options misrepresent its role. Correct!
• If you chose D: This is incorrect. Exponential Generating Function (EGF) serves the purpose described in the correct answer. The other options misrepresent its role.

Q4: Which statement about Convolution is TRUE?

A) Convolution is a fundamental concept covered in this subject B) Convolution is mentioned only as a historical footnote C) Convolution is an advanced topic beyond this subject's scope D) Convolution is not related to this subject

Correct: A)

• If you chose A: Convolution is a fundamental concept covered in this subject. This subject covers Convolution as part of its core content. Correct!
• If you chose B: This is incorrect. Convolution is a fundamental concept covered in this subject. This subject covers Convolution as part of its core content.
• If you chose C: This is incorrect. Convolution is a fundamental concept covered in this subject. This subject covers Convolution as part of its core content.
• If you chose D: This is incorrect. Convolution is a fundamental concept covered in this subject. This subject covers Convolution as part of its core content.

Q5: Based on the worked examples in this subject, what is the correct result?

A) A different result from a common mistake B) The inverse of the correct answer C) An unrelated numerical value D) Coefficient Extraction

Correct: D)

• If you chose A: This is incorrect. The worked examples show that the result is Coefficient Extraction. The other options represent common errors.
• If you chose B: This is incorrect. The worked examples show that the result is Coefficient Extraction. The other options represent common errors.
• If you chose C: This is incorrect. The worked examples show that the result is Coefficient Extraction. The other options represent common errors.
• If you chose D: The worked examples show that the result is Coefficient Extraction. The other options represent common errors. Correct!

Q6: How are Convolution and Coefficient Extraction related?

A) Convolution is the inverse of Coefficient Extraction B) Convolution is a special case of Coefficient Extraction C) Convolution and Coefficient Extraction are closely related concepts D) Convolution and Coefficient Extraction are completely unrelated topics

Correct: C)

• If you chose A: This is incorrect. Both Convolution and Coefficient Extraction are covered in this subject as interconnected topics.
• If you chose B: This is incorrect. Both Convolution and Coefficient Extraction are covered in this subject as interconnected topics.
• If you chose C: Both Convolution and Coefficient Extraction are covered in this subject as interconnected topics. Correct!
• If you chose D: This is incorrect. Both Convolution and Coefficient Extraction are covered in this subject as interconnected topics.

Q7: What is a common pitfall when working with Integer Partitions?

A) Integer Partitions is always computed the same way in all contexts B) Integer Partitions has no common misconceptions C) A common mistake is confusing Integer Partitions with a similar concept D) The main error with Integer Partitions is using it when it is not needed

Correct: C)

• If you chose A: This is incorrect. Students often confuse Integer Partitions with similar-sounding or related concepts. Pay attention to the precise definitions.
• If you chose B: This is incorrect. Students often confuse Integer Partitions with similar-sounding or related concepts. Pay attention to the precise definitions.
• If you chose C: Students often confuse Integer Partitions with similar-sounding or related concepts. Pay attention to the precise definitions. Correct!
• If you chose D: This is incorrect. Students often confuse Integer Partitions with similar-sounding or related concepts. Pay attention to the precise definitions.

Q8: When should you apply Ordinary Generating Functions (Ogf)?

A) Ordinary Generating Functions (Ogf) is not practically useful B) Use Ordinary Generating Functions (Ogf) only in pure mathematics contexts C) Apply Ordinary Generating Functions (Ogf) to solve problems in this subject's domain D) Avoid Ordinary Generating Functions (Ogf) unless explicitly instructed

Correct: C)

• If you chose A: This is incorrect. Ordinary Generating Functions (Ogf) is a practical tool used throughout this subject to solve relevant problems.
• If you chose B: This is incorrect. Ordinary Generating Functions (Ogf) is a practical tool used throughout this subject to solve relevant problems.
• If you chose C: Ordinary Generating Functions (Ogf) is a practical tool used throughout this subject to solve relevant problems. Correct!
• If you chose D: This is incorrect. Ordinary Generating Functions (Ogf) is a practical tool used throughout this subject to solve relevant problems.

Practice Problems

1. Find the OGF of $a_n = 2^n$.
   

   Click for answer

   $\sum_{n=0}^{\infty} 2^n x^n = \frac{1}{1-2x}$, for $|x| < 1/2$.

2. Find $[x^4]$ in $(1+x)^{10}$.
   

   Click for answer

   $\binom{10}{4} = 210$.

3. Solve $a_n = 3a_{n-1}$ with $a_0 = 2$ using generating functions.
   

   Click for answer

   $A(x) = \frac{2}{1-3x}$. $a_n = 2 \cdot 3^n$.

4. What is the EGF of $a_n = 1$ for all $n$?
   

   Click for answer

   $\sum_{n=0}^{\infty} 1 \cdot \frac{x^n}{n!} = e^x$.

5. How many ways to partition the number 4? List them.
   

   Click for answer

   $p(4) = 5$: 4, 3+1, 2+2, 2+1+1, 1+1+1+1.

Summary

Key takeaways:

• OGF: $A(x) = \sum a_n x^n$ — turns sequences into power series
• Common OGFs: $1/(1-x)$ for ${1}$, $x/(1-x)^2$ for ${n}$
• Multiplication = convolution; $A(x)/(1-x) = \sum (\sum_{k=0}^n a_k) x^n$
• Solving recurrences: sum, express in terms of $A(x)$, solve rational function, partial fractions, extract coefficients
• EGF: $E(x) = \sum a_n x^n/n!$ — for labeled structures
• Generating functions are a bridge between discrete math and analysis

Pitfalls

• Confusing OGFs with EGFs: Ordinary generating functions use $\sum a_n x^n$; exponential generating functions use $\sum a_n x^n/n!$. The choice matters: OGFs handle unlabeled structures (integer partitions, binary strings) where convolution corresponds to $\sum a_k b_{n-k}$; EGFs handle labeled structures (permutations, set partitions) where convolution corresponds to $\sum \binom{n}{k} a_k b_{n-k}$. Using the wrong type produces incorrect coefficient relationships.
• Errors in shifting indices when summing recurrences: When converting $a_{n+1} = 2a_n$ into generating functions, $\sum_{n \geq 0} a_{n+1} x^n = (A(x) - a_0)/x$, but the exact shift depends on the recurrence index range. A common mistake: using $A(x)/x$ instead of $(A(x) - a_0)/x$ or vice versa, or forgetting that the summation starts at a specific $n$. Always write out the first few terms explicitly to verify the shift.
• Mishandling partial fraction decomposition: After obtaining a rational generating function $A(x) = P(x)/Q(x)$, partial fractions convert it to a sum of terms like $c/(1 - \alpha x)^k$, each of which has a known series expansion. Errors in decomposition (wrong constants, missing terms for repeated roots) produce wrong closed forms. For repeated roots, the decomposition includes terms $c_1/(1-\alpha x) + c_2/(1-\alpha x)^2 + \cdots + c_k/(1-\alpha x)^k$ — don't use only a single term.
• Extracting coefficients from the wrong series expansion: $[x^n] \frac{1}{(1-x)^k} = \binom{n+k-1}{k-1} = \binom{n+k-1}{n}$, NOT $\binom{n}{k}$ or $\binom{k}{n}$. The exponent in the denominator determines which binomial coefficient to use. Also, $[x^n] \frac{1}{1 - \alpha x} = \alpha^n$, not $1/\alpha^n$. Memorize the three fundamental expansions: $1/(1-x)$, $1/(1-x)^k$, and $e^x$.
• Using generating functions for sequences where the power series diverges: The formal power series approach treats $A(x)$ as an algebraic object regardless of convergence, which is valid for deriving recurrences and identities. But when using analytic methods (differentiation, integration, asymptotic extraction via singularity analysis), convergence matters. A generating function with radius of convergence 0 (e.g., $\sum n! x^n$) cannot be manipulated analytically without care — stick to formal power series methods in that case.

Next Steps

Next up: 26-09-graph-theory-basics.md — vertices, edges, degrees, and fundamental graph concepts.