# Given n distinct elements, how many Young tableaux can you make?

Given n distinct elements, how many Young tableaus can you make?

-

You need to give a bit more context to the question. I could tell you that the answer is

$$a(n+1)= a(n) + na(n-1)$$

starting at $a(0)=1$ and $a(1)=1$, which would enable you to work out the number for any $n$, but this may not be what you are looking for.

-
+1 This method is actually faster than using the formula in the answer by Douglas Zare: only $n-1$ multiplications and $n-1$ additions are required to find $a(n)$. –  Marc van Leeuwen Sep 28 '12 at 9:51
The Robinson-Schensted correspondence is a bijection between permutations on $n$ letters and ordered pairs of tableaux with the same shape. The inverse of a permutation is sent to the reversed pair of tableaux, so the restriction to the diagonal gives a bijection with involutions, permutations of order $1$ or $2$, so that they are equal to their inverses. Given a tableau $T$, $(T,T)$ corresponds to an involution. So, the number of tableaux is the number of involutions in the symmetric group on $n$ letters,
$$\sum_{i=0}^{\lfloor n/2 \rfloor} {n \choose 2i} (2i-1)!!$$
where $i$ counts the number of transpositions in the involution.