Chapter 10: Generating Functions and Recurrence Relations

Can a tiling recurrence become a coefficient formula?

Tile a strip of $n$ unit cells using monomers of length $1$ and dominoes of length $2$. Tiles cover every cell exactly once, and their left-to-right order matters. Let $a_n$ count the tilings. There is one empty tiling, so $a_0=1$; also $a_1=1$.

The first tile is either a monomer, leaving a strip of length $n-1$, or a domino, leaving length $n-2$. These cases are disjoint and reversible, giving $a_n=a_{n-1}+a_{n-2}$ for $n\ge2$. A recurrence calculates successive counts. Can it also produce a formula for an arbitrary coefficient, refine the count by domino number, and connect to other recursive objects?

We will encode counts in power series and translate combinatorial decompositions into algebra. The prerequisites are induction and recursive reasoning, binomial identities, partitions, and inclusion–exclusion.

10.1 Ordinary generating functions

For a sequence $a_0,a_1,\ldots$, its ordinary generating function, or OGF, is

$$ A(x)=\sum_{n\ge0}a_nx^n. $$

The coefficient notation $[x^n]A(x)$ means “the coefficient of $x^n$,” so $a_n=[x^n]A(x)$. The variable $x$ records size. Initially, treat the series as a bookkeeping object: equality means equality of every coefficient. Numerical convergence is not needed for the calculations here.

For example, one object of each nonnegative size has OGF $1+x+x^2+\cdots=1/(1-x)$. Binary words have $2^n$ choices at length $n$, giving $1/(1-2x)$.

Worked example: the tiling OGF. Multiply $a_n=a_{n-1}+a_{n-2}$ by $x^n$ and sum for $n\ge2$. Removing the initial terms carefully gives

$$ A(x)-1-x=x\bigl(A(x)-1\bigr)+x^2A(x). $$

Thus

$$ (1-x-x^2)A(x)=1, \qquad A(x)=\frac{1}{1-x-x^2}. $$

The numerator is determined by the initial values. Omitting them would incorrectly produce a homogeneous equation with zero right side.

There is also a direct decomposition: a tiling is an ordered sequence of tiles, each contributing weight $x$ or $x^2$. Therefore

$$ A(x)=\sum_{j\ge0}(x+x^2)^j=\frac{1}{1-x-x^2}. $$

The empty sequence contributes $1$. For any fixed coefficient, only finitely many values of $j$ contribute, because every tile has positive length.

Exercise. What is the OGF for words formed from three distinct symbols? Hint: there are three choices at each position. Answer: $\sum_{n\ge0}3^nx^n=1/(1-3x)$, including the empty word.

10.2 Linear homogeneous and nonhomogeneous recurrences

A linear recurrence with constant coefficients has the form

$$ a_n=c_1a_{n-1}+\cdots+c_da_{n-d}+h_n \qquad(n\ge d), $$

where the constants $c_i$ are fixed and $a_0,\ldots,a_{d-1}$ are specified. It is homogeneous when $h_n=0$ and nonhomogeneous when a forcing term $h_n$ is present. The initial values and recurrence determine the sequence uniquely.

Set $Q(x)=1-c_1x-\cdots-c_dx^d$. Summing after multiplication by $x^n$ gives

$$ Q(x)A(x)=P(x)+\sum_{n\ge d}h_nx^n, $$

where the initial-value polynomial is

$$ P(x)=\sum_{j=0}^{d-1}\left(a_j-\sum_{i=1}^{j}c_i a_{j-i}\right)x^j. $$

The inner sum is empty for $j=0$. Consequently, homogeneous constant-coefficient recurrences have rational OGFs; rational forcing also produces a rational OGF.

The characteristic equation for the homogeneous recurrence is $r^d-c_1r^{d-1}-\cdots-c_d=0$, obtained by testing $a_n=r^n$. Distinct roots give exponential solutions; a nonzero root of multiplicity $s$ gives terms $n^j r^n$ for $0\le j\lt s$. This also follows from partial fractions and coefficients of repeated denominator factors.

Worked example. For the tilings, the roots of $r^2-r-1=0$ are

$$ \phi=\frac{1+\sqrt5}{2}, \qquad \psi=\frac{1-\sqrt5}{2}. $$

The expression

$$ a_n=\frac{\phi^{n+1}-\psi^{n+1}}{\sqrt5} $$

has values $1$ at $n=0,1$ and satisfies the recurrence because both roots satisfy $r^2=r+1$. Uniqueness proves the formula. For exact computation at large $n$, integer recurrence methods avoid floating-point rounding.

Exercise. Solve $c_0=0$ and $c_n=2c_{n-1}+2^n$ for $n\ge1$. Hint: divide by $2^n$ before iterating. Answer: $c_n=n2^n$, with OGF $2x/(1-2x)^2$. The factor $n$ occurs because the forcing uses the same exponential as the homogeneous solution.

10.3 Exponential generating functions

When objects use distinct labels, distributing those labels among components creates binomial factors. An exponential generating function, or EGF, builds these factors into multiplication:

$$ \widehat A(x)=\sum_{n\ge0}a_n\frac{x^n}{n!}, \qquad a_n=n![x^n]\widehat A(x). $$

For a labeled pair of structures, split an $n$-label set into a $k$-label set for the first structure and its complement for the second. There are $\binom nk$ choices of labels, followed by $a_kb_{n-k}$ choices of structures. Hence

$$ c_n=\sum_{k=0}^{n}\binom nk a_kb_{n-k}, \qquad \widehat C(x)=\widehat A(x)\widehat B(x). $$

This follows algebraically because $n!/(k!(n-k)!)=\binom nk$.

Worked example. Give every label one of two group memberships, red or blue. There is one structure on any specified red set and one on any specified blue set, so both EGFs are $e^x=\sum_{n\ge0}x^n/n!$. Their product is $e^{2x}$, yielding $2^n$ assignments of labels to groups.

For $n=3$, the label splits contribute $1+3+3+1=8$, grouped by red-set size. The SVG isolates the three splits with one red label and two blue labels. Each label appears exactly once in each panel; the groups are distinguished by role as well as color.

The choice of OGF or EGF changes coefficient interpretation. Permutations have $a_n=n!$, so their EGF is $1/(1-x)$, whereas their OGF is $\sum_{n\ge0}n!x^n$.

Chapter 9's derangement formula gives another useful EGF. Dividing by $n!$ and summing the finite partial sums yields

$$ \sum_{n\ge0}D_n\frac{x^n}{n!}=\frac{e^{-x}}{1-x}. $$

The coefficient of $x^n$ is $\sum_{j=0}^{n}(-1)^j/j!$, so multiplying by $n!$ recovers the derangement count.

Exercise. Extract the number of derangements on three labels. Hint: multiply the EGF coefficient by $3!$. Answer: $3!(1-1+1/2-1/6)=2$. The EGF coefficient itself is $1/3$.

10.4 Products and compositions of generating functions

For OGFs, multiplication describes an ordered pair whose component sizes add:

$$ [x^n]\bigl(A(x)B(x)\bigr)=\sum_{k=0}^{n}a_kb_{n-k}. $$

There is no binomial label-allocation factor here. For EGFs the same multiplication produces the binomial convolution from Section 10.3. Always specify the underlying object model.

Worked example: order matters. A multiset of monomers and dominoes is specified by their multiplicities. Its size enumerator is

$$ \frac{1}{(1-x)(1-x^2)}. $$

For size $4$, the choices of multiplicities are $(4,0),(2,1),(0,2)$, giving $3$. An ordered tile sequence instead has OGF $1/(1-x-x^2)$ and count $5$. A product of geometric factors for multiplicities does not count tile order.

Composition substitutes a series into another. If $B(0)=0$, then

$$ A(B(x))=\sum_{k\ge0}a_kB(x)^k $$

is formally well-defined: an inner component has positive size, so only finitely many outer terms can contribute to any fixed coefficient. For an ordered sequence of nonempty components, the outer series is $A(t)=1/(1-t)$, giving $1/(1-B(x))$.

Labeled assemblies obey a different rule. If $\widehat B(x)$ counts nonempty labeled components, an unordered set of such components has EGF

$$ \exp\bigl(\widehat B(x)\bigr) =\sum_{k\ge0}\frac{\widehat B(x)^k}{k!}. $$

The product allocates labels among $k$ ordered components; division by $k!$ removes their order. Nonempty, disjoint label sets make these $k!$ orderings distinct. This rule should not be applied blindly to unlabeled components, which can have repeated identical copies.

A set partition is an unordered set of nonempty label blocks. A nonempty block has EGF $e^x-1$, so the Bell numbers have EGF

$$ \sum_{n\ge0}B_n\frac{x^n}{n!}=\exp(e^x-1). $$

Exercise. Recover $B_3$ from this expression. Hint: keep terms through degree three in $\sum_{k\ge0}(e^x-1)^k/k!$. Answer: the coefficient of $x^3$ is $1/6+1/2+1/6=5/6$, giving $B_3=3!\cdot5/6=5$.

10.5 Formal power series and coefficient extraction

A formal power series over $\mathbb Q$ is an expression $F(x)=\sum_{n\ge0}f_nx^n$ in the ring $\mathbb Q[[x]]$. Addition is coefficientwise. Multiplication uses the finite Cauchy sum $[x^n]\bigl(F(x)G(x)\bigr)=\sum_{i=0}^{n}f_i g_{n-i}$. No value of $x$ is substituted, and no analytic limit is implied.

For example, $\sum_{n\ge0}n!x^n$ is a valid formal series, even though at every nonzero numerical $x$ its terms fail to tend to zero. Formal algebra and numerical convergence answer different questions.

A series has a multiplicative inverse exactly when its constant coefficient is nonzero. If $F(x)G(x)=1$, then

$$ g_0=\frac1{f_0}, \qquad g_n=-\frac1{f_0}\sum_{i=1}^{n}f_i g_{n-i}\quad(n\ge1). $$

This recursive construction proves existence and uniqueness. In particular, $1/(1-H(x))=\sum_{j\ge0}H(x)^j$ is valid when $H(0)=0$.

Useful extraction rules, with negative-degree coefficients of power series taken as zero, are

$$ [x^n]\bigl(x^kF(x)\bigr)=[x^{n-k}]F(x), \qquad [x^n]F'(x)=(n+1)f_{n+1}. $$

For an integer $r\ge1$,

$$ [x^n]\,(1-x)^{-r}=\binom{n+r-1}{r-1}. $$

To prove this last identity, multiply $r$ copies of $1+x+x^2+\cdots$. Its coefficient counts ordered $r$-tuples of nonnegative integers summing to $n$, counted by stars and bars.

Worked example: extract the tiling formula. In

$$ A(x)=\sum_{j\ge0}(x+x^2)^j, $$

choose $k$ of the $j$ factors to contribute $x^2$ and the others to contribute $x$. The resulting degree is $j+k$. To obtain $x^n$, set $j=n-k$, with $0\le k\le\lfloor n/2\rfloor$. Therefore

$$ [x^n]A(x)=\sum_{k=0}^{\lfloor n/2\rfloor}\binom{n-k}{k}. $$

This is also a direct bijective count: choose the $k$ domino positions among the $n-k$ tiles. Algebraic extraction and the combinatorial construction agree term by term.

Exercise. Extract $[x^5]\bigl(x^2/(1-x)^3\bigr)$. Hint: shift the requested degree down by two. Answer: $[x^3]\,(1-x)^{-3}=\binom52=10$.

10.6 Rational, algebraic, and D-finite generating functions

Optional graduate extension. Work over $\mathbb Q[[x]]$. A series is rational if it is a ratio of polynomials with a denominator nonzero at the origin; it is algebraic if it satisfies a nonzero polynomial equation $P(x,F(x))=0$. It is D-finite if it satisfies a nontrivial homogeneous linear differential equation

$$ p_0(x)F(x)+p_1(x)F'(x)+\cdots+p_r(x)F^{(r)}(x)=0, $$

with polynomial coefficients $p_i(x)$. In characteristic zero these classes satisfy

$$ \text{rational}\ \subsetneq\ \text{algebraic}\ \subsetneq\ \text{D-finite}. $$

The definition and algebraic-to-D-finite implication are developed in Stanley's Differentiably finite power series. math.mit.edu

Here is the implication's mechanism. For algebraic $F$, implicit differentiation places $F'$ and all higher derivatives in the finite-dimensional field extension $\mathbb Q(x,F)$ over $\mathbb Q(x)$. Sufficiently many derivatives are therefore linearly dependent; clearing denominators gives a polynomial-coefficient differential equation.

Worked example. Ordered full binary trees, counted by internal vertices, are either empty or a root with two ordered subtrees. Thus their series satisfies $C=1+xC^2$, $C(0)=1$. Its solution is

$$ C(x)=\frac{1-\sqrt{1-4x}}{2x}=1+x+2x^2+5x^3+14x^4+\cdots, $$

where the square root has constant term $1$. The numerator is divisible by $x$. This series is not rational: a rational solution would make $\sqrt{1-4x}=1-2xC(x)$ rational, impossible because a square of a rational function has zeros and poles of even order.

The exponential is not algebraic. A polynomial relation would have the form $\sum_{j=0}^{d}p_j(x)e^{jx}=0$ with $p_d\ne0$. Along positive real $x$, dividing by $e^{dx}$ makes all lower terms decay while the nonzero polynomial $p_d(x)$ cannot, a contradiction. These two examples establish strictness.

Exercise. Show that $F(x)=(1-x)^{-2}$ is D-finite directly. Hint: differentiate once. Answer: $(1-x)F'-2F=0$. Extracting coefficients gives $(n+1)f_{n+1}=(n+2)f_n$, consistent with $f_n=n+1$.

10.7 Lagrange inversion theorem

Optional advanced extension. Review formal series and coefficient extraction first. Let $\Phi(u)\in\mathbb Q[[u]]$ have $\Phi(0)\ne0$. There is a unique $T(x)\in x\mathbb Q[[x]]$ satisfying $T=x\Phi(T)$, determined successively by its coefficients. For integers $n,k\ge1$, Lagrange inversion states

$$ [x^n]T(x)^k=\frac{k}{n}[u^{n-k}]\Phi(u)^n. $$

A negative requested degree gives zero. This formal version requires no numerical convergence; see Theorem 2.1.1 in Gessel's survey Lagrange Inversion. arxiv.org

Proof mechanism. For a Laurent series with finitely many negative powers, define $\operatorname{Res}_u F=[u^{-1}]F$. A derivative has residue zero. Set $h(u)=u/\Phi(u)$, so $T(h(u))=u$. The formal substitution rule is $\operatorname{Res}_x F(x)=\operatorname{Res}_u F(h(u))h'(u)$: checking monomials uses derivatives for every exponent except $-1$, while $h'/h$ has residue $1$. Hence integration by parts gives

$$ \begin{aligned} [x^n]T(x)^k &=\operatorname{Res}_u u^k h(u)^{-n-1}h'(u)\\ &=-\frac1n\operatorname{Res}_u u^k\bigl(h(u)^{-n}\bigr)'\\ &=\frac{k}{n}\operatorname{Res}_u u^{k-1}h(u)^{-n}\\ &=\frac{k}{n}[u^{n-k}]\Phi(u)^n. \end{aligned} $$

Worked example. A rooted plane tree has a root and an ordered sequence of child trees. Counting vertices gives $T=x/(1-T)$, so $\Phi(u)=(1-u)^{-1}$. Therefore, for $n\ge1$,

$$ [x^n]T(x)=\frac1n\binom{2n-2}{n-1}. $$

At $n=4$ this is $\binom63/4=5$. Directly, the root has one child in two possible subtree shapes, two children with the larger subtree on either side, or three leaf children: $2+2+1=5$.

Exercise. Let $T=x(1+T)^2$, where the two factors represent optional left and right child structures. Find $[x^n]T$. Hint: use $k=1$ and the binomial theorem. Answer: $\binom{2n}{n-1}/n=\binom{2n}{n}/(n+1)$ for $n\ge1$. Adding the empty structure gives the Catalan series $1+T$.

10.8 Multivariate generating functions

Optional advanced extension. Several variables can record different measurements of one object. For the tilings, let $a_{n,k}$ count length-$n$ tilings with $k$ dominoes and define

$$ A(x,u)=\sum_{n,k\ge0}a_{n,k}x^nu^k. $$

A monomer has weight $x$ and a domino has weight $ux^2$. The unique ordered-sequence decomposition gives

$$ A(x,u)=\frac{1}{1-x-ux^2}, \qquad a_{n,k}=[x^nu^k]A(x,u)=\binom{n-k}{k} $$

for $0\le k\le\lfloor n/2\rfloor$, and zero otherwise. The coefficient proof chooses which $k$ of the $n-k$ tiles are dominoes.

Worked example. For length four,

$$ [x^4]A(x,u)=1+3u+u^2. $$

Setting $u=1$ forgets the domino statistic and gives $5$; setting $u=0$ retains only the all-monomer tiling. Differentiating with respect to $u$ and then setting $u=1$ sums domino counts. If all five tilings are equally likely, their expected number of dominoes is

$$ \frac{[x^4]\left.\dfrac{\partial A}{\partial u}\right|_{u=1}}{[x^4]A(x,1)} =\frac{3+2}{5}=1. $$

The derivative is a weighted count; it becomes an expectation only after division by the total count and specification of the uniform distribution.

Exercise. Find the domino-count polynomial and mean for length five. Hint: the possible domino counts are zero, one, and two. Answer: $1+4u+3u^2$, with total $8$ and mean $(4+6)/8=5/4$.

10.9 Transfer-matrix method

A finite collection of states can record the information needed to extend an object. Define a matrix $M$ whose entry $M_{ij}$ counts transitions from state $i$ to state $j$. Matrix multiplication sums over intermediate states, so $(M^n)_{ij}$ counts length-$n$ transition paths from $i$ to $j$. This follows by induction on path length.

For initial row vector $v$ and accepting column vector $w$, the count is $b_n=vM^nw$. The OGF is

$$ B(x)=v(I-xM)^{-1}w, $$

because $(I-xM)^{-1}=\sum_{n\ge0}x^nM^n$ formally. A finite matrix gives a rational expression. When counting words, the state model must give each word exactly one accepting path; otherwise this formula counts paths with multiplicity.

Worked example. Count binary words with no adjacent ones. Use state A for “start or previous symbol zero” and state B for “previous symbol one.” The transitions are:

With rows and columns ordered A, B,

$$ M=\begin{pmatrix}1&1\\1&0\end{pmatrix}, \qquad v=\begin{pmatrix}1&0\end{pmatrix}, \qquad w=\begin{pmatrix}1\\1\end{pmatrix}. $$

Both states accept, and the initial state accepts the empty word. Computing the inverse gives

$$ (I-xM)^{-1}=\frac{1}{1-x-x^2} \begin{pmatrix}1&x\\x&1-x\end{pmatrix}, \qquad B(x)=\frac{1+x}{1-x-x^2}. $$

The counts are $1,2,3,5,8,\ldots$. At length three, the words are $000,001,010,100,101$. Since $M^2=M+I$, they satisfy $b_n=b_{n-1}+b_{n-2}$ for $n\ge2$. The denominator matches the tiling denominator, but the numerator differs because the initial counts differ.

Exercise. Count valid length-three words ending in one. Hint: accept only state B by replacing $w$ with $(0,1)^{\mathsf T}$. Answer: $vM^3w=2$, represented by $001$ and $101$.

10.10 Continued fractions and combinatorial enumeration

Optional graduate extension. A Motzkin excursion starts at height zero, ends there, never goes below zero, and uses steps U, H, D of height changes $+1,0,-1$. Let $M(x)$ count excursions by total step length, including the empty path.

A nonempty excursion either starts with H, followed by another excursion, or has a first-return decomposition $\mathrm{U}\,P\,\mathrm{D}\,Q$. Here $P$, shifted down one level, and $Q$ are excursions. The first return makes this decomposition unique. Thus

$$ M(x)=1+xM(x)+x^2M(x)^2 =\frac{1}{1-x-x^2M(x)}. $$

Substituting the last expression into itself produces the continued fraction

$$ M(x)=\cfrac{1}{1-x-\cfrac{x^2}{1-x-\cfrac{x^2}{1-x-\ddots}}}. $$

Its formal meaning is coefficient stabilization under finite height bounds. An excursion of length $n$ has height at most $\lfloor n/2\rfloor$, so sufficiently deep truncations give its exact coefficient.

More generally, give a horizontal step at height $h$ weight $\alpha_h$, an upward step weight $1$, and a downward step from $h+1$ weight $\lambda_{h+1}$. If $F_h$ counts excursions above level $h$, first return gives

$$ F_h(x)=\frac{1}{1-\alpha_hx-\lambda_{h+1}x^2F_{h+1}(x)}. $$

Iterating yields a Jacobi continued fraction. This path interpretation is developed in Flajolet's Combinatorial aspects of continued fractions. algo.inria.fr

Worked example. Unit weights give coefficients $1,1,2,4,9$ through length four. At length three the paths are HHH, HUD, UHD, and UDH. If height is restricted to at most one, then $F_1=1/(1-x)$ and

$$ F_0(x)=\frac{1-x}{1-2x}=1+x+2x^2+4x^3+8x^4+\cdots. $$

The missing ninth length-four path is UUDD, the only one reaching height two. Each finite height bound can also be counted by a finite transfer matrix; the continued fraction successively eliminates the height states.

Exercise. Set all horizontal weights to zero and all downward weights to one. What is counted? Hint: only U and D remain. Answer: Dyck excursions. Their series is $C(x^2)$, where $C(z)=1+zC(z)^2$: only even lengths occur, and length $2n$ has Catalan count $C_n$.

Derive and verify a generating function from a combinatorial decomposition

Generating functions become useful when their algebra reflects a uniquely specified construction. The tiling OGF comes from a sequence of length-one and length-two tiles. The Motzkin OGF comes from a first step or first return; retaining the height of that return produces a continued fraction. Both methods encode recursive structure, while finite transfer matrices record bounded state information.

One cross-disciplinary application is counting words accepted by a finite-state protocol or validator. A state records the relevant recent history, such as whether the preceding bit was one. The transfer matrix counts legal messages of each length, and its rational OGF packages the whole sequence. This counts feasible messages under the specified rules; attaching transition probabilities would be a separate probabilistic model.