Can any one help me in proving the following equality:


$$n^n= \sum\_{i=1}^n {n \choose i}\cdot i^{i-1}\cdot (n-i)^{n-i}$$


I tried some different ideas but none of them worked!



Combinatorial equation
Your equation can be written as an equation for exponential generating functions: $f(x) = g(x)(f(x)+1)$, where $$f(x) = \sum\_{n\ge1}n^nx^n/n!$$ and $$g(x) = \sum\_{n\ge1}n^{n-1}x^n/n!$$


We can see that for those $f(x)$ and $g(x)$, we have $f(x) = xg'(x)$. If we then solve the differential equation $$xg'(x) = \frac{g(x)}{1-g(x)}$$ with $g(0)=0$, we get that the solution satisfies $x=g(x)e^{-g(x)}$.


By the Lagrange inversion formula, the computational inverse of $xe^{-x}$ is exactly our $g(x)$.


I'm sure some permutation of the reasoning steps above gives a proof for your equation.


