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

Author

Miklos Kristof, Aug 22 2002

Keywords

• easy
• nonn

Examples

			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.
		

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

Crossrefs

Cf. A079971.

Programs

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

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