The Most Important Sequence: The Catalan Numbers

This is our group submission for #some2
I worked with Tomáš Sláma who made all of the animations in this video. Check out his channel for more beautifully animated math videos: / tom%c3%a1%c5%a1sl%c3%a...
Follow me on Tiktok! / sackvideo
More about the Catalan Numbers:
en.wikipedia.org/wiki/Catalan...
oeis.org/A000108
math.mit.edu/~rstan/ec/catala...
www.amazon.com/Catalan-Number...
www.math.ucla.edu/~pak/lectur...
Corrections:
At 6:43 the formula should only go up to 2n-1 instead of 2n+1

[@chedzeesheeda1019]

The delivery of "Where do they come from? Dyck paths" is killing me and guaranteeing that this knowledge will stay in my head. I'm sure it wasn't intended for comedy, but my internet brainrot is so strong.

[@SunroseStudios]

"a dyck path between two legs" is even better

[@StefanReich]

You're gonna love the quote "Dyck paths with legs on either side" by, uh... SackVideo. This is just too strong

[@asheep7797]

@@StefanReich and the fact it starts to look crinkled like those wrinkles on your...

[@TheAgentJesus]

I'm glad it wasn't just me lmfaoo his face dude I'm dying

[@blazingwreckage]

A Dyck path is a series of Dyck moves

[@ruroruro]

this video, but a vine boom plays every time he says "Dyck path"

[@SamProgramiz]

😂😂

[@BatteryAcid1103]

One of my favorite "wtf are you doing there" Catalan numbers moments is how it shows up in the coefficients of the mandelbrot set.

[@ASackVideo]

What a wonderful connection! I hadn't seen that one before. For anybody else wondering, here it is: For a complex number c, define f(z) = z^2 + c. The Mandelbrot set is the set of c such that the sequence c, f(c), f(f(c)), f(f(f(c)), .... is bounded. (For example by 2) If you leave c as a variable, instead of a sequence of complex numbers, you'll get a sequence of polynomials. As an example, f(f(f(f(c))) = c+c^2+2c^3+5c^4+14c^5 + ... The first several coefficients go 1, 1, 2, 5, 14. The Catalan numbers! As you go further in the sequence, you get more Catalan numbers! Why this happens can be understood with generating functions, and I think is a great connection to a beautiful bit of math.

[@robharwood3538]

@@ASackVideo Please do something on generating functions, especially how to work with them in practice, if you haven't done something like this already. I see they are powerful, but as a mere math hobbyist, I have a hard time navigating the information about them so as to see how I can use them myself in my little explorations. Would be amazing if someone like yourself, with such a great ability to lay out the logic and connections between ideas, could be a guide in my journey to understand them! 🤓😅

[@ASackVideo]

@@robharwood3538 The first video on my channel is about generating functions. I made it 2 years ago, so the presentation is a little worse than my newer videos, but I still think it's a good video!

[@denelson83]

The editors of Wikipedia do not believe this is the case because no proof of this connection has been published.

[@derickd6150]

Really enjoying the format. I like that it is fairly fast, if I don't understand I just watch it a little again. It's also a nice combination of the 3B1B animation style but you also have your own face on the screen so it's like your lecturing. I think you'll be able to do a lot with this format

[@catmacopter8545]

He is using the same animation software 3b1b made, manim

[@johnchessant3012]

Great video! In fact, pi shows up in the Catalan numbers as well. Specifically, pi = limit of 16^n / (n^3 (C_n)^2), as n -> inf

[@ArtArtisian]

Ah yes, the most natural limit to consider =)

[@crackedemerald4930]

Can *every* number real number be derived this way?

In fact, it's just Stirling's formula - so yes, it is surprisingly very natural limit to consider.

[@lookupverazhou8599]

@@ArtArtisian If it is comprised of natudal numbers, if is very natural indeed.

[@glenneric1]

If only I could go back in time and tell Euler not to wear that newspaper on his head.

[@gyattrizzV]

hehehehhehe dyck path ehehehehhehehehe

[@gandalfthegrey9116]

hahahaAHAHAHAHAAHAHAHAAHAHA DAMN BILBO THIS PIPEWEED SLAPS

[@telotawa]

3:29 honestly, it's more obvious to me how to turn nested parentheses into dyck paths than it is for binary trees

[@ASackVideo]

If you replace up-steps with '(' and down steps with ')', you don't get the same types of parenthesizations I'm talking about here! For example, x(yz) and (xy)z are different parenthesizations, but if you remove all the letters they look the same.

[@telotawa]

@@ASackVideo ah gotcha

[@robharwood3538]

@@ASackVideo If you treat each leaf/letter as a single up followed by a single down, i.e. '()', then x(yz) becomes ()(()()) and (xy)z becomes (()())(). In my wanderings, this is the first way I encountered the connection, except that I was only considering the case when the whole 'expression' itself is wrapped in an outer set of parens, so the two above would have been (()(()())) and ((()())()).

[@Brainwizard.2]

We finally reach a point where youtube contents are created by more and more professionals. They surpassed already by such contents by far the university & school program. Anyone who applied to a tech position will realize this over time. :)

[@lookupverazhou8599]

Ok, tell me what you learned.

[@Brainwizard.2]

​@@lookupverazhou8599 Implicitly to this video or the entire 1k++ videos since the beginning of youtube? I learned, that there are better translators, who have the skills to transfer f.e. Fouriertransformation to Vision, Hearing, Smell or Touch. You might associate E-Field not towards this, but under the hood, i do. I write my own Sequence, while others does theirs until we figure out, what is the least redundancy. In form of Primes, Fluktuation or whatever sequences beyond my understanding. Best Greetings

[@ashwinjain5566]

i already love this channel! combines my love of math and computer science

[@draziraphale]

This is really nice, thank you. I remember discovering a link between the Catalan numbers and Freundenthal's equation for root spaces years ago, it does crop up like pi!

[@Leo-if5tn]

Hi, I am a brazillian student and I just wanted to say that I really enjoy your videos, hope you have sucess in this channel so more people watch and learn this content

[@WelshPortato]

New favourite Maths KZbin channel - really, really astounding videos. Hope you're keeping well x

[@sstadnicki]

This was really nice! It took me a moment to realize that triangularizations were being counted in 'ordered' fashion - that is, the pentagon triangulates in five ways rather than just one, but once I got that the rest of that bijection clicked quickly. Your video flourishes and the soft humor in spots are really excellent.

[@academicalisthenics]

I'm studying applied math and physics and I've encountered this sequence during my numerics class, the professor asked us to guess the next number in the sequence. It's weird that so many of us never heard about these numbers, even though we had to complete a module on discrete mathematics beforehand.

[@robharwood3538]

Definitely would like to hear the story of the Associahedron! Hope you make a video on it. I've encountered Dyck paths -- and hence Catalan numbers and the related associativity -- many times in my hobbyist math wanderings, but never realized they could be depicted with some kind of geometric figure like the Associahedron appears to be. Fascinating! It also looks like it is probably connected with Group theory in some way!

[@TheR971]

1. How have I never learned (/recognized) these connections before? This is awesome! 2. Really like having the video of you as I feel like having a person looking at me helps me pay more attention (I remember there was some kind of study from a uni during the beginning of the corona lockdowns that attests that).

[@heisenberg_fisher2890]

Great video and beautiful animations. Thank you!

[@dcqin]

This is super nice! Thanks! : )

[@SimpleLivingHigherThinking]

This is the best video i have watched so far about catalan numbers i really understood the intuition behind catalan numbers and got the feel of it....... i don't need to memorize the applications anymore....thanks a lot

[@ishwarendra]

Amazing video. ❤‍🔥❤‍🔥 dyck pronunciation was a little funny. 😂

[@Grassmpl]

This is why I say it as Dye-kuh instead of Dee-ick. I dont want to cuss inappropriate words by mistake.

[@Mutual_Information]

Just discovered this channel. Excellent stuff. You’ll blow up I’m sure. Just don’t give up!

[@Grassmpl]

Yes. His strict transform will be much better as his singularities will all be resolved. Love the variety.

[@nimennacnamme6328]

4:05 That's a really NICE explanation! :)

[@danielxu3594]

Great video! I love the Catalan numbers. :D Should the product in the RHS of the equation at 6:43 go up to 2n-1 instead of 2n+1?

[@ASackVideo]

Yes, great catch! Thanks for the correction.

[@tvnk1174]

This was surprisingly helpful. Thanks for the video.

[@TechToppers]

man I love this video, amazing summary and very nice setups covering the catalan numbers like he covered every proof in a very nice way and indeed very fast, but still most of the stuff is understandable in one go and yeah it will take some time for me to fully understand this, but this is an amazing video on catalan numbers, no heavy stuff with generating functions or anything else 😄

[@johnchristian5027]

Wow this is super interesting, nice video!

[@racheline_nya]

awesome video! thank you very much for teaching combinatorics so well at 6:44, the 2n+1 should be 2n-1, but that's just a detail (and i guess if someone is attentive enough to notice that it doesn't add up, they're almost certainly attentive enough to notice that it's just an off-by-one error)

[@samrizzo937]

Really great video! Catalan numbers have always been a pretty mysterious thing for me (I learned the formulas and identities in a combo class, but I don't think I ever knew about the Dyck path connection). I had always wondered why the Catalan numbers appeared in recursion so often -- now I know!

[@Grassmpl]

I you want to prove catalan objects, just use strong induction.

[@huhneat1076]

Going into someone's math notes and erasing all the parenthesis is the ultimate display of chaotic intent

[@omargaber3122]

Great, wonderful , amazing , thank you very very much ❤️

[@deathracoffee]

The hardest try not to laugh math video.

[@electra_]

I actually found a different mapping between Dyck paths and binary trees Look at the binary tree and do a depth-first traversal. At each node, go left and mark an L, then process the left child. Then go right and mark an R, then process the right child. Now your sequence of L and R creates a Dyck path. It is a sequence of n Ls and n Rs, who's only restriction is that you can't ever have more Rs than Ls seen by a certain point - this is because each L and R are paired in some way, and within each pair you will always see the L before the R.

[@redpepper74]

Hey I got this too! At first I thought it would be ambiguous when converting from path to tree what to do when you come across an R, but all you do is retreat up the tree until you find a node with exactly 1 child and add a 2nd one :)

[@robharwood3538]

Yes, this is the same binary tree / Dyck path connection I stumbled across when I first found it as well. In my case I was looking for binary strings starting with 0, followed by as many 0s or 1s as you like -- so long as the number of 1s never exceeds the number of 0s -- and then ending with a 'matching' 1 to the initial 0. Just consider 0s as Ls and 1s as Rs, and you get the same Dyck paths as well as a clear link between ( and ) parentheses. In fact, I quickly made the notational switch from 0s and 1s to (s and )s just for readability, and that's where the binary tree connection clicked in as well. Very fascinating interconnection of ideas!

[@someperson9052]

Haha Dyck

[@0xBE7A]

Great Video!

[@uselesscommon7761]

I have encountered Catalan numbers on my own while solving a problem about a game modelled by a state tree. I basically got out a 1/2/5/11 sequence as a term in a part of the model for solution and didn't know what the hell that sequence was, so I generated a few more members and Googled it.

[@TheJara123]

Ohh yes we got one more nice channel for math..combinatorics...a branch badly in need for a channel...thanks...and please keep posting...you make KZbin a better place.

[@msolec2000]

3:23 That's a nice expression there. (Also cool timing)

[@aguyontheinternet8436]

2:22 I love how you can tell he is just barely holding it together with that one

[@FDGuerin]

I wonder if Jacques Tits did any work on Dyck paths.

[@ianweckhorst3200]

There are a finite amount of choices to make for each place in all of these and that finite number goes down by one every time you make a choice, this is the literal definition of the n choose r function

[@martinwestin4539]

Great video! Had a problem in school were I had to find the probability that a given 2n-string with an equal number of 0s and 1s is a dyck word... and I tried for a long time to solve it until I learned about catalan numbers and solved it in 2 minutes...

[@amitshoval7653]

I actually encountered the catalans in a problem I was doing in probability. You start at the number 0, the probability to go up by 1 is 0.8 and to go down is 0.2. What is the probability that you end up in - 1.

[@Grassmpl]

With combinatorics I'm good at coming up with the intuition. However, when it comes to a formal proof, I don't know how to keep it concise. I end up writing very thorough explanations, sometimes spanning many pages.

[@snowy0110]

if anybody knows a dumbed down version of the video, please tell me. I don't understand the proof

[@sagittila]

Nice solution to the parenthetical expression from the hypothetical math book 😂

[@Jaylooker]

These Dyck paths seem really useful for the infinite binary tree of Collatz and could possibly derived an associated approximate generating function from smaller known values. That’s interesting that the triangulation of a polygon gives a book embedding or parenthesized expression after subtracting one edge. I wonder if this triangulation could be considered for more general simplicial complexes in relation to their (co)homology.

[@denki2558]

I stumbled upon this sequence on accident when I was trying to represent polynomials as sums of falling powers, i.e. x^1 = x x^2 = x(x-1) + x x^3 = x(x-1)(x-2) + 3x(x-1) + x and I was trying to find a way to generate those coefficients. I was surprised to find the catalan numbers appear in the formula I derived (and I just learned that that sequence has a name at that time.) Also the sum of the coefficients are also the catalan numbers for a pure unit power.

[@harryfan8785]

Holy fuUUUUU, why on earth do Catalan numbers appear like that!? And nice proof for the closed form; subscribed!

[@mattiasselin4955]

All glory to the Catalan numbers!

[@rentristandelacruz]

Are aware of any relation between the Catalan numbers and the number of partially ordered sets (of a given size)?

[@ASackVideo]

There are plenty of relations to posets, although not to the number of "all of them". For example, C_n is the number of linear extensions of the poset 2 x n. Stanley's book gives a bunch of other examples that are pretty cool, I definitely recommend checking it out.

[@avaraportti1873]

Any connection to functionally complete singleton sets of Boolean operators?

[@ASackVideo]

You could replace the operations in the parenthesization example with Boolean operations if you want.

[@fractal_mind562]

If you'd titled the video "Dyck Paths" it would have a million views

[@usptact]

Is there a relationship between Catalan numbers and Fibonacci numbers?

[@CS_n00b]

I found the proof challenging, what’s the easiest intuitive proof for the Catalan numbers formula?

[@ASackVideo]

In the video, there was a slight error in the proof. At 6:43 the formula should only go up to 2n-1 instead of 2n+1. However I believe the easiest way to get the formula is using Bertrand's ballot theorem. I have a video titled "What are the odds of always winning?" that explains this theorem. For Catalan numbers, you want to consider a contest with n+1 votes for Alice and n votes for Bob. Hopefully it's not too hard to see why this should be in bijection with Dyck paths. With a little algebra you can get the formula.

[@ithaca2076]

the most important sequence, the number sequence

[@yifuxero5408]

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)

[@hannahnelson4569]

Is the simplification at 6:45 obvious? I am having a bit of trouble wrapping my head around it

[@ASackVideo]

Sorry! Check the description for a correction!

[@hannahnelson4569]

Thank you! That should clear it up!

[@pandeyravidev]

Which path ?!!!

[@pje188yt]

In your example of the bisection between polygon triangulation and parentheses, you used a hexagon, which gives C4.. That corresponds to 4 pairs of parentheses. But your example only produces 3 pairs. I could not get this bijection to work properly.

[@ASackVideo]

Triangulations of the (n+2)-gon are in bijection with parenthesizations of an expression with n operations (and hence n-1 pairs of parentheses).

[@pje188yt]

That is very interesting. So there are really two ways to create the catalan sequence with parentheses: one way includes numbers and operations between the parentheses, and one with only parentheses. So for a pentagon, giving C3 = 5, we would have the following five possibilities for parentheses with numbers and operations: (12)(34), (1(23))4, 1((23)4), 1(2(34)), ((12)3)4, but with parentheses only, these reduce to just two possibilities: ( )( ), (( )). Is there any way to relate the expressions with numbers to mountain ranges having expressions like UUDUDD?

[@ASackVideo]

@@pje188yt Yes, both have a binary tree structure. The parenthesizations one is given in the video and the mountain ranges are Dyck paths so you can use that structure.

[@pje188yt]

@@ASackVideo Thankyou very much for clearing that up. Thanks for the great video

[@vitorbortolin6810]

Love the joke, so true! hahahahah

[@drakands8452]

yeh but why n+1 leafs

[@joshp3446]

No shot they named it "Dyck Paths"

[@theshoulderofgiants]

4:48

[@msolec2000]

The Catalan Numbers deserve a full series with each episode going through a few more Catalan objects.

[@APaleDot]

The funniest part about this is that it's actually pronounced Deeck, lol

[@ASackVideo]

I have pretty much only heard it pronounced as I do.

[@oraz.]

I guess Catalan solids have nothing to do with the numbers.

[@txikitofandango]

It's good. It goes too fast, but it's good

[@tylerduncan5908]

Do .75x speed

[@ganiti_314]

@@tylerduncan5908 it's not about speed, it's about steps.

[@erraticskul]

2:37 5:00

[@alihammadshah]

I just read about them. They are the last section of the chapter on counting in Grimaldi's Discrete Math book. His explanation uses paths too with Right and Up steps, and he just permutes a sequence of them to get from (a,b) to (x,y) on a xy-plane. Catalan numbers show up when he adds a condition that the path mustn't exceed y=x. Like most of the topic in his counting chapter it came down to mapping problems to permutation(s). So for paths from (0, 0) to (5, 5), we map "bad" set of steps and remove them from total steps. c(10, 5) - c(10, 4). His explanations are so simple and clear.

[@gandalfthegrey9116]

So the Dyck Paths were very funny but this was also a pretty helpful video so thanks I guess but I still am pretty sure the Dyck Paths were the best part idk

[@jkid1134]

A little brisk but I got most of it

[@jayshewale-vs4dq]

idk but pacing of this video seems to be fast, or I am dumb :(

[@alphahelix5526]

Nice video, but the explanation could be more clear and thorough.

[@Scrolte6174]

0:37 I'm looking at YOU, dirty-minded people!

[@vkvk7113]

Bruh. Pronounce it "dyke path" please

[@abodora532]

dyck what? :path

[@cristipc3033]

bro wtf is this

[@MintCloudyta]

Thank you so much. This video helps me so muh 🫶

[@user-gr4pb4ly7k]

Sorry sir,can I ask an question about how to bijection from cm-labeled dyck path to standard young tableaux? It's hard to study🥲

[@ASackVideo]

I hadn't heard of this before! This is very interesting. I just read the bijection in the paper "From Dyck Paths to Standard Young Tableaux" where they find the bijection by a composition of several bijections. I think none of the individual bijections are too difficult, but it's not clear to me if you can "unwind" them and do it directly or with simpler steps. In particular, bijections that pass through RSK feel difficult to simplify to me.

[@user-gr4pb4ly7k]

@@ASackVideo Thank you for your reply, I have read it, and now I am going to report to the professor haha