Can any one help me in proving the following equality:
$$n^n= \sum_{i=1}^n {n \choose i}\cdot i^{i1}\cdot (ni)^{ni}$$
I tried some different ideas but none of them worked!
Can any one help me in proving the following equality: $$n^n= \sum_{i=1}^n {n \choose i}\cdot i^{i1}\cdot (ni)^{ni}$$ I tried some different ideas but none of them worked! 


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^{n1}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)}{1g(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. 


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^{n2}$ 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^{i1}$ ways to put a tree on $\mathcal L$ and mark a node $L$. There are $(ni)^{ni}$ ways to put a tree on $\mathcal R$ and mark two nodes, if $ni\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^{i1} (ni)^{ni}$$ 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^{n2}$. For each tree, pick one of the $n1$ 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,n1$, there are $\binom n j$ ways to divide $n$ nodes into a pile of size $j$ and a pile of size $nj$, and $j^{j1}$ ways to put a spanning tree and pick a distinguished node from the first pile,and $(nj)^{nj}$ ways to pick a spanning tree and a distinguished node for the second pile. All together, this proves: $$ 2(n1)n^{n2} = \sum_{j=1}^{n1} \binom n j j^{j1}(nj)^{nj1} $$ Multiply the lefthand side by $n$ and the $j$th summand on the righthand side by $j + (nj)$: $$ \begin{aligned} 2(n1)n^{n1} & = \sum_{j=1}^{n1} \binom n j j^{j1}(nj)^{nj1}\bigl(j + (nj)\bigr) \\ & = \sum_{j=1}^{n1}\binom n j j^{j}(nj)^{nj1} + \sum_{j=1}^{n1} \binom n j j^{j1}(nj)^{nj} \\ &= 2\sum_{i=1}^{n1}\binom n i i^{i1}(ni)^{ni} \end{aligned} $$ where we recognize that the two sums in the middle line are the same, either $j\mapsto i$ or $j\mapsto ni$. Dividing by $2$ and adding $n^{n1} = \binom n n n^{n1} 0^0$ to both sides gives your formula. 


This follows from Abel's binomial theorem (see equation (5) here): $$ (x+y)^n = \sum_{i=0}^n \binom{n}{i} x(xai)^{i1}(y+ai)^{ni}. $$ If we take $y=n$ and $a=1$, we get $$ (x+n)^n = \sum_{i=0}^n \binom{n}{i} x(x+i)^{i1}(ni)^{ni}. $$ Now differentiate both sides with respect to $x$ and set $x=0$ to get the desired identity. 


See Todd and Vishal's blog for some combinatorial proofs and further discussion. 


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 i1 ways (the number of colors that aren't the color of i. the remaining ni tiles can be tiles in ni ways (the number of colors not used on the initial tiles. every square is either tiles with one of the i1 colors or the ni 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. 

