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) ***