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

Author

Marko Riedel, Jul 25 2014

Keywords

• nonn
• easy

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

Programs

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

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

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)

Extensions

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