Great video. Extremely helpful. At about 15:30 when you are trying to prove the inverse from the U = R+2 set to the bad path set, for me it is much easier and convincing to go from the opposite direction and go from the back, looking for the first (and only) spot where there is 1 (and only 1) more U than R (and at least 1 R) and flip it from there. It is easier for me to prove/understand that the only way to from 6 U's and 4 R's is to flip it where there is 1 more U than R (and thus subtracting 1 U and adding 1 R). If this is wrong/ I made any wrong assumptions please Comment.
The Catalan numbers give you how many ways there are to parenthesize a sum, e.g. 2 ways of parenthesizing a+b+c as a+(b+c) or (a+b)+c. So how does this correspond with the above problem with paths? Well, at every step, the number U's must be
Im not sure what is right anymore, the lesson is easy but diffirent people present it diffirently , one above and one below line. There are also diffirent catalan number like in () examples
If you have a sequence of R's and U's where it crosses the diagonal twice, there are two places where you can perform the 'flip' to get the U = R +2 result. (i.e. say for RUURRUUR you can perform the flip at RUU | RRUUR and get RUU | UURRU or you can perfom it at RUURRUU | R and get RUURRUU | R which both meet the desired requirements). Now if this is the case isn't it no longer a bijection and a one-to-one function and thus the proof is not longer valid? I know the function still works for determining the number of possible paths, but I don't see how we can validly get to that point. Please help
But this proof is incomplete. ( Why? ) Well you showed that any "bad" walk corresponds to a walk from (0,0) to (4,5) which means the number of bad walks is a less than or equal to total number of walks from 0,0 to 4,5. To complete the proof, you should also prove that every walk from 0,0 to 4,5 corresponds to a unique bad path from 0,0 to 5,5. i.e you have to show the bijection.
Firstly it is to 4,6 not 4,5. Then the other side of proof could be implied like this: for all the path from 0,0 to 4,6, it must be cross the line before the point of 5,5 (I.E. 0,0 1,1 2,2 3,3 4,4). the number of path from 0,0 to 4,6 is then equals the number of path from 0,0 to all crossing points multiply the number of way from crossing point to 4,6 which both has a one to one correspondence with 0,0 to 5,5, why? from 0,0 to all crossing points is common step for 0,0 to 4,6 and 0,0 to 5,5. from crossing points to 4,6 and crossing point to 5,5 are also in one to one correspondence, as shown by switching u and r. Thus it's one to one correspondence
Extra from me Proof for #of bad path = #of new path every new path has (n-1) Rs and (n+1) Us, therefore there is a point where #of Us > #of Rs so to every new path we can make one bad path, since bad path can only created one new path than function bad path to new path is bijection therefore #of bad path = #of new path
Thank you so much. This is the best explanation for catalan numbers that I have seen!
Great video. Extremely helpful.
At about 15:30 when you are trying to prove the inverse from the U = R+2 set to the bad path set, for me it is much easier and convincing to go from the opposite direction and go from the back, looking for the first (and only) spot where there is 1 (and only 1) more U than R (and at least 1 R) and flip it from there. It is easier for me to prove/understand that the only way to from 6 U's and 4 R's is to flip it where there is 1 more U than R (and thus subtracting 1 U and adding 1 R).
If this is wrong/ I made any wrong assumptions please Comment.
Thanks, now I am finally able to derive the formula.
The Catalan numbers give you how many ways there are to parenthesize a sum, e.g. 2 ways of parenthesizing a+b+c as a+(b+c) or (a+b)+c.
So how does this correspond with the above problem with paths? Well, at every step, the number U's must be
Great explanation
What is the point of complementing rest of the path as we are ending at (4,6) not at (5,5)
Great video. Extremely helpful
Clean and lucid explanation.
I'm doing an extra credit presentation for about 10-15 minutes on them and this video helped out great thank you!
You're welcome!
Thank you!!
*Thank you*
What program do you use?
How we can solve if there is another points are given like (2,3) to (4,7)?????????
Really nice video. Great job
thanks a lot for your video
how will the formula vary if the co ordinate of x,y is having x!=y???]
Why does 10C4 represent every bad path though?
Amazing explanation!
Im not sure what is right anymore, the lesson is easy but diffirent people present it diffirently , one above and one below line. There are also diffirent catalan number like in () examples
Great explanation!
greatly explained
why need to change R to U and U to R... somebody can explain?
It is not very well explained here, nor in the other videos. I found the best explaination on english wikipedia (proof 2).
If you have a sequence of R's and U's where it crosses the diagonal twice, there are two places where you can perform the 'flip' to get the U = R +2 result. (i.e. say for RUURRUUR you can perform the flip at RUU | RRUUR and get RUU | UURRU or you can perfom it at RUURRUU | R and get RUURRUU | R which both meet the desired requirements). Now if this is the case isn't it no longer a bijection and a one-to-one function and thus the proof is not longer valid? I know the function still works for determining the number of possible paths, but I don't see how we can validly get to that point. Please help
But this proof is incomplete. ( Why? ) Well you showed that any "bad" walk corresponds to a walk from (0,0) to (4,5) which means the number of bad walks is a less than or equal to total number of walks from 0,0 to 4,5.
To complete the proof, you should also prove that every walk from 0,0 to 4,5 corresponds to a unique bad path from 0,0 to 5,5. i.e you have to show the bijection.
Firstly it is to 4,6 not 4,5. Then the other side of proof could be implied like this: for all the path from 0,0 to 4,6, it must be cross the line before the point of 5,5 (I.E. 0,0 1,1 2,2 3,3 4,4). the number of path from 0,0 to 4,6 is then equals the number of path from 0,0 to all crossing points multiply the number of way from crossing point to 4,6 which both has a one to one correspondence with 0,0 to 5,5, why? from 0,0 to all crossing points is common step for 0,0 to 4,6 and 0,0 to 5,5. from crossing points to 4,6 and crossing point to 5,5 are also in one to one correspondence, as shown by switching u and r. Thus it's one to one correspondence
42 @14:19
Extra from me
Proof for #of bad path = #of new path
every new path has (n-1) Rs and (n+1) Us, therefore there is a point where #of Us > #of Rs so to every new path we can make one bad path, since bad path can only created one new path than function bad path to new path is bijection
therefore #of bad path = #of new path
ITZ THE BEZT VIZEO IVE ZEEN FOR CAZALAN NUMBERZ.
nice explaination.
Thanks a lot! My life is somewhat less miserable now.
Happy to help! Everyone's life would be a little less miserable with Catalan numbers in them!
genius
Accent insupportable (nasal). Désolé. Pas capable.
Thank you!