Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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

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

share|cite|improve this question

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.

share|cite|improve this answer

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.

share|cite|improve this answer
    
+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

Your Answer

 
discard

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