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,2

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).

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)

Prog

(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

Crossrefs

Cf. A001300.

Sequence in context: A109182 A342874 A241047 * A108828 A239825 A145206

Adjacent sequences: A085499 A085500 A085501 * A085503 A085504 A085505

Keyword

easy,nonn

Author

Jason Earls, Aug 15 2003

Status

approved