Young Tableaux generating function

Question

The number of young tableaux of $n$ cells is known to satisfy the recurrence $a_{n+1} = a_{n} + na_{n-1}$. I am trying to find the generating function but I keep getting something dependent on $n$. Here's what I did so far:

Denote by $f(x) = \sum_{n\geq 1}a_nx^n$. We have $\sum_{n \geq 1} a_{n+1}x^n = f(x) + nxf(x)$ (if we assume $a_1 = 1, a_2 = 2$). We can infer that $\sum_{n \geq 1} a_{n+1}x^n = \frac{f(x)}{x} - 1$.

Answer 1

Using $a_{n+1} = a_{n} + n \, a_{n-1}$ with $a_{0} = 1$ then the following exponential generating function can be obtained.

Let $$B(t) = \sum_{n=0}^{\infty} \frac{a_{n}}{n!} \, t^{n}$$ then \begin{align} \sum_{n=0}^{\infty} \frac{a_{n+1}}{n!} \, t^{n} &= \sum_{n=0}^{\infty} \frac{(n+1) \, a_{n+1}}{(n+1)!} \, t^{n} = \frac{d}{dt} \, \sum_{n=1}^{\infty} \frac{a_{n}}{n!} \, t^{n} \\ &= \frac{d}{dt} \left( B(t) - a_{0} \right) = B'(t) \end{align} and \begin{align} \sum_{n=0}^{\infty} \frac{a_{n+1}}{n!} \, t^{n} &= \sum_{n=0}^{\infty} \frac{a_{n}}{n!} \, t^{n} + \sum_{n=0}^{\infty} \frac{n \, a_{n-1}}{n!} \, t^{n} \\ B' &= B + t \, B \end{align} which can be seen as $$ \frac{d}{dt} \, \ln(B) = 1 + t $$ and leads to $$\sum_{n=0}^{\infty} \frac{a_{n}}{n!} \, t^{n} = e^{t + \frac{t^{2}}{2}}.$$

The linear form can be obtained in a similar manor. Let $$A(t) = \sum_{n=0}^{\infty} a_{n} \, t^{n}$$ for: \begin{align} \sum_{n=0}^{\infty} a_{n+2} \, t^{n} &= \sum_{n=0}^{\infty} a_{n+1} \, t^{n} + \sum_{n=0}^{\infty} (n+1) \, a_{n} \, t^{n} \\ \frac{1}{t^2} \, (A - a_{0} - a_{1} \, t) &= \frac{1}{t} \, (A - a_{0}) + \frac{d}{dt} \left( t \, A \right) \\ t^3 \, A' + (t^2 + t -1) \, A &= (a_{0} - a_{1}) \, t - a_{0}. \end{align} Solving this equation leads to $$A(t) = \frac{1}{t} \, e^{\frac{1}{t} - \frac{1}{2 \, t^2}} \, \left( \int_{1}^{t} e^{-\frac{1}{x} + \frac{1}{2 \, x^2}} \, \left(\frac{- a_{0} + (a_{0} - a_{1}) x}{x^2}\right) \, dx + c_{1} \right).$$

From here it is a matter of determining the constants.

Answer 2

The first step is to look in the OEIS and see that this is sequence A000085. The sequence grows so fast that the o.g.f. has radius of convergence $0$. This strongly suggests looking at the e.g.f instead, which in the OEIS entry is given as $\exp(x+x^2/2).$ The question now is how to derive this e.g.f. from the recursion $\;a_{n+1}=a_n+na_{n-1}\;$ and initial values $\;a_0=a_1=1,\;a_2=2.$

There are several methods. First, the OEIS mentions that the e.g.f. $A(x)$ for A000085 satisfies D.E. $A'(x) = A(x)(1+x),\;$ and as mentioned in another answer to this question, and thus leading to $A(x)=\exp(x+x^2/2).\;$ A little different is $\;A''(x) = A'(x)(1+x) + A(x)\;$ which comes directly either from the recursion $\;a_{n+2}=a_{n+1}+(n+1)a_n\;$ or the derivative of the first D.E. for $A(x).$