|
|
A073031
|
|
Number of ways of making change for n cents using coins of sizes 1, 2, 5, 10 cents, when order matters.
|
|
5
|
|
|
1, 1, 2, 3, 5, 9, 15, 26, 44, 75, 129, 220, 377, 644, 1101, 1883, 3219, 5505, 9412, 16093, 27517, 47049, 80448, 137553, 235195, 402148, 687611, 1175712, 2010288, 3437288, 5877241, 10049189, 17182590, 29379620, 50234693, 85893702
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
OFFSET
|
0,3
|
|
REFERENCES
|
Peter Boros (borospet(AT)freemail.hu): Lectures on Fibonacci's World at the SOTERIA Foundation, 1999.
P. Henrici, Applied and Computational Complex Analysis. Wiley, NY, 3 vols., 1974-1986. (Vol. 1, p. 580.)
|
|
LINKS
|
Index entries for linear recurrences with constant coefficients, signature (1,1,0,0,1,0,0,0,0,1).
|
|
FORMULA
|
a(n) = a(n-1) + a(n-2) + a(n-5) + a(n-10), a(0)=1.
With offset 1, the INVERT transform of (1 + x + x^4 + x^9). - Gary W. Adamson, Apr 04 2017
|
|
EXAMPLE
|
a(4)=5 because 4 = 1 + 1 + 1 + 1 = 1 + 1 + 2 = 1 + 2 + 1 = 2 + 1 + 1 = 2 + 2: five possible exchange. a(15) = a(14) + a(13) + a(10) + a(5) = 1883 = 1101 + 644 + 129 + 9.
|
|
MAPLE
|
a:= n-> (Matrix(10, (i, j)-> if i+1=j or j=1 and member (i, [1, 2, 5, 10]) then 1 else 0 fi)^n)[1, 1]: seq(a(n), n=0..35); # Alois P. Heinz, Oct 07 2008
|
|
CROSSREFS
|
|
|
KEYWORD
|
easy,nonn
|
|
AUTHOR
|
|
|
STATUS
|
approved
|
|
|
|