A085502 Number of (unordered) ways of making change for n dollars using coins of denominations 1, 5, 10, 25, 50 and 100.

1, 293, 2728, 12318, 38835, 98411, 215138, 422668, 765813, 1302145, 2103596, 3258058, 4870983, 7066983, 9991430, 13812056, 18720553, 24934173, 32697328, 42283190, 53995291, 68169123, 85173738, 105413348, 129328925, 157399801, 190145268, 228126178, 271946543

Offset: 0

Author

Jason Earls, Aug 15 2003

Keywords

• easy
• nonn

Links

• Colin Barker, Table of n, a(n) for n = 0..1000
• Index entries for linear recurrences with constant coefficients, signature (6,-15,20,-15,6,-1).

Crossrefs

Cf. A001300.

Programs

PARI

{a(n)=if(n<0,0,polcoeff(1/((1-x)*(1-x^5)*(1-x^10)*(1-x^25)*(1-x^50)*(1-x^100))+ x*O(x^n),n))}
for(n=0,30,print1(a(n*100)","))

PARI

Vec((1 + 287*x + 985*x^2 + 325*x^3 + 2*x^4) / (1 - x)^6 + O(x^30)) \\ Colin Barker, Feb 21 2017

Formula

a(n) = (n + 1) (80 n^4 + 310 n^3 + 362 n^2 + 121 n + 6) / 6. - Dean Hickerson

From Colin Barker, Feb 21 2017: (Start)

a(n) = 6*a(n-1) - 15*a(n-2) + 20*a(n-3) - 15*a(n-4) + 6*a(n-5) - a(n-6) for n>5.

G.f.: (1 + 287*x + 985*x^2 + 325*x^3 + 2*x^4) / (1 - x)^6.

(End)