Intuitive proof of $\sum_{k=1}^{n} \binom{n}{k} k^{k-1} (n-k)^{n-k} = n^n$

Question

Is there an intuitive way, though I am not sure how to find a conceptual proof either, to establish the following identity: $$\sum_{k=1}^{n} \binom{n}{k} k^{k-1} (n-k)^{n-k} = n^n$$ for all natural numbers.

I am thinking about binomial formula $$\sum_{k=0}^n\binom nk x^{n-k}y^k=(x+y)^n$$ but I'm not sure how to use it.

I find this problem tantalizing because it looks as if there should be some sort of intuitive way so that is why I share it here. I am looking for an answer like my question before if possible. Can you find one?

Answer 1

Hint. This may be seen as a particular case of Abel-Hurwitz binomial identity, see a probabilistic explanation here. Combinatorial proofs are given in references $[8,11,19,21]$ of this paper. See also this paper.

Answer 2

Difference operator:$\Delta f(k)=f(k+1)-f(k)$, we get $$ \sum_{k=1}^n\Delta f(k)=f(n+1)-f(0), $$ and we let $$ f(k)=\binom{x}k^p(k!)^py^{-kp}, $$ Apply to above equation, we get $$ \begin{aligned} \Delta f(k) &=\binom{x}{k+1}^p(k+1)!^py^{-kp-p}-\binom{x}k^p(k!)^py^{-kp}\\ &=\binom xk^p(k!)^py^{-p(k+1)}[(x-k)^p-y^p]\\ \end{aligned} $$ By using above sum equation, $$ \begin{aligned} &\sum_{k=0}^n\binom xk^p(k!)^py^{-p(k+1)}[(x-k)^p-y^p]\\ =&\binom x{n+1}^p(n+1)!^py^{-pn-p}-1, \end{aligned} $$ Both sides are multiplied together $y^{pn+p}$, we get $$ \begin{aligned} &\sum_{k=0}^n\binom xk^p(k!)^py^{p(n-k)}[(x-k)^p-y^p]\\ =&\binom x{n+1}^p(n+1)!^p-y^{p(n+1)}, \end{aligned} $$ let $p=1,x=n-1,y=n$, and we obtain $$ \sum_{0\leqslant k\leqslant n-1}\binom{n-1}kn^{n-1-k}(k+1)!=n^n. $$