2
$\begingroup$

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?

$\endgroup$
3
$\begingroup$

$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.

$\endgroup$
1
$\begingroup$

The number of pairs of Standard Young Tableaux (SYT) of the same shape of size $n$ which have atmost 2 columns is $C_n$, the $n^{th}$ Catalan number. The bijection between these and Dyck paths is :

  1. For $1 \leq i\leq n$ : by taking a north-east step at the $i^{th}$ step if the $i$ is at the first column in the first SYT and by taking a south-east step if $i$ is at the second column in the first SYT.
  2. For $n+1 \leq i\leq 2n$ : by taking a south-east step at the $i^{th}$ step if the $2n-i+1$ is at the first column in the second SYT and by taking a north-east step if $2n-i+1$ is at the second column in the second SYT.

Applying the Robinson-Schensted correspondence, we also get that $C_n$ is the number of permutations of $\{1, ..., n\}$ that avoid the permutation pattern 123 (or, alternatively, any of the other patterns of length 3); that is, the number of permutations with no three-term increasing subsequence. For $n = 3$, these permutations are $132$, $213$, $231$, $312$ and $321$. (This interpretation of the Catalan number is mentioned on the wikipedia page)

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.