cp's OEIS Frontend

A307849 Number of ways to pay n dollars using Canadian coins, that is: nickels (5 cents), dimes (10 cents), quarters (25 cents), loonies (100 cents or $1 coins) and toonies ($2 coins).

%I A307849 #31 Sep 08 2022 08:46:21
%S A307849 1,30,128,362,813,1588,2808,4620,7185,10690,15336,21350,28973,38472,
%T A307849 50128,64248,81153,101190,124720,152130,183821,220220,261768,308932,
%U A307849 362193,422058,489048,563710,646605,738320,839456,950640,1072513,1205742,1351008,1509018
%N A307849 Number of ways to pay n dollars using Canadian coins, that is: nickels (5 cents), dimes (10 cents), quarters (25 cents), loonies (100 cents or $1 coins) and toonies ($2 coins).
%C A307849 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.
%H A307849 Colin Barker, <a href="/A307849/b307849.txt">Table of n, a(n) for n = 0..1000</a>
%H A307849 <a href="/index/Rec#order_06">Index entries for linear recurrences with constant coefficients</a>, signature (4,-5,0,5,-4,1).
%F A307849 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.
%F A307849 G.f.: -(13*x^2+26*x+1)/((x-1)^5*(x+1)). - _Alois P. Heinz_, May 01 2019
%F A307849 From _Colin Barker_, May 01 2019: (Start)
%F A307849 a(n) = (33 - 9*(-1)^n + 224*n + 298*n^2 + 136*n^3 + 20*n^4) / 24.
%F A307849 a(n) = 4*a(n-1) - 5*a(n-2) + 5*a(n-4) - 4*a(n-5) + a(n-6) for n > 5.
%F A307849 (End)
%e A307849 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.
%e A307849 [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].
%t A307849 LinearRecurrence[{4, -5, 0, 5, -4, 1}, {1, 30, 128, 362, 813, 1588}, 36] (* _Jean-François Alcover_, May 05 2019 *)
%o A307849 (PARI) Vec((1 + 26*x + 13*x^2) / ((1 - x)^5*(1 + x)) + O(x^40)) \\ _Colin Barker_, May 01 2019
%o A307849 (Magma) [#RestrictedPartitions(100*n,{5,10,25,100,200}):n in [0..35]]; // _Marius A. Burtea_, May 06 2019
%Y A307849 Cf. A085502, A160551.
%K A307849 nonn,easy
%O A307849 0,2
%A A307849 _Lucien Haddad_, David Wehlau, May 01 2019