# Enumerative Combinatorics Problem

I'm working on a problem from Enumerative Combinatorics by Richard Stanley. Problem 7 Section 1 says

Let $e^{x+\frac{x^2}{2}}=\sum_{n\geq 0}f(n)\frac{x^n}{n!}$. Find a simple expression for $\sum_{i=0}^n(-1)^{n-i}\binom{n}{i}f(i)$.

Earlier in the section $f(n)$ is defined to be $\sum_{j\geq 0}\binom{n}{2j}\frac{(2j)!}{2^j j!}$, but I suspect that we should be able to do the problem without that.

We tried using a recurrence relation, and that seemed to lead no where. We thought we were clever and tried substituting $x+1$ in for $x$ to pick up the binomial terms, but soon found we were not actually clever.

Any suggestions of how to move forward?

• Hint: the binomial convolution is equivalent to multplication by a certain EGF. – Marko Riedel Sep 24 '15 at 22:01

Just expanding Marko Riedel's comment, $$\begin{eqnarray*}e^{-x}\sum_{n\geq 0}f(n)\frac{x^n}{n!}&=&\left(\sum_{m\geq 0}(-1)^m\frac{x^{m}}{m!}\right)\left(\sum_{n\geq 0}f(n)\frac{x^n}{n!}\right)\\&=&\sum_{r\geq 0}x^r\sum_{h=0}^{r}\frac{(-1)^{r-h}}{(r-h)!h!}\,f(h)\\&=&\sum_{r\geq 0}\frac{x^r}{r!}\sum_{h=0}^{r}(-1)^{r-h}\binom{r}{h}\,f(h).\tag{1}\end{eqnarray*}$$ On the other hand, the LHS of $(1)$ equals: $$e^{x^2/2}=\sum_{p\geq 0}\frac{x^{2p}}{2^p\,p!}=\sum_{p\geq 0}\frac{x^{2q}}{(2p)!}\cdot\frac{(2p)!}{2^p\,p!}\tag{2}$$ so your sum equals zero if $n$ is odd and $\large\frac{n!}{2^{n/2}(n/2)!}$ otherwise.
If an exponential generating function (egf) $F$ counts objects in some combinatorial class $\mathcal{F}$, then $e^F$ counts ways to construct objects with parts in $\mathcal{F}$ with relabeling. So, what does the egf $F$ count? $F$ counts cycles on one and two elements (there is one of each kind), so $e^F$ counts involutions.
Now let property $P_i$, $1\le i\le n$, be that $i$ is in a $1$-cycle (a fixed point). Then by the Inclusion-Exclusion Principle the expression you want to simplify is exactly the number of objects that have none of these properties, i.e. we are counting involutions with no $1$-cycles, i.e. with just the $2$-cycles. Thus, the generating function for those is $e^{x^2/2}$, from which you can extract the coefficient at $x^{2n}$.