8.3 Ordinary Generating Functions & Closed-Form Combinatorial Sequences

Back to Discrete Mathematics Notes

📚Module 08: Combinatorics & Recurrence RelationsTopic 8.3: Ordinary Generating Functions & Combinatorial Sequences⏱️5 min read

🎯High-Yield For:Semester Exams • GATE CSE • Technical Interviews

💡 Core Intuition: The 3-Second Mental Model

🍳 The Everyday Analogy: The Clothesline & The Multi-Compartment Bento Box

Think of generating functions as a mathematical clothesline:

1. The Clothesline Metaphor (Herbert Wilf): An infinite sequence of numbers $(a_0, a_1, a_2, a_3, \dots)$ is like an unwieldy pile of clothes on the floor. A Generating Function hangs them up neatly on a clothesline using powers of $x$ as clothes pegs: $$G(x) = a_0 + a_1 x + a_2 x^2 + a_3 x^3 + \dots$$ We don't actually care about "evaluating" $x$ at a specific numerical value. The polynomial is simply an algebraic display case holding the sequence!
2. Compressing Infinity into a Compact Fraction: The infinite sequence $(1, 1, 1, 1, \dots)$ seems impossible to handle all at once. But in generating function form, it is simply the infinite geometric series: $$1 + x + x^2 + x^3 + \dots = \frac{1}{1 - x}$$ The simple algebraic fraction $\frac{1}{1 - x}$ encodes the entire infinite sequence in 5 characters!
3. Convolution (Multiplying Clotheslines): Multiplying two generating functions $A(x) \cdot B(x)$ automatically cross-multiplies all possible combinations whose index powers add up to $n$ ($x^k \cdot x^{n-k} = x^n$). This solves complex coin change, partitioning, and resource distribution problems effortlessly!

💻 Bridging to Computer Science: Z-Transforms, Digital Signal Processing & Counting Paths

In computer science:

• Digital Signal Processing (DSP): The Ordinary Generating Function is the exact mathematical counterpart of the Z-Transform ($X(z) = \sum x[n] z^{-n}$) used to analyze discrete filters, impulse responses, and stability in control systems.
• Dynamic Programming Optimization: Generating functions compute closed forms for state transitions that would otherwise require $O(n^2)$ DP memoization table filling.
• Counting Graph Walks: The $(i, j)$ entry of $(I - xA)^{-1}$ is the generating function for the number of walks of length $n$ between vertices $i$ and $j$ in a network.
• Formal Language Theory: Regular expressions and context-free grammars convert directly into algebraic generating functions via the Chomsky-Schützenberger theorem to count words of length $n$.

📑Table of Contents

• 📜 Ordinary Generating Functions (OGF) Formalism
• 🧰 The Master Generating Function Toolbox
• ⚙️ Operations on Generating Functions
• 🔀 Derangements & The Principle of Inclusion-Exclusion
• 🔄 Solving Recurrence Relations via Generating Functions
• 📝 Step-by-Step Worked Examples
  • Example 1: Solving a First-Order Recurrence via Generating Functions
  • Example 2: The Coin Change Problem
• 🎯 Exam & Interview Pitfall Check

---

📜 Ordinary Generating Functions (OGF) Formalism

📖Definition 8.2: Ordinary Generating Functiondefinition

Let $(a_0, a_1, a_2, \dots) = (a_n)_{n=0}^\infty$ be a sequence of real numbers. The Ordinary Generating Function (OGF) of the sequence is the formal power series:

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

The coefficient of $x^n$ in $G(x)$ is denoted by the operator:

$$[x^n] \, G(x) = a_n$$

Formal Power Series Invariant: In discrete mathematics, we treat $G(x)$ algebraically within the formal ring $\mathbb{R}[[x]]$. We do not require $G(x)$ to converge for any specific real value of $x$; the variable $x$ serves strictly as a positional placeholder.

★ Generating Function Method

Transform discrete recurrence into algebraic equation G(x), decompose via partial fractions, and extract [xⁿ].

---

🧰 The Master Generating Function Toolbox

Canonical Generating Function Closed Forms

Essential sequence-to-function duals used throughout combinatorial analysis

OGF 1

All-Ones Sequence: (1, 1, 1, 1, ...)

1️⃣

1 / (1 - x) = 1 + x + x² + x³ + ...

Formula: ∑ₙ₌₀^∞ xⁿCoefficients: aₙ = 1 for all n ≥ 0

↓Scale by Geometric Ratio a

OGF 2

Geometric Progression: (1, a, a², a³, ...)

📈

1 / (1 - ax) = 1 + ax + a²x² + a³x³ + ...

Formula: ∑ₙ₌₀^∞ aⁿ xⁿCoefficients: aₙ = aⁿ

↓Differentiate to Introduce Linear Factors

OGF 3

Linear Increment Sequence: (1, 2, 3, 4, ...)

🔢

1 / (1 - x)² = 1 + 2x + 3x² + 4x³ + ...

Formula: ∑ₙ₌₀^∞ (n + 1) xⁿCoefficients: aₙ = n + 1

↓Generalize to Arbitrary Integer Exponent k

OGF 4

Extended Negative Binomial (Stars and Bars)

⭐

1 / (1 - x)ᵏ = ∑ₙ₌₀^∞ C(n + k - 1, n) xⁿ

Formula: (1 - x)⁻ᵏ = ∑ₙ₌₀^∞ C(n + k - 1, k - 1) xⁿDirectly generates Stars and Bars allocations for k containers!

⚡Law 8.2: Negative Power Binomial Series Cataloglaw

The standard negative power series expansions frequently tested in competitive examinations:

1. First-Order Simple Series: $$(1 - x)^{-1} = \frac{1}{1 - x} = 1 + x + x^2 + x^3 + x^4 + \dots = \sum_{n=0}^{\infty} x^n$$ $$(1 + x)^{-1} = \frac{1}{1 + x} = 1 - x + x^2 - x^3 + x^4 - \dots = \sum_{n=0}^{\infty} (-1)^n x^n$$
2. Second-Order Differentiated Series: $$(1 - x)^{-2} = \frac{1}{(1 - x)^2} = 1 + 2x + 3x^2 + 4x^3 + 5x^4 + \dots = \sum_{n=0}^{\infty} (n + 1) x^n$$ $$(1 + x)^{-2} = \frac{1}{(1 + x)^2} = 1 - 2x + 3x^2 - 4x^3 + 5x^4 - \dots = \sum_{n=0}^{\infty} (-1)^n (n + 1) x^n$$
3. General $k$-th Order Negative Binomial (Stars and Bars Generating Function): $$(1 - x)^{-k} = \frac{1}{(1 - x)^k} = \sum_{n=0}^{\infty} \binom{n + k - 1}{n} x^n = \sum_{n=0}^{\infty} \binom{n + k - 1}{k - 1} x^n$$

---

⚙️ Operations on Generating Functions

Algebraic Transforms on Sequences and OGFs

How operations on generating functions modify their underlying sequence coefficients

➕

Linear Combination

Superposition

• α F(x) + β G(x) generates the sequence (α aₙ + β bₙ).
• Allows term-by-term addition of distinct combinatorial components.

⏩

Right Shifting (Delay)

Index Shifting

• xᵏ G(x) prepends k leading zeros to the sequence: (0, 0, ..., 0, a₀, a₁, a₂, ...).
• Essential for aligning recurrence relation indices during summation.

✖️

Convolution (Product)

Multiplicative Cross-Sum

• F(x) · G(x) generates the Cauchy convolution cₙ = ∑ₖ₌₀ⁿ aₖ bₙ₋ₖ.
• Solves partitioning problems: choosing k items from A and n - k items from B.

📐

Differentiation

Multiplying by n

• x · G'(x) = x ∑ₙ₌₀^∞ n aₙ xⁿ⁻¹ = ∑ₙ₌₀^∞ n aₙ xⁿ.
• Multiplying the OGF derivative by x scales each coefficient by n: (n aₙ).

---

🔀 Derangements & The Principle of Inclusion-Exclusion

A derangement is a permutation of $n$ elements in which no element appears in its original position ($\pi(i) \neq i$ for all $1 \le i \le n$).

📐Theorem 8.6: Closed Form & Recurrences for Derangements (Dₙ or !n)theorem

1. Exact Closed-Form Formula via Inclusion-Exclusion: $$D_n = !n = n! \sum_{k=0}^{n} \frac{(-1)^k}{k!} = n! \left( \frac{1}{0!} - \frac{1}{1!} + \frac{1}{2!} - \frac{1}{3!} + \dots + \frac{(-1)^n}{n!} \right)$$
2. First-Order Non-Homogeneous Recurrence: $$D_n = n D_{n-1} + (-1)^n \quad \text{for } n \ge 2, \quad D_1 = 0$$
3. Second-Order Homogeneous Recurrence: $$D_n = (n - 1) (D_{n-1} + D_{n-2}) \quad \text{for } n \ge 3, \quad D_1 = 0, \; D_2 = 1$$
4. Asymptotic Probability ($n \to \infty$): Since $\sum_{k=0}^\infty \frac{(-1)^k}{k!} = e^{-1}$, the probability that a random permutation is a derangement approaches: $$\lim_{n \to \infty} \frac{D_n}{n!} = \frac{1}{e} \approx 0.367879 \quad (\approx 36.8\%)$$

📐Derangements Reference Table (GATE Essentials)observation

$n$	Derangements $D_n$ ($!n$)	Total Permutations $n!$	Ratio $D_n / n!$
1	0	1	0.0000
2	1	2	0.5000
3	2	6	0.3333
4	9	24	0.3750
5	44	120	0.3667
6	265	720	0.3681
7	1,854	5,040	0.3679

---

🔄 Solving Recurrence Relations via Generating Functions

Architecture Flow

The 5-Step Generating Function Recurrence Solver

Universal algebraic pipeline to convert a recurrence relation into an exact closed form

∑Step 1

Multiply by xⁿ & Sum

Multiply both sides of the recurrence by xⁿ and sum from the recurrence threshold (e.g., n = 1 or n = 2) to ∞.

→

Infinite Sum Constructed

📦Step 2

Substitute G(x)

Rewrite all summation terms in terms of G(x) = ∑ aₙ xⁿ and the initial conditions (e.g., a₀, a₁).

→

Algebraic Equation in G(x)

⚙️Step 3

Solve for G(x)

Isolate G(x) as a rational fraction: G(x) = P(x) / Q(x).

→

Rational Function G(x)

✂️Step 4

Partial Fractions

Factor Q(x) and decompose P(x) / Q(x) into standard partial fractions A / (1 - r₁ x) + B / (1 - r₂ x).

→

Decomposed Summands

🎯Step 5

Extract [xⁿ]

Use standard toolbox expansions to read off the coefficient of xⁿ, giving the exact closed form for aₙ!

---

📝 Step-by-Step Worked Examples

Example 1: Solving a First-Order Recurrence via Generating Functions

Problem Statement: Solve the recurrence relation $a_n = 3a_{n-1} + 2$ for $n \ge 1$ with initial condition $a_0 = 1$ using generating functions.

Step-by-Step Solution:

1. Step 1: Multiply by $x^n$ and sum for $n \ge 1$

   $$\sum_{n=1}^{\infty} a_n x^n = 3 \sum_{n=1}^{\infty} a_{n-1} x^n + 2 \sum_{n=1}^{\infty} x^n$$

2. Step 2: Express in terms of $G(x)$

   • Left-hand side: $$\sum_{n=1}^{\infty} a_n x^n = G(x) - a_0 = G(x) - 1$$
   • First term on RHS: $$3 \sum_{n=1}^{\infty} a_{n-1} x^n = 3x \sum_{n=1}^{\infty} a_{n-1} x^{n-1} = 3x G(x)$$
   • Second term on RHS: $$2 \sum_{n=1}^{\infty} x^n = 2 \left( \frac{1}{1 - x} - 1 \right) = \frac{2x}{1 - x}$$
   • Equating: $$G(x) - 1 = 3x G(x) + \frac{2x}{1 - x}$$

3. Step 3: Solve for $G(x)$

   $$G(x) (1 - 3x) = 1 + \frac{2x}{1 - x} = \frac{1 - x + 2x}{1 - x} = \frac{1 + x}{1 - x}$$ $$G(x) = \frac{1 + x}{(1 - x)(1 - 3x)}$$

4. Step 4: Partial Fraction Decomposition

   $$\frac{1 + x}{(1 - x)(1 - 3x)} = \frac{A}{1 - x} + \frac{B}{1 - 3x}$$
   • Multiply by $(1 - x)(1 - 3x)$: $$1 + x = A(1 - 3x) + B(1 - x)$$
   • Set $x = 1$: $$1 + 1 = A(1 - 3) + 0 \implies 2 = -2A \implies A = -1$$
   • Set $x = 1/3$: $$1 + \frac{1}{3} = 0 + B\left(1 - \frac{1}{3}\right) \implies \frac{4}{3} = \frac{2}{3} B \implies B = 2$$
   • Thus: $$G(x) = -\frac{1}{1 - x} + \frac{2}{1 - 3x}$$

5. Step 5: Extract the coefficient of $x^n$

   • By standard toolbox expansions: $$[x^n] \, \frac{1}{1 - x} = 1 \quad \text{and} \quad [x^n] \, \frac{1}{1 - 3x} = 3^n$$
   • Combining terms: $$a_n = -1 \cdot (1) + 2 \cdot (3^n) = 2 \cdot 3^n - 1$$

---

Example 2: The Coin Change Problem

Problem Statement: Find the generating function for the number of ways to make $n$ cents using pennies (1¢), nickels (5¢), and dimes (10¢).

Step-by-Step Solution:

1. Step 1: Express Each Coin's Contribution as an Independent Series

   • Pennies (1¢): Can use $0, 1, 2, 3, \dots$ pennies. Generates values $0, 1, 2, 3, \dots$: $$P(x) = 1 + x^1 + x^2 + x^3 + \dots = \frac{1}{1 - x}$$
   • Nickels (5¢): Can use $0, 1, 2, 3, \dots$ nickels. Generates values $0, 5, 10, 15, \dots$: $$N(x) = 1 + x^5 + x^{10} + x^{15} + \dots = \frac{1}{1 - x^5}$$
   • Dimes (10¢): Can use $0, 1, 2, 3, \dots$ dimes. Generates values $0, 10, 20, 30, \dots$: $$D(x) = 1 + x^{10} + x^{20} + x^{30} + \dots = \frac{1}{1 - x^{10}}$$

2. Step 2: Multiply the Independent Generating Functions

   • By the convolution rule, multiplying the polynomials sums the exponents ($x^a \cdot x^b \cdot x^c = x^{a+b+c}$): $$G(x) = P(x) \cdot N(x) \cdot D(x) = \frac{1}{(1 - x)(1 - x^5)(1 - x^{10})}$$
   • The number of ways to make $n$ cents is simply the coefficient $[x^n] \, G(x)$.

---

🎯 Exam & Interview Pitfall Check

Generating Function Concept	Governing Formula	Common Fatal Trap
Coefficient of $(1 - x)^{-k}$	$\binom{n + k - 1}{n}$	Using $\binom{n}{k}$ (forgetting the extended negative binomial rule)
Sequence $(0, 1, 2, 3, \dots)$	$\frac{x}{(1 - x)^2}$	Confusing with $\frac{1}{(1 - x)^2}$, which generates $(1, 2, 3, 4, \dots)$
Right-shifting $x^k G(x)$	$(0, \dots, 0, a_0, a_1, \dots)$	Forgetting that $k$ leading zeros are prepended
Derangements $D_n$	$n! \sum_{k=0}^n \frac{(-1)^k}{k!}$	Writing $n! / e$ without rounding or checking small $n$ ($D_1 = 0$)
Coin Change OGF	$\prod \frac{1}{1 - x^{w_i}}$	Adding generating functions instead of multiplying via convolution

Core Conceptual Questions

Question 1: What sequence is generated by $G(x) = \frac{x}{(1 - x)^2}$? Key Focus Points: Recall that $\frac{1}{(1 - x)^2} = \sum_{n=0}^\infty (n + 1) x^n = 1 + 2x + 3x^2 + 4x^3 + \dots$. Multiplying by $x$ right-shifts the entire sequence by 1 place:

$$\frac{x}{(1 - x)^2} = x + 2x^2 + 3x^3 + 4x^4 + \dots = \sum_{n=0}^{\infty} n x^n$$

Thus, it generates the natural counting sequence $(0, 1, 2, 3, 4, \dots)$ where $a_n = n$!

Question 2: Does the radius of convergence of a generating function matter in discrete mathematics? Key Focus Points: No! In combinatorics, generating functions are manipulated as formal power series in the ring $\mathbb{R}[[x]]$. We only perform algebraic operations (addition, convolution multiplication, formal differentiation, division). Analytic convergence is irrelevant because we never assign a numerical value to $x$; $x$ is merely a coefficient holder.

Common Interview Traps: Architectural Trade-Offs

Trap 1: Forgetting Initial Conditions when Shifting Indices in $\sum a_n x^n$ Why it fails: Writing $\sum_{n=1}^\infty a_{n-1} x^n$ as $G(x)$ is a common error. Factoring out $x$ gives $x \sum_{n=1}^\infty a_{n-1} x^{n-1} = x \sum_{k=0}^\infty a_k x^k = x G(x)$. Always factor out powers of $x$ to match the index of the sequence with the exponent of $x$!

Trap 2: Forgetting $(1 - x)^{-k}$ uses $\binom{n+k-1}{n}$, NOT $\binom{n}{k}$ Why it fails: $\binom{n}{k}$ is the standard binomial coefficient for $(1 + x)^n$. For negative exponents $(1 - x)^{-k}$, the coefficient is $\binom{n + k - 1}{n}$. Confusing the two produces incorrect coefficients!

🗺️View Complete Discrete Mathematics Roadmap & Syllabus

← Previous Topic8.2 Linear Recurrence Relations: Characteristic Roots & Particular SolutionsNext Topic →9.1 Graph Formalisms, Degree Sequences & the Handshaking Lemma