Catalan number interpretation

Question

I have a $2 \times n$ chessboard where numbers are increasing from left to right and top to bottom. I want to show that the number of arrangements is the $nth$ catalan number.

for example one such arrangement with n = 3 could be:

$\pmatrix{1 3 4\\ 256}$

I think it would be easiest to use: $C_n = \frac{1}{n+1} {2n\choose n}$

What I see is that the first entry must be $1$ and the last entry must be $2n$ Also, if one row is complete (and valid) it completely determines the other row. So it suffices to satisfy one row. Thus we must do $2n\choose n$ to fill a row. However, a bunch of these combinations would not satisfy these conditions. What is the reason to divide by $n+1$?

I tried to use the sequence of $(n+1)$ $1$'s and $(n-1)$ $-1$'s trick (matching parenthesis example that is counted by catalan) but could not establish the proper bijection.

All help is greatly appreciated.

Answer 1

HINT: Given a properly filled in $2\times n$ chessboard, define a string $a_1,\dots,a_{2n}$ by setting $a_k=1$ if $k$ is in the top row of the chessboard, and $a_k=-1$ if $k$ is in the bottom row. For example, your board $\pmatrix{1 3 4\\ 256}$ generates the string $1,-1,1,1,-1,-1$.

Added: You may want to consider Marc van Leeuwen’s answer together with mine; the terminology is a bit different, but we’re describing the same bijection from opposite ends, so to speak.

Answer 2

Given a matching string of $2n$ parentheses, if you consider the first $k$ symbols and count opening and closing parentheses among them, the two counts $(a,b)$ you find must satisfy $a\geq b$ (there are at least as many opening as closing parentheses). Now one can define a Young tableau corresponding to the string in which for any $k$ the numbers $\{1,\ldots,k\}$ fill a shape $(a,b)$ (the first $a$ positions of the first row, and the first $b$ of the second row). Supposing the numbers up to $k-1$ have already been placed, there there is a unique position for $k$, which is in the first row if symbol $k$ is an opening parenthesis, and in the second row if it is a closing parenthesis. This gives a bijection.