Identity with number of surjective functions Let $S(n,k)$ denote the number of surjective functions from $\{1,2\cdots,n\}$ onto $\{1,2,\cdots,k\}$. I  have verified for $n = 2, 4, 6, 8, 10$ that
$$-(1/2)S(n,1) + (1/4)S(n,2) - (1/8)S(n,3) + \cdots + (-1/2)^n S(n,n) = 0$$
Is this true for all positive even n? Is it a known identity? Any nice proof?
 A: I’ll leave it to you to decide whether this is a “nice” proof – I certainly had fun finding it :-) I suspect there’s an elegant and shorter combinatorial proof, though.
In terms of the Stirling numbers of the second kind $\def\stir#1#2{\left\{#1\atop#2\right\}}\stir nk$, there are $k!\stir nk$ surjective functions from $[n]$ to $[k]$. The ordinary generating function for the $\stir nk$ with respect to the lower index $k$ is the $n$-th Touchard polynomial:
$$
T_n(x)=\sum_{k=0}^n\stir nkx^k\;.
$$
These polynomials have an interesting series representation (see Equation $(4.2.16)$ on page $116$ in generatingfunctionology):
$$
T_n(x)=\mathrm e^{-x}\sum_{r=0}^\infty\frac{x^rr^n}{r!}\;.
$$
We can use this to obtain the generating function $F_n(x)$ for the number of surjective functions, with an extra factor $k!$:
\begin{eqnarray}
F_n(x)
&=&
\sum_{k=0}^n\stir nkk!x^k
\\
&=&
\sum_{k=0}^n\stir nkx^k\int_0^\infty\mathrm e^{-y}y^k\mathrm dy
\\
&=&
\int_0^\infty\mathrm e^{-y}\sum_{k=0}^n\stir nk(xy)^k\mathrm dy
\\
&=&
\int_0^\infty\mathrm e^{-y}T_n(xy)\mathrm dy
\\
&=&
\int_0^\infty\mathrm e^{-y}\mathrm e^{-xy}\sum_{r=0}^\infty\frac{(xy)^rr^n}{r!}\mathrm dy
\\
&=&
\sum_{r=0}^\infty\frac{x^rr^n}{r!}\int_0^\infty\mathrm e^{-y}\mathrm e^{-(1+x)y}y^r\mathrm dy
\\
&=&
\sum_{r=0}^\infty\frac{x^rr^n}{r!}\frac{r!}{(1+x)^{r+1}}
\\
&=&
\frac1{1+x}\sum_{r=0}^\infty\left(\frac x{1+x}\right)^rr^n
\end{eqnarray}
We want to show that this is zero at $x=-\frac12$. The factor in parentheses is $-1$ at this point, so the series diverges and we have to take the limit $x\searrow-\frac12$. (Remember that this is actually a polynomial, written as an infinite series.) Now for $n\gt0$
\begin{eqnarray}
\sum_{r=0}^\infty z^rr^n
&=&
\left(z\frac{\mathrm d}{\mathrm d z}\right)^n\sum_{r=0}^\infty z^r
\\
&=&
\left(z\frac{\mathrm d}{\mathrm d z}\right)^n\frac1{1-z}
\\
&=&
\left(\frac{\mathrm d}{\mathrm d\log z}\right)^n\frac1{1-z}
\\
&=&
\frac{\mathrm d^n}{\mathrm dt^n}\frac1{1-\mathrm e^t}
\\
&=&
\frac{\mathrm d^n}{\mathrm dt^n}\left(\frac1{1-\mathrm e^t}-\frac12\right)
\\
&=&
\frac12\frac{\mathrm d^n}{\mathrm dt^n}\frac{1+\mathrm e^t}{1-\mathrm e^t}
\\
&=&
\frac12\frac{\mathrm d^n}{\mathrm dt^n}\frac{\mathrm e^{-\frac t2}+\mathrm e^{\frac t2}}{\mathrm e^{-\frac t2}-\mathrm e^{\frac t2}}\;.
\end{eqnarray}
This is the $n$-th derivative of an odd function, so for even $n$ it’s zero at $t=0$, which corresponds to $z=1$ and $x=-\frac12$. Thus, for even $n\gt0$ we have $F_n\left(-\frac12\right)=0$.
A: Following @joriki we try to evaluate (formal power series)
$$\sum_{q=1}^n (-1/2)^q q! {n\brace q}
= n! [z^n] \sum_{q=1}^n (-1/2)^q (\exp(z)-1)^q.$$
With $n\ge 1$ we can include $q=0$ with no change. Also since
$\exp(z)-1 = z + \cdots$ we can also include $q\gt n$ for no extra
contribution. We get
$$n! [z^n] \frac{1}{1+(\exp(z)-1)/2}
= n! [z^n] \frac{2}{1+\exp(z)}.$$
Now
$$[z^{2n}] \frac{2}{1+\exp(z)}
= \frac{1}{2} [z^{2n}] \frac{2}{1+\exp(z)}
+ \frac{1}{2} [z^{2n}] \frac{2}{1+\exp(-z)}
\\ = [z^{2n}] \frac{1+\exp(-z)+1+\exp(z)}{1+\exp(z)+\exp(-z)+1}
= [z^{2n}] 1 = 0.$$
