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

Question

Given $n$ distinct elements, how many Young Tableaux can one make?

Answer 1

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.

You can use this formula, or careful calculation, to compute the first few values 1, 2, 4, 10, 26, 76, 232, which you can look up in the Online Encyclopedia of Integer Sequences to find it was sequence A000085, and to see a lot more information and references about this sequence. This is a useful technique for recognizing other sequences: compute a few values, and then use the OEIS.

Answer 2

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.