Re: Making Change

*To*: mathgroup at smc.vnet.net*Subject*: [mg15175] Re: [mg15160] Making Change*From*: Robert Pratt <rpratt at math.unc.edu>*Date*: Thu, 17 Dec 1998 00:27:52 -0500*Sender*: owner-wri-mathgroup at wolfram.com

The solutions for the change-making problem can be enumerated by means of the following generating function. gf[x_]:=1/((1 - p x)(1 - n x^5)(1 - d x^10)(1 - q x^25)(1 - h x^50)(1 - b x^100)) This function is really a product of six geometric series, one for each denomination: penny, nickel, dime, quarter, half dollar, and buck. For example, the 1/(1 - q x^25) factor expands to the series 1 + q x^25 + q^2 x^50 + q^3 x^75 + ... Each term in this series represents a choice of the number of quarters to use, together with their total value in cents. We can enumerate all the ways to make change for a dollar with these six denominations by expressing gf[x] as a power series in x and extracting the coefficient of x^100. Expand[Coefficient[Series[gf[x],{x,0,100}],x,100]] The output will be a sum of terms such as d^5 n^2 p^40, which corresponds to 5 dimes, 2 nickels, and 40 pennies. To find out the total number of ways, substitute 1 for p, n, d, q, h, and b. Note that if we ignore dollar coins, we obtain 292 ways. If we also ignore half dollars, we obtain only 242 ways. Rob Pratt Department of Mathematics The University of North Carolina at Chapel Hill CB# 3250, 331 Phillips Hall Chapel Hill, NC 27599-3250 rpratt at math.unc.edu http://www.math.unc.edu/Grads/rpratt/ On Wed, 16 Dec 1998, Wilson Figueroa wrote: > Hello Group, > > I have a question pertaining to making change. > > I was reading The Bathroom Trivia Book and came across the following > statement: > > There are 293 ways to make change for a dollar. > > In the book Introduction to Programming with Mathematica by Gaylord, > Kamin and Wellin there is the following routine: > > makeChange[x_]:=Quotient[Drop[FoldList[Mod,x,{25,10, > 5,1}],-1],{25,10,5,1}] > > that will use he fewest of each coin to make change. > > is there a way to modify this so that it will enumerate the 293 ways of > making change for a dollar or any number of bills? > > For example, for $1.00 the output would show > > 100, pennies > 95 pennies, 1 nickel > 90 pennies, 1 dime > 90 pennies, 2 nickels > > .. > .. > .. > > and then tell me there are 293 such enumerations. > > Thank you for any help. > > Wilson > > > *** Posted from RemarQ - http://www.remarq.com - Discussions Start Here > (tm) ***