A245573 Minimal coin changing sequence for denominations 1, 2, 5 and 10 cents.

0, 1, 1, 2, 2, 1, 2, 2, 3, 3, 1, 2, 2, 3, 3, 2, 3, 3, 4, 4, 2, 3, 3, 4, 4, 3, 4, 4, 5, 5, 3, 4, 4, 5, 5, 4, 5, 5, 6, 6, 4, 5, 5, 6, 6, 5, 6, 6, 7, 7, 5, 6, 6, 7, 7, 6, 7, 7, 8, 8, 6, 7, 7, 8, 8, 7, 8, 8, 9, 9, 7, 8, 8, 9, 9, 8, 9, 9, 10, 10, 8, 9, 9, 10, 10, 9, 10, 10, 11, 11, 9, 10, 10, 11, 11, 10, 11, 11, 12, 12, 10, 11, 11, 12

Offset

0,4

Links

Colin Barker, Table of n, a(n) for n = 0..1000

Bailor Tow, Coin changing problem, Maths StackExchange

Index entries for linear recurrences with constant coefficients, signature (1,0,0,0,0,0,0,0,0,1,-1).

Formula

From Colin Barker, Feb 22 2017: (Start)

a(n) = a(n-1) + a(n-10) - a(n-11) for n>10.

G.f.: x*(1 + x^2 - x^4 + x^5 + x^7 - 2*x^9) / ((1 - x)^2*(1 + x)*(1 - x + x^2 - x^3 + x^4)*(1 + x + x^2 + x^3 + x^4)).

(End)

Mathematica

CoefficientList[Series[x (1 + x^2 - x^4 + x^5 + x^7 - 2 x^9)/((1 - x)^2*(1 + x) (1 - x + x^2 - x^3 + x^4) (1 + x + x^2 + x^3 + x^4)), {x, 0, 103}], x] (* Michael De Vlieger, Feb 22 2017 *)

Prog

(PARI) concat(0, Vec(x*(1 + x^2 - x^4 + x^5 + x^7 - 2*x^9) / ((1 - x)^2*(1 + x)*(1 - x + x^2 - x^3 + x^4)*(1 + x + x^2 + x^3 + x^4)) + O(x^100))) \\ Colin Barker, Feb 22 2017

Crossrefs

Sequence in context: A137419 A057536 A245574 * A236968 A345220 A265744

Adjacent sequences: A245570 A245571 A245572 * A245574 A245575 A245576

Keyword

nonn,easy

Author

Marko Riedel, Jul 25 2014

Extensions

a(0)=0 prepended by Alois P. Heinz, May 26 2015

Status

approved