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.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.