Thank you for several things. First : I'm not an English speaker. You speak a little quickly but your pronunciation is perfect and I understand everything. Second : I knew the formula, but I had no idea how it was discovered. Third : The logical flow of your presentation is really excellent. You deserve the same audience for number theory as blackpenredpen's for calculus. I wish it for you !
I like your explanations from a perspective of understanding why the claims are correct, however, I suggest you to explain (especially on the putnam and math around the world vids) how someone would approach the problem WITHOUT having key "building block" before hand, like in a real competition. Keep it going!
Thank you, very good video! Ireally enjoed the collaboration and the combination of more intuitive combinatorial thinking in 1st part and analysis in 2nd part.
I always pause these videos whenever the next step is not obvious to me. What's going to happen next? Is he going to re-index the sum, do some algebra or a use a theorem/lemma/tool? Then I mull things over for a bit before un-pausing. This is really good exercise!
Easy recursive way to get the Catalan numbers: Begin (1, 1,) dot (1, 1) = 2. Place the 2 on the right of (1, 1,) getting (1, 1, 2). Reverse and take the dot product of (1, 1, 2) and (2, 1, 1), getting (2 + 1 + 2) = 5. Then place the 5 to the right of 1, 1, 2, 5 and take the dot product of the reverse,(5, 2, 1, 1) getting (5 + 2 + 2 + 5) = 14. Put 14 to the right of the ongoing string getting (1, 1, 2, 5, 14) and take the dot product of the reverse, so dot product of (1, 1, 2, 5, 14) and (14, 5, 2, 1, 1) = (14 + 5 + 4 + 5 + 14) = 42., etc
Yeah, but it's not efficient, its O(n^2) operations. I've derived Catalan number formula by constructing a modified Pascal triangle from incomplete Catalan numbers and induction. Let's call an incomplete Catalan number as I(m, n). Incomplete Catalan number is the number of unique lattice paths where the starting point is (0,0), the destination point is (m,n) and the lattice path is under the diagonal. Obviously, the full Catalan number C(n) equals to I(n.n). Now there is a recursive relationship between the Incomplete Catalan numbers is the following: I(m, n) = I(m - 1, n) + I(m - 1, n - 1) + I(m - 1, n - 2) + ... + I(m - 1, 0) the graphical representation when m >= n is this: 1 1 1 1 1 1 1 1 ... 0 1 2 3 4 5 6 7 ... 0 2 5 9 14 20 27 ... 0 5 14 28 48 75 ... 0 14 42 90 165..... 0 42 ............. ......... I've noticed that I(m, n) = I(m - 1, n) + I(m, n - 1), which is similar to pascal triangle relationship. You can fill symmetrically the part bellow the diagonal with the negative values while still preserving this relationship: 0 1 1 1 1 1 1 1 1 ... -1 0 1 2 3 4 5 6 7 ... -1 -1 0 2 5 9 14 20 27 ... -1 -2 -2 0 5 14 28 48 75 ... -1 -3 -5 -5 0 14 42 90 165..... -1 -4 -9 -14 -14 0 42 ............. .......................................................... so I need to find a formula that satisfies these conditions: A(m,0) = 1 A(m,n) = - A(n,m) A(m,n) = A(m, n) =A(m - 1, n) + A(m, n - 1) and it turns out to be (m - n) * (n + m - 1) ! / (m! * n!) it can be easily checked in those 3 conditions, the exception was a(0, 0), but fortunately we can ignore this since n-th Catalan number is I(n, n) then I(n, n) = A(n + 1, n) = (n + 1 - n) * (n + 1 + n - 1) / ((n + 1)! * n!) = (2n) ! / (n! * n!) / (n + 1)
Hey you’re substituting values of x in the formal power series , I think that is not allowed and you have to expand for sqrt(1-4x) here and then check whether it matches to def of your catalans sequence and also when you get the closed form expression then you can say where the power series converge and here for |x| < 1
I always wonder what does n choose r physically mean when n is fraction or negative. As the general notion, choose r objects from n doesn't fit here. Pls. Explain this!!
naman jain Taking factorials of fractions is just generalising properties that we see work for integers and extending them. The same is true for taking arbitrary powers of numbers, what exactly does it mean to raise a number to the power of π? More formally you’d use gamma functions in place of factorials as factorials are a discrete function
The "proper" definition of x choose r is: x(x-1)(x-2)...(x-r+1)/r! which doesn't require the Gamma function as long as r is a nonnegative integer and x is any complex number -- actually x can be from any unital associative algebra.
Thank you for several things.
First : I'm not an English speaker. You speak a little quickly but your pronunciation is perfect and I understand everything.
Second : I knew the formula, but I had no idea how it was discovered.
Third : The logical flow of your presentation is really excellent.
You deserve the same audience for number theory as blackpenredpen's for calculus. I wish it for you !
I like your explanations from a perspective of understanding why the claims are correct, however, I suggest you to explain (especially on the putnam and math around the world vids) how someone would approach the problem WITHOUT having key "building block" before hand, like in a real competition. Keep it going!
Thank you very much!
Thank you, very good video! Ireally enjoed the collaboration and the combination of more intuitive combinatorial thinking in 1st part and analysis in 2nd part.
Enjoyed both videos very much.☺
I always pause these videos whenever the next step is not obvious to me. What's going to happen next? Is he going to re-index the sum, do some algebra or a use a theorem/lemma/tool? Then I mull things over for a bit before un-pausing. This is really good exercise!
Easy recursive way to get the Catalan numbers: Begin (1, 1,) dot (1, 1) = 2. Place the 2 on the right of (1, 1,) getting (1, 1, 2). Reverse and take the dot product of (1, 1, 2) and (2, 1, 1), getting (2 + 1 + 2) = 5. Then place the 5 to the right of 1, 1, 2, 5 and take the dot product of the reverse,(5, 2, 1, 1) getting (5 + 2 + 2 + 5) = 14. Put 14 to the right of the ongoing string getting (1, 1, 2, 5, 14) and take the dot product of the reverse, so dot product of (1, 1, 2, 5, 14) and (14, 5, 2, 1, 1) = (14 + 5 + 4 + 5 + 14) = 42., etc
Yeah, but it's not efficient, its O(n^2) operations.
I've derived Catalan number formula by constructing a modified Pascal triangle from incomplete Catalan numbers and induction.
Let's call an incomplete Catalan number as I(m, n). Incomplete Catalan number is the number of unique lattice paths where the starting point is (0,0), the destination point is (m,n) and the lattice path is under the diagonal. Obviously, the full Catalan number C(n) equals to I(n.n). Now there is a recursive relationship between the Incomplete Catalan numbers is the following: I(m, n) = I(m - 1, n) + I(m - 1, n - 1) + I(m - 1, n - 2) + ... + I(m - 1, 0)
the graphical representation when m >= n is this:
1 1 1 1 1 1 1 1 ...
0 1 2 3 4 5 6 7 ...
0 2 5 9 14 20 27 ...
0 5 14 28 48 75 ...
0 14 42 90 165.....
0 42 .............
.........
I've noticed that I(m, n) = I(m - 1, n) + I(m, n - 1), which is similar to pascal triangle relationship.
You can fill symmetrically the part bellow the diagonal with the negative values while still preserving this relationship:
0 1 1 1 1 1 1 1 1 ...
-1 0 1 2 3 4 5 6 7 ...
-1 -1 0 2 5 9 14 20 27 ...
-1 -2 -2 0 5 14 28 48 75 ...
-1 -3 -5 -5 0 14 42 90 165.....
-1 -4 -9 -14 -14 0 42 .............
..........................................................
so I need to find a formula that satisfies these conditions:
A(m,0) = 1
A(m,n) = - A(n,m)
A(m,n) = A(m, n) =A(m - 1, n) + A(m, n - 1)
and it turns out to be (m - n) * (n + m - 1) ! / (m! * n!)
it can be easily checked in those 3 conditions, the exception was a(0, 0), but fortunately we can ignore this
since n-th Catalan number is I(n, n) then I(n, n) = A(n + 1, n) = (n + 1 - n) * (n + 1 + n - 1) / ((n + 1)! * n!) = (2n) ! / (n! * n!) / (n + 1)
1:58 this finite sum is the convolution of two sequences
If you solve for C(1), you get that the "sum" of all Catalan numbers is a complex sixth root of unity!
Great explanation thanks. Amazing what can be deducted and understood from a simple question: How many ways I can create triangles in a polygon
Hey you’re substituting values of x in the formal power series , I think that is not allowed and you have to expand for sqrt(1-4x) here and then check whether it matches to def of your catalans sequence and also when you get the closed form expression then you can say where the power series converge and here for |x| < 1
dang... this is good.
In the binomial coefficient, where is the (1/2-n)! term on the bottom?
Please prove the genera binomial theorem!
I always wonder what does n choose r physically mean when n is fraction or negative.
As the general notion, choose r objects from n doesn't fit here.
Pls. Explain this!!
Its abuse of notation.
naman jain Taking factorials of fractions is just generalising properties that we see work for integers and extending them. The same is true for taking arbitrary powers of numbers, what exactly does it mean to raise a number to the power of π? More formally you’d use gamma functions in place of factorials as factorials are a discrete function
The "proper" definition of x choose r is:
x(x-1)(x-2)...(x-r+1)/r!
which doesn't require the Gamma function as long as r is a nonnegative integer and x is any complex number -- actually x can be from any unital associative algebra.
Desire' Andre', 1887 had a beautiful solution to this. Look up "Problem solving strategies by Arthur Engel". I'm sure you are aware of this book.
I do know this book! I used it a bit when I was coaching the Colorado College Putnam team.
@@MichaelPennMath This book was treated as a holy grail back in the day.
nice
What if you defined Csub0 = 0!!
Why C(x) as x go to 0 equals C0?