Combinatorial equation 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!
 A: 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.
A: See Todd and Vishal's blog for some combinatorial proofs and further discussion. 
A: I posted an answer (which I have kept, below the horizontal rule) that starts out combinatorial and then becomes one of algebraic manipulation.  This is, of course, disappointing: algebraic manipulation should code for combinatorics.  No sooner did I click "submit" than I thought of a better answer.
Recall Cayley's formula that there are $n^{n-2}$ spanning trees on $n$ labeled nodes, and hence $n^n$ trees with labeled nodes, a particular node also marked $L$, and a particular node also marked $R$ (we can have $R=L$).  To such a tree $\mathcal T$, do the following.  Create a subset of the nodes $\mathcal L$ as follows: a node is in $\mathcal L$ if and only if its minimal path in the tree to $R$ passes through $L$.  In particular, $L \in \mathcal L$, and we have $R \in \mathcal L$ iff $L=R$.  Let $\mathcal R$ be the rest of the nodes, so that $\mathcal R$ is empty if $L=R$.  Then the restriction of the tree $\mathcal T$ to the subset $\mathcal L$ gives a tree on $|\mathcal L|$ nodes with a marked vertex $L$, and the restriction of $\mathcal T$ to $\mathcal R$, provided $\mathcal R$ is not empty, gives a tree with two marked nodes ($R$ and the unique node in $\mathcal R$ that is adjacent to $L\in \mathcal L$).
Conversely, how can you construct a tree on a set of $n$ labeled nodes?  One way is: first partition the set into two disjoint subsets $\mathcal L$ and $\mathcal R$, where $\mathcal L$ is not empty.  Put on the set $\mathcal L$ a spanning tree, and also mark a node $L$.  Provided $\mathcal R$ is not empty, put on it a spanning tree and mark two nodes ($R$ and $S$, say).  Then build a spanning tree on the whole of $\mathcal L \cup \mathcal R$ by connecting $L$ to $S$.  If $\mathcal R$ is empty, then take as your tree just $\mathcal L$, and let $R=L$.
For each $i = 1,\dots, n$, there are $\binom n i$ ways to pick $\mathcal L$ with $i = |\mathcal L|$.  There are $i^{i-1}$ ways to put a tree on $\mathcal L$ and mark a node $L$.  There are $(n-i)^{n-i}$ ways to put a tree on $\mathcal R$ and mark two nodes, if $n-i\neq 0$, and if $\mathcal R = \emptyset$, then there's $1 = 0^0$ thing to do.  All together, we have:
$$ n^n = \sum_{i=1}^n \binom n i i^{i-1} (n-i)^{n-i}$$
as each side counts the number of trees on $n$ labeled vertices with two marked nodes.

Recall Cayley's formula: the number of spanning trees on $n$ labeled nodes is $n^{n-2}$.  For each tree, pick one of the $n-1$ edges, and pick an endpoint of it: you have just divided the nodes into two sets, neither of which is empty, and each of which has a distinguished vertex and a spanning tree.
Conversely, for each $j = 1,\dots,n-1$, there are $\binom n j$ ways to divide $n$ nodes into a pile of size $j$ and a pile of size $n-j$, and $j^{j-1}$ ways to put a spanning tree and pick a distinguished node from the first pile,and $(n-j)^{n-j}$ ways to pick a spanning tree and a distinguished node for the second pile.
All together, this proves:
$$ 2(n-1)n^{n-2} = \sum_{j=1}^{n-1} \binom n j j^{j-1}(n-j)^{n-j-1} $$
Multiply the left-hand side by $n$ and the $j$th summand on the right-hand side by $j + (n-j)$:
$$ \begin{aligned} 2(n-1)n^{n-1} & = \sum_{j=1}^{n-1} \binom n j j^{j-1}(n-j)^{n-j-1}\bigl(j + (n-j)\bigr) \\
& = \sum_{j=1}^{n-1}\binom n j j^{j}(n-j)^{n-j-1} + \sum_{j=1}^{n-1} \binom n j j^{j-1}(n-j)^{n-j} \\
&= 2\sum_{i=1}^{n-1}\binom n i i^{i-1}(n-i)^{n-i}
\end{aligned} $$
where we recognize that the two sums in the middle line are the same, either $j\mapsto i$ or $j\mapsto n-i$.
Dividing by $2$ and adding $n^{n-1} = \binom n n n^{n-1} 0^0$ to both sides gives your formula.
A: This follows from Abel's binomial theorem (see equation (5) here):
$$ (x+y)^n = \sum_{i=0}^n \binom{n}{i} x(x-ai)^{i-1}(y+ai)^{n-i}. $$
If we take $y=n$ and $a=-1$, we get
$$ (x+n)^n = \sum_{i=0}^n \binom{n}{i} x(x+i)^{i-1}(n-i)^{n-i}. $$
Now differentiate both sides with respect to $x$ and set $x=0$ to get the desired identity.
A: So the left side is the number of ways to tile a 1 x n board with n differently colored tiles, colors c_1, c_2, c_3.... c_n.
the right side seems attainable with letting i be the number of tiles that are colored with a closed subset of nCi tiles. those i tiles can be tiled in i-1 ways (the number of colors that aren't the color of i. the remaining n-i tiles can be tiles in n-i ways (the number of colors not used on the initial tiles. every square is either tiles with one of the i-1 colors or the n-i colors with the combination nCi covering the tiles colored with the last unaccounter for color. Summing for i gives the left side.
oh and Math 300 is the last class im taking(computing) before graduation so i have no idea about how to input the mathML.  
