A067996 - OEIS

%I #11 Dec 04 2023 01:10:43

%S 1,1,2,3,4,6,8,10,13,16,21,25,31,37,44,53,62,72,84,96,113,128,147,167,

%T 189,216,243,273,307,342,386,428,477,529,585,650,716,788,867,949,1046,

%U 1141,1248,1361,1481,1617,1755,1904,2065,2232,2424,2614,2824,3045,3278

%N Number of ways of making change for n cents using coins of 1, 2, 3, 5, 10, 20, 25, 50, 100 cents (all historical U.S.A. coinage from 1 to 100 cents).

%C The U.S.A. issued the following unusual denomination coins during the 19th century: 2-cent pieces, 1864-1873; 3-cent pieces, 1851-1889; and 20-cent pieces, 1875-1878.

%D R. S. Yeoman, A Guide Book of United States Coins, Ed. Kenneth Bressett, 53rd Edition (2000). New York: St. Martin's Press, 1999. pp. 104-106, 135. (also known as The Official Red Book of United States Coins)

%H <a href="/index/Mag#change">Index entries for sequences related to making change.</a>

%H <a href="/index/Rec#order_216">Index entries for linear recurrences with constant coefficients</a>, order 216.

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

%e a(5)=6 because change can be made for 5 cents in these 6 ways: (1) 5 1-cent coins, (2) 3 1-cent, 1 2-cent, (3) 2 1-cent, 1 3-cent, (4) 1 1-cent, 2 2-cent, (5) 1 2-cent, 1 3-cent, (6) 1 5-cent coin.

%t CoefficientList[ Series[1/((1 - x)(1 - x^2)(1 - x^3)(1 - x^5)(1 - x^10)(1 - x^20)(1 - x^25)(1 - x^50)(1 - x^100)), {x, 0, 55} ], x ]

%o (PARI) a(n)=polcoeff(1/((1-x)*(1-x^2)*(1-x^3)*(1-x^5)*(1-x^10)*(1-x^20)*(1-x^25)*(1-x^50)*(1-x^100)+x*O(x^n)), n)

%Y Cf. A067995, A067997, A000008.

%K easy,nonn

%O 0,3

%A _Rick L. Shepherd_, Feb 07 2002

%E Offset corrected to 0 by _Ray Chandler_, Dec 04 2023