A085502 -id:A085502 - 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).

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

Lucien Haddad, David Wehlau, May 01 2019

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.

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

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

Cf. A085502, A160551.

[#RestrictedPartitions(100*n,{5,10,25,100,200}):n in [0..35]]; // Marius A. Burtea, May 06 2019

LinearRecurrence[{4, -5, 0, 5, -4, 1}, {1, 30, 128, 362, 813, 1588}, 36] (* Jean-François Alcover, May 05 2019 *)

Vec((1 + 26*x + 13*x^2) / ((1 - x)^5*(1 + x)) + O(x^40)) \\ Colin Barker, May 01 2019

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)

A339094 Number of (unordered) ways of making change for n US Dollars using the current US denominations of $1, $2, $5, $10, $20, $50 and $100 bills.

Original entry on oeis.org

1, 1, 2, 2, 3, 4, 5, 6, 7, 8, 11, 12, 15, 16, 19, 22, 25, 28, 31, 34, 41, 44, 51, 54, 61, 68, 75, 82, 89, 96, 109, 116, 129, 136, 149, 162, 175, 188, 201, 214, 236, 249, 271, 284, 306, 328, 350, 372, 394, 416, 451, 473, 508, 530, 565, 600, 635, 670, 705, 740, 793, 828, 881, 916

Offset: 0

Robert G. Wilson v, Nov 25 2020

Not the same as A001313. First difference appears at A001313(100) being 4562, whereas a(100) is 4563; obviously one more than A001313(100).
Not the same as A057537.
Number of partitions of n into parts 1, 2, 5, 10, 20, 50 and 100.

			a(5) is 4 because 1+1+1+1+1 = 2+1+1+1 = 2+2+1 = 5.

Cf. A000008, A001299, A001300, A001301, A001306, A001302, A001306, A001310, A001312, A001313, A001314, A001319, A001343, A001362, A001364, A057537, A067996, A067997, A073031, A085502, A112024, A124146, A160551, A169718, A181934, A187243.

f[n_] := Length@ IntegerPartitions[n, All, {1, 2, 5, 10, 20, 50, 100}]; Array[f, 75, 0] (* or *)
CoefficientList[ Series[1/((1 - x) (1 - x^2) (1 - x^5) (1 - x^10) (1 - x^20) (1 - x^50) (1 - x^100)), {x, 0, 75}], x] (* or *)
Table[ Length@ FrobeniusSolve[{1, 2, 5, 10, 20, 50, 100}, n], {n, 0, 75}] (* much slower *)

coins(v[..])=my(x='x); prod(i=1, #v, 1/(1-x^v[i]))
Vec(coins(1, 2, 5, 10, 20, 50, 100)+O(x^99)) \\ Charles R Greathouse IV, Jan 24 2022

G.f.: 1/((1-x)*(1-x^2)*(1-x^5)*(1-x^10)*(1-x^20)*(1-x^50)*(1-x^100)).

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

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Magma

Mathematica

PARI

Formula