Generating Functions — Ordinary and Exponential

⚡ Key Takeaways

Generating functions encode a sequence $(a_n)$ as the coefficients of a formal power series. The ordinary generating function (OGF) is $\sum a_n x^n$ ; the exponential generating function (EGF) is $\sum a_n x^n/n!$ . They convert combinatorial operations (sums, shifts, products, compositions) into algebraic operations, letting you solve recurrences, count structures, and prove identities. Core toolkit of combinatorics; popularized by Euler (18th c.) and Wilf's generatingfunctionology (1990).

💡 The Core Insight

Translate operations on sequences into operations on functions.

Shifting a sequence ↔ multiplying/dividing by $x$ .
Adding sequences ↔ adding functions.
The convolution of two sequences ↔ the product of their OGFs.
The binomial convolution of two sequences ↔ the product of their EGFs.
Combinatorial constructions (union, pairing, sequence-of, set-of) ↔ sum, product, $\frac{1}{1-A}$ , $e^{\hat A}$ .

Once you know the dictionary, counting reduces to algebra and calculus.

DefinitionOrdinary Generating Function (OGF)

For a sequence $(a_n)_{n\ge 0}$ of real or complex numbers, 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: Definitional — $a_n = [x^n]A(x)$ , the coefficient of $x^n$ . The symbol $x$ is a formal indeterminate; no value is substituted unless convergence is invoked. Here $[x^n]A(x)$ denotes "the coefficient of $x^n$ in $A(x)$ ." The set of all formal power series over a field $K$ , denoted $K[[x]]$ , forms a commutative ring under coefficientwise addition and Cauchy-product multiplication.

DefinitionExponential Generating Function (EGF)

For a sequence $(a_n)_{n\ge 0}$ , its exponential generating function is

2

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

Derivation hint: Definitional — $a_n = n!\,[x^n]\hat A(x)$ . The weight $1/n!$ is chosen so that products of EGFs implement binomial (labeled) convolution. The factor $1/n!$ is exactly what is needed so that multiplying two EGFs counts ways to interleave labels of two labeled structures.

DefinitionThe Two Convolutions

The defining algebraic properties. If $C(x) = A(x)B(x)$ as OGFs, and $\hat C(x) = \hat A(x)\hat B(x)$ as EGFs, then

3

\quad c_n = \sum_{k=0}^{n} a_k b_{n-k} \qquad\text{(Cauchy / ordinary convolution)}

Derivation hint: Multiply $\sum a_k x^k \cdot \sum b_j x^j$ and collect the coefficient of $x^n$ over all $k+j=n$ .

4

\quad c_n = \sum_{k=0}^{n} \binom{n}{k} a_k b_{n-k} \qquad\text{(binomial / exponential convolution)}

Derivation hint: The coefficient of $x^n/n!$ in $\hat A\hat B$ is $n!\sum_{k}\frac{a_k}{k!}\frac{b_{n-k}}{(n-k)!} = \sum_k \binom{n}{k}a_k b_{n-k}$ .

TheoremOperational Dictionary

Let $A(x)=\sum a_n x^n$ . The following equivalences hold in $K[[x]]$ :

5

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

Derivation hint: First: drop $a_0$ and divide by $x$ to shift indices down by one. Second: differentiate $A$ term-by-term ( $\frac{d}{dx}x^n = nx^{n-1}$ ) and multiply by $x$ .

6

\quad \sum_{n\ge 0}\Big(\sum_{k=0}^n a_k\Big)x^n = \frac{A(x)}{1-x}

Derivation hint: Partial-sum sequence is the convolution of $(a_n)$ with the constant sequence $(1,1,1,\dots)$ , whose OGF is $\frac{1}{1-x}$ . For EGFs, differentiation shifts:

7

\quad \frac{d}{dx}\hat A(x) = \sum_{n\ge 0} a_{n+1}\frac{x^n}{n!}

Derivation hint: $\frac{d}{dx}\frac{x^n}{n!} = \frac{x^{n-1}}{(n-1)!}$ , so differentiation maps the EGF of $(a_n)$ to the EGF of $(a_{n+1})$ .

ProofThe geometric series and partial fractions, the master tools

Step 1 — The fundamental OGF. Consider $(1,1,1,\dots)$ . In $K[[x]]$ , $(1-x)\sum_{n\ge0}x^n = 1$ because all terms cancel telescopically. Hence

8

\quad \frac{1}{1-x} = \sum_{n=0}^{\infty} x^n

Derivation hint: Multiply $\sum x^n$ by $(1-x)$ ; the coefficient of $x^n$ for $n\ge 1$ is $1-1=0$ , and the constant term is $1$ .

Step 2 — Scaling and the negative binomial. Substituting $x \to cx$ gives $\frac{1}{1-cx}=\sum c^n x^n$ . Differentiating $k$ times and normalizing gives

9

\quad \frac{1}{(1-x)^{k+1}} = \sum_{n=0}^{\infty}\binom{n+k}{k} x^n

Derivation hint: Apply $\frac{1}{k!}\frac{d^k}{dx^k}$ to [8]; the $k$ -th derivative of $(1-x)^{-1}$ is $k!(1-x)^{-(k+1)}$ , and term-by-term it produces $\binom{n+k}{k}$ .

Step 3 — Solving a linear recurrence (template). Suppose $a_n = p\,a_{n-1} + q\,a_{n-2}$ for $n\ge 2$ . Multiply by $x^n$ , sum over $n\ge 2$ :

10

\quad A(x) - a_0 - a_1 x = px\big(A(x)-a_0\big) + qx^2 A(x)

Derivation hint: $\sum_{n\ge2}a_{n-1}x^n = x(A-a_0)$ and $\sum_{n\ge2}a_{n-2}x^n = x^2 A$ ; substitute and isolate $A$ . Solving for $A(x)$ yields a rational function $\dfrac{P(x)}{1-px-qx^2}$ . Step 4 — Partial fractions. Factor the denominator $1-px-qx^2 = (1-\alpha x)(1-\beta x)$ and write $A(x) = \frac{C_1}{1-\alpha x}+\frac{C_2}{1-\beta x}$ . By [8], $a_n = C_1\alpha^n + C_2\beta^n$ . This is the closed form. $\blacksquare$

∎

mathematician · Leonhard Euler | 1707–1783

Euler was the first to wield generating functions as a systematic instrument. In Introductio in analysin infinitorum (1748) he used them to study partitions of integers, deriving the product formula $\prod_{k\ge1}(1-x^k)^{-1}$ as the OGF for the partition function $p(n)$ , and discovering the Pentagonal Number Theorem $\prod(1-x^k) = \sum_{j}(-1)^j x^{j(3j-1)/2}$ . He treated power series with fearless formal manipulation, anticipating modern formal-power-series rigor by two centuries. His genius lay in seeing that an infinite catalogue of combinatorial facts could be compressed into a single analytic expression and then operated upon.

🧠 Intuition

Think of a generating function as a single object holding an entire sequence, where the variable $x^n$ is a "tag" marking position $n$ . Multiplication by $x$ pushes every tag up by one — a shift. Multiplying two OGFs is like asking: in how many ways can I split a budget of size $n$ between two activities? That is exactly the convolution $\sum a_k b_{n-k}$ . The EGF's $1/n!$ has a precise meaning. If you are counting labeled objects on $\{1,\dots,n\}$ (graphs, permutations, set partitions), then combining a structure on a $k$ -subset with a structure on the complementary $(n-k)$ -subset requires choosing which labels go where — the $\binom{n}{k}$ in [4]. The $1/n!$ weights bake this choosing directly into the product. Rule of thumb: unlabeled/positional ⟶ OGF; labeled/permutational ⟶ EGF.

Figure

OGF vs EGF: the two convolution products

ExampleFibonacci numbers via OGF

Given: $F_0=0,\ F_1=1,\ F_n=F_{n-1}+F_{n-2}$ . Find a closed form.

Step 1. Let $F(x)=\sum_{n\ge0}F_n x^n$ . Using the recurrence (template [10] with $p=q=1$ ):

F(x) - 0 - x = x F(x) + x^2 F(x).

Step 2. Solve: $F(x) = \dfrac{x}{1-x-x^2}$ .

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

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

Step 4. Read off coefficients with [8]:

\boxed{F_n = \frac{\varphi^n - \psi^n}{\sqrt5}}\quad\text{(Binet's formula, dimensionless count)}

Check: $F_5 = \frac{\varphi^5-\psi^5}{\sqrt5} = 5$ . ✓

ExampleCounting set partitions / derangements via EGF

Given: $D_n$ = number of permutations of $n$ labeled items with no fixed point (derangements). A permutation decomposes into fixed points (each a singleton) and a derangement of the rest:

n! = \sum_{k=0}^{n}\binom{n}{k}D_{n-k}.

This is a binomial convolution [4] of $(D_n)$ with the all-ones sequence.

Step 1. In EGF language: $\sum n!\,\frac{x^n}{n!} = \hat D(x)\cdot e^x$ , i.e. $\frac{1}{1-x} = \hat D(x)\,e^x$ .

Step 2. Solve: $\hat D(x) = \dfrac{e^{-x}}{1-x}$ .

Step 3. Multiply the series $e^{-x}=\sum\frac{(-1)^k}{k!}x^k$ and $\frac{1}{1-x}=\sum x^m$ ; the coefficient of $x^n$ is $\sum_{k=0}^n \frac{(-1)^k}{k!}$ . Then $D_n = n!\,[x^n]\hat D(x)$ :

\boxed{D_n = n!\sum_{k=0}^{n}\frac{(-1)^k}{k!}}\quad\text{(integer count of derangements)}

Check: $D_4 = 24(1-1+\tfrac12-\tfrac16+\tfrac1{24}) = 9$ . ✓ And $D_n/n! \to e^{-1}$ .

⚠️ Common mistake

Convergence is not required for formal manipulation. The series $\sum n!\,x^n$ has radius of convergence $0$ , yet it is a perfectly legitimate element of $K[[x]]$ and can be added, multiplied, and differentiated formally. Convergence is only needed when you substitute a number for $x$ or extract asymptotics via complex analysis. Conversely, you may NOT freely substitute $x=1$ to "sum a sequence" unless the series actually converges there.

Do not confuse OGF and EGF coefficients. From an OGF, $a_n=[x^n]A(x)$ . From an EGF, $a_n = n!\,[x^n]\hat A(x)$ — forgetting the $n!$ is the single most common error.

Counterexample

Naively using the OGF product for labeled objects fails. Suppose you count labeled structures and try the ordinary product. The number of ways to 2-color the labels of $\{1,\dots,n\}$ (each element either red or blue) is $2^n$ . Its EGF is $e^x\cdot e^x = e^{2x} = \sum 2^n x^n/n!$ — correct. If you instead used the OGF product $\frac{1}{1-x}\cdot\frac{1}{1-x}=\frac{1}{(1-x)^2}=\sum(n+1)x^n$ , you would get $n+1$ , the count of unlabeled compositions into two parts — a completely different, wrong answer for the labeled problem. The mismatch is precisely the missing $\binom nk$ choices of label placement.

connection

Generating functions sit at the crossroads of several areas. Solving Linear Recurrence Relations becomes routine partial-fraction extraction. The Symbolic Method in Combinatorics (Flajolet–Sedgewick) systematizes the OGF/EGF dictionary into "admissible constructions" — SEQ, SET, CYC, MSET — translating combinatorial classes directly into functional equations. The EGF formalism is the analytic shadow of Species of Structures (Joyal), a category-theoretic foundation for labeled enumeration. Extracting $a_n$ asymptotically from a generating function is the subject of Analytic Combinatorics, using Cauchy's Integral Formula and singularity analysis. The Binomial Theorem and Catalan Numbers both fall out as special cases, and the multiplicative structure on Dirichlet series mirrors the OGF story for number-theoretic functions.

🔬 Where this appears

⏳ History

- 1730s–1748 — Euler introduces generating functions for integer partitions; proves the Pentagonal Number Theorem and the product formula for

p(n)

.

- 1751 — Euler studies the Catalan numbers via the polygon-triangulation generating function

C(x)=\frac{1-\sqrt{1-4x}}{2x}

.

- 1812 — Laplace, in Théorie analytique des probabilités, develops the fonction génératrice as a central tool of probability; the Laplace transform is its continuous analogue.

- 1830s–1850s — Cayley and Sylvester use generating functions in invariant theory and tree enumeration.

- 1889 — Cayley's formula

n^{n-2}

for labeled trees; later given EGF proofs via the tree function

T(x)=xe^{T(x)}

.

- 1927 — George Pólya's enumeration theorem (cycle index series) systematizes counting under symmetry — a deep OGF construction.

- 1973 — Foata & Schützenberger's combinatorial theory of formal power series cements the formal viewpoint.

- 1981 — André Joyal introduces the theory of species, giving EGFs a rigorous categorical foundation.

- 1990 — Herbert Wilf publishes generatingfunctionology, the standard undergraduate text; 2009 — Flajolet & Sedgewick's Analytic Combinatorics unifies the symbolic and asymptotic theory.

open-problem

When does a generating function have a "nice" closed form? A power series is D-finite (holonomic) if it satisfies a linear ODE with polynomial coefficients — equivalently its coefficients are P-recursive. Algebraic ⊂ D-finite, but many natural sequences are non-holonomic, and deciding holonomicity for a combinatorially defined class can be subtle. A deeper question: for a given lattice-walk model in a quadrant, when is the OGF algebraic, D-finite, or neither? The Bousquet-Mélou–Mishna classification (2010) resolved the 79 small-step quadrant models using a group-of-the-walk invariant, but extensions to higher dimensions, weighted steps, and three-quarter-plane walks remain active research. Separately, effective asymptotics from generating functions (transfer theorems, multivariate singularity analysis) is well developed for meromorphic/algebraic singularities but still open in full generality for functions with complicated singular structure.

Generating Functions — Ordinary and Exponential

Formal Statement

Why It Holds / Derivation

Building Intuition

Worked Examples

Common Misconceptions

Connections

Real-World Applications

Historical Development

Subtleties & Limits

See Also