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?

  • 2
    $\begingroup$ Hint: the binomial convolution is equivalent to multplication by a certain EGF. $\endgroup$ – 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}$.


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.