Combinatorics – Relation Between Standard Young Tableaux and Catalan Number

Question

From wikipedia, I know some basic facts about Catalan number and Young tableaux. Moreover, I know that Catalan number $C_n$ is the number of triangulations of a $n+2$-gon.

What's the relation between standard Young tableaux and Catalan number?

Answer 1

$C_n$ is the number of correctly balanced strings of $2n$ parentheses, $n$ left and $n$ right parentheses. Any string of $n$ left and $n$ right parentheses can be described by a $2\times n$ array of the integers $1,\ldots,2n$: the numbers on top are the positions of the left parentheses, listed in increasing order, and the numbers on the bottom are the positions of the right parentheses, also listed in increasing order. The string is balanced if and only if the array is a standard Young tableau.

To see why this is true, note that if both rows are listed in increasing order, the array is not a standard Young tableau if and only if there is a column in which the top number exceeds the bottom number. But that happens if and only if there is a $k$ such that the $k$-th right parenthesis precedes the $k$-th left parenthesis, i.e., if and only if the string isn’t correctly balanced.

Thus, there are $C_n$ standard $2\times n$ Young tableaux.