Is there a bijective proof of this identity? I am interested in finding a bijective proof of
\begin{equation}
n^n = \displaystyle\sum_{k=1}^n \binom{n}{k}(n-k)^{n-k}k^{k-1}
\end{equation}
It seems like there should be such a proof where the left side of the above equation is interpreted as functions from a set of size $n$ to itself and the right side represents some partitioning of this set of functions.
 A: As noted in the comments, $n^{n-2}$ is the number of labelled trees on $n$ vertices. Hence $n^{n-1}$ is the number of labelled trees on $n$ vertices with one marked vertex and $n^n$ is the number of labelled trees on $n$ vertices with two marked vertices (which can be the same).
We wish to show that
\begin{equation}
n^n = \displaystyle\sum_{k=1}^n \binom{n}{k}(n-k)^{n-k}k^{k-1}
\end{equation}
The left side of this is the number of labelled trees on $n$ vertices with one vertex colored red and one vertex colored blue (the red and blue vertices can be the same). 
If the red and blue vertices are the same, then this is just the number of labelled trees on $n$ vertices with a single vertex marked, namely $n^{n-1}$, which is the $k = n$ term of the sum.
If the red and blue vertices are distinct, consider the unique path from the red vertex to the blue vertex. Now do the following: mark the vertex following the red vertex green and cut the first edge of this path. (Note that the green vertex and the blue vertex may be the same.) 
This produces two labelled trees on non-empty complimentary subsets of $\{1,...,n\}$, one of which has a blue and green vertex marked and the other has a single red vertex marked. 
Moreover, by joining the green and red vertices with an edge and forgetting about the green label, we can invert this procedure.
Now, if the size of the labelled tree containing the single red vertex is $k$, then the number of pairs of trees is
\begin{equation}
\binom{n}{k}(n-k)^{n-k}k^{k-1}
\end{equation}
This follows, since after choosing any subset of $\{1,...,n\}$ of size $k$ for the vertices in the red component, we choose a labelled tree with a single marked vertex for that component and a labelled tree with two marked vertices for its complement. Since the number of choices for the marked, labelled trees are $k^{k-1}$ (only one marked vertex for the red component) and $(n-k)^{n-k}$ (two marked vertices for its complement), we obtain the above expression.
Summing over the possible sizes of the red component after performing this operation, and noting that we already dealt with the case where the red and blue vertices are the same, we obtain the desired formula
\begin{equation}
n^n = \displaystyle\sum_{k=1}^n \binom{n}{k}(n-k)^{n-k}k^{k-1}
\end{equation}
