4
$\begingroup$

Let $\mathfrak{S}_n$ be the permutation group on $[n]$. Denote the cardinality of $\{\pi\in\mathfrak{S}_n: \pi^2=id\}$, the set of involutions, by $I(n)$. It is well-known that these numbers have the exponential generating function $$\sum_{n\geq0}I(n)\frac{x^n}{n!}=e^{x+\frac12x^2}.$$

After these preparations, we wish to tackle the problem of computing arbitrary order derivatives of the function $f(x)=e^{x+\frac12x^2}$, which sure get complicated very quickly.

Question. Instead, is it true we could bypass this with $$\frac{D^mf(x)}{f(x)}=(x+I)^m?$$

In umbral notation, one writes $I^k=I(k)$.

I wish to see combinatorial arguments; if not, other cute proofs will do.

$\endgroup$

2 Answers 2

4
$\begingroup$

Here is what I would consider a "cute proof." Write \begin{eqnarray*} \sum_{m\geq 0} D^mf(x) \frac{t^m}{m!} & = & f(x+t)\\ & = & f(x)e^{t+\frac 12t^2 +tx}. \end{eqnarray*} We get your formula by taking the coefficient of $t^m/m!$ in the product $$ e^{t+\frac 12t^2}e^{tx}. $$ Note also that directly from the Exponential Formula we get the equivalent formulation $$ (x+I)^m = \sum_w (1+x)^{c_1(w)}, $$ where the sum is over all involutions $w\in\mathfrak{S}_m$, and $c_1(w)$ is the number of fixed points of $w$.

$\endgroup$
1
  • $\begingroup$ Cool, up-voted. $\endgroup$ Dec 21, 2016 at 19:00
3
$\begingroup$

Taylor's theorem is often an effective way of finding formulas for higher derivatives. With $f(x) = e^{x+x^2/2}$, we have $$ \begin{aligned} \sum_{m=0}^\infty D^m f(x)\frac{y^m}{m!} &=f(x+y)\\ &= e^{x+y +(x+y)^2/2}\\ &=f(x) e^{xy}f(y). \end{aligned} $$ Thus $D^m f(x)/f(x)$ is the coefficient of $y^m/m$ in $e^{xy}f(y)$, which is $$\sum_{i=0}^m \binom{m}{i} x^i I(m-i)=(x+I)^m.$$ It's not hard to give a corresponding combinatorial proof.

We can also give an umbral proof, though the proof isn't really any shorter and the computation is similar. We first show that for any polynomial $p$ we have (umbrally) $$p(I)e^{xI}=p(x+I) e^{x+x^2/2}.\tag{$*$}$$ To do this we check that $(*)$ holds for $p(z) = e^{uz}$, where both sides are equal to $f(u+x)$. Then by equating coefficients of $u^m/m!$ we see that $(*)$ holds for $p(z) = z^m$, so by linearity it holds for any polynomial.

Then $$ D^m f(x) = I^m e^{xI}=(x+I)^m e^{x+x^2/2} = (x+I)^m f(x). $$

$\endgroup$
1
  • $\begingroup$ Cool, up-voted. $\endgroup$ Dec 21, 2016 at 18:59

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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