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.
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.
Wow, whoever figured out that all the mirror images of the paths above the diagonal reach the same point is a total genius! (I guess.........Catalan, I presume? :-) )
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.
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)
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.
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.
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)?
It would always reach (n-1, n+1). You start reflecting from the first point above the diagonal, not on the diagonal. For n N's and n E's such NNNEEE (n = 3) reflection would start from (0, 1) not from (0, 0). Try doing it on paper once again and you should get it.
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.
All "above" paths end at (n-1, n+1) after flipping. For a path to end at n-1, n+1 you take a total of n-1 East, and n+1 north, a total of 2n steps. You choose n+1 of them to be North, and the rest are automatically East. So the total number is 2n choose n+1, which is the result he got: (2n)! / (n+1)!(n-1)!
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?
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.
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!
Putting Brackets around 1 thing doesnt make sense/ is useless. If you put Brackets around three things you would have too few things to put Brackets around.
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? 🧐
Basically, because it works. You need a way to convert a parenthesis expression into a path to (n,n). To be sure there are the same numbers, you have to fulfill these conditions. - You have to always get the same result when you start from the same expression (ie, no randomness or free choice) - Each expression has to be possible to transform into a path (ie, the way you choose cannot fail) - Two different expressions cannot become the same path (Or you'll have trouble with the next condition) - You must be able to undo the process in a way that has these same conditions This reverse method cannot change your expressions or paths. That is, if you turn an expression into a path, and then do the reverse method to the path you got, you have to get the original expression. And if you change a path to an expression with the reverse, and then transform the expression you got back into a path, you have to get the same path. If you have a method that fulfills all this, that's all you need. The exact method you use doesn't matter, as long as these conditions are met.
at 10:30 what value is n? is it the number of left parens or the number of letters? (alternative form) what happens if letters = L.parens-1? does n go to n-1 or does it stay at n?
+massivejester Imagine that you want to go from (0, 0) to (2, 2) To do that you need to go two times east and two times north. So lets say we have two "teams". "East team that has two members, and North team that has two members as well", A possible pattern is that ENEN. To find the number of all partners we need to pick from any team one element. At first we can do that with 4 ways, after we 3, etc... So it is 4!. But from team1 maybe we have same things, lets say E1 N E2 N is same with E2 N E1 N, but 4! counts it as different, so we need to divide by 2!. Similar for north team we divide with 2!. So formula to go from 0,0 to N,M is (N+M)! / (N! * M!)
The idea is(I guess) to not have the number of Ns (norths) ever greater than the number of Es (easts). To keep it under the line in this case. Still, what the shit did happen here?
![[Discrete Mathematics] Discrete Probability](http://i.ytimg.com/vi/FHRuqc0eHdw/mqdefault.jpg)
![[Discrete Mathematics] Discrete Probability](/img/tr.png)
He keeps saying 'We' as if i have any idea of what's going on.
It's a hard concept.
Discreet math
Takes time
🤣🤣🤣
@@scoutjohnston2125 he tries to make us understand and as you write proofs you use the word we so you get used to it
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.
for the bracket example, it is much simpler to ignore the letters and consider open brackets as E and close brackets as N
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.
Wow, whoever figured out that all the mirror images of the paths above the diagonal reach the same point is a total genius! (I guess.........Catalan, I presume? :-) )
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 !!!
Glad you liked it
Nice; Helped me to understand it in a whole new (even first) way.
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.
I could not understand n+1, and n-1 from other algebraic tutorials until I see this beautiful explanation.
why would it be such?
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)
Thanks!
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.
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.
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)?
It would always reach (n-1, n+1). You start reflecting from the first point above the diagonal, not on the diagonal. For n N's and n E's such NNNEEE (n = 3) reflection would start from (0, 1) not from (0, 0). Try doing it on paper once again and you should get it.
Thank you for your excellent explanation and proportional examples
His explaination is really confusing.
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.
It means you will cross the diagonal which violates the condition of the sequence.
There is no proof. It just violates the definition.
How you got equation for "above"
All "above" paths end at (n-1, n+1) after flipping. For a path to end at n-1, n+1 you take a total of n-1 East, and n+1 north, a total of 2n steps. You choose n+1 of them to be North, and the rest are automatically East. So the total number is 2n choose n+1, which is the result he got: (2n)! / (n+1)!(n-1)!
amazing explanation, thank you
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?
This is by far the best Explanation of Catalan Number out there. Thanks!!
Number of paths are calculated by adjacency matrices and products of them. Partial solution anyway
What's that
brilliant!!! thanks a lot!!!
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.
wow amazing way to solve this problem
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!
mr.rosen be like: oh no my name! 😂
Why must there be two components after each bracket?
Putting Brackets around 1 thing doesnt make sense/ is useless. If you put Brackets around three things you would have too few things to put Brackets around.
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? 🧐
Great video
why do we delete right brackets and last product f?
Basically, because it works. You need a way to convert a parenthesis expression into a path to (n,n). To be sure there are the same numbers, you have to fulfill these conditions.
- You have to always get the same result when you start from the same expression (ie, no randomness or free choice)
- Each expression has to be possible to transform into a path (ie, the way you choose cannot fail)
- Two different expressions cannot become the same path (Or you'll have trouble with the next condition)
- You must be able to undo the process in a way that has these same conditions
This reverse method cannot change your expressions or paths. That is, if you turn an expression into a path, and then do the reverse method to the path you got, you have to get the original expression. And if you change a path to an expression with the reverse, and then transform the expression you got back into a path, you have to get the same path.
If you have a method that fulfills all this, that's all you need. The exact method you use doesn't matter, as long as these conditions are met.
Thanks, this helped a lot!
This is much more confusing than how my lecturer explained.
at least we can rewind this guy when we don't get it
beautiful handwriting
at 10:30 what value is n? is it the number of left parens or the number of letters?
(alternative form) what happens if letters = L.parens-1? does n go to n-1 or does it stay at n?
What are you using for writing these tutorials?
Thank you for doing this
@12:30 why do we add the letter f? the explanation didnt quite make sense
You need 6 letters to perform 5 letters.
very intuitive! thanks :D
Well. Thank you,Sir
fairly speaking ...i didnt get anything
Why do we only care about crossing from the bottom but not crossing from top? Why isn't it Total - Above Diagonal - Below Diagonal?
Then you'd get 0 no?
Like the total is 100, above is 50 and under is 50
Then you get 100 - 50 - 50 = 0
Why is it (2n)! , and not just 2n?
+massivejester Imagine that you want to go from (0, 0) to (2, 2)
To do that you need to go two times east and two times north.
So lets say we have two "teams". "East team that has two members, and North team that has two members as well", A possible pattern is that ENEN.
To find the number of all partners we need to pick from any team one element. At first we can do that with 4 ways, after we 3, etc...
So it is 4!. But from team1 maybe we have same things, lets say E1 N E2 N is same with E2 N E1 N, but 4! counts it as different, so we need to divide by 2!. Similar for north team we divide with 2!. So formula to go from 0,0 to N,M is (N+M)! / (N! * M!)
tnx
Why dividing by 2 won't work
My problem is how we came up with formula originally (2n)!/n!n! please?
Because it's the law of binomial coefficients
The idea is(I guess) to not have the number of Ns (norths) ever greater than the number of Es (easts). To keep it under the line in this case. Still, what the shit did happen here?
why is the above （2n)!/(n+1)！(n-1)！
number of ways to find N+1 norths out of 2N moves as he finally ends up at (n-1, n+1)
! Represents factorial I believe
This made no sense.
How many paths there are from A to B imgur.com/a/fDpUR