Generating Functions

⚡ Key Takeaways

A generating function encodes a sequence $(a_n)$ as the coefficients of a formal power series $\sum a_n x^n$ , turning sequence operations into algebra. Key result: counting, recurrences, and convolutions become multiplication, differentiation, and substitution of functions. Used across combinatorics, probability, number theory, and analysis of algorithms. Introduced by Abraham de Moivre (1730) and developed extensively by Euler and Laplace.

💡 The Core Insight

A sequence is hard to manipulate term-by-term, but the whole sequence at once, viewed as a power series, lives in a ring where you can add, multiply, invert, differentiate, and compose. The clothesline metaphor (Wilf): a generating function is a clothesline on which we hang up the terms of a sequence for display. The power of $x^n$ is just a label remembering position $n$ ; the coefficient is the datum. Combinatorial operations on objects (disjoint union, pairing, sequencing) correspond exactly to algebraic operations on their generating functions.

DefinitionOrdinary Generating Function (OGF)

Given a sequence $(a_n)_{n\ge0}$ of numbers (in a commutative ring $R$ , typically $\mathbb{Q}$ , $\mathbb{R}$ , or $\mathbb{C}$ ), its ordinary generating function is the formal power series

1

\quad A(x) = \sum_{n=0}^{\infty} a_n x^n = a_0 + a_1 x + a_2 x^2 + \cdots

Derivation hint: This is a definition; $x$ is a formal indeterminate, not a number, and convergence is not required. Here $a_n = [x^n]A(x)$ denotes the coefficient extraction operator: $[x^n]$ returns the coefficient of $x^n$ .

DefinitionExponential Generating Function (EGF)

The exponential generating function of $(a_n)_{n\ge0}$ is

2

\quad \hat{A}(x) = \sum_{n=0}^{\infty} a_n \frac{x^n}{n!}

Derivation hint: The $n!$ weighting is chosen so that labelled-structure operations (where order of labels matters) become clean products. EGFs are preferred for labelled combinatorial structures (permutations, labelled graphs); OGFs for unlabelled ones (partitions, integer compositions).

DefinitionThe Ring of Formal Power Series

The set $R[[x]]$ of all formal power series over $R$ forms a commutative ring under coefficientwise addition and Cauchy-product multiplication:

3

\quad \left(\sum_n a_n x^n\right)\!\left(\sum_n b_n x^n\right) = \sum_{n=0}^\infty\left(\sum_{k=0}^{n} a_k\, b_{n-k}\right)x^n

Derivation hint: Collect all products $a_k x^k \cdot b_{n-k}x^{n-k}$ contributing to $x^n$ ; the inner sum is the convolution $(a*b)_n$ . A series $A(x)$ is invertible in $R[[x]]$ if and only if $a_0$ is a unit of $R$ (e.g. $a_0\ne 0$ when $R$ is a field).

TheoremConvolution Theorem

If $A(x)=\sum a_n x^n$ and $B(x)=\sum b_n x^n$ are OGFs, then the product $A(x)B(x)$ is the OGF of the convolution sequence $c_n = \sum_{k=0}^n a_k b_{n-k}$ . For EGFs, the product $\hat A(x)\hat B(x)$ is the EGF of the binomial convolution:

4

\quad c_n = \sum_{k=0}^{n}\binom{n}{k} a_k\, b_{n-k}

Derivation hint: Multiply $\sum a_k x^k/k!$ by $\sum b_j x^j/j!$ , set $n=k+j$ , and multiply and divide by $n!$ to recover the binomial coefficient.

TheoremFundamental Operations Dictionary

For OGFs, the following correspondences hold (with $A(x)=\sum a_n x^n$ ):

5

\quad \sum_n a_{n+1}x^n = \frac{A(x)-a_0}{x},\qquad \sum_n n\,a_n x^n = x A'(x),\qquad \sum_n\Big(\sum_{k=0}^n a_k\Big)x^n = \frac{A(x)}{1-x}

Derivation hint: Shift by reindexing $m=n+1$ ; the factor $n$ comes from $\frac{d}{dx}x^n = n x^{n-1}$ ; the partial-sum identity is convolution of $(a_n)$ with the all-ones sequence $1/(1-x)$ .

ProofSolving a Linear Recurrence via OGF: the Fibonacci case

We derive the closed form of the Fibonacci numbers $F_0=0,\ F_1=1,\ F_n=F_{n-1}+F_{n-2}$ .

Step 1. Define $F(x)=\sum_{n\ge0}F_n x^n$ .

Step 2. Encode the recurrence. Multiply $F_n=F_{n-1}+F_{n-2}$ (valid for $n\ge2$ ) by $x^n$ and sum:

\sum_{n\ge2}F_n x^n = \sum_{n\ge2}F_{n-1}x^n + \sum_{n\ge2}F_{n-2}x^n.

Step 3. Express each sum via $F(x)$ . The left side is $F(x)-F_0 - F_1 x = F(x)-x$ . The first right sum is $x\sum_{n\ge2}F_{n-1}x^{n-1}=x(F(x)-F_0)=xF(x)$ . The second is $x^2\sum_{n\ge2}F_{n-2}x^{n-2}=x^2 F(x)$ .

Step 4. Assemble: $F(x)-x = xF(x)+x^2 F(x)$ , hence

6

\quad F(x) = \frac{x}{1-x-x^2}.

Derivation hint: Collect $F(x)$ terms on the left and factor.

Step 5. Partial fractions. Factor $1-x-x^2 = (1-\varphi x)(1-\psi x)$ where $\varphi=\frac{1+\sqrt5}{2}$ , $\psi=\frac{1-\sqrt5}{2}$ . Decompose:

F(x)=\frac{1}{\sqrt5}\left(\frac{1}{1-\varphi x}-\frac{1}{1-\psi x}\right).

Step 6. Expand each geometric series $\frac{1}{1-r x}=\sum_n r^n x^n$ and read off coefficients:

7

\quad F_n = \frac{\varphi^n - \psi^n}{\sqrt5}\qquad(\text{Binet's formula}).

Derivation hint: $[x^n]\frac{1}{1-rx}=r^n$ ; subtract the two geometric expansions termwise. $\qquad\blacksquare$

∎

mathematician · Leonhard Euler | 1707–1783

Though de Moivre first used generating functions to solve recurrences, Euler made them a central tool of analysis and number theory. His 1748 Introductio in analysin infinitorum used the product $\prod_k (1-x^k)^{-1}$ as the generating function for partitions, leading to the Pentagonal Number Theorem and deep partition identities. Euler treated formal series with a fearless algebraic spirit—manipulating divergent series and infinite products to extract finite truths—anticipating the rigorous formal-power-series framework formalized only in the 20th century.

🧠 Intuition

Think of $x^n$ as a box labelled $n$ , and $a_n$ as the number of marbles in that box. The series $A(x)$ is the entire shelf of boxes. Multiplying two generating functions is like asking: in how many ways can I pick a marble from $A$ 's box $k$ and one from $B$ 's box $n-k$ so the labels add to $n$ ? That's exactly a convolution, which is how counting "split this object into two parts" works. The variable $x$ "remembers size by exponent and adds sizes by multiplication"—it is a size-tracking accountant. You never plug in a number unless you want a value (e.g. setting $x=1$ to sum the sequence, or differentiating then setting $x=1$ to get a weighted sum/expectation).

Figure

OGF as a shelf of labelled coefficient-boxes; product = convolution

ExampleCounting compositions of an integer

Given. How many ways can a positive integer $n$ be written as an ordered sum of positive integers (compositions)? E.g. $3 = 3 = 2+1 = 1+2 = 1+1+1$ , so $4$ ways.

Step 1. A single positive part has OGF $P(x)=x+x^2+x^3+\cdots = \dfrac{x}{1-x}$ (one object of each size $\ge1$ ).

Step 2. A composition is a sequence of $\ge1$ parts. The "sequence of one or more $P$ " construction gives

C(x)=\sum_{k\ge1}P(x)^k = \frac{P(x)}{1-P(x)} = \frac{x/(1-x)}{1-x/(1-x)} = \frac{x}{1-2x}.

Step 3. Expand: $\dfrac{x}{1-2x} = x\sum_{m\ge0}(2x)^m = \sum_{m\ge0}2^m x^{m+1}$ , so $[x^n]C(x)=2^{\,n-1}$ for $n\ge1$ .

Answer. $\boxed{\,2^{\,n-1}\text{ compositions of }n\,}$ (e.g. $n=3 \Rightarrow 2^2 = 4$ ✓, dimensionless count).

ExampleMean of a probability distribution via PGF

Given. Roll a fair die; let $X$ be the outcome. Find $E[X]$ using the probability generating function $G(x)=E[x^X]=\sum_k P(X=k)x^k$ .

Step 1. Each face has probability $\tfrac16$ , so

G(x)=\tfrac16(x+x^2+x^3+x^4+x^5+x^6)=\frac{x(1-x^6)}{6(1-x)}.

Step 2. Use the identity $E[X]=G'(1)$ .

G'(x)=\tfrac16(1+2x+3x^2+4x^3+5x^4+6x^5).

Step 3. Evaluate at $x=1$ :

G'(1)=\tfrac16(1+2+3+4+5+6)=\tfrac16\cdot 21 = \tfrac{21}{6}=3.5.

Answer. $\boxed{E[X]=3.5}$ (dimensionless; matches direct computation). Note: variance follows from $G''(1)+G'(1)-G'(1)^2$ .

⚠️ Common mistake

Generating functions are formal, not analytic—by default. You do not need $\sum a_n x^n$ to converge anywhere for the algebra to be valid. The series $\sum n!\,x^n$ has radius of convergence $0$ , yet is a perfectly good element of $\mathbb{Q}[[x]]$ on which you may add, multiply, and invert. Convergence is required only when you actually substitute a numerical value of $x$ (e.g. setting $x=1/2$ , or applying analytic methods like singularity analysis to estimate $a_n$ ). Confusing the formal and analytic viewpoints leads to false statements about "the value" of a divergent generating function.

Counterexample

Multiplication is not always valid for two-sided or Laurent series. The Cauchy product $\sum_n(\sum_k a_k b_{n-k})$ requires each coefficient to be a finite sum. If you allow doubly-infinite series $\sum_{n\in\mathbb{Z}} a_n x^n$ , the convolution $\sum_k a_k b_{n-k}$ can become an infinite sum with no formal meaning. For example, formally multiplying $\sum_{n\ge0}x^n$ by $\sum_{n\ge0}x^{-n}$ gives a coefficient of $x^0$ equal to $\sum_{k\ge0}1\cdot1=\infty$ . Thus the ring structure $R[[x]]$ relies crucially on series being bounded below in degree.

connection

Generating functions sit at a crossroads of many fields. The OGF dictionary is the engine of Analytic Combinatorics, where the location and nature of singularities of $A(x)$ control the asymptotic growth of $a_n$ (Flajolet–Sedgewick). In probability, the Probability Generating Function and Moment Generating Function are specializations giving moments and supporting limit theorems. The EGF formalism is the species-theoretic shadow of Exponential Formula for labelled structures. Number theory uses Dirichlet Series $\sum a_n/n^s$ —a "multiplicative" cousin where convolution corresponds to Dirichlet rather than Cauchy product. The recurrence-solving method generalizes via the Z-transform in signal processing and the Laplace Transform in the continuous setting.

🔬 Where this appears

⏳ History

- 1730 — Abraham de Moivre, in Miscellanea Analytica, introduces generating functions to solve linear recurrences, including a closed form for Fibonacci-type sequences.

- 1748 — Euler publishes Introductio in analysin infinitorum, using infinite products as generating functions for partitions; foundation of partition theory.

- 1750s — Euler discovers the Pentagonal Number Theorem, expressing

\prod(1-x^k)

as a sparse signed series.

- 1782 — Pierre-Simon Laplace systematizes "fonctions génératrices" in his probability work, coining the modern term and applying them to difference equations.

- 1812 — Laplace's Théorie analytique des probabilités makes generating functions (and the Laplace transform) central to probability.

- 1900s–1930s — Formal power series receive rigorous algebraic foundations; the ring

R[[x]]

is studied abstractly.

- 1960s — Donald Knuth popularizes generating functions for rigorous algorithm analysis.

- 1970s–1980s — Gian-Carlo Rota, Joyal's theory of species, and the umbral calculus give combinatorics a structural, functorial language for generating functions.

- 1990s–2009 — Philippe Flajolet and Robert Sedgewick develop Analytic Combinatorics, linking singularities of generating functions to coefficient asymptotics; Wilf's generatingfunctionology becomes a standard text.

open-problem

Generating functions are most powerful when they have a nice closed form, but classifying which sequences admit which kind of GF is deep. A sequence is D-finite (holonomic) iff its OGF satisfies a linear ODE with polynomial coefficients; algebraic iff the OGF satisfies a polynomial equation; and these classes are properly nested. Determining whether a given combinatorially defined OGF is algebraic, D-finite, or "wild" can be extremely hard. Famous open territory: many sequences in enumerative combinatorics (e.g. certain self-avoiding-walk and lattice-animal counts) are conjectured to be non-D-finite, but proving non-holonomicity is notoriously difficult. The automatic/transcendence classification of multivariate generating functions, and effective asymptotics from implicit functional equations, remain active research areas.

Formal Statement

Why It Holds / Derivation

Building Intuition

Worked Examples

Common Misconceptions

Connections

Real-World Applications

Historical Development

Subtleties & Limits

See Also