cp's OEIS Frontend

A151945 Denomination sequence. Start with the 0th and first coins of value 1 cent: a(0)=a(1)=1. Thereafter a(n), the value of the n-th coin (n>=2), is the number of ways to make change for n cents in earlier coins. The two one-cent coins are considered distinct.

%I A151945 #33 Jul 29 2018 19:08:24
%S A151945 1,1,3,5,7,10,14,19,25,32,42,53,66,82,101,124,150,181,216,257,306,361,
%T A151945 424,495,577,671,776,895,1029,1180,1350,1540,1752,1988,2252,2547,2872,
%U A151945 3231,3630,4071,4558,5093,5683,6330,7040,7822,8674,9606,10625,11738
%N A151945 Denomination sequence. Start with the 0th and first coins of value 1 cent: a(0)=a(1)=1. Thereafter a(n), the value of the n-th coin (n>=2), is the number of ways to make change for n cents in earlier coins. The two one-cent coins are considered distinct.
%C A151945 a(n) is the number of nonnegative solutions to the Diophantine equation 1*x_0 + 1*x_1 + ... + a(n-1)*x_(n-1) = n. - _Melvin Peralta_, Jan 03 2016
%H A151945 Robert G. Wilson v, <a href="/A151945/b151945.txt">Table of n, a(n) for n = 0..3500</a>
%F A151945 G.f: g(x) = Product_{n >= 0} 1/(1-x^a(n)) - x.
%e A151945 Call the two one-cent coins c and d.
%e A151945 Then we can make change for 2 cents in three ways: cc,cd,dd, so a(2) = 3.
%e A151945 Then we can make change for 3 cents in five ways: ccc,ccd,cdd,ddd,3, so a(3) = 5.
%p A151945 b:= proc(n,i) option remember;
%p A151945       if n<0 then 0
%p A151945     elif n=0 then 1
%p A151945     elif i<0 then 0
%p A151945     elif i=1 then n+1
%p A151945     else b(n,i-1) +b(n-a(i),i)
%p A151945       fi
%p A151945     end:
%p A151945 a:= n-> b(n, n-1):
%p A151945 seq(a(n), n=0..100);  # _Alois P. Heinz_, Aug 14 2009
%t A151945 b[n_, i_] := b[n, i] = If[n < 0, 0, If[n == 0, 1, If[i < 0, 0, If[i == 1, n + 1, b[n, i - 1] + b[n - a[i], i]] ]]]; a[0] = a[1] = 1; a[n_] := a[n] = b[n, n - 1]; Table[ a@n, {n, 0, 50}] (* _Robert G. Wilson v_, Aug 17 2009 *)
%t A151945 Nest[Join[#,{Length[FrobeniusSolve[#,Length[#]]]}]&,{1,1},50] (* _Harvey P. Dale_, Jul 29 2018 *)
%o A151945 (Haskell)
%o A151945 a151945 n = a151945_list !! n
%o A151945 a151945_list = 1 : 1 : f [2..] where
%o A151945    f (x:xs) = p (take x a151945_list) x : f xs
%o A151945    p _ 0 = 1; p [] _ = 0
%o A151945    p ds'@(d:ds) m = if m < d then 0 else p ds' (m - d) + p ds m
%o A151945 -- _Reinhard Zumkeller_, Jan 21 2014
%K A151945 nonn,nice
%O A151945 0,3
%A A151945 _David W. Wilson_, Aug 14 2009
%E A151945 More terms from _Alois P. Heinz_, Aug 14 2009