Is this identity trivial? $n^n=n!+\sum_{k=1}^{n-1}(-1)^{k+1}\binom{n}{k}(n-k)^n$ If $m$ and $n$ are two positive integers such that $m\ge n$, then it is a standard counting exercise that the number of surjective functions between the sets $\{1, 2, ..., m\}$ and $\{1, 2, ..., n\}$ is $\displaystyle n^m-\sum_{k=1}^{n-1}(-1)^{k+1}\binom{n}{k}(n-k)^m$.
Now, if we let $m=n$ in this formula, we get that the number of permutations of the set $\{1, 2,...,n\}$ equals $ \displaystyle \sum_{k=1}^{n-1}(-1)^{k+1}\binom{n}{k}(n-k)^n$. But we also know that the number of the permutations equals $n!$. Hence, by double counting, we get the identity I mentioned in the title: $$ n^n=n!+\sum_{k=1}^{n-1}(-1)^{k+1}\binom{n}{k}(n-k)^n.$$
Now, I haven't seen this identity before. When we found this in class, we suspected that it is just trivially true, but no one was able to actually show that it is so. I have come across this identity again today while I was revising for my final exam and I couldn't help but wonder whether this is actually trivially true or if there is something more to it. I have tried using the Binomial Theorem, but things only started to look messier. So, I am looking forward to seeing some clever manipulations which may render this trivial (I doubt that it is some remarkable identity, but who knows, maybe I am wrong).
 A: I'm not sure if this counts as "trivial" (and this is at heart identical to your surjections argument) but just note that you are counting the number of functions $\{1,\dots,n\}\to\{1,\dots,n\}$ in two ways.
The LHS is just $n^n$ because each of $1,\dots,n$ is mapped to one of $n$ possible values.
The RHS is inclusion-exclusion, where your sets $A_i$ are the set of all functions that don't include $i\in\{1,\dots,n\}$ in their image. The number of functions that don't hit (at least) $k\geq1$ points is $\binom {n}{k}(n-k)^n$, as you choose $k$ "illegal" points, and then each of $1,\dots,n$ map to any of the other $n-k$ "legal" points.
The $n!$ term is to account for the number of functions that hit every point, i.e. the permutations.
A: It is not quite trivial, but your identity
$$ n^n=n!+\sum_{k=1}^{n-1}(-1)^{k+1}\binom{n}{k}(n-k)^n $$
can be easily simplified to
$$ n!=\sum_{k=0}^n(-1)^k\binom{n}{k}(n-k)^n =
\sum_{k=0}^n(-1)^{n-k}\binom{n}{k}k^n $$
which is well known in combinatorics and proved in
several ways including inclusion-exclusion.
The OEIS sequence A000142
for the factorial sequence has this formula
$$ \sum_{i=0}^n (-1)^i(n-i)^n \binom{n}{i} = n!. $$
Also see
MSE question 1512743
"An identity for the factorial function".
A: Note that the identity can be rearranged to
\begin{eqnarray*}
n!= \sum_{k=0}^{n-1} (-1)^k \binom{n}{k} (n-k)^n =n^n-\binom{n}{1} (n-1)^n+ \cdots.
\end{eqnarray*}
Now condiser maps from $[n]$ to$[n]$, the LHS is permutations of $[n]$.
The RHS counts the permutations using inclusion-exclusion principle.
