Formula for number of surjective functions in case where codomain is greater than domain We were deriving the formula for number of surjective functions from f: $X \to Y$, where $|X| = n$ and $|Y| = m$. The formula that we have is:
$$\sum_{k=0}^m(-1)^k (m-k)^n {m \choose k}$$
Now, if $m>n$ we have no surjective functions, as codomain is greater than domain and the answer should be zero. The formula gives the right answer, but I cannot figure out why does it work algebraically.
Any hints on why does this sum equals to zero when $m > n$?

There are two proofs I can think of. The first uses exponential generating functions. Note that
$$
\frac{(m-k)^n}{n!}=[x^n]e^{(m-k)x}
$$
Here, $[x^n]$ is the "coefficient-of" operator, so $[x^n]f(x)$ is the coefficent of $x^n$ in the power series $f(x)$. Therefore,
$$
\begin{align}
\sum_{k=0}^m(-1)^k(m-k)^n\binom{m}k
&=n!\sum_{k=0}^m \binom{m}k(-1)^k[x^{n}]e^{(m-k)x}
\\&=n![x^{n}]\sum_{k=0}^m \binom{m}k(-1)^k(e^{x})^{m-k}
\\&=n![x^n](e^x-1)^m
\end{align}
$$
Finally, note $e^x-1=x+x^2/2+\dots$, so that $(e^x-1)^m=x^m+$ higher order terms, meaning the coefficient of $[x^n]$ in $(e^x-1)^m$ is zero when $n<m$.

The second is to note that $\sum_{k=0}^m(-1)^k(m-k)^n\binom{m}k$ is the zeroth term of the $m^{th}$ forward difference of the sequence $a_i=i^n$. Furthermore, for a nonzero polynomial of degree $n$, the forward difference has degree at most $n-1$. For example,
\begin{aligned}
\Delta(i^n)&=(i+1)^n-i^n &&\xrightarrow{i=0}1^n-0^n 
\\
\Delta(\Delta(i^n))&=(i+2)^n-2(i+1)^n+i^n &&\xrightarrow{i=0}2^n-2\cdot 1^n+0^n 
\\
\Delta(\Delta(\Delta(i^n)))&=(i+3)^n-3(i+2)^n+3(i+1)^n-i^n &&\xrightarrow{i=0}3^n-3\cdot 2^n+3\cdot 1^n-0^n
\end{aligned}
Note that on the right, we exactly have the summations for $m=1$, $m=2$, and $m=3$ (respectively), and in the middle column, there are polynomials with degree at most $n-1,n-2$ and $n-3$ (respectively).
