Two pounds in 73,682 ways

How many ways are there to pay two pounds exactly in British coins? There are eight coins — 1p, 2p, 5p, 10p, 20p, 50p, £1 and £2 — and a payment is a choice of how many of each, so two pounds can be paid as a single £2 coin, as two hundred pennies, and in many ways between. The answer is 73,682. A dollar in pennies, nickels, dimes, quarters and half-dollars can be paid in 292 ways, a number that appears in George Pólya’s writing on generating functions as the classic example of counting by multiplying series.

A way of making change is a partition whose parts are restricted to a fixed finite set. The size of a number with no formula showed that the number of unrestricted partitions has no closed form, only an asymptotic one and Rademacher’s exact series. With finitely many allowed parts the situation is opposite: the count does have a formula, an exact one, and its shape — a polynomial plus repeating waves — is the subject of this essay.

Counting by adding one coin at a time #

The count is computed by a method older than computers. List the amounts from 0 to 200. With only pennies, every amount can be paid in exactly one way. Now allow 2p coins as well: the number of ways to pay $n$ is the number that use no 2p coin, which is the old count, plus the number that use at least one, which is the number of ways to pay $n - 2$ with 2p coins still allowed. Working upwards from small amounts, each entry is the entry above plus the entry two to the left. Then allow 5p coins, and so on for each coin in turn. Two hundred amounts, eight coins, sixteen hundred additions.

This is the generating function in disguise. The number of ways to pay $n$ with parts from a set $A$ is the coefficient of $q^n$ in

$$\prod_{a \in A} \frac{1}{1 - q^a} = \prod_{a\in A}(1 + q^a + q^{2a} + \cdots),$$

because choosing a term $q^{ma}$ from each factor is choosing to use $m$ coins of value $a$, and the exponents add up to the amount. Multiplying by one more factor $1/(1 - q^c)$ is exactly the update rule: the new coefficient at $n$ is the old one plus the new one at $n - c$. A polynomial that counts introduced the idea; here the product is infinite in each factor but has only finitely many factors.

The table shows the process for United States coins. Pennies alone allow one way for every amount. Adding nickels gives one extra way for every five cents. Dimes, quarters and half-dollars each multiply the possibilities further, and the last row reaches 292 at a dollar.

A polynomial with waves #

For a few parts the counts can be written down exactly, and they have a definite shape. With parts 1 and 2 the count is $\lfloor n/2 \rfloor + 1$: choose how many 2s, from none up to half of $n$. With parts 1, 2 and 3 it is the nearest whole number to $(n + 3)^2/12$, a pretty fact that conceals a more precise one.

Subtract the polynomial $(6n^2 + 36n + 47)/72$ from the count, and what is left repeats every six steps, taking the values of $(-1)^n/8 + \tfrac29\cos(2\pi n/3)$. So the exact count is

$$p_{\{1,2,3\}}(n) = \frac{6n^2 + 36n + 47}{72} + \frac{(-1)^n}{8} + \frac{2}{9}\cos\frac{2\pi n}{3},$$

which the computation checks for every $n$ up to 300. The polynomial has degree 2, one less than the number of parts; the wave of period 2 comes from the part 2, and the wave of period 3 from the part 3. A function of this shape — a polynomial whose coefficients repeat periodically in $n$ — is a quasi-polynomial, and every count of partitions into finitely many parts is one.

The reason is in the generating function. It is a rational function whose poles lie at roots of unity: at $q = 1$, where every factor $1/(1 - q^a)$ has a pole, so the pole has order equal to the number of parts; and at every other root of unity whose order divides some part, with order equal to the number of parts it divides. Expanding the rational function in partial fractions, the pole at 1 gives a polynomial in $n$ of degree one less than its order, and each other root $\zeta$ gives a polynomial times $\zeta^n$, a periodic wave. James Joseph Sylvester described this decomposition in 1857 and called the pieces waves; the polynomial part is the first wave.

Schur’s leading term #

The dominant part of the polynomial wave is simple. Issai Schur proved that when the parts have no common factor, the number of partitions of $n$ into $k$ parts from $A$ grows like

$$\frac{n^{k-1}}{(k-1)!\,\prod_{a \in A} a}.$$

The reason is geometric. A partition into the parts $a_1, \ldots, a_k$ is a point with whole-number coordinates $m_i \ge 0$ on the hyperplane $\sum m_i a_i = n$, and the number of such points is roughly the volume of the slice of that hyperplane in the positive region, a simplex whose volume is the leading term.

The approach is slow when the parts are large. For parts 1, 2 and 3 the ratio is within a percent by an amount of a hundred. For British coins, with eight parts up to 200, the leading term is $n^7/(7! \cdot 2 \times 10^9)$, the product of the coins being two thousand million, and at two pounds it is about 1,270 against the true 73,682; at four hundred pounds it is still 3% short. The next term of the polynomial has relative size about $(k - 1)$ times half the sum of the parts, divided by $n$, which for British coins is about $1{,}358/n$. So for everyday amounts the whole quasi-polynomial matters, waves included, and the leading term is a statement about very large payments.

Points in a simplex #

Schur’s geometric reason connects the count to a larger theory. A way to pay $n$ with coins $a_1, \ldots, a_k$ is a point $(m_1, \ldots, m_k)$ with whole-number coordinates, all non-negative, on the hyperplane $\sum m_i a_i = n$. Those conditions cut out a simplex, and as $n$ grows the simplex is the same shape scaled up by the factor $n$. Counting lattice points in dilates of a fixed polytope is the subject of Eugène Ehrhart’s theory from the 1960s: for a polytope with whole-number corners the count is a polynomial in the scale, and for one with rational corners — as here, where the corners sit at $n/a_i$ on each axis — it is a quasi-polynomial whose period divides the denominators. That is Sylvester’s waves again, from the other side.

The leading coefficient is the volume, which is Schur’s term, and the next coefficient is half the boundary’s volume, the analogue of the boundary term in Pick’s theorem, which counts lattice points in a polygon by its area plus half its boundary points. Pick’s theorem has no simple version in three dimensions, and Ehrhart’s theory is what replaces it: not a formula in volume and boundary alone, but a quasi-polynomial whose coefficients must be computed for each shape.

Two coins, exactly #

With just two coins of coprime values $a$ and $b$ the whole quasi-polynomial has a closed form, found by Tiberiu Popoviciu in 1953:

$$p_{\{a,b\}}(n) = \frac{n}{ab} - \left\{\frac{b' n}{a}\right\} - \left\{\frac{a' n}{b}\right\} + 1,$$

where $\{x\}$ is the fractional part, and $a'$ and $b'$ are the inverses of $a$ modulo $b$ and of $b$ modulo $a$. The first term is Schur’s, the two fractional parts are the waves of periods $a$ and $b$, and the 1 is the constant term. For 3p and 5p coins, which have no common factor, the count at $n$ is about $n/15$, with a correction that cycles through fifteen values; and the amounts where the count is zero are the ones that cannot be paid at all, the largest being $3 \times 5 - 3 - 5 = 7$. The formula is a small instance of what Sylvester’s decomposition promises in general, and one of the few cases where every wave can be written in elementary terms.

Ten pence, drawn #

A small case shows the objects themselves. Ten pence from coins of 1, 2 and 5 can be made in ten ways, from two 5p coins to ten pennies, each drawn as a Ferrers diagram whose columns are the coins. Schur’s leading term for these three coins is $n^2/20$, which at ten gives 5; the lower terms of the polynomial and the waves of periods 2 and 5 supply the other five.

Restricted against unrestricted #

The contrast with unrestricted partitions is extreme. With every whole number allowed as a part, the number of partitions of 200 is 3,972,999,029,388, and it grows like $e^{\pi\sqrt{2n/3}}$, faster than any polynomial. With eight coins it is 73,682 at 200 and grows like $n^7$. The waves have no counterpart in the unrestricted case either: there, every root of unity is a pole of the generating function, the poles accumulate on the unit circle, and Rademacher’s exact formula needs an infinite series of them. Restricting the parts to a finite set leaves finitely many poles and turns an analytic problem into an algebraic one.

The shape of a random partition changes too. A random unrestricted partition of $n$ has a curved limiting shape, with about $\sqrt n \log n$ parts. A random way of paying a large amount in eight coins behaves quite differently: the shares of the amount carried by the eight denominations are, in the limit, a uniformly random point of a simplex, so each denomination carries an eighth of the value on average. That means a typical payment of a large sum uses thousands of pennies alongside its £2 coins — the counting treats every combination as equally likely, and almost all combinations are extravagant in small change. Nothing like a curved limit shape appears; the geometry is a flat simplex.

The euro area uses the same eight denominations as Britain, 1, 2, 5, 10, 20 and 50 cents and 1 and 2 euros, so two euros can also be paid in exactly 73,682 ways. The counts depend only on the denominations, not on the currency.

The fewest coins is a different question #

A cashier faces a different question: not how many ways, but the fewest coins. The cashier’s rule is greedy — take the largest coin that fits, then repeat. For British and United States coins it is always optimal, which the figure checks against an exact search at every amount to 500. But it is not optimal for every coinage.

With coins of 1, 3 and 4 the rule pays 6 as $4 + 1 + 1$, three coins, when $3 + 3$ is two. Add a twenty-cent coin to United States coins and the rule pays 40 cents as $25 + 10 + 5$ instead of $20 + 20$. Coins of 1, 7 and 10 fail first at 14, with five coins against two. Dexter Kozen and Shmuel Zaks proved in 1994 that if the greedy rule ever fails, it fails at some amount below the sum of the two largest coins, so any coinage can be tested quickly. Coinages where it never fails are called canonical, and nearly every national coinage is, which is presumably why the rule is taught to cashiers.

The two questions are related by the same generating function. The number of ways is the coefficient of $q^n$; the fewest coins is the smallest total degree of a term $q^{m_1 a_1} \cdots q^{m_k a_k}$ contributing to it, a question in tropical rather than ordinary arithmetic, with minimum in place of sum. The largest amount two coins cannot pay is a third question about the same product: the largest $n$ whose coefficient is zero.

Waves inside a smooth count #

The surprise is the waves. The number of ways to make change looks like a smooth function that grows like a polynomial, and the hero’s curve has no visible oscillation. But the exact count is a polynomial plus terms that repeat with every period that divides a coin, and those terms are not small corrections to be ignored. For parts 1, 2 and 3 they swing by about a third, which decides whether the count is the nearest whole number to $(n+3)^2/12$ or not. Roots of unity — the complex numbers that repeat their powers with a fixed period — appear in a question about coins in a pocket, through the poles of a generating function, and their periods are the denominations.

The waves also explain a pattern in the table of United States coins: the counts change only at multiples of five, because every coin except the penny is a multiple of five, so paying $n$ and paying the multiple of five just below it differ only in pennies. In generating-function terms, the factors other than $1/(1 - q)$ involve only powers of $q^5$, and the count is constant on blocks of five, a wave of period five so strong that it flattens the curve into steps.

Exact only as far as the tables go #

The counts are exact up to the amounts shown, computed by the coin-by-coin rule in floating point where they are below $2^{53}$ and in exact integers for the checked values 73,682 and 292. Schur’s ratio is computed to 40,000 only; its limit of 1 is a theorem. The quasi-polynomial for parts 1, 2, 3 is checked at every amount to 300 and proved by partial fractions; for British coins its polynomial part has degree 7 and its waves have periods up to 200, and no figure attempts to display them.

Counts by coin, Schur’s asymptotic quoted #

Computed here: the number of ways to make every amount up to 200 pence in British coins and up to 100 cents in United States coins, with 73,682 and 292 checked exactly; the count for parts 1, 2, 3 against the quasi-polynomial at every $n$ to 300; the count for parts 1, 2 against $\lfloor n/2\rfloor + 1$; the ratio of Schur’s leading term to the exact count to 40,000; the fewest coins by exhaustive dynamic programming and the greedy count, compared at every amount to 500 for six coinages; and the ten partitions of 10 into 1, 2 and 5.

Quoted: Sylvester’s waves of 1857; Schur’s leading term; Pólya’s use of the dollar; the theorem of Kozen and Zaks of 1994.

Still open: the canonical coinages #

Deciding whether a given coinage is canonical is quick, by Kozen and Zaks’s bound. But a description of all canonical coinages is not known. Small coinages have been described completely and partial characterisations exist for larger ones, but no simple rule is known that tells, from the denominations alone, whether the cashier’s rule is always right. A related question asks how many coins are needed on average to pay amounts up to some limit, and which coinages minimise it; Jeffrey Shallit computed the best four-coin coinages for amounts up to a dollar, finding that the United States coinage could be improved by replacing the dime with an 18-cent coin, and the general optimisation is unsolved.

A polynomial, waves, and the cashier #

The number of ways to make $n$ from a finite set of coins is a quasi-polynomial in $n$: a polynomial of degree one less than the number of coins, plus waves that repeat with the periods of roots of unity dividing the coins. For parts 1, 2, 3 it is $(6n^2 + 36n + 47)/72 + (-1)^n/8 + \tfrac29\cos(2\pi n/3)$ exactly; for British coins the count at two pounds is 73,682 and the leading term is still 3% off at four hundred pounds. The fewest coins is a separate question, answered by the largest coin first for canonical coinages like these, and wrongly for coins of 1, 3 and 4. Behind all three answers is one product of geometric series, read in three ways: its coefficients count, its smallest exponents economise, and its zero coefficients mark the amounts that cannot be paid at all.