I know there is a $1-1$ correspondence between the number of standard young tableaux of $n$ cells and the number of involutions in $S_n$. Number of involutions in $S_n$ satisfies the recurrence relation \begin{equation} a_{n+1}=a_n+na_{n-1}\end{equation} How can we prove that the number of standard young tableaux of $n$ cells also satisfies this relation without using the correspondence with the number of involutions?
1 Answer
I am surprised that this is still unanswered! See Proposition 1.3.2 in Marc van Leeuwen, The Robinson-Schensted and Schützenberger algorithms, an elementary approach. (NB: van Leeuwen uses the words "saturated decreasing chain in the Young lattice" in the slightly nonstandard meaning of "sequence $\left(\lambda_{\left[0\right]}, \lambda_{\left[1\right]}, \ldots, \lambda_{\left[k\right]}\right)$ of partitions such that $\lambda_{\left[k\right]} = (0)$ and such that every $i \in \left\{0,1,\ldots,k-1\right\}$ satisfies $\lambda_{\left[i+1\right]} \in \left(\lambda_{\left[i\right]}\right)^-$.)