= Generating function
{title2=$A(x)=\sum_{n\geq0}a_nx^n$}
{wiki}
A <generating function> packages a <sequence> into a <series> so that operations on objects become operations on their encodings. An <ordinary generating function> uses the <power series> $A(z)=\sum_{n\geq0}a_nz^n$; in counting problems, the <coefficient> $a_n$ records the number of objects of size $n$. The variable $z$ initially marks size: it need not be assigned a numerical value. <Coefficient extraction> writes this recovery as $[z^n]A(z)=a_n$. One compact expression can therefore answer infinitely many counting questions, while explaining how their answers fit together.
Start with two contributions: choose $i$ from $\{0,1,2\}$ and $j$ from $\{0,1\}$, with exactly one option at each allowed value. Their individual <ordinary generating functions> are the <polynomials> $P(x)=1+x+x^2$ and $Q(x)=1+x$. To count <ordered pairs> by total $i+j$, multiply:
$$
P(x)Q(x)=(1+x+x^2)(1+x)=1+2x+2x^2+x^3.
$$
The <coefficients> $1,2,2,1$ count the ways to obtain totals zero through three. For total two, the possibilities are $(1,1)$ and $(2,0)$; the two corresponding <monomials> both contribute $x^2$. There are six <ordered pairs> altogether, agreeing with $P(1)Q(1)=3\cdot2=6$.
\Image[/generating-function-coefficient-products.png]
{title=Polynomial multiplication groups six ordered choices by their total contribution}
If the first contribution has two distinguishable choices when $i=1$, replace $P(x)$ by $1+2x+x^2$. Its product with $Q(x)$ becomes $1+3x+3x^2+x^3$. The <coefficients> now carry multiplicities as well as possible totals; the exponent still records cost. This lets the same construction handle several actions with identical costs without losing their separate identities.
In general, the <Cauchy product> gives
$$
[z^n]\bigl(A(z)B(z)\bigr)=\sum_{k=0}^n a_kb_{n-k}.
$$
For each split of the total size, the <rule of product> counts the choices of the two components; summing over those splits counts all possibilities. This requires each combined object to have a unique decomposition into the two components. The same idea works for costs, lengths, or other additive measures, not just the number of pieces. See https://ocw.mit.edu/courses/18-310-principles-of-discrete-applied-mathematics-fall-2013/1d3495b2adb2dc35cb8dd1933398a647_MIT18_310F13_Ch7.pdf[MIT 18.310, generating functions, sections 1–2].
Now cover a board of length $n$ with tiles of lengths one and two, without gaps or overlaps. Let $t_n$ count these tilings. There is exactly one empty tiling, so $t_0=1$, and $t_1=1$. Removing the first tile leaves a board shorter by one or two, giving the <recurrence relation>
$$
t_n=t_{n-1}+t_{n-2}\quad(n\geq2),\qquad (t_0,t_1,t_2,t_3,t_4,t_5)=(1,1,2,3,5,8).
$$
These are the <Fibonacci numbers> shifted by one index: $t_n=F_{n+1}$ under the convention $F_0=0$, $F_1=1$. Keeping the empty tiling is essential to both the counting rule and the resulting <ordinary generating function>.
\Image[/fibonacci-tiling-generating-function.png]
{title=Length-one and length-two tiles give five coverings of a length-four board and the Fibonacci recurrence}
For $F(z)=\sum_{n\geq0}t_nz^n$, the empty board or a first tile followed by a remaining tiling gives
$$
F(z)=1+(z+z^2)F(z),\qquad F(z)=\frac{1}{1-z-z^2}=1+z+2z^2+3z^3+5z^4+8z^5+\cdots.
$$
Equivalently, $F(z)=\sum_{m\geq0}(z+z^2)^m$: each factor chooses one tile, and $m$ counts pieces while the exponent of $z$ records total length. The same <ordinary generating function> counts ordered histories of two repeatable actions costing one and two units. Histories $(1,2)$ and $(2,1)$ differ despite having the same total cost. MIT's notes use dots and dashes with these costs, including the empty message. https://ocw.mit.edu/courses/18-200-principles-of-discrete-applied-mathematics-spring-2024/mit18_200_s24_lec07-08.pdf[MIT 18.200, generating functions, section 4]{ref}
These identities hold in <formal power series> algebra: each requested <coefficient> uses only finitely many contributions. The repeated-choice expansion is legitimate because $z+z^2$ has zero <constant term>; a zero-cost repeatable action would allow infinitely many histories of the same size. Numerical evaluation separately requires a <convergent series>. Here the <radius of convergence> is $(\sqrt5-1)/2$, the reciprocal of the <golden ratio>. At $z=1$, the <rational function> equals $-1$, but the counting <series> diverges: that value cannot represent its sum.
Other <generating functions> change the encoding: an <exponential generating function> divides by <factorials>, while a <Dirichlet series> uses $n^{-s}$. A counting <generating function> also differs from a <probability generating function>, whose <coefficients> must be nonnegative and sum to one.
Back to article page
