Given a 2*n matrix, find the number of options to order the numbers $1,2,...,2n$ in the matrix s.t each number appears only once, each row is increasing, and each column is increasing.
The solution is Catalan number $C_n$, but I'm not sure why. I thought maybe we could define an isomorphism between all legal parenthesis sequences and legal options, for example if we place each parenthesis sequence in the order of $(1, 1) \to (2, 1) \to (1, 2) \to (2,2)...$ I think the numbers may be determined but I'm not sure.
If anyone can clarify why $C_n$ is the solution it would be great.
There is a bijection of this matrix to the ways of nesting parenthesis in a typical algebra (which is well known to be counted by the Catalan numbers). Take a "valid" nesting like (()(()())), where valid means that the number of opening and closing parentheses is the same, and that reading left-to-right the number of opening parentheses so far is not less than the number of closing parentheses. Now enumerate the parentheses (independent of type) from left to right with 1,2,...,2n, and put the labels of the opening parentheses in one row and the labels of the closing parentheses in the other. The requirements of monotonicity in both directions of the 2*n matrix are obviously fulfilled.