Q:

A square grid path problem proof

Let n be a positive integer. Consider all possible ways of arranging n pairs of parentheses “(” and “)” in a row. We want to arrange them in a way that it is possible to pair up the left parentheses with the right parenthesis so that “(” is to the left of “)”. Let An be the set of all such arrangements with n pairs of parentheses. There are 5 elements in A3, as shown below.
((())) (()()) (())() ()(()) ()()()
On an n × n grid, we consider paths travelling along the grid lines from the SW corner to the NE corner of the grid with the conditions that we only travel in the N or E direction, and we never travel above the x = y line. Let Bn be the set of all such paths in an n × n grid. There are 5 elements in B3
Now how do I prove this using a bijection(|An| = |Bn|)?

A:

Let $a_0 = (0,0)$ be the SW corner and $a_{2n} = (n,n)$ the NW corner.  Suppose a path from $a_0$ to $a_{2n}$ does go above the diagonal.  Say the first time it does so is at $a_j = (k, k+1)$ (where we must have $j = 2k+1$).
Reflect the part of the path from $a_0$ to $a_j$ across the line $y=x+1$, and
you have a path (still consisting of N and E moves) from $(-1,1)$ to $(n,n)$.  Conversely, given any path from $(-1,1)$ to $(n,n)$, it must at some point hit the line $y=x+1$, and if you reflect the part of the path up to that point you get a path from $(0,0)$ to $(n,n)$ that goes above the diagonal.  We conclude that the number of paths from $a_0$ to $a_{2n}$ that go above the diagonal is the same as the number of all paths from $(-1,1)$ to $a_{2n}$, which is $2n \choose n+1$ (because there are $2n$ steps, of which $n+1$ are E and $n-1$ N).  The total number of paths from $a_0$ to $a_{2n}$ is $2n \choose n$.  So the number of paths that don't cross the diagonal is
${2n \choose n} - {2n \choose n+1}$.

