ways to make change

[Albert Chan]

We could also build ways formula from 5 points: x%100, x%100 + 1, ... x%100 + 4
Formula is good for cents = n * 100 + x%100

Example, if x%100 = 0, we have dollars ways formula

Code:

1    292  2435 9590  26517 ; forward diff = 5 coins ways, 0 to 4 dollars
291  2143 7155 16927
1852 5012 9772
3160 4760
1600

PNDQH ways   = \(1\binom{n}{0}+291\binom{n}{1}+1852\binom{n}{2}+3160\binom{n}{3}+
1600\binom{n}{4}\)
PNDQHB ways = \(1\binom{n+1}{1}+291\binom{n+1}{2}+1852\binom{n+1}{3}+3160\binom{n+1}{4}+
1600\binom{n+1}{5}\)

Or, use Horner's rule:
PNDQH ways   = ((((200n + 380)n + 238)n + 55)n + 3) / 3
PNDQHB ways = (((((80n + 390)n + 672)n + 483)n + 127)n + 6) / 6

Example, using either set of formulas, for n = 1000 dollars:

PNDQH ways   = 66 793412 685001
PNDQHB ways = 13398 445413 854501