I'm trying to construct the exponential generating function of the sequence $(a_n)_{n\in \mathbb{N}_0}$, with $a_n$ the amount of involutions in $\mathbb{S}_n$. So far I've made a combinatorial argument to determine the known recurrence
$$
a_n = a_{n-1} + (n-1)a_{n-2} \ \ \ (n>2)
$$
by separating in cases whether an involution $\sigma\in\mathbb{S}_n$ fixes $n$ or not. We also have $a_0 = a_1 = 1$. Now, if $f = \sum_{j\geq 0}\frac{a_n}{n!}X^n$ is the exponential generating function for this sequence, we have
$$
f = \sum_{n\geq 0}\frac{a_n}{n!}X^n = 1 + X + \sum_{n\geq 2}\frac{a_n}{n!}X^n = 1 + X + \sum_{n\geq 2}\frac{a_{n-1} + (n-1)a_{n-2}}{n!}X^n = \\
= 1 + X + \sum_{n\geq 2}\frac{a_{n-1}}{n!}X^n +\sum_{n\geq 2}\frac{(n-1)a_{n-2}}{n!}X^n = \\ = 1 + \sum_{n\geq 1}\frac{a_{n-1}}{n!}X^n +\sum_{n\geq 2}\frac{(n-1)a_{n-2}}{n!}X^n
$$
Differentiating at both sides,
$$
f' = \sum_{n\geq 1}\frac{na_{n-1}}{n!}X^{n-1} +\sum_{n\geq 2}\frac{n(n-1)a_{n-2}}{n!}X^{n-1} = \\
= \sum_{n\geq 1}\frac{a_{n-1}}{(n-1)!}X^{n-1} +\sum_{n\geq 2}\frac{a_{n-2}}{(n-2)!}X^{n-1} = \\
= \sum_{n\geq 0}\frac{a_{n}}{n!}X^{n} +\sum_{n\geq 0}\frac{a_{n}}{n!}X^{n+1} = f(1+X)
$$
This leaves us with the following differential equation,
$$
f' = f(1+X), \ f(0) = 1
$$
with solution $f = e^{X + \frac{X^2}{2}}$. Now,
$$
f = e^Xe^{\frac{X^2}{2}} = \sum_{j\geq0}\frac{1}{j!}X^j \cdot \sum_{k\geq0}\frac{1}{2^kk!}X^{2k}.
$$
How can I take it from here to the final 'closed' form of the exponential generating function?
Best Answer
In the product $\;\sum_{j\ge0}\frac{1}{j!}X^j \cdot \sum_{k\ge0}\frac{1}{2^kk!}X^{2k}\;$ multiply out and get $\;\sum_{j,k\ge0}\frac1{j!}\frac1{2^kk!}X^{j+2k}\;$ and let $\;n\!=\!j\!+\!2k\;$ and thus $\;j\!=\!n\!-\!2k.\;$ Now rewrite with $\;n,k\;$ to get $\;\sum_{n\ge0}\Big(\sum_{k=0}^{[n/2]}\frac{n!}{(n-2k)!2^kk!}\Big)X^n.$