Блог пользователя sabbirh654

Автор sabbirh654, история, 3 года назад, По-английски

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.

  • Проголосовать: нравится
  • +3
  • Проголосовать: не нравится

»
3 года назад, # |
  Проголосовать: нравится +10 Проголосовать: не нравится

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.