# Generating function of $a_n = \sum_{k = 0}^{\lfloor\frac{n}{2}\rfloor}{n \choose 2k}\frac{(2k)!}{k!2^k}$ is $e^{x+x^2/2}$?

I need to prove that the generating function of $a_n = \sum\limits_{k = 0}^{\lfloor\frac{n}{2}\rfloor}{n \choose 2k}\dfrac{(2k)!}{k!2^k}$ is $e^{x+x^2/2}$.

I tried it like this. I know that $e^x=\sum_{i=0}^{\infty}\dfrac{x^i}{i!}$

So $e^{x+x^2/2}=\sum_{i=0}^{\infty}\dfrac{(x(1+\dfrac{x}{2}))^i}{i!}=\sum_{i=0}^{\infty}\dfrac{x^i\sum_{j=0}^i{i\choose j}\left(\dfrac{x}{2}\right)^j}{i!}$

Let's get the coefficient next to $x^k$. $\dfrac{x^i{i\choose j}\left(\dfrac{x}{2}\right)^j}{i!}$ will have an $x$ in $k$'th power, when $i+j=k$ and $j\leq i \leftrightarrow j\leq k-j \leftrightarrow 2j\leq k$ Let's put $i=k-j$ , then $\dfrac{x^{k}{k-j\choose j}}{(k-j)! 2^j}$

An I'm stuck...

Think of $e^{x+x^2/2}$ as $e^x\cdot e^{x^2/2}$: the series is

$$\left(\sum_{n\ge 0}\frac1{n!}\left(\frac{x^2}2\right)^n\right)\left(\sum_{n\ge 0}\frac{x^n}{n!}\right)=\left(\sum_{n\ge 0}\frac{x^{2n}}{2^nn!}\right)\left(\sum_{n\ge 0}\frac{x^n}{n!}\right)\;,$$

in which the $x^n$ term is

\begin{align*} \sum_{k=0}^{\lfloor n/2\rfloor}\left(\frac1{2^kk!}\cdot\frac1{(n-2k)!}\right)x^n&=\sum_{k=0}^{\lfloor n/2\rfloor}\frac{n!}{2^kk!(n-2k)!}\left(\frac{x^n}{n!}\right)\\\\ &=\sum_{k=0}^{\lfloor n/2\rfloor}\left(\frac{n!}{(2k)!(n-2k)!}\cdot\frac{(2k)!}{2^kk!}\cdot\frac{x^n}{n!}\right)\\\\ &=\sum_{k=0}^{\lfloor n/2\rfloor}\binom{n}{2k}\frac{(2k)!}{2^kk!}\left(\frac{x^n}{n!}\right)\\\\ &=a_n\left(\frac{x^n}{n!}\right)\;, \end{align*}

so $e^{x+x^2/2}$ is the exponential generating function of $\langle a_n:n\in\Bbb N\rangle$.

Here is a combinatorial proof. Note that the species of involutions (permutations $\sigma$ such that $\sigma^2 = \mathrm{Id}$) is given by $$\mathfrak{P}(\mathfrak{C}_{=1}(\mathcal{Z})+\mathfrak{C}_{=2}(\mathcal{Z})).$$ Therefore it has EGF $$f(z) = \exp(z+z^2/2).$$ Now to prove that $f(z)$ is the EGF of $$\sum_{k=0}^{\lfloor n/2\rfloor} {n\choose 2k} \frac{(2k)!}{k! 2^k}$$ we just need to show that the above sum counts involutions.

This is straightforward to see. Choose $2k$ elements from $n$ that will form two-cycles and let the rest be fixed points. Line up your $2k$ elements from left to right getting $(2k)!$ permutations and form two-cycles from adjacent elements. Then we need to divide by $2^k$ because the cycle $(a,b)$ is the same as $(b,a).$ Moreover every permutation of two-cycles shows up $k!$ times on the line. This concludes the argument.