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?
Why is symmetry not found in number of paths in a N X N grid not crossing the diagonal
combinatorics
Related Solutions
Sorry for pictures like that but...
Lets denote C as the point, where our good path touched diagonal the last time.
Lets put good paths to the sets according to their points $C(m,m)$. We have $C(0,0),\dots,C(n-1,n-1)$. How many paths belong to the set of point $C(m,m)$?
There are $P_m$ ways to go to the point $C(m,m)$. We know that for the rest part of the path we wont touch the diagonal anymore, so that means that our path lies under the line DE. Which means, that for the rest part of the path we have $P_{n-(m+1)}$ ways to do that. So the group of $C(m,m)$ consists of $P_m\cdot P_{n-(m+1)}$ good paths. We may take $m=0,\dots,n-1$ and then the sum of all possible paths is $\sum_{m=0}^{n-1}P_m\cdot P_{n-m-1}=P_n$
I find it easier to work with up-down paths, defined as sequence of up-steps (e.g., from $\langle m,n\rangle$ to $\langle m+1,n+1\rangle$) and downsteps (e.g., from $\langle m,n\rangle$ to $\langle m+1,n-1\rangle$). A Dyck path is then an up-down path that does not go below the $x$-axis, and there are $C_n$ Dyck paths from $\langle 0,0\rangle$ to $\langle 2n,0\rangle$.
If $n,n'\ge 0$, $m<m'$, and $t\ge 0$, let $\mathscr{D}(m,n,m',n',t)$ be the set of Dyck paths from $\langle m,n\rangle$ to $\langle m',n'\rangle$ that hit the $x$-axis exactly $t$ times, and let $d(m,n,m',n',t)=|\mathscr{D}(m,n,m',n',t)|$. Thus, $d(0,0,2n,0,2)=C_n$.
Suppose that $t\ge 1$, and $0\le k<t$. Let $P\in\mathscr{D}(m,n,m',n',t)$. Let the points where $P$ hits the $x$-axis be $\langle\ell_i,0\rangle$ for $i=1,\ldots,t$, where $\ell_1<\ldots<\ell_t$. Since $P$ is a Dyck path, $P$ has an up-step immediately after each of these points except possibly the last. Remove the first $k$ of these up-steps, and translate the resulting path upwards $k$ units to get a path $\hat P$; it’s straightforward to check that $\hat P\in\mathscr{D}(m,n+k,m'-k,n',t-k)$: the path has been shortened by $k$ steps, and the first $k$ hits have been eliminated.
This procedure is reversible. If $P\in\mathscr{D}(m,n+k,m'-k,n',t-k)$, we first shift $P$ down by $k$ units to get an up-down path $P'$. For $i=1,\ldots,k$ let $\ell_i$ be minimal such that $\langle\ell_i,1-i\rangle$ is on $P'$. Let $Q$ be the up-down path obtained from $P'$ by inserting an up-step immediately after each of the points $\langle\ell_i,1-i\rangle$. Then $Q\in\mathscr{D}(m,n,m',n',t)$, and $Q=\hat P$. It follows that
$$d(m,n,m',n',t)=d(m,n+k,m'-k,n',t-k)\;.$$
In particular,
$$d(0,0,2n,0,k+1)=d(0,k,2n-k,0,1)=d(0,0,2n-k,k,1)\;.$$
This bijection between paths $P$ and $\hat P$ is the up-down version of the correspondence that is very, very badly described at your CodeChef link, where its author writes ‘This mapping is same as decreasing value of $y$ for a path when it touches a diagonal’.
Each path in $\mathscr{D}(0,0,2n-k,k,1)$ must begin with an up-step; if we remove this up-step and shift the path one unit down and to the left, we get a Dyck path from $\langle 0,0\rangle$ to $\langle 2n-k-1,k-1\rangle$. Conversely, any Dyck path from $\langle 0,0\rangle$ to $\langle 2n-k-1,k-1\rangle$ becomes a path in $\mathscr{D}(0,0,2n-k,k,1)$ if we shift it one unit up and to the right and prepose an up-step. Thus,
$$d(0,0,2n-k,k,1)=\sum_{t\ge 1}d(0,0,2n-k-1,k-1,t)\;.$$
Each up-down path from $\langle 0,0\rangle$ to $\langle 2n-k-1,k-1\rangle$ corresponds to a possible sequence of $2n-k-1$ votes, $n-1$ of them for candidate $A$ and $n-k$ of them for candidate $B$. On this interpretation the Dyck paths in $\mathscr{D}(0,0,2n-k-1,k-1,1)$ correspond to the sequences in which candidate $A$ is never behind candidate $B$. Calculating the number of such paths is essentially the ballot problem.
Clearly there are $\binom{2n-k-1}{n-1}$ up-down paths from $\langle 0,0\rangle$ to $\langle 2n-k-1,k-1\rangle$. If $P$ is one of these paths that is not a Dyck path, there is a least $\ell$ such that $\langle\ell,-1\rangle$ is on the path $P$. Reflect the initial segment of $P$ between $\langle 0,0\rangle$ and $\langle\ell,-1\rangle$ in the line $y=-1$; the result is a path $P'$ from $\langle 0,-2\rangle$ to $\langle 2n-k-1,k-1\rangle$ that first hits the line $y=-1$ at $x=\ell$. Note that if this initial segment has $u$ up-steps, then it has $u+1$ down-steps, and the rest of $P$ has $n-1-u$ up-steps. As a result, $P'$ has $(n-1-u)+(u+1)=n$ up-steps and $n-k-1$ down-steps.
Conversely, if $P$ is an up-down path from $\langle 0,-2\rangle$ to $\langle 2n-k-1,k-1\rangle$ that first hits the line $y=-1$ at $x=\ell$, reflecting the first $\ell$ steps of $P$ in the line $y=-1$ produces an up-down path $Q$ from $\langle 0,0\rangle$ to $\langle 2n-k-1,k-1\rangle$ that first hits the line $y=-1$ at $x=\ell$, and it’s clear that $Q'=P$. Every up-down path from $\langle 0,-2\rangle$ to $\langle 2n-k-1,k-1\rangle$ hits the line $y=-1$, and there are $\binom{2n-k-1}{n}$ such paths (since each has $n$ up-steps and $n-k-1$ down-steps). Thus, the number of up-down paths from $\langle 0,0\rangle$ to $\langle 2n-k-1,k-1\rangle$ that are not Dyck paths is $\binom{2n-k-1}n$, and
$$\begin{align*} d(0,0,2n,0,k+1)&=\binom{2n-k-1}{n-1}-\binom{2n-k-1}n\\ &=\binom{2n-k-1}{n-k}-\binom{2n-k-1}{n-k-1}\\ &=\binom{2n-k-1}{n-k}\left(1-\frac{n-k}{n}\right)\\ &=\binom{2n-k-1}{n-k}\frac{k}n\;. \end{align*}$$
The Dyck paths in $\mathscr{D}(0,0,2n,0,k+1)$ correspond naturally to the paths in the plane from $\langle 0,0\rangle$ to $\langle n,n\rangle$ using only right-steps and up-steps that hit the diagonal exactly $k-1$ times between the two endpoints, or $k+1$ times including the endpoints.
Best Answer
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.