# How many ways to make change for a googol dollars? (infinite generating functions)

0
(0)

From Mathologer.

Okay, as it says in the title of this video, today’s mission is to figure out how many ways there are to make change for one googol, that is 10^100 dollars. The very strange patterns in the answer will surprise, as will the explanation for this phenomenon, promise.

A very nice Mathematica file created by Andrew Neitsch in 2005 covers pretty much every aspect of change making mathematics. http://andrew.neitsch.ca/publications/m496pres1.nb
What I cover in the last part of this video is pretty much fleshing out and animating the section "Coin change revisited". All this is part of to Andrew’s answer to a post on math.stackoverflow https://stackoverflow.com/questions/1106929/how-to-find-all-combinations-of-coins-when-given-some-dollar-value

The visual algebra approach to calculate the number of ways to make change at the very beginning of this video was inspired by this article G. Pólya, On Picture-Writing, Am Math Monthly 63 (1956), 689-697. https://www.jstor.org/stable/2309555

Concrete mathematics by Graham, Knuth and Patashnik, the book I mentioned at the end of the video does the whole analysis for the coin set 1, 5, 10, 25, 50 (so no dollar coins).

A complete list of all the different ways to make change for a dollar appears in this post https://www.maa.org/frank-morgans-math-chat-293-ways-to-make-change-for-a-dollar

The book "Generatingfunctionology" by Herbert Wilf, is a great intro to generating functions 🙂 https://www2.math.upenn.edu/~wilf/DownldGF.html

Ron Graham to who this video is dedicated did a couple of videos with Numberphile. So if you’d like to see him in action, check out those videos. A lot of other interesting articles about Ron Graham can be found on his wife’s (also a math professor) website. http://www.math.ucsd.edu/~fan/ron/

Enjoy!

Burkard