Olympiad level counting (Generating functions)

A lesson on generating functions, and clever uses of complex numbers for counting
An equally valuable form of support is to simply share the videos.

Artwork by Kurt Burns
Music by Vince Rubinetti

Nice writeup and video giving solutions to the exercises at the end, by Benjamin Hackl

102 Combinatorial problems, by Titu Andreescu and Zuming Feng

Generatingfunctionology by Herbert Wilf

Visualizing the Riemann zeta function

Fourier series

Timestamps
0:00 - Puzzle statement and motivation
4:31 - Simpler example
6:51 - The generating function
11:52 - Evaluation tricks
17:24 - Roots of unity
26:31 - Recap and final trick
30:13 - Takeaways

Thanks to these viewers for their contributions to translations
Hebrew: Omer Tuchfeld

------------------

These animations are largely made using a custom python library, manim. See the FAQ comments here:

You can find code for specific videos and projects here:

Music by Vincent Rubinetti.

Download the music on Bandcamp:

Stream the music on Spotify:

------------------

Various social media stuffs:

[soranuareane]

"There's life before you understand generating functions, and then there's life after you understand generating functions." Having taken those courses, I can 100% agree.

[johnnath]

"The shortest path between two truths in the real domain passes through the complex plane" - Jacques Hadamard. Excellent video!

[requemao]

3:54 "To be clear, this lesson is definitely much more about the journey than the destination".

This is the biggest difference between this channel and other channels that show math problems: it doesn't just show you one correct solution to a specific problem, but it teaches you how to think about a new problem. And that is no small feat. Thank you, Grant.

[recreaper]

As a freshman, I understand only a quarter of the things this man says, but somehow, I still find myself learning. This is mystifying to me.

[msachin]

There's teaching math, and then there's this channel. This isn't just math education, its a window into the sublime

[patrickwienhoft]

At exactly 14:31 I realized where you were going. I just love this feeling when it "clicks" and your videos never fail to deliver on that, thank you for this great content!

[jcantonelli]

For me, this is one of the most challenging 3B1B videos to wrap my mind around.

[UniversoNarrado]

Man, that was a wild solution!

Congrats for the presentention, it was astonishing!

Thanks for the video!

[robyrogo]

Fun fact : Titu Andreescu (the author of the book ) was the coach behind the only perfect win of USA in IMO ( all 6 students got perfect scores )

[bbb]

This channel does not simply teach math, it shows math in all of it’s beauty. I would’ve never knew that I like math so much if not for these videos

[numberfootball]

Every time I watch this guys videos I am blown away by how intelligent people can be, how I would never be able to arrive at any of these ideas, and above all the quality of this guy's videos. The production value is through the roof.

[jyxiutv]

Grant, I'm sure you've heard this before, but I want to express how much I appreciate the extra special care you take that even a person with zero mathematical training like myself could follow along a complicated exposition like this. It's invaluable to me (and countless others). I humbly thank you.
Also, lovely illustrations! Add the rhetorical style, and it all comes together in a most gratifying, soulful, and rich experience. Somebody in the comments used the word 'sublime', and that's accurate.

[leninpavon]

I'm an Applied Maths major and sometimes is hard to see why I'm learning about complex numbers, analytic geometry and other things and it's harder to see how they are connected. It's truly beautiful to see how it all comes together, thanks.

[meiliyinhua]

every time grant mimics a student like "why do complex numbers show up in a counting problem?" I remember that I spend more time with group theory than many target viewers, because my immediate thought is "well the roots of unity are a really natural analog for modular arithmetic"

[aidanwestfall]

Having just finished studying some undergraduate level abstract algebra, this video gave me a greater understanding roots of unity and their applications. Your work never fails to both stimulate the creative mathematician in each of us as well as supplement our previous education with new insight. What a gift this channel is, I cannot wait to see what it continues to give in the future. Thank you, Grant, for everything you do.

[michaelhaffer]

When I first encountered this problem (it was in fact the number of subsets of {1 .. 300} whose sum was divisible by 3), I came up with the following solution:

Generalized question: How many subsets of {0 .. 3n-1} are divisible by 3?

I will call this number a(n). I will call b(n) the number of subsets of {0 .. 3n-1} whose sum has rest 1 modulo 3. For symmetry reasons this is exactly half of all subsets which have a sum not divisible by 3.

It follows that a(n)+2*b(n)=2^3n

We now look at a(n)-b(n):

Simple case: n=1. We consider subsets of U={0..2}
Let f(x):=(x+1) mod 3. Then for each subset s let f(s)={f(x)|x€s}. It's easy to see that f³(s)=s for each subset s of U and that exactly one of s, f(s) and f²(s) has a sum divisible by 3 for any s - except s=U and s={}.
So of the 8 subsets of U, four subsets have a sum divisible by 3, two have a sum =1 mod 3 and two have a sum =2 mod 3.
We see that a(1)=4 and b(1)=2, so a(1)-b(1)=2.

We now assume that we know a(n) und b(n) for a specific n.

Let s be a subset of {0 .. 3n-1} and s0 be a subset of {0..2}. Let g(s, s0)=s U {3n+x|x€s0}. The sum of g(s, s0) equals the sum of the sums of s and s0 mod 3.
It's also easy to see that for every subset t of U={0 .. 3n+2} there is exactly one subset s of {0 .. 3n-1} and one subset s0 of {0..2} with t=g(s, s0).

A subset g(s, s0) of U has sum divisible by 3 iff either both sums are divisible by 3 or both sums are not divisible by 3 and have different rests mod 3. This leads to a(n+1)=a(1)*a(n)+2*b(1)*b(n) and

From this follows that a(n)-b(n)=2^n for every n.

Conclusion: b(n)=(2^(3n)-2^n)/3 and a(n)=(2^(3n)-2^n)/3+2^n

It's obviously irrelevant whether we look at the subsets of {0 .. 3n-1} or of {1 .. 3n}


The same reasoning also works for primes other than 3 and leads to

Let a(k, n) be the number of subsets of {1 .. k*n} whose sum is divisible by k. Let b(k, n) be the number of subsets of {1 .. k*n} whose sum has rest 1 mod k.

Then a(k, n) + (k-1)*b(k, n) = 2^(kn) and a(k, n) - b(k, n) = 2n,

so a(k, n) = (2^(kn)-2n)/k + 2n which in this case means there are (2^2000-2^400)/5 + 2^400 subsets of {1 .. 2000} whose sum is divisible by 5.

Seems I am more Bob than Alice.

[bugfacedog]

I love how this channel embraces the math and ACTUALLY TEACHES. So many channels want to make math/physics fun and approachable but end up sacrificing substantiative content to do so. This channel doesn't compromise and I love it. Keep it coming!! <3

(btw generating functions was interesting and all but imo the real spotlight goes to roots of unity - IT'S JUST SO ELEGANT!!! AHHH!!)

[bretthannigan]

People with an electrical engineering background might see the roots of unity just like filtering a discrete-time signal in the z-domain. Super cool to see the parallels with the same math used for something seemingly completely different and explained so well!

[daedrom]

I'm not the kind of viewer that pauses and try to solve the problems by myself because I know I'm getting nowhere, but I watch all your videos and come back to watch them again after a while and it's surprising that, even if don't remember the steps to the solution, it gets less magical and starts to sound more like something that I would have come up by myself.
Thanks!

[XThunderBoltFilms]

When I was doing my undergraduate course in physics, I fell In love with complex analysis. A way to re-think older problems (infinite trig integrals etc.) with seemingly disconnected injections of complex numbers. But the fact that they *arent* at all disconnected is the beauty in it. Its not 'imaginary' but a very real expression of the root of mathematics (ergo, logic). Probably one of the hardest courses I took. And absolutely my favourite. I wish I had more opportunity in my professional life to get back into complex analysis. For now I think I'm going to just dig up my old notebooks.