## 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!

-
Why do you know this equality is true? is this something you've been asked to work out? – Yemon Choi Oct 24 2010 at 2:02
@Thierry: $0^0=1$ here. – Mark Sapir Oct 24 2010 at 2:19
I would prefer if this question had (a) more motivation, (b) a better title. I think that (b) is the more important one: there are many "combinatorial equations", and so you should try to rewrite the title to include a focused version of your question. (Remember that titles can be 240 characters --- if it fits in a tweet, it fits as a title on mathoverflow.) – Theo Johnson-Freyd Oct 24 2010 at 3:00
Mark, there are many reasons why one might not post a solution to a problem, and being unable to solve the problem is only one of them. I'm of the opinion that little is to be gained in public speculation about the mathematical abilities of fellow members of MO. – Gerry Myerson Oct 24 2010 at 5:34
Downvoted because I would like to see less questions like this in the future. On the other hand this question is perfect for artofproblemsolving. – Gjergji Zaimi Oct 24 2010 at 19:01
show 12 more comments

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.

-
Thanks for your answer. Actually, I did not want to use Lagrangian inversion formula!. I was hoping if one can give me a combinatorial proof for this. For example, n^n is the number of functions from {1..n} to {1..n} or it can be considered as the number of strings with length n over alphabet {1..n}. But I could not find a way to count the same objects using the right-hand side of the equation. – Amir Oct 24 2010 at 2:37
The identity is a special case of a class of identities known as "Abel's (binomial) identity." See for instance mathworld.wolfram.com/BinomialIdentity.html. For a more general result, see Exercise 5.31 of my book Enumerative Combinatorics, vol. 2. – Richard Stanley Oct 24 2010 at 2:46
@Richard: Is there a "1:1 correspondence" type proof of it. Say, if you, indeed, represent $n^n$ as the size of the set of all functions $\{1,..,n\}$ to itself? – Mark Sapir Oct 24 2010 at 2:54

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.

-
 At the end of paragraph 2, you may want to replace "it is nonempty" with "$\mathcal{R}$ is nonempty", and $R$ with $\mathcal{R}$ in the parentheses. – S. Carnahan♦ Oct 24 2010 at 11:53 @Scott: I had some Ls and Rs mixed up in that paragraph --- thanks for catching it. – Theo Johnson-Freyd Oct 24 2010 at 18:57

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.

-
 I guess there are some typos in your equations. Based on (5), it should be $(y+ai)^{n-i}$ – Amir Oct 24 2010 at 3:14 Thanks -- they're fixed now. – Faisal Oct 24 2010 at 3:17

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

-
 Huh. My solution above is almost exactly the same as David Eppstein's solution. I do read your blog, but not carefully or religiously, so I might have seen it there. Anyway, nice problem! – Theo Johnson-Freyd Oct 25 2010 at 0:57 Or: possibly you've seen Joyal's stunningly beautiful proof of Cayley's theorem? I think the solution due to you and David would come naturally to someone who's taken Joyal's proof to heart; it's certainly the solution that came naturally to me. – Todd Trimble Oct 25 2010 at 2:08

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.

-