sabbirh654's blog

By sabbirh654, history, 4 years ago, In English

we all know that, the very known application of catalan number is, given a grid of n*n. one can move in that grid only right(R) and up(U) direction. how many ways to go from (0,0) to (n,n) so that the diagonal of that grid is not crossed. the solution is. (2n C n) — (2n C (n-1)). My question is : in the standard version, the restriction is to not crossing the diagonal. that means not crossing y = x line. what will be the answer if the equtaion is y = x + k instead of y = x? and the grid is of size n*m instead of n*n?

i have tried to figure it out using reflection trick. but it is not clear to me.even the standard version of this prolem is not clear to me. how reflection trick works here? what is the intuition behind it?

please explain this in a simple manner.. thanks.

  • Vote: I like it
  • +3
  • Vote: I do not like it

»
4 years ago, # |
  Vote: I like it +10 Vote: I do not like it

Your question seems really similar to this recent ABC problem. The editorial there was pretty good; you should read it if you haven't. If you still have questions maybe I can try to explain it.