Counting Lesson 6: Catalan Numbers

[@VV-xt7fj]

Thank you so much. This is the best explanation for catalan numbers that I have seen!

[@neslef3]

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.

[@neeraj33negi]

Thanks, now I am finally able to derive the formula.

[@dolevdo]

Great video. Extremely helpful

[@samchan2535]

Clean and lucid explanation.

[@f5673-t1h]

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

[@meetamin7343]

Great explanation

[@socrates4446]

Really nice video. Great job

[@mk-ml4tn]

What is the point of complementing rest of the path as we are ending at (4,6) not at (5,5)

[@nikaa-yr7qe]

*Thank you*

[@yanhao9583]

Amazing explanation!

[@muhammadhattahakimkeren]

thanks a lot for your video

[@AdonisGaming93]

I'm doing an extra credit presentation for about 10-15 minutes on them and this video helped out great thank you!

[@djdmath]

You're welcome!

[@woonsang]

Great explanation!

[@jaspreetkaur6745]

How we can solve if there is another points are given like (2,3) to (4,7)?????????

[@Gaer56]

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

[@user-kw4jn8od4z]

ITZ THE BEZT VIZEO IVE ZEEN FOR CAZALAN NUMBERZ.

[@Ashdude9415]

how will the formula vary if the co ordinate of x,y is having x!=y???]

[@debarghyakundu4094]

nice explaination.

[@sabyasachi36]

greatly explained

[@S_P_A_C_E_DD]

Why does 10C4 represent every bad path though?

[@hilafishman6339]

Thank you!

[@박주호오늘은찐수학]

What program do you use?

[@muhammadhattahakimkeren]

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

[@lohe2499]

why need to change R to U and U to R... somebody can explain?

[@croraf]

It is not very well explained here, nor in the other videos. I found the best explaination on english wikipedia (proof 2).

[@neslef3]

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

[@vishwaprakash4191]

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.

[@CarterChen]

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

[@luojihencha]

genius

[@vatsaakhil]

42 @14:19

[@ManishKumar-je2zp]

Thanks a lot! My life is somewhat less miserable now.

[@djdmath]

Happy to help! Everyone's life would be a little less miserable with Catalan numbers in them!

[@EcoleLibre]

Accent insupportable (nasal). Désolé. Pas capable.

[@mardenge]

Thank you!!