# Proof of a combinatorial equation

How can we use elementary methods to prove that

$$\sum_{i = 2}^{n}{{n \choose i} i! n^{n - i}} = \sum_{i = 1}^{n - 1}{{n \choose i}i^i (n - i)^{n - i}}$$

for any integer $n \geq 0$?

The values of each side for fixed $n$ are 0, 0, 2, 24, 312, 4720, ... (A001864 - OEIS).

Everything is already contained in OEIS comments for A001864 and A000435 (a remarkable comment is that A000435 is the sequence that started it all: the first sequence in the database!)

We take $n$ labelled vertices, consider all trees on them, and sum up the distances between all pairs of vertices (each distance counted twice).

One way to do it is the following: this sum is the number of 5-tuples $(T,a,b,c,d)$ such that $T$ is a tree, $a,b,c,d$ are vertices, $ab$ is an edge of $T$ and this edge belongs to the path between $c$ and $d$ (in the order $cabd$ on the path). If we remove $ab$, we get two connected components $A\ni a$, $B\ni b$. If $|A|=i$, $|B|=n-i$, we may fix $A$, $B$ by $\binom{n}i$ ways, after that fix restrictions of $T$ onto $A$, $B$ by $i^{i-2}(n-i)^{n-i-2}$ ways and fix $a,b,c,d$ by $i^2(n-i)^2$ ways. Totally we get RHS of your formula.

Why we get LHS is explained in Claude Lenormand's comment for A000435 (there we count the sum of distances from the fixed vertex 0 to other vertices in all trees, of course it is $n$ times less than the sum of all distances.)

• Really nice combinatorial interpretation! – Sam Hopkins Aug 22 '18 at 16:16
• Thanks for inspiration. It should be the most appropriate interpretation if we focus on combinatorics. By the way, it would be better if it is mentioned that "total height of rooted trees with $n$ labeled nodes" is equal to "total length of directed simple paths of unrooted trees with $n$ labeled nodes". – Jingzhe Tang Aug 25 '18 at 21:50
• mentioned where, here or on OEIS? It is not quite the same, but the ratio equals $n$. – Fedor Petrov Aug 25 '18 at 22:40

Let $$\mathbb{N}=\left\{ 0,1,2,\ldots\right\}$$. The following fact I have seen referred to as the "Cauchy identity":

Theorem 1. Let $$n\in\mathbb{N}$$. Then, $$\begin{equation} \sum_{k=0}^n \dbinom{n}{k} \left( X+k\right) ^k \left( Y-k\right) ^{n-k} =\sum_{t=0}^n \dfrac{n!}{t!}\left( X+Y\right) ^t \end{equation}$$ in the polynomial ring $$\mathbb{Z}\left[ X,Y\right]$$.

One proof of Theorem 1 can be found in Darij Grinberg, 6th QEDMO 2009, Problem 4 (the Cauchy identity). A simpler proof can be found in the solution of Exercise 1 (a) in UMN Fall 2018 Math 5705 midterm #3 (this one was found by Tomoya Imaizumi, a student in that class). (My exercise uses two rational numbers $$x$$ and $$y$$ instead of the indeterminates $$X$$ and $$Y$$, but the proof does not care.) Alternatively, Theorem 1 is the particular case (for $$\mathbb{L}=\mathbb{Z}\left[ X,Y\right]$$, $$S=\left\{ 1,2,\ldots ,n\right\}$$ and $$x_{s}=1$$) of Theorem 2.2 in Darij Grinberg, Noncommutative Abel-like identities. More directly, it is the particular case (for $$Z=1$$) of equality (1) in the latter reference, where I also cite other sources.

Corollary 2. Let $$n\in\mathbb{N}$$. Then, $$\begin{equation} \sum_{i=0}^n \dbinom{n}{i}i^i \left( n-i\right) ^{n-i} =\sum_{i=0}^n \dbinom{n}{i}i!n^{n-i}. \end{equation}$$

Proof of Corollary 2. Theorem 1 is an equality between two polynomials. Renaming the summation index $$k$$ as $$i$$ in this equality, we obtain $$\begin{equation} \sum_{i=0}^n \dbinom{n}{i}\left( X+i\right) ^i \left( Y-i\right) ^{n-i}=\sum_{t=0}^n \dfrac{n!}{t!}\left( X+Y\right) ^t . \end{equation}$$ Substituting $$0$$ and $$n$$ for $$X$$ and $$Y$$ in this equality, we find \begin{align*} & \sum_{i=0}^n \dbinom{n}{i}i^i \left( n-i\right) ^{n-i}\\ & =\sum_{t=0}^n \dfrac{n!}{t!}n^t \\ & =\sum_{i=0}^n \underbrace{\dfrac{n!}{\left( n-i\right) !}}_{=\dbinom {n}{i}i!}n^{n-i}\qquad\left( \begin{array} [c]{c} \text{here, we have substituted }n-i\text{ for }t\\ \text{in the sum} \end{array} \right) \\ & =\sum_{i=0}^n \dbinom{n}{i}i!n^{n-i}. \end{align*} This proves Corollary 2. $$\blacksquare$$

Are there combinatorial proofs of Corollary 2? I'm pretty sure that the answer is "Yes", and I suspect that they involve counting some sort of functions from $$\left\{ 1,2,\ldots,n\right\}$$ to $$\left\{ 1,2,\ldots,n\right\}$$ with some specific conditions on their recurrent values.

Corollary 3. Let $$n\in\mathbb{N}$$. Then, $$\begin{equation} \sum_{i=2}^n \dbinom{n}{i}i!n^{n-i} =\sum_{i=1}^{n-1}\dbinom{n}{i}i^i \left( n-i\right) ^{n-i}. \end{equation}$$

Proof of Corollary 3. If $$n\leq1$$, then both sides are $$0$$, whence the equality follows. Hence, we WLOG assume that $$n>1$$. Thus, \begin{align*} & \sum_{i=0}^n \dbinom{n}{i}i^i \left( n-i\right) ^{n-i}\\ & =\underbrace{\dbinom{n}{0}}_{=1}\underbrace{0^{0}}_{=1}\underbrace{\left( n-0\right) ^{n-0}}_{=n^n }+\sum_{i=1}^{n-1}\dbinom{n}{i}i^i \left( n-i\right) ^{n-i}+\underbrace{\dbinom{n}{n}}_{=1}n^n \underbrace{\left( n-n\right) ^{n-n}}_{=0^{0}=1}\\ & =n^n +\sum_{i=1}^{n-1}\dbinom{n}{i}i^i \left( n-i\right) ^{n-i}+n^n . \end{align*} Comparing this with \begin{align*} & \sum_{i=0}^n \dbinom{n}{i}i^i \left( n-i\right) ^{n-i}\\ & =\sum_{i=0}^n \dbinom{n}{i}i!n^{n-i}\qquad\left( \text{by Corollary 2}\right) \\ & =\underbrace{\dbinom{n}{0}}_{=1}\underbrace{0!}_{=1}\underbrace{n^{n-0} }_{=n^n }+\underbrace{\dbinom{n}{1}}_{=n}\underbrace{1!}_{=1}n^{n-1} +\sum_{i=2}^n \dbinom{n}{i}i!n^{n-i}\\ & =n^n +\underbrace{nn^{n-1}}_{=n^n }+\sum_{i=2}^n \dbinom{n}{i} i!n^{n-i}=n^n +n^n +\sum_{i=2}^n \dbinom{n}{i}i!n^{n-i}, \end{align*} we obtain \begin{align*} n^n +n^n +\sum_{i=2}^n \dbinom{n}{i}i!n^{n-i}=n^n +\sum_{i=1}^{n-1} \dbinom{n}{i}i^i \left( n-i\right) ^{n-i}+n^n . \end{align*} Subtracting $$n^n +n^n$$ from both sides of this equality, we obtain $$\begin{equation} \sum_{i=2}^n \dbinom{n}{i}i!n^{n-i}=\sum_{i=1}^{n-1}\dbinom{n}{i}i^i \left( n-i\right) ^{n-i}. \end{equation}$$ This proves Corollary 3. $$\blacksquare$$

A standard approach to proving this kind of identity is to use differences of polynomials.

First note that if change the limits on both sums to 0 and $n$, then we add two terms on the left and two terms on the right, and each of the four additional terms is equal to $n^n$. So we may instead prove the modified identity in which each sum goes from 0 to $n$.

We have \begin{aligned} \sum_{i=0}^n \binom ni i^i (n-i)^{n-i}&=\sum_{i=0}^n \binom ni i^i \sum_{j=0}^{n-i} \binom{n-i}{j} n^j (-i)^{n-i-j}\\ &=\sum_{j=0}^n \binom nj n^j \sum_{i=0}^{n-j}(-1)^{n-i-j}\binom{n-j}{i}i^{n-j}.\end{aligned} The inner sum on the right is the $(n-j)$th difference of a polynomial in $i$ of degree $n-j$ with leading coefficient 1, and is therefore equal to $(n-j)!$. Thus the sum is equal to $$\sum_j \binom nj n^j (n-j)! = \sum_{i=0}^n \binom ni i!\, n^{n-i}.$$

Here is an alternative proof of the Cauchy identity.

Fix constants $x$ and $y$ and consider $C=(x\partial_s+y+\partial_s\partial_t-\partial_t)^n(e^{se^t})|_{s=t=0}$.

Dealing with the $s$ terms and then $t$ terms gives \begin{align} C&=\sum_{k=0}^n{n\choose k}(x\partial_s+\partial_s\partial_t)^k(y-\partial_t)^{n-k}(e^{se^t})|_{s=t=0}\\ &=\sum_{k=0}^n{n\choose k}(x+\partial_t)^k(y-\partial_t)^{n-k}(e^{kt+se^t})|_{s=t=0}\\ &=\sum_{k=0}^n{n\choose k}(x+\partial_t)^k(y-\partial_t)^{n-k}(e^{kt})|_{t=0}\\ &=\sum_{k=0}^n{n\choose k}(x+k)^k(y-k)^{n-k}(e^{kt})|_{t=0}\\ &=\sum_{k=0}^n{n\choose k}(x+k)^k(y-k)^{n-k}. \end{align} The reverse order gives \begin{align} C&=\sum_{k=0}^n{n\choose k}(x\partial_s+y)^k(\partial_s\partial_t-\partial_t)^{n-k}(e^{se^t})|_{s=t=0}\\ &=\sum_{k=0}^n{n\choose k}(x\partial_s+y)^k(\partial_s-1)^{n-k}(p(s)e^{s})|_{s=0}, \end{align} where $p(s)$ is a polynomial with initial term $s^{n-k}$. Hence \begin{align} C&=\sum_{k=0}^n{n\choose k}(x\partial_s+y)^k((n-k)!e^{s})|_{s=0}\\ &=\sum_{k=0}^n{n\choose k}(x+y)^k((n-k)!e^{s})|_{s=0}\\ &=\sum_{k=0}^n\frac{n!}{k!}(x+y)^k. \end{align}

• How do you get $p\left(s\right)$ and its initial term? And why does $\left(\partial_s-1\right)^{n-k}$ take $p\left(s\right)e^s$ to $\left(n-k\right)! e^s$ ? – darij grinberg Aug 22 '18 at 22:03
• @darijgrinberg By induction, $\partial_t^m e^{se^t}$ is a sum of terms of the form $q(s)e^{kt+se^t}$ for all $m$. There's exactly one term where the $\partial_t$ pulled out an $s$ each time, so $p(s)$ has degree $n-k$ and leading coefficient $1$. For the latter point, note that $(\partial_s-1)(p(s)e^s)=p'(s)e^s$. – MTyson Aug 22 '18 at 22:23
• Ah. Since I can't quite follow your "$\partial_t$ pulled out an $s$" argument, let me re-argue your first claim in my language: For each $m \geq 0$, there is a sequence $\left(q_{m,0}, q_{m,1}, q_{m,2}, \ldots\right)$ of univariate polynomials such that $\partial^m_t e^{se^t} = \sum\limits_{k=0}^{\infty} q_{m,k}\left(s\right) e^{kt+se^t}$, and such that $q_{m,k} = 0$ for all $k > m$. This is proven by induction on $m$, and this argument also shows that $q_{m,k} = k q_{m-1,k} + s q_{m-1,k-1}$ for all $m$ and $k$, where $q_{m-1,k-1}$ is understood to be $0$ if $k = 0$. This ... – darij grinberg Aug 23 '18 at 0:15
• ... recursive equation (along with the fact that $q_{0,k}$ is the Kronecker delta $\delta_{0,k}$ for each $k \geq 0$) determines the polynomials $q_{m,k}$ uniquely. Now, set $q_m = \sum\limits_{k=0}^{\infty} q_{m,k}$ for each $m \geq 0$. It is then easy to see that $\left(\partial_t^m e^{se^t}\right)\mid_{t=0} = q_m\left(s\right)$. So we need to show that the leading term of $q_m\left(s\right)$ is $s^m$. But this easily follows from the fact that ... – darij grinberg Aug 23 '18 at 0:20
• ... the polynomial $q_{m,k}\left(s\right)$ equals $s^m$ when $k = m$ but is a linear combination of smaller powers of $s$ when $k \neq m$. (This fact, in turn, can be proven by induction on $m$ using the above recurrence.) – darij grinberg Aug 23 '18 at 0:24

Similar questions can also be dealt with using generating functions and Lagrange inversion.

Let $T(z)$ (the "tree function") be the formal power series satisfying $T(z)=z\,e^{T(z)}$.

If $F$ is a formal power series the coefficients of $G(z):=F(T(z))$ are given by (Lagrange inversion) $$[z^0]G(z)=[z^0] F(z) \mbox{ , } [z^k]G(z)=\tfrac{1}{k} [y^{k-1}] F^\prime(y)\,e^{ky} =[y^k](1-y)F(y)\,e^{ky}\mbox{ for } k\geq 1\;.$$ In particular
$$T(z)=\sum_{n\geq 1}\frac{n^{n-1}}{n!}z^n \;\mbox{ and }\; \frac{T(z)}{1-T(z)}=\sum_{n\geq 1}\frac{n^{n}}{n!}z^n$$ When you divide the rhs of your equation above by $n!$ you clearly get the $n$-th coefficient of the convolution of the series $a_0:=0, a_k:=\frac{k^k}{k!}\;\;{k\geq 1}$ (i.e. the coefficients of ${T(z) \over 1-T(z)}$) with itself.

Therefore \begin{align*}\sum_{i=1}^{n-1} {n \choose i} i^i(n-i)^{n-i}&=n!\,[z^n] \bigg({T(z) \over 1-T(z)}\bigg)^2\\ &=n!\,[y^n] (1-y) {y^2 \over (1-y)^2}\,e^{ny}\\ &=n!\,[y^{n-2}] {e^{ny} \over 1-y}=n!\sum_{i=0}^{n-2}{n^i \over i!} \end{align*} which is what you want.

Remark: the exponential generating function $\big({T(z) \over 1-T(z)}\big)^2$ for the rhs was already given by Vladeta Jovovic in the notes to A001864 - OEIS

Here is an alternative.

Define the functions $A_n(t)=\sum_k\binom{n}kt(t+k)^{k-1}(n-k)^{n-k}, B_n(t)=\sum_k\frac{n!}{(n-k)!}(t+n)^{n-k}$ and $C_n(t)=\sum_k\binom{n}k(t+k)^k(n-k)^{n-k}$.

From $(t+k)^k=t(t+k)^{k-1}+k(t+k)^{k-1}$ and on the basis of Abel's identity, one gets $C_n(t)=A_n(t)+nC_{n-1}(t+1)=(t+n)^n+nC_{n-1}(t+1)$. It is easy to check that $B_n(t)=(t+n)^n+nB_{n-1}(t+1)$. Since both $B_n$ and $C_n$ satisfy the same initial conditions, it follows $B_n(t)=C_n(t)$. So, $B_n(0)=C_n(0)$ gives the desired result.