3
$\begingroup$

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?

$\endgroup$

1 Answer 1

5
$\begingroup$

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

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