# Number of Standard Young Tableaux of n cells

I know there is a 1-1 correspondance 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 $$a_{n+1}=a_n+na_{n-1}$$ How can we prove that the number of standard young tableaux of $n$ cells also satisfies this relation without using the correspondance 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)^-$.)

-