[Discrete Mathematics] Catalan Numbers

In this video we introduce the Catalan Numbers, which is a way of looking at lattice paths from (0,0) to (n,n) where it never crosses the diagonal line. This is also the number of ways to multiply n+1 products.

*--Playlists--*

*--Recommended Textbooks--*

Hello, welcome to TheTrevTutor. I'm here to help you learn your college courses in an easy, efficient manner. If you like what you see, feel free to subscribe and follow me for updates. If you have any questions, leave them below. I try to answer as many questions as possible. If something isn't quite clear or needs more explanation, I can easily make additional videos to satisfy your need for knowledge and understanding.

[scoutjohnston]

He keeps saying 'We' as if i have any idea of what's going on.

[AmeyaGharpure]

At 10:22,
1) The reason that we can count paths from (0, 0) to (n, n) is because the number of braces (Es) and letters (Ns) are equal.
2) The reason that we count only the "number of paths above the diagonal" is because it doesn't make sense to have more number of letters (Es) than braces (Ns) at any point.
Eg: ab((c)) is wrong whereas (a(bc)) and ((ab)c) are both correct.

[tinnguyen]

for the bracket example, it is much simpler to ignore the letters and consider open brackets as E and close brackets as N

[alextran]

I could not understand n+1, and n-1 from other algebraic tutorials until I see this beautiful explanation.

[jessstuart]

A long time ago, I used catalan numbers when I was trying to figure out when to walk away and cut your losses while playing $5 blackjack. Assuming you play for just $5 each time, if you get 3 games down, you should walk away. At that point you have a less than 50% chance of recovering your money.

[LaughingManRa]

Wow, whoever figured out that all the mirror images of the paths above the diagonal reach the same point is a total genius! (I I presume? :-) )

[yonatansmn]

What about the case where the path is n N's, n E's? the reflected path also ends at (n, n). More generally, when I have a sequence of N's, followed by the same amount of E's, followed by N's and then again the same amount of E's until I reach (n, n) - e.g. 5N 5E 5N 5E or 6N 6E 4N 4E (where n = 10)?

[yifuxero]

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.

[Sicaine]

Nice; Helped me to understand it in a whole new (even first) way.

[_soop_]

At first i was confused but after making doing some research, i understood it.
He's not explaining what the catalan numbers are but how they got the formule to get the catalan numbers (atleast in the first half)

[virtualassassin]

brilliant idea, i was looking for a hint to understand the catalan numbers and your work did an awesome job. thank you so much for the video !!!

[visheshsharma]

Sir can you explain what does it mean ("Path NNENE will not work") Is it so that i cannot reach a target if at anytime i got to see more N than E. Is there any formal proof.

[spicy_wizard]

the reason why he removed the last letter is to reduce it to an (0, 0) -> (n, n) problem. As for having confirmed a-e and (, there is only one way to put f (i guesss?)
removing the parenthesis: n pairs of () has n (, therefore we dont need to worry about the closing bracket.

[arpanbanejee]

I forgot the concepts of factorials in probability, in 2:03 mins how can we write that total number of ways is 2n!/n!*n! can someone break this down for me.

[Luamn]

I was wondering if, by any chance, the name (Rosen) in the recommended textbooks relate in any way with the chess player Eric Rosen, which has a voice reaaally similar to yours. Thanks for the intuitions!

[alifadaeimanesh]

Thank you for your excellent explanation and proportional examples

[PanCholec]

Thanks! This was very helpful. Trying to understand this explanation from wikipedia without the visualization was a little too much for me.

Btw. could you maybe do an explanation of Narayana numbers?

[yatharthsameer]

How you got equation for "above"

[justinlangley]

Are we limited to only North and East or not? The question posed is incomplete without specifying. We could go east a bit, then north, east some more, then south some, east and north as long as we don't intersect our own path of travel.

Similar idea we can go far east, north, and play around with going west north and east. If we do it right we don't intersect the diagonal and have a valid path of travel albeit an inefficient one. I feel as though you should reupload this video with an updated version of the question.

The question didn't state only allowing particular directions of travel and then you limited it to only North and East. I understand that's what we need for this problem, and understand the concept, but a good question for learning these concepts should state these things explicitly. It's exactly why people get confused with math when they're learning. I struggled with it for years until I learned how to think analytically.

Once we're talking about real world problems it's ok to be less explicit in what's expected because it's assumed the math is known to the student, but while teaching, until that point, math should be a lot more rigorous and explicit as possible in nature to fully describe the concepts.

I don't mean any disrespect but any mathematics can be hard enough as it is, especially discrete mathematics since it builds off of so many different areas of mathematics.

[anna.bananna]

Isn’t the reason to remove the last product and right brackets because for each way of positioning the rest of the letters and brackets there is only one corresponding way to add back the removed elements and therefore these leftover elements don’t play any role in the final result of number of ways? 🧐