Generating Functions as a Puzzle Tool

In how many ways can you make $1 (100 cents) using pennies (1¢), nickels (5¢), and dimes (10¢)? Order doesn't matter — 3 dimes and 1 nickel and 65 pennies is one way, however you list the coins.

You could set up nested loops over how many dimes, then how many nickels, then check the pennies fill the rest — and that works, but there's a slicker packaging that turns the whole counting problem into multiplying three simple expressions together.

The packaging trick

For a single denomination — say pennies — the number of ways to contribute exactly $k$ cents using only pennies is 1 for every $k$ (you either use $k$ pennies or you don't; there's exactly one way). Encode that entire infinite list of answers (1, 1, 1, 1, ...) as the coefficients of a formal power series:

$P(x) = 1 + x + x^2 + x^3 + \cdots = \frac{1}{1-x}$

Read $x^k$ as "a placeholder marking $k$ cents contributed," and the coefficient in front of it as "the number of ways to contribute that amount using this denomination." For nickels, you can only contribute in multiples of 5, so only every fifth power of $x$ has a nonzero coefficient:

$N(x) = 1 + x^5 + x^{10} + x^{15} + \cdots = \frac{1}{1-x^5}$

And for dimes: $D(x) = 1 + x^{10} + x^{20} + \cdots = \dfrac{1}{1-x^{10}}$.

Here's the payoff. If you multiply $P(x) \cdot N(x) \cdot D(x)$, the coefficient of $x^{100}$ in the product is exactly the number of ways to pick a penny-count, a nickel-count, and a dime-count that together sum to 100 — because multiplying power series adds exponents in every possible combination, which is precisely what "choose some pennies AND some nickels AND some dimes that sum to 100" means. The hard combinatorics question has become a purely mechanical algebra question: find one coefficient in a product of three series.

Why multiplying series does the counting for you

This deserves a small concrete check before trusting it on the full $1 problem. Suppose you only had pennies and nickels, and wanted ways to make 6 cents. $P(x) = 1+x+x^2+x^3+x^4+x^5+x^6+\cdots$ and $N(x) = 1+x^5+x^{10}+\cdots$. Multiply and collect the $x^6$ term: it can come from ($x^6$ term of $P$) × ($x^0$ term of $N$) — one way, using 6 pennies and 0 nickels — or ($x^1$ term of $P$) × ($x^5$ term of $N$) — one way, 1 penny and 1 nickel. No other pairing of exponents sums to 6. Total: 2 ways, which matches direct enumeration (6 pennies; or 1 nickel + 1 penny). The algebra reproduced exactly what hand-counting gives, confirming the machinery is doing what it claims.

Solving the $1 puzzle

Rather than expanding the full product symbolically, use the same direct-counting logic the generating function represents, now that you trust it: for each number of dimes $d = 0, 1, \ldots, 10$, the dimes contribute $10d$ cents, leaving $100 - 10d$ cents for nickels and pennies. For a fixed remainder $r = 100-10d$, the number of ways to split $r$ between nickels and pennies is the number of nickel-counts from 0 up to $\lfloor r/5 \rfloor$ (pennies fill in the rest automatically) — that's $\lfloor r/5 \rfloor + 1$ ways.

Since $r = 100-10d$ is always a multiple of 10, $\lfloor r/5 \rfloor = r/5 = 20-2d$, giving $21-2d$ ways for each $d$. Summing over $d=0$ to $10$:

$\sum_{d=0}^{10}(21-2d) = 21(11) - 2(0+1+\cdots+10) = 231 - 2(55) = 231-110 = \textbf{121}$

121 ways to make a dollar out of pennies, nickels, and dimes. The generating function justified why this "fix the dimes, then count nickel-penny splits" approach is exhaustive and non-overlapping — every term in the triple product corresponds to exactly one (pennies, nickels, dimes) triple, so summing over all valid dime-counts covers every case exactly once.

Where this generalizes

Generating functions are the standard tool behind partition-counting puzzles ("how many ways to write $n$ as a sum of..."), and the same "encode a sequence as coefficients, manipulate the whole object algebraically" trick solves linear recurrences in closed form (multiply the recurrence by $x^n$, sum over $n$, and the generating function satisfies a simple algebraic equation you can solve for a closed form). In a quant context, the identical idea underlies option pricing via characteristic functions and moment-generating functions in probability — packing an entire distribution into one transformed object so that an operation that's hard on the distribution (like a convolution, i.e. summing independent variables) becomes easy on the transform (like a product).