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).
1, 30, 128, 362, 813, 1588, 2808, 4620, 7185, 10690, 15336, 21350, 28973, 38472, 50128, 64248, 81153, 101190, 124720, 152130, 183821, 220220, 261768, 308932, 362193, 422058, 489048, 563710, 646605, 738320, 839456, 950640, 1072513, 1205742, 1351008, 1509018
Offset: 0
Examples
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].
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).
Programs
-
Magma
[#RestrictedPartitions(100*n,{5,10,25,100,200}):n in [0..35]]; // Marius A. Burtea, May 06 2019 -
Mathematica
LinearRecurrence[{4, -5, 0, 5, -4, 1}, {1, 30, 128, 362, 813, 1588}, 36] (* Jean-François Alcover, May 05 2019 *) -
PARI
Vec((1 + 26*x + 13*x^2) / ((1 - x)^5*(1 + x)) + O(x^40)) \\ Colin Barker, May 01 2019
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)
Comments