OFFSET
0,2
COMMENTS
Our proof for the formula is based on an observation by David Wehlau that the number f(n) of ways to pay n dollars using nickels, dimes and quarters satisfies the recurrence f(n) = f(n-1) + 40*n - 12 and f(1)=29.
LINKS
Colin Barker, Table of n, a(n) for n = 0..1000
Index entries for linear recurrences with constant coefficients, signature (4,-5,0,5,-4,1).
FORMULA
a(n) = (5/6)*n^4 + (17/3)*n^3 + (149/12)*n^2 + (28/3)*n + (11 + 3*(-1)^(n+1))/8. Our proof is based on the fact that the number of ways f(n) to pay n dollars using nickels, dimes and quarters is f(n) = 20*n^2 + 8*n + 1. From this one can show that the number of ways g(n) to pay n dollars using nickels, dimes, quarters and loonies ($1 coins) is g(n) = (20/3)*n^3 + 14*n^2 + (25/3)*n + 1.
G.f.: -(13*x^2+26*x+1)/((x-1)^5*(x+1)). - Alois P. Heinz, May 01 2019
From Colin Barker, May 01 2019: (Start)
a(n) = (33 - 9*(-1)^n + 224*n + 298*n^2 + 136*n^3 + 20*n^4) / 24.
a(n) = 4*a(n-1) - 5*a(n-2) + 5*a(n-4) - 4*a(n-5) + a(n-6) for n > 5.
(End)
EXAMPLE
For n = 1, a(1)=30. There are 30 ways to pay $1 using Canadian coins. They are all listed below. A vector [n1,n2,n3,n4,0] means n1 nickels plus n2 dimes plus n3 quarters plus n4 loonies make $1.
[0, 0, 0, 1, 0], [0, 0, 4, 0, 0], [0, 5, 2, 0, 0], [0, 10, 0, 0, 0], [1, 2, 3, 0, 0], [1, 7, 1, 0, 0], [2, 4, 2, 0, 0], [2, 9, 0, 0, 0], [3, 1, 3, 0, 0], [3, 6, 1, 0, 0], [4, 3, 2, 0, 0], [4, 8, 0, 0, 0], [5, 0, 3, 0, 0], [5, 5, 1, 0, 0], [6, 2, 2, 0, 0], [6, 7, 0, 0, 0], [7, 4, 1, 0, 0], [8, 1, 2, 0, 0], [8, 6, 0, 0, 0], [9, 3, 1, 0, 0], [10, 0, 2, 0, 0], [10, 5, 0, 0, 0], [11, 2, 1, 0, 0], [12, 4, 0, 0, 0], [13, 1, 1, 0, 0], [14, 3, 0, 0, 0], [15, 0, 1, 0, 0], [16, 2, 0, 0, 0], [18, 1, 0, 0, 0], [20, 0, 0, 0, 0].
MATHEMATICA
LinearRecurrence[{4, -5, 0, 5, -4, 1}, {1, 30, 128, 362, 813, 1588}, 36] (* Jean-François Alcover, May 05 2019 *)
PROG
(PARI) Vec((1 + 26*x + 13*x^2) / ((1 - x)^5*(1 + x)) + O(x^40)) \\ Colin Barker, May 01 2019
(Magma) [#RestrictedPartitions(100*n, {5, 10, 25, 100, 200}):n in [0..35]]; // Marius A. Burtea, May 06 2019
CROSSREFS
KEYWORD
nonn,easy
AUTHOR
Lucien Haddad, David Wehlau, May 01 2019
STATUS
approved