Holiday shopping

Below we plot the number of ways to come up with change for various amounts up to $1.00.   In red, we just allow the usual: namely, pennies, nickels, dimes and quarters.   In green we plot the number of ways to do so allowing for a half-dollar coin and a dollar coin as well.   So, next time you have to come up with $.99 while waiting in line at the cash register, you have to decide which among the 213 ways to come up with $.99 you want to use (if you use the usual coins; you'll have 252 choices to ponder if you allow a half dollar coin as well).  (Similarly, surpisingly, there are 293, and 242, ways, respectively, to make change for a dollar, depending on whether you allow use of half-dollar and dollar coins, or not.)

How can we deduce the number of options? We can use a generating function approach for this; expanding out the product of p[x]=1+x+x²+... times n[x]=1+x⁵+x¹⁰+... times d[x]=1+x¹⁰+x²⁰+... times q[x]=1+x²⁵+x⁵⁰+... , then looking at the coefficient of x⁹⁹ and x¹⁰⁰, and so on. (This approach can thus be made accessible to someone who has had high school algebra I.)

Questions?  Contact Rick Kreminski (kremin@boisdarc.tamu-commerce.edu)