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.

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,3

Comments

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.

Links

Table of n, a(n) for n=0..63.

Index entries for sequences related to making change

Index entries for linear recurrences with constant coefficients, order 188.

Formula

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

Example

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

Mathematica

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

Prog

(PARI) 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

Crossrefs

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.

Sequence in context: A001302 A001313 A057537 * A286874 A065459 A011873

Adjacent sequences: A339091 A339092 A339093 * A339095 A339096 A339097

Keyword

easy,nonn

Author

Robert G. Wilson v, Nov 25 2020

Status

approved