0

Sequence A000085 in the On-Line Encyclopedia of Integer Sequences counts the number $A_n$ of involutions on $n$ letters, and also, the number of Young tableaux with $n$ cells.

I am curious, what is the limit of $A_n/A_{n-1}$ as $n\to\infty$ ?

How do you figure that out?

And, if it exists, is it a number of any special significance?

Andrius Kulikauskas
  • 683

1 Answers1

1

The limit does not exist. For example note the recurrence

$$A_n = A_{n-1} + (n-1) A_{n-2}$$

from which you can see that $A_n > (n-1) A_{n-2}$. However it appears that $$\lim_{n \to \infty} {A_n \over \sqrt{n} A_{n-1}} = 1.$$ This should be provable from the asymptotic formula (given in the OEIS entry)

$$ A_n \sim {1 \over \sqrt{2}} * \exp \left( \sqrt{n} - {n \over 2} - {1 \over 4} \right) n^{n/2}. $$

Michael Lugo
  • 22,354
  • thank you! The recurrence makes perfect sense. I did not know how to read the OEIS. :) – Andrius Kulikauskas Oct 26 '17 at 19:38
  • OEIS entries are quite dense, so that's understandable. It also helped that I knew that there is an asymptotic formula for the number of involutions - had I not known I might have given up looking for it. – Michael Lugo Oct 26 '17 at 20:45