Detailed mathematical approach

Problem Summary

The UK coin system uses the eight denominations \(C=\{1,2,5,10,20,50,100,200\}\), measured in pence. The problem asks for the number of unordered collections of these coins whose total is 200 pence, that is, £2.

Equivalently, we must count the non-negative integer solutions of

$n_1+2n_2+5n_5+10n_{10}+20n_{20}+50n_{50}+100n_{100}+200n_{200}=200.$

The key word is unordered: only the multiset of coins matters, not the order in which coins are listed. The implementations compute this count exactly, and the final value is \(73682\).

Mathematical Approach

The clean way to count unordered coin combinations is to process the denominations one by one and keep track of how many totals are reachable with the denominations seen so far.

Counting Restricted Partitions

Write the sorted denominations as \(c_1=1,c_2=2,\dots,c_8=200\). Let \(A_j(t)\) denote the number of ways to make \(t\) pence using only the first \(j\) denominations. Then \(A_j(t)\) counts restricted partitions of \(t\): parts may repeat, but each part must belong to \(\{c_1,\dots,c_j\}\).

The base conditions are immediate:

$A_0(0)=1,\qquad A_0(t)=0\quad (t>0).$

There is exactly one way to make 0 with no coins, namely the empty choice, and no way to make a positive amount with no denominations available.

Splitting by the Current Denomination

Fix \(j\) and consider amount \(t\). Every valid combination counted by \(A_j(t)\) falls into exactly one of two classes.

The first class uses no coin of value \(c_j\), so it contributes \(A_{j-1}(t)\). The second class uses at least one \(c_j\); after removing one such coin, what remains is a valid combination for \(t-c_j\) that may still use \(c_j\), so it contributes \(A_j(t-c_j)\).

Therefore, for \(t\ge c_j\),

$A_j(t)=A_{j-1}(t)+A_j(t-c_j).$

For \(t<c_j\), the denomination \(c_j\) cannot appear at all, so \(A_j(t)=A_{j-1}(t)\). This recurrence is the mathematical core of the solution.

The One-Dimensional Table and Its Invariant

The recurrence only needs the previous denomination set and the current denomination set at smaller amounts, so the usual two-dimensional table can be collapsed to one dimension. Maintain an array \(W[0],W[1],\dots,W[200]\), and after finishing denomination \(c_j\), interpret \(W[t]\) as \(A_j(t)\).

Initially \(W[0]=1\) and every other entry is 0. When processing coin \(c\), update amounts in ascending order:

$W[t]\leftarrow W[t]+W[t-c]\qquad (t=c,c+1,\dots,200).$

This order is crucial. Before the assignment, \(W[t]\) still represents the count without the current coin, namely \(A_{j-1}(t)\). Because \(t\) increases, the entry \(W[t-c]\) has already been updated for the current coin and therefore equals \(A_j(t-c)\). After the addition, \(W[t]\) becomes exactly \(A_j(t)\).

If the amounts were scanned in descending order instead, the update would forbid repeated use of the same denomination and would solve a different problem. The ascending sweep is precisely what enforces “unlimited copies of each coin, but counted without order.”

Worked Example: Why the 10-Pence Checkpoint Is 11

The implementations verify that the number of ways to make 10 pence is \(11\). That value illustrates the recurrence nicely.

After processing 1p and 2p coins, the number of ways to make 10 is \(6\), corresponding to 0, 1, 2, 3, 4, or 5 copies of the 2p coin. When the 5p coin is processed, the update adds the number of ways to make 5, which is \(4\), so the count for 10 rises from \(6\) to \(10\). Finally, processing the 10p coin adds \(W[0]=1\), producing \(11\).

In direct combinatorial terms, those 11 combinations are: one 10p coin; two 5p coins; one 5p coin plus any of the 3 ways to make 5 from \(\{1,2\}\); or no 5p coin plus any of the 6 ways to make 10 from \(\{1,2\}\). The dynamic program packages exactly that case split into repeated local updates.

Generating-Function Interpretation

The same answer can be described as a coefficient extraction problem. Each denomination \(c\) contributes the geometric series

$1+x^c+x^{2c}+x^{3c}+\cdots=\frac{1}{1-x^c},$

because we may choose 0, 1, 2, 3, ... copies of that coin. Hence the number of valid £2 combinations is the coefficient of \(x^{200}\) in

$\prod_{c\in C}\frac{1}{1-x^c} =\frac{1}{(1-x)(1-x^2)(1-x^5)(1-x^{10})(1-x^{20})(1-x^{50})(1-x^{100})(1-x^{200})}.$

The dynamic program is simply a practical way to build this product while discarding coefficients above degree 200, which are irrelevant for the target amount.

How the Code Works

Initialization

The C++, Python, and Java implementations store the eight UK denominations in ascending order, default the target to 200, and allocate an array of length 201. The entry for amount 0 is set to 1, and every other entry starts at 0.

Denomination Sweep

For each coin value, the implementation scans all reachable amounts from that coin up to the target and adds the count from the smaller amount. After the 1p pass, every amount has exactly one representation. Each later pass adds the representations that use at least one coin of the newly processed denomination.

Sanity Checks and Final Output

Before printing the main result, the implementations verify two small benchmark cases: 4 ways for 5 pence and 11 ways for 10 pence. Those checks confirm both the recurrence and the loop order. The final answer is then read directly from the entry for 200 pence, which is \(73682\).

Complexity Analysis

For \(m\) denominations and target \(T\), the method runs in \(O(mT)\) time and uses \(O(T)\) space. Here \(m=8\) and \(T=200\), so the array has only 201 entries.

More concretely, the inner addition is executed exactly

$\sum_{c\in C}(200-c+1)=1220$

times. That is why all three implementations finish essentially instantly for Problem 31.

Footnotes and References

1. Problem page: Project Euler - Problem 31
2. Change-making problem: Wikipedia - Change-making problem
3. Generating function: Wikipedia - Generating function
4. Integer partitions: Wikipedia - Partition (number theory)