A073031 Number of ways of making change for n cents using coins of sizes 1, 2, 5, 10 cents, when order matters.

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

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

Table of n, a(n) for n=0..35.

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.

G.f.: 1/(1 - x - x^2 - x^5 - x^10). - Franklin T. Adams-Watters, Oct 24 2006

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

Mathematica

LinearRecurrence[{1, 1, 0, 0, 1, 0, 0, 0, 0, 1}, {1, 1, 2, 3, 5, 9, 15, 26, 44, 75}, 36] (* Jean-François Alcover, Jan 25 2025 *)

Crossrefs

Cf. A079971.

Sequence in context: A114623 A079971 A355805 * A114138 A114140 A302018

Adjacent sequences: A073028 A073029 A073030 * A073032 A073033 A073034

Keyword

easy,nonn

Author

Miklos Kristof, Aug 22 2002

Status

approved