Counting recurrences replace the minimum with a sum, and the change is larger than it looks: with the coin types on the outside each multiset is built in one fixed order and counted once, and with the amounts on the outside every ordering is counted separately. Both loops read the table exactly 295 times on the lab's instance. One answers 541 and the other 91 197 869 007 632 925 819 218.
Core ideas
The hard idea is that the loop nesting is the specification here, not an implementation choice: it is what fixes whether an ordering counts as a second way of paying.
The optimising recurrences on this course take the best of several options. A counting recurrence adds them: the number of ways to make v is the sum, over the options, of the number of ways to make what is left. The empty amount has exactly one way of being made — take nothing — so the base case is 1 rather than 0, and getting that wrong makes every count zero.
Running the coin loop outermost means every combination is assembled in one fixed order: all the ones, then all the twos, then all the fives. A multiset has exactly one such assembly, so it is counted exactly once, and the answer for 100 from 1, 2 and 5 is 541.
Running the amount loop outermost lets any coin be the last one added at any step, so 1 then 2 and 2 then 1 are two different histories and both are counted. That is a count of ordered sequences, and for 100 from the same three coins it is a twenty-three-digit number. Readers write this loop while meaning the other one, which is why both are on the panel.
The material
The counting recurrences, why the loop order decides the question, what the objects look like at small amounts, and why the numbers are BigInt.
A combination is a multiset of coins adding to the amount: how many of each denomination, with no notion of order. An ordered sequence is a list of coins adding to the amount, where two lists differing only in order are different. Every combination corresponds to one or more ordered sequences, and the two counts are never equal once more than one denomination is used.
Let C(i, v) be the number of combinations of the first i coin types adding to v, with C(i, 0) = 1 and C(0, v) = 0 for v > 0. Then C(i, v) = C(i−1, v) + C(i, v − c(i)), the second term omitted when c(i) > v. Let S(v) be the number of ordered sequences adding to v, with S(0) = 1. Then S(v) is the sum of S(v − c) over all coins c ≤ v.
For combinations, split on how many copies of coin type i are used. If none, the combination uses the first i−1 types and there are C(i−1, v) of those. If at least one, remove exactly one copy and what remains is a combination of the first i types adding to v − c(i), and this correspondence is a bijection. The two cases are disjoint and exhaustive, so the counts add.
For sequences, split on the last coin. Each sequence adding to v has a final coin c, and deleting it leaves a sequence adding to v − c; conversely appending c to such a sequence gives one adding to v. That is a bijection for each c, the cases are disjoint because the final coin differs, and summing over c gives S(v). The single-row loop with the amounts outermost is exactly this recurrence, and the one with the coins outermost is exactly the other.
□
Four combinations: 5, 2 + 2 + 1, 2 + 1 + 1 + 1, 1 + 1 + 1 + 1 + 1. Nine ordered sequences: the five ones; 1 1 1 2 and its three other arrangements; 1 2 2, 2 1 2 and 2 2 1; and 5. Four and nine, and the lab lists both at this size so the difference is an object rather than a number.
Notice which objects multiplied. The combination 2 + 2 + 1 has three arrangements and the combination 2 + 1 + 1 + 1 has four, while 5 and the five ones have one each: 1 + 4 + 3 + 1 = 9. The ratio between the two counts is not a constant and is not a factorial — it depends on how many copies of each denomination each combination uses.
On the lab's main instance — 1, 2 and 5 at an amount of 100 — both nestings read the table 295 times. Identical work, identical table, identical arithmetic per step. The only difference is which loop is outside, and the two answers differ by twenty orders of magnitude. There is no performance argument for either one and there is no way to tell them apart by watching them run.
This is the most direct version of a claim this course keeps making. A measurement of what an algorithm costs tells you nothing about what it computes, and here the two are completely decoupled: same reads, same cells, different question. The only defence is a second route, and the panel provides one — a memo-free recursion for each count, which at small amounts confirms both, and the objects themselves listed where they fit.
91 197 869 007 632 925 819 218 has twenty-three digits, and the largest integer a double holds exactly is 9 007 199 254 740 992, which has sixteen. A page computing this count in floating point would print a number that is merely close — the leading digits right, the tail invented — and would look exactly like a page that had computed it. Every count of ways in this kit is an arbitrary-precision integer for that reason, and none is ever converted.
One consequence for the cost model, and it is the divergence this page closes on. The table makes 295 reads, and each read is followed by an addition; but those additions are on numbers of up to twenty-three digits, not on machine words. The bound Θ(nk) counts arithmetic operations and treats each as constant, which is exactly what stops being true here. Measured: 295 reads. Proved: Θ(nk) operations. What neither of them says is how long an addition takes when the numbers are as long as the answer, and on this instance it is the addition that dominates.
Interactive
Combinations and ordered sequences, exact in BigInt, both checked twice
Method
Three of these four steps are about deciding what the question is before deciding how to answer it.
A shopkeeper handing over change wants combinations; a process that emits coins one at a time and cares about the history wants sequences. The two loops are both correct and they answer those two different questions, so the question has to be settled first.
There is exactly one way to make nothing. A counting table initialised entirely to zero stays entirely zero, which at least fails loudly; a table whose base is zero only at the empty amount fails quietly and undercounts.
That nesting fixes an assembly order, and one fixed assembly order per multiset is what makes the count a count of multisets. The inner loop then runs upward, so that a coin may be reused — which is the same forward sweep that made the one-row knapsack unbounded, doing the same job for the same reason.
These numbers pass what a double holds long before they stop being interesting. An exact integer type costs nothing at this size and is the difference between a printed answer and a printed approximation that looks like an answer.
Three coin types, amounts zero to five. The first block adds one coin type per row, which counts combinations; the second is a single row swept once per amount, which counts ordered sequences.
The row for ordered sequences begins 1, 1, 2, 3, 5 and a reader who has met the Fibonacci numbers will recognise it: with coins 1 and 2 alone that is exactly what counting ordered sequences gives, and the 5 coin first shows up at amount 5, where it turns the expected 8 into 9. That recognition is worth having, because it makes the sequence count feel like the natural one, and it is usually not the one wanted.
The combination block is the one to read slowly. After the first row every amount has exactly one combination, made of ones. Adding the 2 coin gives the row 1 1 2 2 3 3: the entry at 4 is 3 because a four is four ones, two and two ones, or two twos, and the entry was reached by adding the count from two columns left in the same row, which is the forward sweep allowing reuse.
For a faded rehearsal, change the coins to 3 and 7 and keep the amount at 20 before running it. The supplied first move: 20 is not a multiple of 3, and subtracting one 7 leaves 13, which is not either, so at least two sevens are needed. Work out how many combinations there are, predict how many ordered sequences, and check both — the panel lists the combinations, and the sequence count is the one you have to reason about.
You should be able to write both counting recurrences and prove each by a bijection, explain why one counts multisets and the other counts orderings, set the empty case correctly, and say at what size a floating-point count stops being a count.
Something to change about this lesson? Write it down, tick it off when it is handled, and export the list when you want to act on it. Kept in this browser only: nothing is sent anywhere, and nobody is notified.
No recommendations yet for this lesson.