login
Number of ways of making change for n cents using coins whose values are the previous terms in the sequence, starting with 1,2 cents.
0

%I #32 Feb 21 2016 19:42:52

%S 1,2,2,3,5,8,10,14,17,23,28,35,43,53,64,78,93,112,132,158,184,217,253,

%T 295,342,396,455,526,600,689,784,893,1014,1150,1299,1468,1651,1860,

%U 2084,2339,2613,2921,3257,3628,4034,4482,4967,5508,6087,6731,7426,8188,9017,9920,10898,11969,13120,14382,15737,17215

%N Number of ways of making change for n cents using coins whose values are the previous terms in the sequence, starting with 1,2 cents.

%e For n=4, the coins available are 1,2. There are a(4)=3 ways to make 4 cents with these coins:

%e 4 = 1+1+1+1

%e 4 = 2+1+1

%e 4 = 2+2

%e Since there are 3 ways, now the available coins are 1,2,3. For n=5, we have:

%e 5 = 1+1+1+1+1

%e 5 = 2+1+1+1

%e 5 = 2+2+1

%e 5 = 3+1+1

%e 5 = 3+2

%e for 5 ways to make change, so now 1,2,3,5 are available, etc.

%t a = {1, 2}; Do[AppendTo[a, Count[IntegerPartitions@ n, w_ /; AllTrue[w, MemberQ[a, #] &]]], {n, 3, 60}]; a (* _Michael De Vlieger_, Jan 15 2016, Version 10 *)

%Y Cf. A000008, A001300, A089197, A208216.

%K nonn

%O 1,2

%A _Christopher Cormier_, Jan 14 2016