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
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.
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
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.
Also I just realized that that comment is one year old and when it was commented the video was one year old, the video is now 3 years old, we have found some rounding weirdness
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?
Yes I believe given a context-free grammar there is an algorithm that gives the generating function for the number of words of length n. (Although it may give them implicitly as the root of an algebraic equation.) I've heard that the software Maple can do this, but I don't have access to it so I haven't tried. From what I remember, there are combinatorics problems that get solved by constructing a context-free grammar that's in bijection with the objects in a class and then just using the software. I'm not sure about character strings/search engines, but you can use the generating function to get asymptotics on the coefficients which I'm sure could be useful in some way for that.
Also check out Algebraic Type Theory if you're not familiar. The way you write the type of a data structure corresponds to the polynomial equations in generators that you see here.
If you are interested in the connection with type theory mentioned by Nicholas Ham, I highly recommend this nice little exposition of the idea applied to this simple problem: Can you find a *natural* bijection between the class of binary trees and the class of 7-tuples of binary trees? The paper is Seven Trees in One.
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
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?
The 2 functions share a finite number of terms (at least in these examples), while the other terms pick up a - sign. The result is that the leading terms are mucked up (the infinite part overlaps the shared finite part), while all the remaining terms pick up a - sign. I'm not entirely sure how to interpret negative #s in counting.
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!
Thank you! If you think of A as being "apples" and B as being "oranges", then A+B would be "fruit". (Assuming the only fruit in existence are apples and oranges.)
@@ASackVideoGotcha. From your N+N example it's also fine if the atoms of the two classes being added are the same, but in this case wouldn't N+N = N since atoms are the same? Or do you still consider them to be different atoms or maybe the same atoms, but colored differently?
At 2:39 , where you got F(z) = -z/(z²+z-1), what if we input z = 1...? Since F(z) = 0z⁰ + 1z¹ + 1z² + 2z³...., F(1) should be equal to the sum of first n ( as n-->inf) fibonacci numbers, And if we compute F(1) from the formula you deduced, we get -1/(1²+1-1), which equals -1, But how is this possible, F(1) by definition should be the summation of the fibonacci series, how can it be negative 1...? Ik this video was posted 3 years ago and i have no hopes of getting a reply, but by chance if anybody sees this, plz reply so that i can be reminded of this video sometime in the future, I am still a student so maybe by then i would have gotten the mathematical maturity to be able to solve this by myself... Also, if i made a mistake plz feel free to correct me in the comments..!!
This is a good question! The radius of convergence of this series is 1/phi which is about .618. So when plugging in a value outside of the radius of convergence (such as 1), we shouldn't expect the power series to be equal to the function in question! In a similar vein, we know that the geometric series 1+r+r^2 + r^3 + ... = 1/(1-r). But we only know this when |r| < 1! If we try plugging in a value outside of this, such as for r = 2, it would look like saying 1+2+4+8 + ... = -1. I did unfortunately make a mistake a little later in the video at 3:16, where there should be a minus sign between the sums and between the two phis.
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.
@@ASackVideo Thanks for the reply! I just googled the answer. According to the fandom wiki: From Cube Escape: Seasons to Cube Escape: The Mill, Rusty Lake [the game publisher] used royalty-free music by composer and music producer Kevin MacLeod.
Why don't we define the fibonacci sequence to (sum of all numbers before the current number) +1? The spontanious 1 after 0 makes no sence. That requres a 1 before the 0, a -1 before that 1, a 2 before that -1 and so on. If it is a spontanious start with 0 as the first number then the normal deffinition makes no sence to me.
I actually like hearing everything, since it means even if something causes me to look somewhere else, I can still understand what's going on, I totally get why that isn't everyone's cup of tea... err, preferred beverage?
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
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.
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
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.
Good catch!
Very helpfull thx :))
I was wondering what was wrong with the formula, because if you try finding the 0th Fibonacci number with it, you get 2/sqrt(5)
Uuhuuuuyuuu😮😮a sua 😢no 😢do 😮😮😢a t😮😮
just by watching the start of the video this helped me realize what a generating function is now
wait no it's exactly not what i expected
Ok this blew my mind. Please make more!
wait this video is 1y old not a few hours old
3y now, and the same thought crosses my mind. This feels like a SOME video (in the best way possible)
Heh? Ah, yeah, that happens when you go through enough of these
Also I just realized that that comment is one year old and when it was commented the video was one year old, the video is now 3 years old, we have found some rounding weirdness
@@Nzargnalphabet indeed
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?
Yes I believe given a context-free grammar there is an algorithm that gives the generating function for the number of words of length n. (Although it may give them implicitly as the root of an algebraic equation.) I've heard that the software Maple can do this, but I don't have access to it so I haven't tried.
From what I remember, there are combinatorics problems that get solved by constructing a context-free grammar that's in bijection with the objects in a class and then just using the software.
I'm not sure about character strings/search engines, but you can use the generating function to get asymptotics on the coefficients which I'm sure could be useful in some way for that.
Also check out Algebraic Type Theory if you're not familiar.
The way you write the type of a data structure corresponds to the polynomial equations in generators that you see here.
If you are interested in the connection with type theory mentioned by Nicholas Ham, I highly recommend this nice little exposition of the idea applied to this simple problem: Can you find a *natural* bijection between the class of binary trees and the class of 7-tuples of binary trees?
The paper is Seven Trees in One.
Great video! I use Manim for my own videos, so I really appreciate how long this must have taken :)
This is soooo good, thank you very much just wow, keep it up.
Thank you! I've actually been making math tiktoks lately but I may upload some of that here as well.
this is a great introduction to generating series. thanks
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
the coolest operation is counting sets of objects instead of sequences. My jaw dropped when I found what it does for generating functions.
What a fascinating topic
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?
The two series are the same except for the first couple terms.
The 2 functions share a finite number of terms (at least in these examples), while the other terms pick up a - sign. The result is that the leading terms are mucked up (the infinite part overlaps the shared finite part), while all the remaining terms pick up a - sign. I'm not entirely sure how to interpret negative #s in counting.
Brilliantly explained
Brilliant! Blew me away, too!
5:02 this is crazy coming from numberphile's most recent video at the time of commenting: the catalan numbers
Do not loop a music please. Except for this huge mistake, this a very interesting video, thanks!
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!
Thank you! If you think of A as being "apples" and B as being "oranges", then A+B would be "fruit". (Assuming the only fruit in existence are apples and oranges.)
@@ASackVideoGotcha. From your N+N example it's also fine if the atoms of the two classes being added are the same, but in this case wouldn't N+N = N since atoms are the same? Or do you still consider them to be different atoms or maybe the same atoms, but colored differently?
@@joseville The reason we color them differently is so that the two things we add never have any overlap. This keeps the algebra very nice.
I like your magic words Keep going!
thanks sir
At 2:39 , where you got F(z) = -z/(z²+z-1), what if we input z = 1...?
Since F(z) = 0z⁰ + 1z¹ + 1z² + 2z³...., F(1) should be equal to the sum of first n ( as n-->inf) fibonacci numbers,
And if we compute F(1) from the formula you deduced, we get -1/(1²+1-1), which equals -1,
But how is this possible, F(1) by definition should be the summation of the fibonacci series, how can it be negative 1...?
Ik this video was posted 3 years ago and i have no hopes of getting a reply, but by chance if anybody sees this, plz reply so that i can be reminded of this video sometime in the future, I am still a student so maybe by then i would have gotten the mathematical maturity to be able to solve this by myself...
Also, if i made a mistake plz feel free to correct me in the comments..!!
This is a good question! The radius of convergence of this series is 1/phi which is about .618. So when plugging in a value outside of the radius of convergence (such as 1), we shouldn't expect the power series to be equal to the function in question!
In a similar vein, we know that the geometric series 1+r+r^2 + r^3 + ... = 1/(1-r). But we only know this when |r| < 1! If we try plugging in a value outside of this, such as for r = 2, it would look like saying 1+2+4+8 + ... = -1.
I did unfortunately make a mistake a little later in the video at 3:16, where there should be a minus sign between the sums and between the two phis.
Just awesome!!❤
Great video!
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.
They're continuous at 0. Sorry for the confusion!
Very beautiful!
love this
Can you make video about applications of Chinese remainder theorem?
The music... is it from the Cube Escape games?
They're the Gymnopedies by Satie performed by Kevin MacLeod.
@@ASackVideo Thanks for the reply!
I just googled the answer. According to the fandom wiki:
From Cube Escape: Seasons to Cube Escape: The Mill, Rusty Lake [the game publisher] used royalty-free music by composer and music producer Kevin MacLeod.
Isn't it easier to include the empty tree in T and write T = 1 + zT²
If you find the empty tree conceptually easier, then yes!
Why don't we define the fibonacci sequence to (sum of all numbers before the current number) +1? The spontanious 1 after 0 makes no sence. That requres a 1 before the 0, a -1 before that 1, a 2 before that -1 and so on. If it is a spontanious start with 0 as the first number then the normal deffinition makes no sence to me.
The negative integers for the Fibonacci series are actually reasonable, I think Matt Parker has a video on that
If only this video came out in 2020 when I took combinatorics lol
category theory?
Very closely related! The category theory framing of this is typically called "combinatorial species"
it's not counting with calculus if you think of the power series as an formal power series...
Solving for the function and taking a derivative is definitely calculus!
모든게 무한하다면 무한히 겹치는 것도 무한하지 않을까요?
This can be just the beginning... The applications of generating functions is a wide field
Nice video. Let me just say that it is my feeling that you do not need to read every bit of a formula out loud. I find this too verbally verbose.
I agree! I think I have improved a bit in making videos since this one, but I still have a lot of room to improve.
I actually like hearing everything, since it means even if something causes me to look somewhere else, I can still understand what's going on, I totally get why that isn't everyone's cup of tea... err, preferred beverage?
Holy C++!
Oh God, I'm lost 🤦
You thoughts this was a video about combinatorics and generating function ?
WRONG
Catalan number propaganda baby
bud your formula’s wrong
dude wtf are you even talking about
no it's not. i hate how people don't understand anything. like get out of the math community