Generating functions: turning sequences into algebra
A generating function is a way to encode a sequence \(\{a_n\}_{n\ge 0}\) into a single expression in a variable \(x\).
Once the sequence is packaged into a function, algebraic operations (like multiplying, differentiating, or expanding) translate into meaningful operations on the coefficients.
This is why generating functions show up so often in combinatorics, probability, and discrete mathematics.
Ordinary generating functions (OGFs)
The ordinary generating function (OGF) of \(\{a_n\}\) is
\[
A(x)=\sum_{n\ge 0} a_n x^n.
\]
Here, the coefficient of \(x^n\) is exactly \(a_n\).
Coefficient extraction is written as \([x^n]A(x)=a_n\).
OGFs are especially natural for counting objects where “size” adds, because multiplying two OGFs corresponds to a convolution of coefficients.
For example, if \(A(x)=\sum a_n x^n\) and \(B(x)=\sum b_n x^n\), then
\[
A(x)B(x)=\sum_{n\ge 0}\left(\sum_{k=0}^{n} a_k b_{n-k}\right)x^n,
\]
which matches the idea of splitting a size-\(n\) structure into a size-\(k\) part and a size-\(n-k\) part.
Exponential generating functions (EGFs)
The exponential generating function (EGF) is
\[
A(x)=\sum_{n\ge 0} a_n \frac{x^n}{n!}.
\]
EGFs are often the right tool when the objects being counted have labels (distinguishable elements), because the factor \(1/n!\) interacts nicely with permutations.
A classic example is the exponential function:
\[
e^{cx}=\sum_{n\ge 0} c^n \frac{x^n}{n!},
\]
so the sequence is \(a_n=c^n\).
Binomial example: \((1+x)^n\)
A very common coefficient task is expanding a binomial:
\[
(1+x)^n=\sum_{k=0}^{n}\binom{n}{k}x^k.
\]
The coefficients \(\binom{n}{k}\) form a row of Pascal’s triangle.
For \(n=5\), the coefficients are \(1,5,10,10,5,1\).
This tool computes these coefficients exactly (as integers) and lets you extract a single coefficient \(a_k\) as well.
Coefficient extraction and partial sums
In many situations you only need the first few coefficients, not an infinite series.
The calculator can list the first \(N\) terms and also visualize a partial sum:
\[
A_N(x)=\sum_{n<N} a_n x^n \quad \text{(OGF)}, \qquad
A_N(x)=\sum_{n<N} a_n \frac{x^n}{n!} \quad \text{(EGF)}.
\]
As \(N\) grows, the partial sum typically becomes a better approximation (within the radius of convergence for infinite series).
University tease: partitions and “coin change”
One of the most famous generating-function applications is counting integer partitions.
The product
\[
\prod_{k\ge 1}\frac{1}{1-x^k}
\]
encodes the number of ways to write an integer as a sum of positive integers (order ignored).
Related “coin change” problems use products like \(\prod_{c\in C}\frac{1}{1-x^c}\), where each coin value \(c\) contributes a factor.
Even if you don’t expand these products fully by hand, the coefficient viewpoint explains why the method works.
