cp's OEIS Frontend

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.

%I A339094 #37 Jun 20 2025 17:41:58
%S A339094 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,
%T A339094 75,82,89,96,109,116,129,136,149,162,175,188,201,214,236,249,271,284,
%U A339094 306,328,350,372,394,416,451,473,508,530,565,600,635,670,705,740,793,828,881,916
%N 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.
%C A339094 Not the same as A001313. First difference appears at A001313(100) being 4562, whereas a(100) is 4563; obviously one more than A001313(100).
%C A339094 Not the same as A057537.
%C A339094 Number of partitions of n into parts 1, 2, 5, 10, 20, 50 and 100.
%H A339094 <a href="/index/Mag#change">Index entries for sequences related to making change</a>
%H A339094 <a href="/index/Rec#order_188">Index entries for linear recurrences with constant coefficients</a>, order 188.
%F A339094 G.f.: 1/((1-x)*(1-x^2)*(1-x^5)*(1-x^10)*(1-x^20)*(1-x^50)*(1-x^100)).
%e A339094 a(5) is 4 because 1+1+1+1+1 = 2+1+1+1 = 2+2+1 = 5.
%t A339094 f[n_] := Length@ IntegerPartitions[n, All, {1, 2, 5, 10, 20, 50, 100}]; Array[f, 75, 0] (* or *)
%t A339094 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 *)
%t A339094 Table[ Length@ FrobeniusSolve[{1, 2, 5, 10, 20, 50, 100}, n], {n, 0, 75}] (* much slower *)
%o A339094 (PARI) coins(v[..])=my(x='x); prod(i=1, #v, 1/(1-x^v[i]))
%o A339094 Vec(coins(1, 2, 5, 10, 20, 50, 100)+O(x^99)) \\ _Charles R Greathouse IV_, Jan 24 2022
%Y A339094 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.
%K A339094 easy,nonn
%O A339094 0,3
%A A339094 _Robert G. Wilson v_, Nov 25 2020