Table Number Filling Catalan Numbers

Question

Assume there is a $2\times n$ table. We are supposed to count the number of ways of filling this table with numbers from $1$ to $2n$ so that from left to right and from down to top, the numbers are increasing. I know the answer is the nth Catalan number but I can't seem to find a relation. I would appreciate any kind of help.

Answer 1

Picture the table like this:

$$x\; x\; x\; x\; x\; x\; x$$ $$\underbrace{x\; x\; x\; x\; x\; x\; x}_{n\;times}$$

Observe that we need to pick n out of $2n$ numbers to fill the top row. However, we cannot pick just any set of $n$ because for each number $x$, we have to have a corresponding number smaller than $x$.

For instance, picking the smallest n numbers first to put in the top row would instantly fail.

So, call the top numbers $A$ and the bottom numbers $B$. We need to sequentially put the numbers $1,...,2n$ into either $A$ or $B$ so that $|B|>|A|$ at all times. Which is exactly $C_n$.