The problem is : find number of paths in N X N grid where you are allowed to move only UP or RIGHT, such that no path crosses the diagonal, i.e. line y = x, if you have to go from point (0, 0) to (N, N). The answer to this problem is Nth catalan number. But this case seems to be highly symmetrical. The diagonal divides the grid in half. So why is it logically wrong to say that the answer to this problem is half of the answer when the restriction of paths not crossing diagonal was not there?
2
-
$\begingroup$ In the body you say no path "touches" the diagonal, but I think you mean no path "crosses" the diagonal, as in the title. $\endgroup$– saulspatzCommented Aug 14, 2019 at 18:17
-
$\begingroup$ Yes.. sorry.. I meant not crossing the diagonal. $\endgroup$– ankur314Commented Aug 14, 2019 at 18:18
Add a comment
|
2 Answers
$\begingroup$
$\endgroup$
By reflecting paths over the diagonal, one can see that the number of paths that never go below the diagonal equals the number of paths that never go above the diagonal.
However, it's possible for a path to be below the diagonal at one point and above the diagonal at another point, so the total number of paths is greater than twice the Catalan number.
answered Aug 14, 2019 at 18:48
$\begingroup$
$\endgroup$
Actually the number of paths from $(0,0)$ to $(n,n)$ under condition of only upwards or to the right and secondly not crossing the diagonal does not equal the $n$-th Catalan number $C_n$ but equals $2C_n$.
They can be spit up in non-crossing paths that begin with "up" (they stay above the diagonal and there are $C_n$ of them) and non-crossing paths that begin with "right" (they stay beneath the diagonal and there are $C_n$ of them).
That is the symmetry you are talking of.
If the condition of non-crossing is dropped then new paths (crossing ones) are involved.
