40.01.03 · combinatorics / enumeration-generating-functions

Generating Functions: Ordinary, Exponential, and the Exponential Formula

shipped3 tiersLean: none

Anchor (Master): Stanley 1999 *Enumerative Combinatorics, Volume 2* (Cambridge) Ch. 5 (the exponential formula, the compositional formula, Lagrange inversion, and the symbolic algebra of labelled species); Flajolet-Sedgewick 2009 *Analytic Combinatorics* (Cambridge) Ch. I-II (the symbolic method, OGF/EGF dictionaries); Bender-Williamson 1991 *Foundations of Applied Combinatorics*; Euler 1748 *Introductio in analysin infinitorum* Ch. XVI (the originating generating-function method)

Intuition Beginner

Suppose someone hands you a counting problem and you compute the answers one at a time: zero of something, one of something, two, three, and so on. You get a list of numbers. The list is the honest answer, but a bare list is hard to work with — you cannot easily find a pattern, prove an identity, or jump straight to the thousandth term. A generating function is a single algebraic object that carries the entire list at once, so that the tools of algebra do the counting for you.

The trick is to hang the numbers onto the powers of a bookkeeping symbol $x$ . If your counts are $1, 1, 2, 5, 14, \dots$ , you write down the one expression $1 + 1 x + 2 x^{2} + 5 x^{3} + 14 x^{4} + \dots$ and treat it as a thing you can add, multiply, and invert. You are not plugging in a number for $x$ and you are not worrying about whether the sum settles down to a value; $x$ is a placeholder whose only job is to keep the term for each position from colliding with the others.

Why bother? Because two combinatorial operations become two clean algebraic ones. When you build a structure by laying down one labelled piece after another, the counts multiply through the product of two generating functions. When you build a structure by gluing together independent "connected" pieces in any number, the counts come out of an exponential of a generating function. So a hard problem about assembling things becomes an easy problem about multiplying, dividing, or exponentiating series.

This unit is the engine room of the whole chapter. Recurrences like the Fibonacci numbers get solved by turning them into one equation in a series and reading off the closed form. Labelled structures — ways of seating named people, partitioning a named set, drawing a graph on numbered dots — get counted by a second flavour of generating function that builds the position-number into the bookkeeping. Later chapters turn these same moves into a complete dictionary.

Visual Beginner

Think of a generating function as a clothesline. Each peg on the line is a power of $x$ : the peg $x^{0}$ , then $x^{1}$ , then $x^{2}$ , and so on, marching off to the right. On the peg $x^{n}$ you hang the count of whatever you are counting at size $n$ . The whole hung-up line, read as one algebraic expression, is the generating function.

The two basic moves are pictured in the table below. "Multiply two lines" lays one structure next to another and counts the joint sizes by pairing up pegs whose powers add to $n$ — this is the product rule. "Exponentiate a line" stacks any number of independent connected pieces and counts the result — this is the set rule that becomes the exponential formula at the next tier.

operation on structures	operation on the line	what the peg $x^{n}$ collects
lay piece A then piece B (ordered)	multiply the two lines	every split of $n$ into a part for A and a part for B
use any number of A-pieces in a row	divide by $1$ minus the A-line	every way to break $n$ into A-pieces in order
glue any number of connected pieces (labelled)	exponentiate the line	every way to partition the labels among connected pieces

Each row is a counting fact you can check on small numbers, and the rest of the unit explains why each algebraic move is exactly the right bookkeeping for its combinatorial picture.

Worked example Beginner

Let us count the Fibonacci numbers with a generating function and pull out a closed formula. The Fibonacci rule is: each term is the sum of the two before it. Starting from $0$ and $1$ , the list is $0, 1, 1, 2, 3, 5, 8, 13, \dots$

Step 1. Hang the list on the clothesline. Write $F = 0 + 1 x + 1 x^{2} + 2 x^{3} + 3 x^{4} + 5 x^{5} + \dots$ , the one expression carrying every Fibonacci number on its matching power of $x$ .

Step 2. Turn the recurrence into an equation. The rule "term $n$ equals term $n - 1$ plus term $n - 2$ " says, in clothesline language, that $F$ equals $x$ times $F$ (shift the line one peg right) plus $x^{2}$ times $F$ (shift two pegs right), with the very first peg $x^{1}$ added back because the seed $1$ has no two predecessors. That bookkeeping gives the single equation $F = x F + x^{2} F + x$ .

Step 3. Solve for the whole line at once. Collecting $F$ on the left, $F - x F - x^{2} F = x$ , so $F (1 - x - x^{2}) = x$ , and therefore $F = x \div (1 - x - x^{2})$ . One short division has captured every Fibonacci number.

Step 4. Read off a count. To find the fifth Fibonacci number without the closed form, expand the division as a series to five pegs: dividing $x$ by $1 - x - x^{2}$ yields $x + x^{2} + 2 x^{3} + 3 x^{4} + 5 x^{5} + \dots$ , and the coefficient on $x^{5}$ is $5$ . The list agrees: the fifth term after the seed is indeed $5$ .

What this tells us: a recurrence that ties each term to earlier ones becomes a single equation in a generating function, and solving that equation hands back the whole sequence as a ratio you can expand or analyze. The hard step-by-step recurrence is replaced by one division.

Check your understanding Beginner

Exercise (easy, true-false).

True or false: in a generating function, the symbol $x$ must be a small number so that the infinite sum settles down to a finite value.

Hint

Recall that $x$ is a bookkeeping placeholder, not a number you plug in. Its only job is to keep the count for each position on its own peg.

Answer

False. The symbol $x$ is a formal placeholder; you never substitute a number into it, and you never ask whether the sum converges. The whole point is to manipulate the series algebraically — add, multiply, divide — using only the rule that powers of $x$ track positions. Feedback-correct: this "formal" stance is what lets you handle sequences that grow far too fast for any number to be plugged in. Feedback-wrong: convergence matters only later, when a generating function is reinterpreted as an analytic function to extract growth rates.

Formal definition Intermediate+

Fix a commutative ring $K$ containing the rationals (so that division by $n!$ is available; take $K = Q$ or $C$ unless stated otherwise). The ring of formal power series $K [[x]]$ consists of all expressions $\sum_{n \geq 0} a_{n} x^{n}$ with $a_{n} \in K$ , added coefficientwise and multiplied by the Cauchy product $$ \Big(\sum_{n} a_n x^n\Big)\Big(\sum_{n} b_n x^n\Big) = \sum_{n} \Big(\sum_{k=0}^{n} a_k b_{n-k}\Big) x^n . $$ No convergence is assumed: $x$ is an indeterminate, and the sum defining each product coefficient is finite. The constant series $1$ is the multiplicative identity. A series is a unit (has a multiplicative inverse) if and only if its constant term $a_{0}$ is a unit of $K$ ; the inverse is computed recursively from $a_{0} b_{0} = 1$ and $\sum_{k = 0}^{n} a_{k} b_{n - k} = 0$ for $n \geq 1$ . In particular $1 - x$ is invertible with $\frac{1}{1 - x} = \sum_{n \geq 0} x^{n}$ . Formal convergence of an infinite sum or product means coefficientwise stabilisation: $\prod_{i} (1 + f_{i})$ converges when each $f_{i}$ has positive-order lowest term tending to infinity, so that every coefficient is determined by finitely many factors.

Definition (ordinary generating function). The ordinary generating function (OGF) of a sequence $(a_{n})_{n \geq 0}$ is $A (x) = \sum_{n \geq 0} a_{n} x^{n} \in K [[x]]$ . The OGF of the disjoint union of two combinatorial classes is the sum of their OGFs; the OGF of the product (ordered pairs $(α, β)$ with size $∣ α ∣ + ∣ β ∣$ ) is the product $A (x) B (x)$ , whose $x^{n}$ -coefficient $\sum_{k} a_{k} b_{n - k}$ is the convolution counting the ways to split a total size $n$ between the two coordinates. The sequence rule follows: a structure that is an ordered list of any number of parts drawn from a class with OGF $C (x)$ (and $c_{0} = 0$ ) has OGF $\frac{1}{1 - C ( x )}$ .

Definition (exponential generating function). The exponential generating function (EGF) of $(a_{n})_{n \geq 0}$ is $\hat{A} (x) = \sum_{n \geq 0} a_{n} \frac{x ^{n}}{n !}$ . EGFs are the right device for labelled structures, where the $n$ objects carry the distinct labels $1, \dots, n$ . The labelled product of two classes superimposes an $α$ -structure and a $β$ -structure on disjoint label sets whose union is ${1, \dots, n}$ ; choosing which $k$ labels go to $α$ contributes a factor $(k n)$ , so the product rule reads $$ \widehat{(A \star B)}(x) = \hat{A}(x),\hat{B}(x), \qquad (A \star B)n = \sum{k=0}^{n} \binom{n}{k} a_k, b_{n-k}, $$ the binomial convolution. Notation $\hat{A}$ , the operator $[x^{n}]$ for "coefficient of $x^{n}$ ", and the formal $exp$ , $lo g$ on $x K [[x]]$ are recorded in _meta/NOTATION.md.

Counterexamples to common slips Intermediate+

"The OGF and EGF of a sequence carry different information." They carry the same sequence $(a_{n})$ ; only the weighting of the bookkeeping symbol differs ( $x^{n}$ versus $x^{n} / n!$ ). The choice is dictated by which product rule matches the combinatorics: plain convolution (unlabelled, ordered concatenation) calls for the OGF, binomial convolution (labelled, label-splitting) for the EGF.
"A formal power series with $a_{0} = 0$ can be inverted." It cannot: invertibility requires a unit constant term. The series $x$ , $sin x$ , $e^{x} - 1$ are non-units. What a series with $a_{0} = 0$ admits instead is a compositional inverse (an inverse under substitution), provided $a_{1} \neq = 0$ — a different operation, handled by Lagrange inversion.
" $\frac{1}{1 - C ( x )}$ is the sequence rule for any class $C$ ." It requires $c_{0} = 0$ (no empty part), otherwise $1 - C (0) = 0$ and the geometric expansion fails to converge formally — there would be infinitely many ways to pad with empty parts, so the coefficient is undefined.
" $exp$ of a series always makes sense formally." Formal $exp (f) = \sum_{n} f^{n} / n!$ converges coefficientwise only when $f$ has zero constant term; otherwise the constant terms $f (0)^{n} / n!$ do not stabilise. This is why the exponential formula applies to connected structures of positive size.

Key theorem with proof Intermediate+

The signature theorem is the exponential formula, because it is the single statement that turns "a labelled structure is a set of connected components" into "the EGF of all structures is the exponential of the EGF of the connected ones", and every later set-construction in analytic combinatorics is an instance of it.

Theorem (exponential formula). Let a class of labelled structures be such that every structure on a label set $S$ is determined by a partition of $S$ into nonempty blocks together with a "connected" structure on each block, with connected structures counted by $c_{n}$ on an $n$ -element label set and $c_{0} = 0$ . Let $C (x) = \sum_{n \geq 1} c_{n} \frac{x ^{n}}{n !}$ be the EGF of the connected structures and $H (x) = \sum_{n \geq 0} h_{n} \frac{x ^{n}}{n !}$ the EGF of all structures, where $h_{n}$ counts the structures on an $n$ -set (with $h_{0} = 1$ , the empty structure). Then $$ H(x) = \exp\big(C(x)\big) = \sum_{k \ge 0} \frac{C(x)^k}{k!}. $$

Proof. A structure on ${1, \dots, n}$ is a set partition $π = {B_{1}, \dots, B_{k}}$ of ${1, \dots, n}$ together with, on each block $B_{i}$ , a connected structure, of which there are $c_{∣ B_{i} ∣}$ . Summing over the number $k$ of blocks and over all partitions into $k$ blocks, $$ h_n = \sum_{k \ge 0} ;\sum_{\substack{B_1 \sqcup \cdots \sqcup B_k = {1,\dots,n} \ B_i \ne \varnothing}} \frac{1}{k!}\prod_{i=1}^{k} c_{|B_i|}, $$ where dividing by $k!$ compensates for ordering the (unordered) blocks. Fix $k$ and the block sizes $n_{1}, \dots, n_{k}$ with $\sum n_{i} = n$ . The number of ordered set partitions of ${1, \dots, n}$ into blocks of these sizes is the multinomial coefficient $(n _{1} , \dots , n _{k} n) = \frac{n !}{n _{1} ! \dots n _{k} !}$ . Hence $$ \frac{h_n}{n!} = \sum_{k \ge 0} \frac{1}{k!} \sum_{\substack{n_1 + \cdots + n_k = n \ n_i \ge 1}} \prod_{i=1}^{k} \frac{c_{n_i}}{n_i!}. $$ The inner sum is exactly the $x^{n}$ -coefficient of $C (x)^{k}$ , since multiplying $k$ copies of $C (x) = \sum_{m \geq 1} \frac{c _{m}}{m !} x^{m}$ and collecting the $x^{n}$ term sums $\prod_{i} \frac{c _{n_{i}}}{n _{i} !}$ over all compositions $n_{1} + \dots + n_{k} = n$ with $n_{i} \geq 1$ . Therefore $\frac{h _{n}}{n !} = \sum_{k \geq 0} \frac{1}{k !} [x^{n}] C (x)^{k} = [x^{n}] \sum_{k \geq 0} \frac{C ( x ) ^{k}}{k !} = [x^{n}] exp (C (x))$ . Equating EGFs gives $H (x) = exp (C (x))$ . $□$

Corollary (set partitions and Bell numbers). Take the connected structures to be single nonempty blocks with exactly one structure each: $c_{n} = 1$ for $n \geq 1$ , so $C (x) = \sum_{n \geq 1} \frac{x ^{n}}{n !} = e^{x} - 1$ . Then $H (x) = exp (e^{x} - 1) = \sum_{n} B_{n} \frac{x ^{n}}{n !}$ , recovering the Bell-number EGF $e^{e^{x} - 1}$ ; refining by the number of blocks $k$ gives $\sum_{n \geq k} S (n, k) \frac{x ^{n}}{n !} = \frac{( e ^{x} - 1 ) ^{k}}{k !}$ , the Stirling-second EGF foreshadowed at 40.01.01.

Bridge. This theorem is the foundational reason ordinary and exponential generating functions are two specialisations of one idea rather than two tricks: the OGF product rule counts ordered concatenation by plain convolution, and the exponential formula is exactly the labelled analogue where unordered gluing of connected pieces is counted by the binomial convolution iterated, which builds toward the symbolic method of 40.08.01. The set-of-connected-pieces picture generalises the permutation-as-product-of-cycles decomposition — there the connected pieces are cycles with $c_{n} = (n - 1)!$ and $C (x) = lo g \frac{1}{1 - x}$ , so $exp (C (x)) = \frac{1}{1 - x}$ recovers $n!$ permutations — and it is dual to the OGF sequence rule $\frac{1}{1 - C}$ in the sense that "set" replaces "sequence" precisely when labels are present. Putting these together, the appearance of $exp$ here and of $\frac{1}{1 - C}$ in the sequence rule is the central insight that each combinatorial construction has one canonical generating-function operation, and this same dictionary appears again in 40.01.04 where the rational case is solved by transfer matrices and in 40.01.07 where the tree recursions are inverted by Lagrange inversion.

Exercises Intermediate+

Exercise 3 (medium, symbolic).

Solve the recurrence $a_{n} = 3 a_{n - 1} - 2 a_{n - 2}$ with $a_{0} = 0$ , $a_{1} = 1$ by the OGF method, and give a closed form for $a_{n}$ .

Hint

Form $A (x) = \sum a_{n} x^{n}$ , multiply the recurrence by $x^{n}$ and sum over $n \geq 2$ , and solve for $A$ . Factor the denominator and use partial fractions.

Answer

Let $A (x) = \sum_{n \geq 0} a_{n} x^{n}$ . Multiplying $a_{n} = 3 a_{n - 1} - 2 a_{n - 2}$ by $x^{n}$ and summing over $n \geq 2$ gives $A - a_{0} - a_{1} x = 3 x (A - a_{0}) - 2 x^{2} A$ , i.e. $A - x = 3 x A - 2 x^{2} A$ . Hence $A (1 - 3 x + 2 x^{2}) = x$ , and since $1 - 3 x + 2 x^{2} = (1 - x) (1 - 2 x)$ , $$ A(x) = \frac{x}{(1-x)(1-2x)} = \frac{-1}{1-x} + \frac{1}{1-2x}, $$ by partial fractions (solve $x = a (1 - 2 x) + b (1 - x)$ : at $x = 1$ , $1 = - a$ so $a = - 1$ ; at $x = \frac{1}{2}$ , $\frac{1}{2} = \frac{1}{2} b$ so $b = 1$ ). Reading off coefficients, $a_{n} = - 1 + 2^{n} = 2^{n} - 1$ . Check: $a_{0} = 0$ , $a_{1} = 1$ , $a_{2} = 3$ , matching $3 \cdot 1 - 2 \cdot 0 = 3$ . Rubric: full credit for forming the rational OGF, the partial-fraction split, and the closed form $2^{n} - 1$ .

Exercise 4 (medium, symbolic).

Let $C (x) = \sum_{n \geq 0} C_{n} x^{n}$ be the OGF of the Catalan numbers, satisfying $C = 1 + x C^{2}$ (a nonempty binary tree is a root with an ordered pair of subtrees). Solve the quadratic for $C (x)$ and extract $C_{n} = \frac{1}{n + 1} (n 2 n)$ .

Hint

The quadratic $x C^{2} - C + 1 = 0$ has $C = \frac{1 - 1 - 4 x}{2 x}$ (the root with $C (0) = 1$ ). Expand $1 - 4 x$ by the binomial series.

Answer

Solving $x C^{2} - C + 1 = 0$ by the quadratic formula gives $C = \frac{1 \pm 1 - 4 x}{2 x}$ . The $+$ root blows up as $x \to 0$ , so the formal-power-series solution is $C (x) = \frac{1 - 1 - 4 x}{2 x}$ . The binomial series gives $1 - 4 x = \sum_{k \geq 0} (k 1/2) (- 4 x)^{k}$ , and $(k 1/2) (- 4)^{k} = - \frac{2}{k} (k - 1 2 k - 2)$ for $k \geq 1$ , so $$ 1 - \sqrt{1-4x} = \sum_{k \ge 1}\frac{2}{k}\binom{2k-2}{k-1}x^k, \quad C(x) = \sum_{k \ge 1}\frac{1}{k}\binom{2k-2}{k-1}x^{k-1} = \sum_{n \ge 0}\frac{1}{n+1}\binom{2n}{n}x^n, $$ re-indexing $n = k - 1$ . Thus $C_{n} = \frac{1}{n + 1} (n 2 n)$ . Rubric: full credit for selecting the correct root, the binomial expansion of $1 - 4 x$ , and the re-indexing to the Catalan closed form.

Exercise 7 (hard, symbolic).

Let $D_{n}$ be the number of derangements (fixed-point-free permutations) of $n$ labels. A permutation is a set of cycles, and a derangement is a set of cycles each of length $\geq 2$ . Use the exponential formula to derive the EGF $\sum_{n} D_{n} \frac{x ^{n}}{n !} = \frac{e ^{- x}}{1 - x}$ , and deduce $D_{n} = n! \sum_{k = 0}^{n} \frac{( - 1 ) ^{k}}{k !}$ .

Hint

The connected pieces are cycles of length $\geq 2$ , with EGF $C (x) = lo g \frac{1}{1 - x} - x$ (subtract the length- $1$ cycle term $x$ ). Then the EGF of all derangements is $exp (C (x))$ .

Answer

Cycles of length $m \geq 1$ have $(m - 1)!$ structures on $m$ labels, giving the full cycle EGF $lo g \frac{1}{1 - x} = \sum_{m \geq 1} \frac{x ^{m}}{m}$ . Removing the length- $1$ cycles (the $m = 1$ term $x$ ) leaves the connected-piece EGF for derangements $C (x) = lo g \frac{1}{1 - x} - x$ . By the exponential formula the EGF of derangements is $$ \exp!\Big(\log\tfrac{1}{1-x} - x\Big) = e^{-x}\exp!\Big(\log\tfrac{1}{1-x}\Big) = \frac{e^{-x}}{1-x}. $$ Now $e^{- x} = \sum_{k} \frac{( - 1 ) ^{k}}{k !} x^{k}$ and $\frac{1}{1 - x} = \sum_{j} x^{j}$ , so the OGF-style product (Cauchy product of the two series, then re-weight) gives $[x^{n}] \frac{e ^{- x}}{1 - x} = \sum_{k = 0}^{n} \frac{( - 1 ) ^{k}}{k !}$ . Since this is the EGF coefficient $D_{n} / n!$ , we obtain $D_{n} = n! \sum_{k = 0}^{n} \frac{( - 1 ) ^{k}}{k !}$ , the inclusion-exclusion count, with $D_{n} / n! \to e^{- 1}$ . Rubric: full credit for the cycle-EGF with length- $1$ removed, the factorisation $e^{- x} / (1 - x)$ , and the extraction of the alternating sum.

Exercise 8 (hard, symbolic).

Prove the EGF product rule: if $\hat{A}, \hat{B}$ are the EGFs of $(a_{n}), (b_{n})$ , then $\hat{A} (x) \hat{B} (x)$ is the EGF of the binomial convolution $h_{n} = \sum_{k = 0}^{n} (k n) a_{k} b_{n - k}$ , and interpret it as counting labelled products.

Hint

Multiply $\sum a_{k} \frac{x ^{k}}{k !}$ by $\sum b_{j} \frac{x ^{j}}{j !}$ , collect the $x^{n}$ term, and multiply and divide by $n!$ .

Answer

Compute the Cauchy product $$ \hat{A}(x)\hat{B}(x) = \Big(\sum_{k}a_k\frac{x^k}{k!}\Big)\Big(\sum_{j}b_j\frac{x^j}{j!}\Big) = \sum_{n}\Big(\sum_{k=0}^{n}\frac{a_k}{k!}\frac{b_{n-k}}{(n-k)!}\Big)x^n . $$ Multiplying the inner coefficient by $\frac{n !}{n !}$ gives $\frac{1}{n !} \sum_{k = 0}^{n} \frac{n !}{k ! ( n - k )!} a_{k} b_{n - k} = \frac{1}{n !} \sum_{k = 0}^{n} (k n) a_{k} b_{n - k}$ , so $\hat{A} \hat{B} = \sum_{n} h_{n} \frac{x ^{n}}{n !}$ with $h_{n} = \sum_{k} (k n) a_{k} b_{n - k}$ . Combinatorially: a labelled product structure on ${1, \dots, n}$ is an $a$ -structure on a chosen $k$ -subset and a $b$ -structure on the complementary $(n - k)$ -subset; the subset is chosen in $(k n)$ ways, giving exactly the binomial convolution. Rubric: full credit for the Cauchy product, the $n!$ normalisation producing $(k n)$ , and the labelled-product interpretation (choice of label subset).

Advanced results Master

The two product rules and the exponential formula are the elementary stratum; their reach extends through rational-function asymptotics, the compositional formula, Lagrange inversion, and the species-level algebra that unifies the OGF and EGF dictionaries.

Theorem 1 (rational generating functions and linear recurrences). A sequence $(a_{n})$ satisfies a linear recurrence with constant coefficients $a_{n} = \sum_{i = 1}^{d} c_{i} a_{n - i}$ for $n \geq d$ if and only if its OGF is a rational function $A (x) = P (x) / Q (x)$ with $Q (x) = 1 - c_{1} x - \dots - c_{d} x^{d}$ and $de g P < d$ . Partial-fraction decomposition over $C$ writes $A (x) = \sum_{j} \frac{R _{j} ( x )}{( 1 - ρ _{j} x ) ^{m_{j}}}$ , where the $ρ_{j}$ are the reciprocals of the roots of $Q$ ; reading coefficients gives $a_{n} = \sum_{j} π_{j} (n) ρ_{j}^{n}$ with $π_{j}$ a polynomial of degree $< m_{j}$ . The dominant term is governed by the $ρ_{j}$ of largest modulus, so $a_{n} \sim c n^{m - 1} ρ^{n}$ ; for Fibonacci $ρ = φ = \frac{1 + 5}{2}$ gives $F_{n} \sim φ^{n} / 5$ ^{[Stanley §4.1]}.

Theorem 2 (compositional formula). If a labelled structure is built by partitioning the label set, placing a connected $F$ -structure on each block, and then placing a single $G$ -structure on the set of blocks (treated as a new labelled set), then the EGFs compose: the EGF of the composite is $\hat{G} (\hat{F} (x))$ , provided $\hat{F} (0) = 0$ . The exponential formula is the case $\hat{G} = exp$ (an unstructured set of blocks). Functional substitution of EGFs thus models "a structure of structures", and the requirement $\hat{F} (0) = 0$ is the same zero-constant-term condition that makes formal composition well-defined ^{[Stanley §5.1]}.

Theorem 3 (Lagrange inversion). Let $ϕ (x) \in K [[x]]$ with $ϕ (0) \neq = 0$ , and let $w = w (x)$ be the unique formal power series with $w (0) = 0$ solving $w = x ϕ (w)$ . Then for any formal Laurent series $H$ and $n \geq 1$ , $$ [x^n],H(w(x)) = \frac{1}{n}[w^{n-1}]\big(H'(w),\phi(w)^n\big), \qquad [x^n],w(x) = \frac{1}{n}[w^{n-1}],\phi(w)^n . $$ This inverts the tree-type functional equations directly: the EGF $T (x)$ of labelled rooted trees satisfies $T = x e^{T}$ (a root attached to a set of subtrees), so $ϕ = e^{w}$ and $[x^{n}] T = \frac{1}{n} [w^{n - 1}] e^{n w} = \frac{n ^{n - 1}}{n !}$ , recovering Cayley's count $n^{n - 1}$ of labelled rooted trees. The full development and forward applications live at 40.01.07 ^{[Stanley §5.4]}.

Theorem 4 (symbolic dictionary). For unlabelled classes the admissible constructions translate to OGF operations: disjoint union to $+$ , product to $\times$ , sequence $SEQ$ to $\frac{1}{1 - C}$ , multiset $MSET$ to $exp (\sum_{k \geq 1} \frac{1}{k} C (x^{k}))$ (Euler transform), cycle $CYC$ to $\sum_{k \geq 1} \frac{φ ( k )}{k} lo g \frac{1}{1 - C ( x ^{k} )}$ . For labelled classes the EGF operations are $+$ , the labelled product $\times$ , sequence to $\frac{1}{1 - C}$ , set $SET$ to $exp (C)$ , cycle $CYC$ to $lo g \frac{1}{1 - C}$ . The exponential formula is the labelled $SET$ row; the entire chapter is the systematic exploitation of this table, made analytic in 40.08.01.

Theorem 5 (multivariate refinement). Introducing a second variable $u$ marking a statistic (number of components, number of parts, number of cycles) refines the exponential formula to $H (x, u) = exp (u C (x))$ , whose $u^{k}$ -coefficient is $\frac{C ( x ) ^{k}}{k !}$ — the EGF of structures with exactly $k$ connected components. Setting $u = 1$ recovers the univariate count; differentiating in $u$ at $u = 1$ extracts the mean number of components. For set partitions $H (x, u) = e^{u (e^{x} - 1)}$ is the bivariate Bell EGF whose $u^{k}$ -coefficient is $\frac{( e ^{x} - 1 ) ^{k}}{k !} = \sum_{n} S (n, k) \frac{x ^{n}}{n !}$ , the Stirling-second EGF of 40.01.01.

Synthesis. The generating-function method is the foundational reason enumeration and algebra are the same subject viewed twice: a sequence becomes a single element of $K [[x]]$ , and each way of assembling combinatorial objects becomes one canonical operation on that ring — ordered concatenation is convolution, so the OGF sequence rule is $\frac{1}{1 - C}$ ; labelled gluing of connected pieces is the binomial convolution iterated, so the EGF set rule is $exp (C)$ . The central insight is that this is one dictionary, not two: the OGF and EGF are the unlabelled and labelled specialisations of the symbolic method, and the exponential formula, the compositional formula, and Lagrange inversion are exactly the $SET$ , substitution, and inversion entries of that dictionary. Putting these together, rational OGFs solve linear recurrences because partial fractions diagonalise the convolution, and this is dual to the way $exp$ diagonalises the set construction; the bridge is that every closed form in the chapter — Fibonacci's golden ratio, Catalan's $\frac{1}{n + 1} (n 2 n)$ , Cayley's $n^{n - 1}$ , the Bell EGF $e^{e^{x} - 1}$ — is the coefficient extraction from one of these canonical operations, and this generalises directly into the analytic combinatorics of 40.08.01, where the location and nature of the singularities of the same generating functions deliver the asymptotic growth that the formal theory leaves implicit. The formal ring and the analytic function are one object read at two resolutions.

Full proof set Master

Proposition 1 (unit criterion and the sequence rule). A series $A = \sum_{n} a_{n} x^{n} \in K [[x]]$ is invertible iff $a_{0}$ is a unit of $K$ ; consequently, for $C$ with $c_{0} = 0$ , the geometric series $\frac{1}{1 - C} = \sum_{k \geq 0} C^{k}$ converges formally and is the OGF of sequences of $C$ -parts.

Proof. If $A B = 1$ then $a_{0} b_{0} = 1$ , so $a_{0}$ is a unit. Conversely, given $a_{0}$ a unit, define $b_{0} = a_{0}^{- 1}$ and recursively $b_{n} = - a_{0}^{- 1} \sum_{k = 1}^{n} a_{k} b_{n - k}$ ; then $\sum_{k = 0}^{n} a_{k} b_{n - k} = δ_{n 0}$ by construction, so $B = \sum_{n} b_{n} x^{n}$ is a two-sided inverse (the ring is commutative). For the sequence rule, $C$ with $c_{0} = 0$ has lowest term of order $\geq 1$ , so $C^{k}$ has lowest term of order $\geq k$ ; for fixed $n$ only the terms $k \leq n$ contribute to $[x^{n}] \sum_{k} C^{k}$ , a finite sum, giving formal convergence. The coefficient $[x^{n}] C^{k}$ counts ordered $k$ -tuples of $C$ -parts of total size $n$ , and summing over $k$ counts all ordered sequences of parts, the sequence-rule interpretation. Since $1 - C$ has constant term $1$ (a unit), it is invertible, and $(1 - C) \sum_{k} C^{k} = 1$ identifies $\sum_{k} C^{k} = \frac{1}{1 - C}$ . $□$

Proposition 2 (EGF product rule, labelled product). The EGF of the labelled product $A ⋆ B$ is $\hat{A} \hat{B}$ , with $(A ⋆ B)_{n} = \sum_{k} (k n) a_{k} b_{n - k}$ .

Proof. A labelled product structure on ${1, \dots, n}$ consists of a choice of subset $S \subseteq {1, \dots, n}$ to carry an $A$ -structure (with the complement carrying a $B$ -structure), where the labels in $S$ and in its complement are order-isomorphically relabelled to ${1, \dots, ∣ S ∣}$ and ${1, \dots, n - ∣ S ∣}$ . For $∣ S ∣ = k$ there are $(k n)$ subsets, $a_{k}$ structures on $S$ , and $b_{n - k}$ on the complement, giving $(k n) a_{k} b_{n - k}$ ; summing over $k$ yields $(A ⋆ B)_{n}$ . The Cauchy product of $\hat{A} = \sum_{k} a_{k} x^{k} / k!$ and $\hat{B} = \sum_{j} b_{j} x^{j} / j!$ has $x^{n}$ -coefficient $\sum_{k} \frac{a _{k}}{k !} \frac{b _{n - k}}{( n - k )!} = \frac{1}{n !} \sum_{k} (k n) a_{k} b_{n - k}$ , so $\hat{A} \hat{B} = \sum_{n} (A ⋆ B)_{n} \frac{x ^{n}}{n !}$ . $□$

Proposition 3 (exponential formula, component-marked form). With $C (x) = \sum_{n \geq 1} c_{n} \frac{x ^{n}}{n !}$ the connected EGF and $u$ marking the number of components, the EGF of all structures is $H (x, u) = exp (u C (x))$ , and $[u^{k}] H = \frac{C ( x ) ^{k}}{k !}$ is the EGF of structures with exactly $k$ components.

Proof. A structure with exactly $k$ components on ${1, \dots, n}$ is an unordered partition into $k$ nonempty blocks with a connected structure on each. Ordering the blocks and dividing by $k!$ , and grouping by the size profile $(n_{1}, \dots, n_{k})$ as in the Key theorem, the EGF of $k$ -component structures is $\frac{1}{k !} (\sum_{m \geq 1} c_{m} \frac{x ^{m}}{m !})^{k} = \frac{C ( x ) ^{k}}{k !}$ , because the $k$ -fold product of $C$ sums $\prod_{i} \frac{c _{n_{i}}}{n _{i} !}$ over compositions $n_{1} + \dots + n_{k} = n$ , and the multinomial $(n _{1} , \dots , n _{k} n)$ supplies the labelled count exactly as in Proposition 2 iterated. Marking each component by $u$ and summing over $k$ gives $H (x, u) = \sum_{k \geq 0} u^{k} \frac{C ( x ) ^{k}}{k !} = exp (u C (x))$ . Setting $u = 1$ recovers $H (x) = exp (C (x))$ . $□$

Proposition 4 (Lagrange inversion, coefficient form). Let $ϕ (0) \neq = 0$ and $w = x ϕ (w)$ with $w (0) = 0$ , $w^{'} (0) = ϕ (0) \neq = 0$ . Then $[x^{n}] w = \frac{1}{n} [w^{n - 1}] ϕ (w)^{n}$ for $n \geq 1$ .

Proof. Since $w^{'} (0) \neq = 0$ , $w$ has a compositional inverse $x = x (w) = w / ϕ (w)$ . For $n \geq 1$ , by the formal residue calculus $[x^{n}] w = \frac{1}{2 π i} \oint \frac{w}{x ^{n + 1}} d x$ (formal contour integral / residue at $0$ ), and integrating by parts on the formal level, $[x^{n}] w = \frac{1}{n} Res_{x} \frac{w ^{'}}{x ^{n}}$ . Changing the variable of the formal residue from $x$ to $w$ via $x = w / ϕ (w)$ , $d x =$ the formal differential, gives $\frac{1}{n} Res_{w} \frac{1}{x ^{n}} = \frac{1}{n} Res_{w} \frac{ϕ ( w ) ^{n}}{w ^{n}} = \frac{1}{n} [w^{n - 1}] ϕ (w)^{n}$ , where the residue $Res_{w} f = [w^{- 1}] f$ picks the $w^{n - 1}$ coefficient of $ϕ (w)^{n}$ . The change-of-variable for formal residues is invariant because $Res$ is a well-defined linear functional annihilating derivatives. Applying this to $T = x e^{T}$ ( $ϕ = e^{w}$ ) gives $[x^{n}] T = \frac{1}{n} [w^{n - 1}] e^{n w} = \frac{1}{n} \cdot \frac{n ^{n - 1}}{( n - 1 )!} = \frac{n ^{n - 1}}{n !}$ , so $T_{n} = n! [x^{n}] T = n^{n - 1}$ . $□$

Connections Master

The rational-OGF solution of linear recurrences by partial fractions specialises, when the recurrence is encoded by a finite automaton or a weighted digraph, to the transfer-matrix method: the OGF becomes $\frac{d e t ( I - x A ) _{cofactor}}{d e t ( I - x A )}$ for a transition matrix $A$ , and the same denominator $det (I - x A)$ governs the recurrence. That refinement, with its applications to walks, tilings, and the cluster method, is owned by 40.01.04; this unit supplies the underlying partial-fraction asymptotics that read coefficients off any rational generating function.
Lagrange inversion, previewed here on $T = x e^{T}$ and the Catalan quadratic, is the engine that inverts every tree-type functional equation, and its full statement (the Bürmann form, the residue calculus, and the enumeration of labelled and plane trees) is developed at 40.01.07. The forward link is exact: the exponential formula gives the EGF of a set of components, and Lagrange inversion gives the EGF of a root attached to a set of components, so trees are the recursive closure of the set construction proved here.
The OGF/EGF symbolic dictionary — disjoint union, product, sequence, set, cycle mapping to $+, \times, \frac{1}{1 - C}, exp (C), lo g \frac{1}{1 - C}$ — is exactly the symbolic method that organises 40.08.01, where the constructions are made into an automatic translation scheme and the singularity structure of the resulting generating functions yields asymptotic counts. This unit is the formal-power-series foundation those analytic results stand on: the exponential formula is the labelled SET row, and analytic combinatorics adds the complex-analytic coefficient asymptotics.
The exponential formula's instances — set partitions with EGF $e^{e^{x} - 1}$ , permutations as sets of cycles with $exp (lo g \frac{1}{1 - x}) = \frac{1}{1 - x}$ — are the generating-function repackaging of the surjection and partition counts of 40.01.01; the twelvefold-way Stirling cells $\sum_{n} S (n, k) \frac{x ^{n}}{n !} = \frac{( e ^{x} - 1 ) ^{k}}{k !}$ are precisely the component-marked exponential formula applied to nonempty blocks, so the elementary table is the source data and this unit is its generating-function lift.

Historical & philosophical context Master

The generating-function method originates with Euler's 1748 Introductio in analysin infinitorum ^{[Euler 1748]}, where the product $\prod_{n} (1 - x^{n})^{- 1}$ is introduced to count integer partitions and the coefficients of an infinite product are read as combinatorial counts — the founding act of treating a formal series as a bookkeeping device for a sequence. Abraham de Moivre had used recurrence-to-rational-function arguments somewhat earlier (in the analysis of the Fibonacci-type recurrences arising from his work on annuities and probability, 1718–1730), giving the first systematic use of the partial-fraction reading of a linear recurrence.

The exponential generating function and the exponential formula crystallised much later. The combinatorial content — that the EGF of a structure built from connected components is the exponential of the connected EGF — appears in the cycle-index work of Pólya (1937) and was placed on a fully structural footing by André Joyal's 1981 theory of species ^{[Stanley §5.1, citing Joyal]}, which recast labelled structures as functors and the OGF/EGF passage as the move from a species to its generating series; the SET, SEQ, and CYC constructions and their exponential, geometric, and logarithmic generating-function images are the operations of that category. Lagrange's 1770 reversion of series supplied the inversion half of the dictionary, later given its residue-calculus form by Bürmann. The synthesis into a single algorithmic "symbolic method" with analytic coefficient asymptotics is due to Flajolet and Sedgewick, whose Analytic Combinatorics (2009) made the OGF/EGF dictionary and its singularity analysis a complete framework, the form in which the method is now taught and the foundation on which 40.08.01 builds.

Bibliography Master

@book{stanley2012ec1,
  author    = {Stanley, Richard P.},
  title     = {Enumerative Combinatorics, Volume 1},
  series    = {Cambridge Studies in Advanced Mathematics},
  volume    = {49},
  edition   = {2},
  publisher = {Cambridge University Press},
  year      = {2012}
}

@book{stanley1999ec2,
  author    = {Stanley, Richard P.},
  title     = {Enumerative Combinatorics, Volume 2},
  series    = {Cambridge Studies in Advanced Mathematics},
  volume    = {62},
  publisher = {Cambridge University Press},
  year      = {1999}
}

@book{wilf2006gfology,
  author    = {Wilf, Herbert S.},
  title     = {generatingfunctionology},
  edition   = {3},
  publisher = {A K Peters},
  year      = {2006}
}

@book{flajoletsedgewick2009,
  author    = {Flajolet, Philippe and Sedgewick, Robert},
  title     = {Analytic Combinatorics},
  publisher = {Cambridge University Press},
  year      = {2009}
}

@book{gkp1994concrete,
  author    = {Graham, Ronald L. and Knuth, Donald E. and Patashnik, Oren},
  title     = {Concrete Mathematics: A Foundation for Computer Science},
  edition   = {2},
  publisher = {Addison-Wesley},
  year      = {1994}
}

@book{euler1748introductio,
  author    = {Euler, Leonhard},
  title     = {Introductio in analysin infinitorum},
  volume    = {1},
  publisher = {Marcum-Michaelem Bousquet},
  address   = {Lausanne},
  year      = {1748}
}

@article{joyal1981species,
  author  = {Joyal, Andr\'{e}},
  title   = {Une th\'{e}orie combinatoire des s\'{e}ries formelles},
  journal = {Advances in Mathematics},
  volume  = {42},
  number  = {1},
  year    = {1981},
  pages   = {1--82}
}

@article{polya1937cycleindex,
  author  = {P\'{o}lya, George},
  title   = {Kombinatorische Anzahlbestimmungen f\"{u}r Gruppen, Graphen und chemische Verbindungen},
  journal = {Acta Mathematica},
  volume  = {68},
  year    = {1937},
  pages   = {145--254}
}

Prerequisites

40.01.01

Tier anchors

beginner: Wilf 2006 *generatingfunctionology* 3e (A K Peters) Ch. 1 (the 'method', turning a sequence into a function and back); Graham-Knuth-Patashnik 1994 *Concrete Mathematics* 2e (Addison-Wesley) Ch. 7 for the hands-on Fibonacci/closed-form bookkeeping
intermediate: Stanley 2012 *Enumerative Combinatorics, Volume 1* 2e (Cambridge) §1.1 (formal power series), §2.1-2.4 (exponential generating functions and the exponential formula); Wilf 2006 *generatingfunctionology* 3e Ch. 2-3 (series, recurrences, and EGFs)
master: Stanley 1999 *Enumerative Combinatorics, Volume 2* (Cambridge) Ch. 5 (the exponential formula, the compositional formula, Lagrange inversion, and the symbolic algebra of labelled species); Flajolet-Sedgewick 2009 *Analytic Combinatorics* (Cambridge) Ch. I-II (the symbolic method, OGF/EGF dictionaries); Bender-Williamson 1991 *Foundations of Applied Combinatorics*; Euler 1748 *Introductio in analysin infinitorum* Ch. XVI (the originating generating-function method)

References

Stanley, R. P. — Enumerative Combinatorics, Volume 1 and Volume 2 · Vol. 1 (Cambridge Studies in Advanced Mathematics 49, 2e 2012) §1.1 builds the ring of formal power series $K[[x]]$, units (invertible iff non-zero constant term), formal differentiation, composition, and the product rule for ordinary generating functions as convolution; §2.1-2.4 develop exponential generating functions, the binomial/labelled product rule $h_n = \sum_k \binom{n}{k} f_k g_{n-k}$, and the exponential formula EGF(all) = exp(EGF(connected)) with set partitions (Bell numbers, $e^{e^x-1}$) and permutations by cycles ($1/(1-x)$, $e^{-\log(1-x)}$) as the worked instances. Vol. 2 (1999) Ch. 5 gives the exponential formula and compositional formula in full, Lagrange inversion (Theorem 5.4.2), and the species/symbolic algebra of labelled structures.
Wilf, H. S. — generatingfunctionology · A K Peters, 3rd edition (2006). Chapter 1 introduces the generating function as the 'clothesline on which we hang up a sequence for display'; Chapter 2 develops the algebra of ordinary generating functions, the geometric-series and binomial-series identities, partial fractions for rational generating functions and the resulting closed forms for linear-recurrence solutions (Fibonacci, the Catalan quadratic); Chapter 3 treats exponential generating functions, the product rule as the binomial convolution, and the exponential formula for set constructions.
Flajolet, P. & Sedgewick, R. — Analytic Combinatorics · Cambridge University Press (2009). Part A (Chapters I-III) sets up the symbolic method: an unlabelled combinatorial class maps to an ordinary generating function and a labelled class to an exponential generating function, with the admissible constructions (disjoint union, product, sequence, multiset, set, cycle) translating to closed operations on generating functions ($+$, $\times$, $1/(1-f)$, $\exp$, $\log\frac{1}{1-f}$). The SET construction giving $\exp$ is exactly the exponential formula; Lagrange inversion (Note I.49, Theorem A.2) handles the tree/composition recursions.
Graham, R. L., Knuth, D. E. & Patashnik, O. — Concrete Mathematics · Addison-Wesley, 2nd edition (1994). Chapter 7 'Generating Functions' develops the bookkeeping by hand: the Fibonacci generating function $x/(1-x-x^2)$ and its partial-fraction closed form via the golden ratio, the Catalan generating function from the quadratic $C = 1 + xC^2$, convolution as the combinatorial meaning of the product, and exponential generating functions for labelled problems.

Estimated time

beginner: 20m
intermediate: 50m
master: 90m