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.

1, 1, 3, 5, 7, 10, 14, 19, 25, 32, 42, 53, 66, 82, 101, 124, 150, 181, 216, 257, 306, 361, 424, 495, 577, 671, 776, 895, 1029, 1180, 1350, 1540, 1752, 1988, 2252, 2547, 2872, 3231, 3630, 4071, 4558, 5093, 5683, 6330, 7040, 7822, 8674, 9606, 10625, 11738

Offset: 0

Author

David W. Wilson, Aug 14 2009

Keywords

• nonn
• nice

Comments

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

Examples

			Call the two one-cent coins c and d.
Then we can make change for 2 cents in three ways: cc,cd,dd, so a(2) = 3.
Then we can make change for 3 cents in five ways: ccc,ccd,cdd,ddd,3, so a(3) = 5.
		

Links

• Robert G. Wilson v, Table of n, a(n) for n = 0..3500

Programs

Haskell

a151945 n = a151945_list !! n
a151945_list = 1 : 1 : f [2..] where
   f (x:xs) = p (take x a151945_list) x : f xs
   p  0 = 1; p []  = 0
   p ds'@(d:ds) m = if m < d then 0 else p ds' (m - d) + p ds m
-- Reinhard Zumkeller, Jan 21 2014

Maple

b:= proc(n,i) option remember;
      if n<0 then 0
    elif n=0 then 1
    elif i<0 then 0
    elif i=1 then n+1
    else b(n,i-1) +b(n-a(i),i)
      fi
    end:
a:= n-> b(n, n-1):
seq(a(n), n=0..100);  # Alois P. Heinz, Aug 14 2009

Mathematica

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 *)
Nest[Join[#,{Length[FrobeniusSolve[#,Length[#]]]}]&,{1,1},50] (* Harvey P. Dale, Jul 29 2018 *)

Formula

G.f: g(x) = Product_{n >= 0} 1/(1-x^a(n)) - x.

Extensions

More terms from Alois P. Heinz, Aug 14 2009