Let's consider labelling the square of a $2\times n$ chessboard from $1$ to $2n$ such that the numbers increase from left-to-right and bottom-to-top.
Prove that the number of such labellings equals the $n$-th Catalan number $C_n$
I still have no clue how to even start this problem after all the "research" I've done. Extremely confused.
We can make a bijection onto the set of strings of $n$ pairs of regular parenthesis, as follows:
Let "$($" stand on exactly the indices in the upper row, and "$)$" on the indices in the lower row.
For example, $\pmatrix{1&2&4\\3&5&6}$ corresponds to "$(()())$", and $\pmatrix{1&3&5\\2&4&6}$ to "$()()()$".