ways to make change

[Albert Chan]

There is no need to count it all, case by case:
Lets use shorthand, P = penny, N = nickel, D = dime, Q = quarter, H = half-dollar.

Code:

def PN(x): return 1 + x//5

def PND(x): return (1 + x//10) * (1 + x//5 - x//10)

def PNDH(x):
    'Ways with only pennies, nickels, dimes, and half-dollar'
    n, d, h = x//5, x//10, x//50
    return ((50*h-15*n-5)*h + 6*(1+d)*(1+n-d)) * (h+1) // 6

def PNDQ(x): return PNDH(x) + PNDH(x-25)

>>> PNDQ(100) # ways to add to 1 dollar, with pennies, nickels, dimes, quarter
242

>>> PNDQ(100000) # how about 1000 dollars ?
133423351001L

Explanation:
Let x in cents, and n, d, h = floor(x/5), floor(x/10), floor(x/50)

PN ways = Σ (1, k=0 to n) = 1 + n
PND ways = Σ (1 + (n - 2k), k=0 to d) = (1 + d) (1 + n - d)

Adding quarter directly is complicated, since quarter cannot split evenly to dimes.
So, "borrow" a half-dollar, 1 half-dollar = 2 quarters = 5 dimes = 10 nickels.

PNDH ways
= Σ((1 + (d-5k)) * (1 + (n-10k) - (d-5k)), k=0 to h)
= Σ(((1+d) - 5k) * ((1+n-d) - 5k), k=0 to h)
= Σ((1+d)(1+n-d) - 5k*(2+n), k=0 to h) + 25 * Σ(k^2, k=0 to h)
= (h+1) * ((1+d)(1+n-d) - (5h/2)(2+n)) + 25 * h*(h+1)*(2h+1) / 6
= ((50*h-15*n-5)*h + 6*(1+d)*(1+n-d)) * (h+1) / 6

Above formula returns 0 ways for x = range(-65, 0).
To fill the missing counts, PNDQ(x) = PNDH(x) + PNDH(x-25)