Frank Morgan

I stumbled across an old Math Chat column of yours, which mentioned that the number of ways to make change for a dollar is the coefficient of in the Taylor expansion of

.

But I don’t see there, or anywhere on the web, the general formula for the number of ways c(n) to make change for n dollars.  In case you are interested, below I derive it to be:

.

Spending 1 trillion dollars with the federal stimulus means that Obama has

=  13 333333 333398 333333 333445 333333 333413 833333 333354 500000 000001

ways to make Change for America.

Derivation: For any one instance of making change, the value contributed in pennies will be some non-negative integer number of dollars plus some fractional amount in [$0.00, $0.99], and likewise for the other coins.  The generating function for making an integer number of dollars using less than $1.00 value from each coin is a polynomial:

(1-x^100)^6 / ((1-x)(1-x^5)(1-x^10)(1-x^25)(1-x^50)(1-x^100))

where each factor of the numerator truncates the series for each contributing coin.  This polynomial shows 1 way to make $0, 287 ways to make $1, 985 ways to make $2, 325 ways to make $3, 2 ways to make $4, and 0 ways to make $5 or more using less than $1.00 value of each coin.  The way to make $n using a non-negative integer number of dollars of each coin has the generating function 1/(1-x)^6.  Thus the generating function for the solution c(n) is:

(1+ 287*x + 985*x^2 + 325*x^3 + 2*x^4) / (1-x)^6.

and this gives the c(n) formula above.

Making Change for a Small Purse (added 18 February 2014)

Suppose you have a small purse or are otherwise motivated to carry your money using the largest denominations possible. For example, to carry an amount of $123.45, you’d first use the largest-denomination bill that does not exceed that amount, which is $100; then the largest-denomination bill that does not exceed the remaining amount ($23.45), which is $20; then three $1 bills; then one quarter; then two dimes. In symbols we’ll write a multiset Purse[123.45] = {100, 20, 1, 1, 1, 0.25, 0.10, 0.10} for a set of bill and coin denominations, D = {100, 50, 20, 10, 1, 0.25, 0.10, 0.05, 0.01}. Generally, we define Purse[S] recursively with Purse[0] = ∅ Purse[S] = {m(S,D)} ∪ Purse[S-m(S,D)] … where m(S,D) is the largest value in D that does not exceed the value S. (Note that for this set D, Purse[S] is well defined only if S is a non-negative multiple of 0.01.) If you start with S in your purse, and are buying an item that costs C, you will finally end up with F=S-C in your purse. In terms of the actual bills and coins, you start with Purse[S] in your purse and you want to finish with Purse[F] in your purse. Consider this strategy for achieving this goal: Look at every bill and coin that is present in Purse[S] more often than it is in Purse[F], and write Purse[S]-Purse[F] for the multiset that contains only the excess amount of these bills and coins. Give Purse[S]-Purse[F] to the cashier. (Note that at least these bills and coins must be given to the cashier if there is to be any hope of finishing with Purse[F].) Receive the proper change R without telling the cashier which bills and coins you are hoping for; assume that the change is given with the largest denominations possible; that is, as Purse[R].

Questions:

1.With this strategy will you always end up with Purse[F]?

2.Writing G=Value(Purse[S]-Purse[F]) for the value of the excess bills and coins given to the cashier, is it always the case that the multiset of given bills and coins, Purse[S]-Purse[F], is equal to Purse[G]?

3. If you give the excess bills and coins, Purse[S]-Purse[F], in an order that saves an instance of the largest denomination until last, is it the case that you will not reach or exceed the item’s price until you have given every bill and coin? (This will be useful for those automated cashiers at the supermarket that give you your change the moment you reach or exceed the purchase price.)

Lee Newberg, Ph.D.

Research Scientist, Center for Bioinformatics, Wadsworth Center, NYS Department of Health,

Research Associate Professor, Bioinformatics Research Group, Department of Computer Science, Rensselaer Polytechnic Institute