Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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 \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 correspondance with the number of involutions?

share|cite|improve this question

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

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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