> temp > à-trier > explaining-the-bizarre-pattern-in-making-change-for-a-googol-dollars-infinite-generating-functions-mathologer

Explaining the bizarre pattern in making change for a googol dollars (infinite generating functions)

Mathologer - 2021-01-23

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. 

0:00 Intro
1:15 Chapter 1: curious count
9:05 Chapter 2: googol
14:10 Chapter 3: infinite change
28:41 Acknowledgements

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
Here is a pdf version of this file:  https://andrew.neitsch.ca/publications/m496pres1.nb.pdf
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/

As usual the music in the video is from the free YouTube audio library: No. 2 Remembering her by Ester Abrami, Morning Mandolin by Chris Haugen, First time experience and T'is the season by Nate  Blaze

Today's t-shirts: google "only half evil t-shirt".

Enjoy!

Burkard

David Woods - 2021-01-25

As we’re all home-schooling at the moment, the school is sending challenge sheets out to all the kids. The final question on my daughter’s maths one was “how many different ways can you make £3.10 using coins”.

She’s 7 years old...

I just changed the question to “think of a few ways you could” instead, because even I didn’t know how to solve it. But now I do! I don’t think I’ll be teaching this to her yet though.

ANNA CLARA Fenyo - 2021-09-20

@Phil Ramsden In ENGLAND. I am in the US, where it is easy.

Phil Ramsden - 2021-09-20

@ANNA CLARA Fenyo Well, I don't think it's that easy for a seven-year-old even there, to be honest. But England, or at least the UK, is where we're talking about, in any case; clue's in the currency symbol.

ANNA CLARA Fenyo - 2021-09-20

@Phil Ramsden I discussed it ad nauseum in further comments, if you bothered to look past the first. I am sure I could have solved it for American currency at age 7, the introduction of 2c 50c and 1 pound coins makes it impossible.

Phil Ramsden - 2021-09-20

I’ve read your other comments. Pence, btw.

Aaron Fisher - 2022-01-17

That's the kind of question you might not expect a child to get right. But it could send the bright ones exploring in a way that really opens their eyes to maths.

Suqi Chen - 2021-01-23

I studied the infinite generating function for high school math competitions. They are very useful in combinatorics problem!

joao pedro b menezes - 2021-04-08

Same, but not only in combinatorics problems!

The Double Helix - 2021-01-23

I already knew about generating functions, but seeing that automated algebra and the reason for all those 3s and 0s was seriously amazing

Mathologer - 2021-01-23

A "short" video for a change, "only" 30 minutes long :)

Vincent Batens - 2021-01-27

I mean you can say 1 googol and 1 bit that would be kinda stupid, people that work with such big numbers usually use scientifical notation

RS Cepat Waras - 2021-01-29

@David Meijer thank you for your correction 🙏🏼❤️

May Piatt - 2021-01-29

@David Meijer I’ve seen all his vids since like 500 subs lol

Shiladitya Chakraborty - 2021-09-02

Mathologer never shortchanges.

Onur Yiğit Taş - 2022-02-01

Sir can you make a video about extended binomial theorem

Gabriel Mel - 2021-01-28

Extremely cool! Made me realize there’s a very practical strategy for handling these problems that, in my opinion, beats the pure programming AND pure math approach: programming this sort of thing correctly is nontrivial, and even with a smart implementation isn’t that fast (my quick and dirty python version takes about 20 seconds for $2500 - I just remembered I only bothered with 1, 5, 10, and 25 cent coins). The pure math approach to obtain a closed form expression through generating functions is mechanical and straightforward (and beautiful) but incredibly unwieldy for generating functions of this size. Even if you use Mathematica to do the algebra, you still face the problem of convincing yourself you didn’t make a mistake in writing the code! My approach, inspired by your video, is to simply observe that since the generating function is a rational function, its coefficients will be exponentials times polynomials in the index (and I think a bit more reasoning gets you to the fact that if you only extract coefficients with the same residue mod 100, they’ll just be polynomials (as you show for residue 0, of course)). For N coins, this polynomial will be of degree N-1. So pages and pages of computer algebra, in the end, are just to get N rational numbers! A much more direct way is to write a piece of code that is just barely fast enough to deliver N values of the function, and then solve the resulting linear system for the coefficients of the polynomial! No need for super slick iterative implementations, which will top out way before a million of dollars anyway; no need for huge amounts of algebra. Fast, easy, and delivers an essentially O(1) algorithm for a huge number of problems (ie. anything with a rational generating function, so anything produced by a finite state machine)!

mebamme - 2021-01-23

This video makes a lot of cents.

Prometheus - 2021-01-24

Oh my god

GaryChap - 2021-02-05

Mebamme, NO! Go stand in the corner till you learn 'shame' ; ))))))))

Adam Doughty - 2021-02-06

MAKE GOGOOL CENTS

Kasper Joonatan - 2021-03-20

It's like pennies from heaven!

Mega User - 2021-10-07

LOL!

Patrick Kotsch - 2021-01-23

Having coins worth 1, 2, 4, 8, ..., 2^n each exactly once will allow you to represent each number up to 2^(n+1) - 1 exactly once, because it's just the binary represantation of that choosen number. It will work for any number system in general. As long as you've got enough coins to fill up each digits place to its maximum, you will be able to represent each number up to the next digits value minus 1.
For example:
- 2 coins worth 1, 2 coins worth 3 and 2 coins worth 9 can represent each number up to 26 in base 3 exactly once and
- 1 coin worth 1, 2 coins worth 2, 3 coins worth 6 and 4 coins worth 24 can represent each number up to 119 in base factorial exactly once.

Democritus T - 2021-01-24

@Locke Demosthenes Mathologer states the challenge as having exactly one of each coin, as does Patrick in his answer. It is a given that there is exactly one of each type of coin, for precisely the reason you are stating - otherwise you can end up with duplicates.

Riley Wells - 2021-01-24

This is great. Phrased in another way, choose your favourite natural number n >= 2, and choose n-1 1 cent coins, n-1 n cent coins, n-1 n^2 cent coins up to n-1 n^k cent coins (for you second favourite natural number k), and you will always be able to make unique change anywhere up to n^(k+1) - 1 cents.

American Patriot - 2021-01-24

This is one of the very few mathologer challenges where I immediately knew the answer

Adityarup Laha - 2021-01-24

@American Patriot same. It was such a nice feeling. Finally CS classes paid off.

Big Ball - 2021-02-01

(n-1)*x^n-1


geometrical progression sum =

(q^n - 1)/(q-1)

but the formula is ((q^n) - 1) so we multiply sum of g.p. to q-1,

as example with 2 coins worth 1, 2 worth 3, 2 worth 9.

1,3,9 is 3^0, 3^1, 3^2

sum=(3^3 - 1)/(3-1)

multiply on (3-1)=2

that is why we have 2 coins of each nominal

Will To Win - 2021-01-23

I've been a fan ever since your humble beginning, and I'm more excited than ever for new Mathologer vids!

Mathologer - 2021-01-23

Actually I always wondered whether YouTube would ever consider making a list of subscribers in chronological order available in a reasonable way. Still waiting :(

Ye Tian - 2021-01-23

Actually, YouTube should have sent you an email each time someone subscribed. If you rank your 647K subscription emails, you will know who subscribed before whom.

Tiessie - 2021-01-24

@Ye Tian any reasonable person will have turned that off :)

Mathologer - 2021-01-24

@Ye Tian They only send you an e-mail if you tick a certain box and if you've got lots of subscribers you most definitely don't want to tick that box :)

Brendon Green - 2021-01-27

@Mathologer that sounds more like an argument for filtering your emails through Python

Subhasish Mukherjee - 2021-01-23

The power of 2 coins can make any amount in exactly one way! (binary representations :))

Tom LaMarre - 2021-01-23

It's cool to see "unique representation in base 2 exists" formulated differently. Works for other bases too, except for example in base 3 you say "I can have 0, 1, or 2 coins worth 1 each, 3 each, 9 each, ..." So the polynomial you have for, say 3 digits in base 3 would be (1 + x + x^2)(1 + x^3 + x^6)(1 + x^9 + x^18) and as expected that is equal to the sum of all x^j for j from 0 to 26 (because 26 = 3^3 - 1) so base 3 numbers can represent natural numbers uniquely too.

Jonas Daverio - 2021-01-23

Well, it's easy to prove by induction, if we want a different way. We have our n factors of the form (1+x^(2^k)), let's prove that the product of those is indeed the sum of x^j with j form 0 to 2^n-1.
First (1+x)(1+x^2) is indeed (1+x+x^2+x^3).
Then, the induction gives us that the n first factors give us (1+x+...+x^(2^n-1)). Let's multiply it with the next factor (1+x^(2^n)). By distributing, we have the sum of (1+x+...+x^(2^n-1)+(x^(2^n)+(x^(2^n+1)+...+x^(2^n-1+2^n)).
That last exponent is equal to 2*2^n - 1, which is equal to 2^(n+1)-1). Induction done.
It's pretty easy to visualise this proof, but a bit hard to do in a comment, so I'll let you the exercice to do it.

Mason Hunter - 2021-01-24

5 is 1 and 4 and 1 and 2 and 2 as well

Jonas Daverio - 2021-01-24

@Mason Hunter you have only one of each coin allowed

Marlin Maughan - 2021-07-15

Also, you can generalize it for any base n counting system by using coins worth the powers of n, where you can use up to n-1 of each coin type. The powers of n corresponds to the different number places, ie. 10s place, 100s place, 1000s place. The n-1 coins per type is corrected by 0 coins of a type being an option, making it n possibilities, corresponding to the n digits of a base n system (base 2 -> 0,1 base 10 -> 0,1,2,3,4,5,6,7,8,9, base 12 -> 0,1...8,9,χ,ε). :)

David Rosa - 2021-01-26

23:56 I guess that the formula doesn't work because the binomial coefficient "isn't defined" if the number on the top is smaller than the one on the bottom. I think that, if we define the choose function to be 0 in those cases, it works just fine. When you replaced them by algebraic expresions, you indeed set them to be 0 in those cases, so the last formula works in general.

Mathologer - 2021-01-27

That's it :)

Mega User - 2021-10-07

Yep!

Brent DeJong - 2021-01-28

The formula shown at 24:00 works for any dollar amount if you let n choose m = 0 for n<m, which is a natural definition. It only falls apart when you expand the formula.

Mathologer - 2021-01-29

That's it :)

Jordan - 2021-01-25

There's something beautifully simple about this, once you get to the end it just feels completely obvious that it works. Love all your content, definitely helps me to see things in different perspectives and to engage with problems better! Now and then I get into little mathematical rabbit holes of my own and end up taking between a couple weeks and months to intermittently chip away at them til I get somewhere satisfactory, I actually just got started right now on a new such thing and probably am gonna have to break into programming cause the spreadsheets won't cut it. Thanks for the inspiration <3

VibratorDefibrilator - 2021-01-24

Aww, this is sweet!... I knew it, that this clever way of dealing with the coin change problem must have been done already!

I've played with this coin change problem recently, deliberetely not knowing about backtracking approach or dynamic programming - I just wanted to see what can I discover on my own (later on, I found that I did not do anything radically new, but I was pleased anyway). I'd loved, of course, to find some formula for it, but theoretical approach was not my goal back then, I just wanted to make my computer to calculate the damn thing.

I was not particularly interested in calculating the minimum number of coins (of certain denominations) that add up to a given amount of money, but only in the number of ways such amount of money can be presented. I was also not very keen in writing computer program to do the job, just to make a table, filled with formulae that are calculating everything. The reason for all this is that for many years dealing with various problems I developed for myself a lazy approach to programming - part of the work (a huge chunk of it, if possible) can be done in table forms, another part - with much simpler program, if writing such a program is inevitable, otherwise custom functions are good enough in many cases (I mean, in Excel spreadsheets). So, practising such "programming" style helped me to learn how to compartmentalise any heuristic problem in smaller, more "edible" problems.

Firstly, I made a counter that gives me the answer, just for verifying the results (for relatively small amount of money, of course; for bigger ones it has to count for hours). Easy-peasy.

The analysis of the problem resulted in following table:

1. The number of columns = the number of 'n' distinct positive integer values (whole numbers), arranged in increasing order as c(1) through c(n); oddly, the results do appear in the leftmost column, associated with the smaller coin in the set, c(1).
The set of coins may be whichever one wants {1; 2; 5; 10; 20; 50; 100;...}, {1; 2; 5; 10; 25; 50; 100;...}, or some exotic: {3; 7; 12; 19}, {1; 2; 3; 5; 7; 11; 13; 17; 19;...}. One even can play dumb and use a set as {6; 9; 18; 30}, but the table will give back zeroes for all odd and not divisible by 3 sums anyway.

2. The number of rows is not limited above, with increment of 1 cent per row. Naturally, you should have 100 rows if you want to calculate the function for 1 dollar, or 250 rows if the target is 2 dollars and 50 cents.


3. In every cell [x, y] there is a formula that does one simple thing (for the leftmost column is slightly different) - it calculates the ways 'x' dollars can be presented by coins with nominal value >= c(y): cell[x, y] = sum( cell[x - c(y), j] ) for j = y to n / for 1st column: cell[x, 1] = cell[x-1, 1] + sum( cell[x, j] ) for j = 2 to n.

This is all, now every row will give you the corresponding number, for example, in the sequence A000008 (it is only for set [1, 2, 5, 10], doesn't include coins of 20, 50, 100 cents). If we use all coins and banknotes up to 20$ , {1; 2; 5; 10; 20; 50; 100; 200; 500; 1000; 2000}, the sum $20,21 will be presented in 30,399,653,516 ways. Clearly my counter will outlive me here ;-).

Now on, the hypothetical program is easy to be written and if one looks closer a little bit on the method, will see that this program will have to memorise maximum n*c(n) numbers to do its job (or even less, if you are greedy), for arbitrary large amount of money.

I was delighted that this problem has such simple practical solution, but thankfully, here I learned about the heavy, theoretical stuff, and they are also so elegant. The practical approach has some similarity with Pascal's triangle, so, no wonder that binomial coefficients do appear here and there.

Wompa Stompa - 2021-01-23

For anyone working on the problem at about 16:20 with derivatives, do yourself a favor and use (1-x)^(-1) instead of the fraction. Power rule & Chain rule is sooooo much easier than Quotient rule when it comes to taking more and more derivatives in this case.

Dramwertz - 2021-02-03

ye i agree totally. i just seem to be stuck on the left side somehow. not sure where my error of thought is

Joshua Cohen - 2021-02-10

@Dramwertz Induction is a better way to do it if you know induction.

Yusuf Onur - 2021-01-24

13:27 I would guess there is a O(N^2 * M) dynamic programming approach for that (N = the amount we want to partition, M = the number of distinct coins). I will assume we have a sufficient amount of every coin type. Let's define count(i, j) as being the number of ways to partition i dollars with the first j coins (coin values are sorted in ascending order). Then count(0, j) = 1 for all j and count(i, 0) = 0 for all i. The recursion comes out to be count(i, j) = count(i, j-1) + count(i - c[j], j-1) + count(i - 2*c[j], j-1) + ... The answer will then be stored in count(N, M). If you do some clever stuff with the memoization, the time complexity can also be reduced to O(N * M), I think.

Inciaradible - 2021-01-30

This is a really cool video and reminded me of when I first came across generating functions when figuring out the probability in regard to the sums of the outcome of dice, and this actually deepened my understanding of them a bit as they always felt a bit like magic to me.

Victor Paes Plinio - 2021-01-27

I like the idea of coins with powers of 2.

Having coins of 1, 2, 4 and 8 allows us to make charge for all values up to 15.

It is basically binary numbers.

If each coin is a bit and you have 4 of those bits (1, 2, 4 and 8) you can make charge for 0 to 15, exactly 2^4=16 different amounts.

Alexander Roderick - 2021-01-23

"We started with an infinite sum so let's count our blessings"

Well it does seem like there are countably many...

KC Sutherland - 2021-02-09

This feels like all those math lectures that really made me realize how amazing Mathematics is. Thoroughly enjoyed this, and such a cool result!!

Dave Langers - 2021-01-24

23:56 It doesn't work for k<=3 because then for some nCk we get n<k, for which n choose k is not defined. However, thinking of Pascal's triangle, we can set those equal to zero (or omit these terms) and that should work.

Mathologer - 2021-01-24

Exactly :)

richard schreier - 2021-01-25

@Mathologer You had me pondering this for a while. Since I already understood that nCk = 0 when n<k, I couldn't see what was wrong and resorted to sifting through the comments. This is undoubtedly good for my humility, but since there is nothing really wrong, the answer did feel a tad disappointing. Don't get me wrong, though-- the video and the explanations were all top-notch. I am always impressed with your clear and enthusiastic explanations, and am grateful that you so tirelessly share your mathematical expertise with those less well-versed in the wonders of mathematical thought.

Dave Langers - 2021-01-29

@richard schreier It depends how you define the nCk function and how you choose its domain, I guess?
It is quite natural to define it as n!/(k!(n-k)!) and restrict it to integers n ≥ k ≥ 0; but if it is extended beyond that, then these other integer cases normally equal 0 indeed.

Ardin Chesters - 2021-01-24

great video!! I'm really grateful that as a high school student wanting to become a mathematician I have access to such inspiring channels as mathologer and 3b1b, giving beautiful yet still accessible mathematics to sink your teeth in to!

Fiaca - 2021-01-24

This was a particularly fun one. I feel like I was able to follow pretty much every part of the proof. Enough hand-holding for casual viewers but no tricky stuff shoved to the background.
Even the algebra autopilot is fun to watch, as its pace and animation make it easy to understand and apreciate the cleverness involved. Many channels like to focus more on geometric proofs only (which are also nice) but algebra has some charm too.

Xubono - 2021-01-23

Some of us will recognise Donald Knuth as the creator of the typesetting language TeX. For that alone, he has been responsible for the professional quality appearance of thousands of PhD theses.

Cole Abrahams - 2021-01-25

Don’t you mean LaTeX? By yeah, it is the best!!!

Xubono - 2021-01-25

@Cole Abrahams LaTeX is built on top to TeX. It is basically a set of macros, written in the TeX language.

Stevie Budden - 2021-01-31

Yup, amazing man. I notice that you, quite rightly, specify that he's responsible for the professional quality appearance - rather than professional quality content. That's an important distinction. But yes, they do look nice.

Xubono - 2021-01-31

@Stevie Budden Oh yes, that is certainly true. I first used TeX some 38-39 years ago, back when laser printers were quite expensive and 240dpi was a luxury. TeX (and later the easier to use LaTeX) became popular when people realised that their documents could be realised at better resolutions (on newer printers) with no changes to the author’s .tex document.
LaTeX added many things, like generating table of contents, indexes etc (though a 2nd or 3rd pass was necessary to resolve forward references.
I am sure the young Dr Polster used the software when he was here at The University of Adelaide (when he wasn’t juggling or on his unicycle).

mailtorajrao - 2021-02-12

Yes, me too. I wrote my (not PhD!) B.Tech project in LaTex.. It is super for equations

Armin Vollmer - 2021-01-26

Once again, great work, Mathologer! However, I see a tiny error there in the distribution of terms at 4:22 You would expect the empty set in the "first column" in the cross product, but you made the leading empty terms disappear (except for the very first partial product).
In Mathematica, by the way, it would look like this: with Distribute[{{}, {1}, {1, 1}, {1, 1, 1}}, {{}, {3}, {3, 3}}, List, List] you get {{},{}},{3}},{{},{3, 3}},{{1},{}},{{1},{3}},{{1},{3,3}},{{1,1},{}},{{1,1},{3}},{{1,1},{3,3}},{{1,1,1},{}},{{1,1,1},{3}},{{1,1,1},{3,3}}}

Anyway: a very exciting topic! As a chemist, I see great applications there: e.g. if you ask for the possible elementary compositions for a given (exact) molar mass, you can get all conceivable "sum formulas" this way (and with a few chemoinformatics tricks even the valid molecular formulas).
Looking forward to future videos! Here are a few "wish titles": Polya-enumerations of isomers, automorphism groups of graphs or even solving functional equations.

Killian Defaoite - 2021-01-25

I thoroughly enjoyed this video, but it definitely reminded me why I've done my best to avoid serious combinatorics :)

Jazza BigHits - 2021-01-25

Great video as always, even after chapter 1 I was amazed. Thanks for this :)

Akash Kumar - 2021-01-29

Loved your dedication, Professor Polster.

A side story: I interviewed with Ron Graham years ago for a PhD position at UCSD. While I did not get the offer, my conversation with him is one of my treasured memories.

Least Significant Bit - 2021-01-23

23:58 Choose function is undefined for negative values, but we can easily generalise known formula using generalisation of factorial - gamma function. Then everything works out nicely

Mathologer - 2021-01-23

Something like this. Actually the only thing you have to do is to extend the definition of binomial coefficients: anything with a top less than the bottom is set to 0 :)

David Terr - 2021-03-04

Wow, you never stop blowing me away with your videos! I'd offer you a googol dollars for letting me watch it, but I'm afraid I don't have the exact change!

Maxim Golubev - 2021-01-23

Thank you, for your videos. "fresh" ideas and content and ton of work behind them.

David Barnett - 2021-01-23

This is simply a brilliant explanation. Your videos are getting better and better. I am astounded at the ideas and creativity you have in the topics you cover. Thanks!

David s - 2021-01-23

I love this, Ive always played with numbers and somehow when i was a kid i figured this stuff out. Watching this reminded me of some amazing numbers. My favorite being x/7. A good idea for a video would be to explain why you will never see the digits 3, 6, or 9 in the decimal places when you do x/7. That would be so interesting to see. I Hope youre having a nice day :)

Max Sch. - 2021-01-24

Everyday you upload feels like christmas. I was always fascinated by generating functions. Thanks for the great content as always! Greetings from Germany :)

Konstantin Kalashnikov - 2021-01-24

Hey Burkard, thank you for your amazing videos, now that's my fav Friday night entertainment! Just out of curiosity, what kind of software do you use to make such a beautiful animation (and how much time does it take to prepare a video like this one?) Thanks!

Marco Gallone - 2021-01-28

This is absolutely mind blowing. Please never stop producing content like this! I absolutely love the channel.

MintsJams - 2021-01-23

9:45 just from eyeballing the question, I can pretty clearly see that the answer is that you can make 15 different amounts (16 if you include 0) and they're all made in a unique way. What's more, if you have n coins, you can make every value in a unique way up to
2^n - 1 (Again, 2^n if you include 0). You can do this just like if you were counting in binary, which uses the powers of 2 to uniquely construct every whole number. Pretty cool if I do say so myself!

Mathologer - 2021-01-23

That's exactly it :) Try doing it with the product anyway, very satisfying...

Rafael Moreira - 2021-01-23

9:33- I don’t know if it is correct but I think we can make all the integers between 1 and 15 (including 1 and 15) only once. I didn’t use the product it’s just the same idea of binary notation.
If you have infinitely many coins with all the powers of two it is the same idea: all the integers only once.

Robin Ros - 2021-01-23

Watching this made me wonder whether you could calculate these specific coefficients by integrating your generating functions over a small closed loop around 0 in the complex plane and using the residue theorem. So the amount of ways to make n cents, using coins of amounts 1, 5, 10, 25, 50 and 100, would be 1/(2i pi) times the integral of 1/(x^(n+1)(1-x)(1-x^5)(1-x^10)(1-x^25)(1-x^50)(1-x^100)) dx over a complex circle around 0 with sufficiently small radius (I think <1 might be small enough). Am I missing something here? If not, then that is amazing: being able to calculate a discrete amount of ways by evaluating a complex integral and dividing by an irrational, imaginary constant :O

Mathologer - 2021-01-23

Yep, something like that would work just like any other way that gives you the coefficients of the Maclaurin series of 1/(x^(n+1)(1-x)(1-x^5)(1-x^10)(1-x^25)(1-x^50)(1-x^100)

Argo Lake - 2021-01-24

The first time I encountered generating functions was when I was having fun filling up paper charting how many vertices, edges, faces, etc. there are in a line segment, square, cube, 4-cube, etc. and finding the patterns. I showed this to a math teacher, and he was like, “or you could find the coefficients of (2 + x)^n.” (Where n is the dimension of the cube, and the power of x is the dimension of the face.) I was blown away and mystified and had no idea how it worked.
To find the k-faces of an n-cube, you doubled the k-faces of the (n-1)-cube and added the (k-1)-faces of the (n-1) cube. Which shows that (2+x)*f_(n-1)(x)=f_n(x). And f_1(x)=2+x, because you start with a line segment, with 2 vertices and 1 edge. So you have proof by induction. You could even start with f_0=1, and start with a single point (Pointland).
But the proof by induction isn’t that satisfying, and doesn’t quite bring a greater understanding. I’ll look into it tomorrow morning.

Ethan Jensen - 2021-01-24

:) I love this video! I have just been learning about q series! It's so strange how your videos are always surprisingly relevant

Gerard Farmar - 2021-01-24

Mathologer, wonderful video! You are a legend and you explain things so beautifully.

Easy Mathematics - 2021-02-17

Great video. Thanks for that.

The powers of two would be the most effective way of changing money in daily life.

But the numbers are not so "familiar".

But if we take

1, 2, 5 (pseudo doubling of 2) and 10 (double of 5) we have a almost the most effective way.

Yin Q - 2021-01-24

8:56 293 - 1 = 292
9:12 1 through 15 and all unique because that's how binary works. Using the polynomial product, (1+x)(1+x^2)(1+x^4)(1+x^8) = (1+x^16)/(1-x) = 1+x+x^2+...+x^15.
24:00 because we don't need all the 5 highlighted terms from the 405-degree polynomial to make the product x^(k * 100). And to make the formula work, the answer is at 24:12 right?

Mathologer - 2021-01-24

All good :)

David Rosa - 2021-01-25

9:08 With one of each of the first n powers of 2 coins, you can make any amount up to 2^(n+1)-1 exactly one way. This is like the base 2 representation of natural numbers in (I believe it's called) positional systems, which we use with arabic numerals. There's a general theorem for this, so, for example, you can make any amount up to 3^(n+1)-1 with TWO of each of the first n powers of 3 coins (1, 3, 9, 27, etc...) exactly one way; the obvious example is NINE of each of the first n powers of 10 coins (1, 10, 100, 1000, etc...). ^.^

globulin - 2021-01-24

There's only one way to make change for any particular value given a single coin for each power of two. It corresponds to 1 coin for each 1 in the binary representation of the number.
Also, I lost my keys in July and found them in January, in the change pocket of my wallet where I had put them for safe keeping. I had not used coins for six months because of covid.

mathwithjanine - 2021-02-03

This is so fascinating! Really enjoyed watching this video :)

Mostly Mental - 2021-01-23

Thanks for putting out such great content. This is way better than my video on generating functions. Do you have any tips for someone with a new math channel looking to improve?

Rafael Moreira - 2021-01-23

8:58- I think it is 292 (one less the result you gave us due to the fact we exclude the possibility of using the 100 cent coin).

Alvarez Julio - 2021-02-06

Amazing video: I really enjoy it. Thank you Mr. Mathologer.

Boring Extrovert - 2021-01-23

9:40 I think you can make all the numbers up to 2^(n+1) - 1, where n is the largest power of n you have. Furthermore, you will get each number only once. It's easier to think of this in binary.
Finally, this works for any sequence of increasing powers
Edited for the typo

Mathologer - 2021-01-23

Yes, but you should probably think about this again "Finally, this works for any sequence of increasing powers" :)

Boring Extrovert - 2021-01-23

@Mathologer ah you should have base - 1 of each coin 😅