I am struggling with this proof. Can anyone help me?
Prove that the number of distinct $2$-by-$n$ arrays
$$ \begin{bmatrix}x_{11} x_{12} ... x_{1n} \\ x_{21} x_{22} ... x_{2n} \end{bmatrix}$$
that can be made from the numbers $1,2 ... ,2n$ such that
$$ x_{11} < x_{12} < ... < x_{1n}, $$ $$ x_{21} < x_{22} < ... < x_{2n} $$
$$x_{11} < x_{21}, x_{12} < x_{22}, ..., x_{1n} < x_{2n}, $$
equals the $n$th Catalan number $C_n$.
Call a (possibly incomplete) arrangement of numbers in the $2 \times n$ array admissible if each number is greater than all those to its left or above it. Now consider constructing a complete admissible arrangement by adding numbers $1, 2, \ldots, 2n$ one by one to the empty array in increasing order. If the numbers $1, 2, \ldots, m$ have been admissibly arranged, then there can be no empty cells above or to the left of the occupied cells, for in that case, putting any number from $m+1, \ldots, 2n$ in the empty cells would make the arrangement inadmissible. Therefore at each step the lowest unassigned number can only be assigned to the leftmost empty cell in either row, or only in the top row if both rows contain the same number of assigned cells. In the Figure, $?$ denotes one of $1, 2, 3, 4 $ (admissibly arranged), and $*$ a possible assignment for number 5.
The process of adding one number at a time in the leftmost empty cell of a row can be represented as a path in a grid. Starting at $(0,0)$, when we add the new number to the top row, we move right horizontally by one unit and when we place the number in the bottom row, we move down in the grid by one unit (we represent the grid downwards). A mapping between the $2 \times 5$ array and the corresponding path is shown in Figure.
Thus the number of admissible arrays is the same as the number of paths that lie above the diagonal and hence equals $C_n$.