Counting with Calculus: The Magic of Generating Functions

This is an introduction to generating functions and a combinatorial technique known as the symbolic method. This technique allows us to count a wide range of objects by simply carefully writing down their structure and then using elementary calculus.

If you want more information on this topic, I recommend the book Analytic Combinatorics by Flajolet and Sedgewick and Generatingfunctionology by Herbert S. Wilf, the latter of which can be gotten for free as a PDF on the author's website.

For a lighter resource, I also recommend the following Wikipedia links:

Corrections:

At 3:16, there should be a minus sign between the sums and between the two phis.

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

Music:
Licensed under Creative Commons: By Attribution 3.0 License

Licensed under Creative Commons: By Attribution 3.0 License

Licensed under Creative Commons: By Attribution 3.0 License

[accountname]

When i first learned about combinatorial classes and generating functions, I went from not understanding combinatorics at all to it being one of my favorite disciplines

[johnchessant]

19:02 To prove this formula without generating functions: Arrange n dots in a line, with spaces between them to put separators. Now, any choice of where to put separators yields a different partition of n (since order matters). Since there are n-1 possible spots for the separators, each of which has a binary choice, there must be 2^(n-1) partitions of n.

[andrea.dibiagio]

what a fascinating tool, and great, clear video. Looking forward to applying these to better understand QFT and statistical physics, where partition functions play a starring role

[predrik]

wait this video is 1y old not a few hours old

[francescosorce]

The way you treat combinatorial classes looks a lot like regular expressions/free context grammars and other types of ways to generate sequences using symbols.

Have these topics also been connected to generating functions? If so, are generating functions used in the study of character strings, search engines etc?

[PowerhouseCell]

Great video! I use Manim for my own videos, so I really appreciate how long this must have taken :)

[micklethenickel]

Ok this blew my mind. Please make more!

[omnikar]

There are a couple mistakes at 3:14 that lead to the calculation of an incorrect formula for the Fibonacci sequence:

1. Regarding the second line, after partial fraction decomposition, the denominator of the second fraction should be 1 + (1/φ)z — plus, not a minus. This means that on line 3, the second summation should contain (-1/φ)z rather than (1/φ)z.

2. From the second to the third line the minus between the fractions is mistakenly changed to a plus between the summations.

With these errors fixed, the correct Fibonacci formula comes out to be (φ^n - (-φ)^(-n))/√5.

[predrik]

just by watching the start of the video this helped me realize what a generating function is now

[krumpy]

This is soooo good, thank you very much just wow, keep it up.

[pauselab]

this is a great introduction to generating series. thanks <3

[TheLuckySpades]

In my combinatorics class we got to the Catalan Numbers by a very different method, using logarithmic derivatives, exponentiation and some other tools

This is a pretty neat way to find them, also never saw that particular counting problems that ended with them, we had a lot of others though

[TheDannyAwesome]

Interesting how for each derivation of the Catalan numbers in this video, you arrived at a quadratic equation and took one of the roots. This leads to the question of what is the function corresponding to the other root? If its Laurent series has all natural coefficients, then what set of objects is it the generating function for? If not, then is there some analogue of counting that it corresponds to, and for (an analogue of) what set of objects?

[rubberduck]

the coolest operation is counting sets of objects instead of sequences. My jaw dropped when I found what it does for generating functions.

[f-th]

You said power series are continuous to justify choosing the minus, but the power series 1+z+z^2+z^3+... is not continuous, as it's 1/(1-z).
One way to correctly justify it is by noting that the power series can be evaluated at 0 to give the 0th term, a finite number. In the + case, the limit does not exist at 0, while it does exist in the - case.

[joseville]

Awesome video!

8:43 the atoms of A are different than the atoms of B, so weight of a_n is defined differently than the weight of b_n, right? It's like adding apples and oranges, but in this case it's fine, right?

Erik Satie's music fits so well with this.

It's great to see so much high quality math content!

[TheArtOfBeingANerd]

5:02 this is crazy coming from numberphile's most recent video at the time of commenting: the catalan numbers

[tomkerruish]

The music... is it from the Cube Escape games?

[DinHamburg]

Can you make video about applications of Chinese remainder theorem?

[grezamisoit]

Do not loop a music please. Except for this huge mistake, this a very interesting video, thanks!