Catalan numbers derived!
HTML-код
- Опубликовано: 18 сен 2024
- How many ways can you validly arrange n pairs of parentheses? We explore this question visually, using generating functions and a combinatoric proof.
Josef Rukavicka's paper (source of the combinatoric proof): www.combinator...
take a moment to appreciate that he went over a lot of cool combinatorial ideas(man they're useful for solving problems I swear), and then went over generating functions showing that all math is really connected... I mean I've seen almost all the ideas before, but the presentation is just amazing. i love how everything comes one after another. I've learned some new stuff here as well. I really love your video sir. thanks a lot for this!
This is by far the best video I have ever seen on Catalan numbers. All I ever saw was ways to compute them. This is brain orgasm! Thanks for the efforts.
second method was just amazing i was like wow it was a week since i was struggling to know visual reason behind formula and you just nailed it🎉🎉
Okay, the fact that you can use a polynomial to represent the number of paths and the algebra takes you the rest of the way is blowing my mind.
Man. You deserve way more than it. I usually don't give good rating to feakin math tutorials. This one was really nice. keep it up man
Ah, I was looking for this video after failing to solve a Computer program to evaluate bracket combinations. Thank you ! Really informative video ! #subscribed :)
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)
I know that one!
Amazing video! You explained some of these difficult concepts really well.
Fabulous video. Very easy to understand and really make sense.
Thank You
Wow. I'm only at 9min, and I love that explanation of a generating function.
please restart making videos they are just lit🔥🔥🔥
Thanks for the kind words! I would like to, it’s just hard finding time with a full time job and separate programming projects I’m working on
Super illustrative animations! What software do you use?
Prob Manim.
Nice combinatorial proof.
Your picture is wrong, it should either count from 0 to 2n or from 1 to 2n+1, as the way you draw it currently, there is an odd number of steps (i.e. parentheses) from 1 to 2n
Unless I'm missing something here, can't there only be 1 path with exceedence n? Wouldn't that contradict your reasoning?
Nope. For example, all the exceedance groups for n=2 are drawn on the screen at 15:40, and you can see that the group with exceedance = n = 2 contains two paths
@@PenguinMaths Ah I see. I misinterpreted the meaning of exceedence.
hey can I ask how you did that blob thing can I know how it goes like I didn't understood that one thing. Any references ...
Thank you.
Dom Ferrel The diagram with the blobs is called a wasp waist factorisation. This pdf looks pretty good for explaining it: igm.univ-mlv.fr/~fpsac/FPSAC02/ARTICLES/Rensburg.pdf
@@PenguinMaths Thank you . Video was very informative and nice visuals .
15:19 i don’t see how it can be reverse easily if we didn’t know which section is the red section.
Nice intro 👌
Awesome
It comes down to counting the number of positions for say, the ones that turn to the right...like, which 3 among the 6 will be turned to the right, etc...number of ways of choosing 3 from 6, so 6 choose 3...but, to avoid repetition, divide by 3!, etc, because ((())) is the same if we switch the first two (, etc, so (6 choose 3)/(3!)...unless I'm forgetting something, lol...
15:36 not understandable