Ordinary Generating Functions

Ordinary generating functions are the working language of enumerative combinatorics: counting lattice paths, set partitions, compositions of integers, and the coefficients of the Catalan Numbers (via the quadratic equation $C(x) = 1 + xC(x)^2$) all reduce to algebraic manipulation of an OGF. In Integer Partitions, infinite products such as $\prod_k (1-x^k)^{-1}$ generate the partition function $p(n)$, and Euler's pentagonal number theorem is proved by manipulating the reciprocal product. In computer science, OGFs analyze the running time of divide-and-conquer algorithms whose recurrences (e.g. $T(n) = 2T(n/2) + n$ in disguise, or more directly integer sequence recurrences) are solved exactly as in Example 2 above, and they underlie automatic complexity analysis in the "symbolic method" of analytic combinatorics. In probability and statistics, OGFs specialize to probability generating functions $\mathbb E[x^X] = \sum_k P(X=k)x^k$, whose derivatives at $x=1$ recover moments and whose products encode independence of sums of random variables. In cryptography and coding theory, generating functions count weight distributions of linear codes and track the structure of feedback shift registers. In physics, OGFs (and their exponential cousins) organize partition functions in statistical mechanics, where the formal variable becomes a fugacity or Boltzmann weight — a direct descendant of Euler's original partition-counting insight.

:::quiz[If $A(x)$ is the OGF of $(a_n)$ with $a_0 \ne 0$, when does $A(x)$ have a multiplicative inverse in $\mathbb R[[x]]$?]

• Never, formal power series are never invertible
• Only if $A(x)$ is a polynomial
• Always, precisely because $a_0 \ne 0$ ✓
• Only if all $a_n > 0$

Ask the tutor: How does the functional equation $C(x) = 1 + xC(x)^2$ for the Catalan numbers get derived and solved using the Product Rule?

Think of $A(x) = \sum a_n x^n$ as a clothesline: the exponent $n$ is a peg, and $a_n$ is the item hanging from it. The variable $x$ carries no numeric meaning by itself; its powers are just labels that keep the sequence's terms from getting mixed up. This is why we can add and multiply these objects with total disregard for convergence — a formal power series is really just a sequence with a multiplication rule attached, and the notation $\sum a_n x^n$ is a convenient way to remember which coefficient goes where. The convolution formula is the heart of every application. If $A(x)$ counts the number of ways, $a_n$, to build an object of "size" $n$ from parts of type-1, and $B(x)$ counts ways $b_n$ to build a size-$n$ object from parts of type-2, then the coefficient of $x^n$ in $A(x)B(x)$ is $\sum_{k=0}^n a_k b_{n-k}$: the number of ways to split $n$ into a type-1 piece of size $k$ and a type-2 piece of size $n-k$, and build each piece independently. This is exactly the count of ordered pairs (type-1 object, type-2 object) whose sizes sum to $n$ — the combinatorial content behind the algebra. A second key move is division by $1-x$. Since $\frac{1}{1-x} = \sum_{n\ge0} x^n$ formally (check: $(1-x)\sum_{n\ge0}x^n = \sum_{n\ge 0}x^n - \sum_{n\ge0}x^{n+1} = 1$), multiplying any $A(x)$ by $\frac{1}{1-x}$ replaces each coefficient $a_n$ by the partial sum $a_0+a_1+\cdots+a_n$. This single algebraic fact recovers, instantly, formulas that would otherwise need induction.

Example 1: Making change with four coin denominations (an asymmetric convolution). Suppose we have unlimited supplies of pennies (1¢), nickels (5¢), dimes (10¢), and quarters (25¢), and we ask for $c_n$, the number of ways to make exactly $n$ cents using these coins, where order does not matter (a "way" is a choice of how many of each coin to use). We build the generating function using the Product Rule for four independent choices — how many pennies, how many nickels, how many dimes, how many quarters — whose contributed values must sum to $n$. The class of "some number of pennies contributing value $v$" has one object for each multiple of $1$, so its OGF (in the variable $x$ tracking value, not count of coins) is $\frac{1}{1-x}$. Similarly, a choice of nickels contributing value a multiple of $5$ has OGF $\frac{1}{1-x^5}$ (one way to contribute value $5j$ for each $j \ge 0$, none otherwise); dimes give $\frac{1}{1-x^{10}}$; quarters give $\frac{1}{1-x^{25}}$. By the Product Rule (applied three times, since choices of different coin types are independent and their values add):

To find $c_{100}$ — the number of ways to make a dollar — one option is to extract the coefficient via partial fractions or a computer algebra system; here we illustrate the method by computing a smaller, fully explicit case, $c_{30}$, by hand using the structure of the product. Write $C(x) = \frac{1}{1-x}\cdot \frac{1}{1-x^5}\cdot\frac{1}{1-x^{10}}\cdot\frac{1}{1-x^{25}}$. We want $[x^{30}]C(x)$. First combine the two "coarse" factors:

The exponents $10i+25j \le 30$ with $i,j\ge0$ are: $(i,j)=(0,0)\to 0$, $(1,0)\to10$, $(2,0)\to20$, $(3,0)\to30$, $(0,1)\to25$. So up to degree $30$,

Next we need $\frac{1}{(1-x)(1-x^5)}$ up to degree $30$; its coefficient of $x^m$ is the number of ways to write $m = a + 5b$ with $a,b\ge0$, i.e. $b$ ranges over $0,1,\dots,\lfloor m/5\rfloor$ and $a$ is determined, so $[x^m]\frac{1}{(1-x)(1-x^5)} = \lfloor m/5\rfloor + 1$. Now $c_{30} = [x^{30}]C(x)$ is obtained by convolving the coefficient sequence $u_m = \lfloor m/5\rfloor+1$ (from pennies+nickels) against the finite sequence $v_m \in \{1 \text{ at } m=0,10,20,25,30\}$ (from dimes+quarters), restricted to $m \le 30$:

matching $m + \{0,10,20,25,30\} = 30$, i.e. $m = 30,20,10,5,0$. Compute each: $u_{30}=\lfloor30/5\rfloor+1=7$, $u_{20}=4+1=5$, $u_{10}=2+1=3$, $u_{5}=1+1=2$, $u_0=0+1=1$. Sum: $7+5+3+2+1 = 18$. So there are $18$ ways to make $30$ cents from pennies, nickels, dimes, and quarters — a fact one can sanity-check directly (quarters used $\in\{0,1\}$; if $1$ quarter, remaining $5$ cents needs $u_5=2$ ways; if $0$ quarters, remaining $30$ cents from pennies/nickels/dimes needs enumerating $10j+u$, matching the computation above), confirming the generating-function method.

Example 2: A linear recurrence with non-constant-free initial data. Let $(a_n)_{n\ge0}$ satisfy $a_0 = 3$, $a_1 = 1$, and for $n\ge 2$,

We find a closed form for $a_n$ using its OGF. Let $A(x) = \sum_{n\ge0}a_n x^n$. Multiply the recurrence by $x^n$ and sum over $n\ge2$:

The left side is $A(x) - a_0 - a_1x = A(x) - 3 - x$. On the right, $\sum_{n\ge2}a_{n-1}x^n = x\sum_{n\ge2}a_{n-1}x^{n-1} = x\sum_{m\ge1}a_m x^m = x(A(x)-a_0) = x(A(x)-3)$, and $\sum_{n\ge2}a_{n-2}x^n = x^2\sum_{m\ge0}a_m x^m = x^2 A(x)$. Substituting:

Expand and collect $A(x)$ terms:

So

Apply partial fractions: seek $A(x) = \frac{P}{1-2x} + \frac{Q}{1-3x}$. Clearing denominators, $3 - 14x = P(1-3x) + Q(1-2x)$. Setting $x = \tfrac12$: $3 - 7 = P(1 - \tfrac32) = -\tfrac12 P$, so $-4 = -\tfrac12 P \Rightarrow P = 8$. Setting $x = \tfrac13$: $3 - \tfrac{14}{3} = Q(1-\tfrac23) = \tfrac13 Q$, so $\tfrac{9-14}{3} = -\tfrac53 = \tfrac13 Q \Rightarrow Q = -5$. Check the constant term: $P + Q = 8 - 5 = 3$, matching the constant term of $3-14x$ at $x=0$ — consistent. So $A(x) = \dfrac{8}{1-2x} - \dfrac{5}{1-3x} = 8\sum_{n\ge0}2^n x^n - 5\sum_{n\ge0}3^n x^n$, using $\frac{1}{1-cx}=\sum_n c^n x^n$ (the geometric series with $x$ replaced by $cx$, valid formally by the same telescoping argument as the Corollary above). Reading off the coefficient of $x^n$:

Check: $a_0 = 8-5=3$ ✓. $a_1 = 16 - 15 = 1$ ✓. $a_2 = 5a_1-6a_0 = 5-18=-13$; formula gives $8\cdot4 - 5\cdot9 = 32-45=-13$ ✓. $a_3 = 5(-13)-6(1) = -65-6=-71$; formula gives $8\cdot8-5\cdot27=64-135=-71$ ✓. The closed form matches on all four checked terms.