Combinatorial equation

Question

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!

Answer 1

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.

Answer 2

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.

Answer 3

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.

Answer 4

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

Answer 5

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.