13
$\begingroup$

In process of doing some computations on Hilbert schemes, I stumbled across the following identity, for $k \ge 2$: $$ k^{k-3} = \frac{1}{2} \sum_{i=1}^{k-1} \binom{k-2}{i-1} i^{i-2} (k-i)^{k-i-2} $$ which can be verified computationally for small values of $k$ (I did it for the first 500).

This is actually a special case of a bigger problem, so I'm hoping to get ideas about what methods might be applicable to prove this kind of identity.

I understand that there are good methods for automatically proving hypergeometric identities, but am I correct in thinking that this is not hypergeometric, due to the $k^{k-3}$ type terms?

EDIT Here is a link to the bigger question that I had that this is a special case of: Counting some binary trees with lots of extra stucture

$\endgroup$
16
  • 3
    $\begingroup$ My impression is that (1) this should follow from one of the "Abel identities" in Table 1.2 in §1.5 of Riordan's "Combinatorial identities" book, and (2) there may be a proof using trees. $\endgroup$ Jun 30 '17 at 22:27
  • 2
    $\begingroup$ Let me multiply your identity by $2$ and substitute $n$ and $k$ for your $k-2$ and $i-1$. Then, your identity becomes $2\left(n+2\right)^{n-1} = \sum\limits_{k=0}^n \dbinom{n}{k} \left(k+1\right)^{k-1} \left(n-k+1\right)^{n-k-1}$. The right hand side counts all forests having exactly two connected components on a given $n+2$-element vertex set, but it counts them twice because it enforces an order on the components. The $\left(n+2\right)^{n-1}$ on the left hand side, meanwhile, counts all trees on this vertex set. So why does the equality hold? ... $\endgroup$ Jun 30 '17 at 22:31
  • 4
    $\begingroup$ Also, the identity $2\left(n+2\right)^{n-1} = \sum\limits_{k=0}^n \dbinom{n}{k} \left(k+1\right)^{k-1} \left(n-k+1\right)^{n-k-1}$ is the particular case for $x = 1$, $y = n+1$, $z = -1$ of the identity (2) in Victor J. W. Guo, Bijective proofs of Gould-Mohanty's and Raney-Mohanty's identities, arXiv:1005.4258v1. So, yes, there is at least one bijective proof. Probably an understatement. $\endgroup$ Jun 30 '17 at 22:52
  • 2
    $\begingroup$ @მამუკაჯიბლაძე: No. Such forests would correspond to $k=-1$ or $k=n+1$, both of which are outside of the range. But now that you brought this up, I see that my interpretation in terms of forests was wrong because $\dbinom{n}{k}$ is not the number of ways to choose $k+1$ from the $n+2$ vertices (that would be $\dbinom{n+2}{k+1}$). No wonder I found no multijection then... There is probably still an interpretation using forests, but it should be less obvious (maybe something like what I said, but with two vertices fixed). $\endgroup$ Jul 1 '17 at 0:02
  • 2
    $\begingroup$ ... Cayley's formula), and the probability for such a tree to contain the edge $\left\{1,2\right\}$ is $\dfrac{n+1}{\left(n+2\right)\left(n+1\right)/2}$ (because each such tree has $n+1$ edges, and each edge is contained in the same number of trees by symmetry reasons). Thus, the number of all trees on the vertex set $\left\{1,2,\ldots,n+2\right\}$ containing the edge $\left\{1,2\right\}$ is $\dfrac{n+1}{\left(n+2\right)\left(n+1\right)/2} \cdot \left(n+2\right)^n = 2 \left(n+2\right)^{n-1}$, which is our left hand side. QED! $\endgroup$ Jul 1 '17 at 0:07
20
$\begingroup$

Let's denote $T(x)=\sum_{n\geq 1}\frac{n^{n-1}x^n}{n!}$ the exponential generating function of labeled rooted trees, and $U(x)=\sum_{n\geq 1}\frac{n^{n-2}x^n}{n!}$ the corresponding function for unrooted trees. We will use the fact that $xU'=T$ and $xe^T=T$, both of which can be derived algebraically or combinatorially. Your identity follows from the relation $$2\left(T(x)-U(x)\right)=T^2$$ since the coefficient of $x^{k}$ on the left is $\frac{2k^{k-3}}{(k-2)!}$ and the corresponding coefficient on the right is $\sum_{i=1}^{k-1}\frac{i^{i-1}}{i!}\cdot\frac{(k-i)^{k-i-1}}{(k-i)!}$.

To get a quick proof of this notice that both sides only have terms of order $x^2$ or higher. Therefore it is enough to prove the derivative of this relation $$2T'-2U'=2TT'$$ $$\iff xT'-xU'=xTT'\iff xT'(1-T)=T\iff T'(1-T)=e^T$$ $$\iff 1=\frac{d}{dx}\left(\frac{T}{e^T}\right).$$


I hope it's clear from above that in principle all such identities follow from the basic relation $xe^T=T$ and all its derivatives. I know it's usually common to give references to books or surveys, but I really like the video lectures by Zagier available here, under the title "Partitions, Modular Forms, and Moduli Spaces" (these are based on a forthcoming paper by Dubrovin, Zagier and Yang). In a series of talks he presents how quasimodular forms appear in enumerative geometry. However in the first couple of lectures he focuses on what he calls "Lambert space" (nonstandard terminology from what I can tell, coming from the closely related Lambert function) which is essentially the space of series that are linear combinations of $T$ and its derivatives. He shows, for example, how generating functions of maps or Hurwitz numbers belong to this Lambert space.

$\endgroup$
2
  • $\begingroup$ Great! I'll see if this can also solve my more general problem. Can you clarify what you mean by "all such identities"? $\endgroup$
    – Drew
    Jul 1 '17 at 15:07
  • 2
    $\begingroup$ @Drew, For example $$\sum_{i=1}^{k-1}\binom{k}{i}i^{i-2}(k-i)^{k-i-3}=k^{k-5}\frac{5k^3+21k^2+94k-120}{12}.$$ Proving such an identity amounts to expressing both sides as coefficients of some differential polynomial expression in $T$, and then showing that the corresponding differential relation can be derived from $xe^T=T$. $\endgroup$ Jul 1 '17 at 15:49
13
$\begingroup$

Here are two proofs of your identity, which I have hinted at in my comments.

The identity

Let me first restate your identity with the letter $k$ renamed as $n$:

Theorem 1. Let $n\geq2$ be an integer. Then, $$ n^{n-3}=\dfrac{1}{2}\sum\limits_{i=1}^{n-1}\dbinom{n-2}{i-1}i^{i-2}\left( n-i\right) ^{n-i-2}. $$

First proof: the Abel identity and its friends

The first proof of Theorem 1 will actually show a more general identity:

Theorem 2. Let $n$ be a nonnegative integer. In the polynomial ring $\mathbb{Z}\left[ x,y,z\right] $, we have $$ \sum\limits_{k=0}^{n}\dbinom{n}{k}xy\left( x-kz\right) ^{k-1}\left( y-\left( n-k\right) z\right) ^{n-k-1}=\left( x+y\right) \left( x+y-nz\right) ^{n-1}. $$

Note that both sides of the equality in Theorem 2 are well-defined polynomials in $\mathbb{Z}\left[ x,y,z\right] $ (not just rational functions in $\mathbb{Q}\left( x,y,z\right) $): Indeed,

  • the only denominators that appear on the left hand side arise from the $\left( x-kz\right) ^{k-1}$ term for $k=0$ and from the $\left( y-\left( n-k\right) z\right) ^{n-k-1}$ term for $k=n$; but both of them are cancelled by the $xy$ factor appearing in each addend.

  • the only denominator that appears on the right hand side arises from the $\left( x+y-nz\right) ^{n-1}$ term for $n=0$; but this denominator is cancelled by the $x+y$ factor.

Theorem 2 is a well-known fact in umbral calculus: It says that the sequence of the Abel polynomials (the sequence $\left( p_{0},p_{1},p_{2} ,\ldots\right) $ whose $n$-th term is $p_{n}=x\left( x-nz\right) ^{n-1}$, where $x$ is considered an indeterminate and $z$ a constant) is of binomial type (i.e., it satisfies $p_{n}\left( x+y\right) =\sum\limits_{k=0}^{n}\dbinom {n}{k}p_{k}\left( x\right) p_{n-k}\left( y\right) $). As such, it is probably proven all across the literature. I also think that Theorem 2 is what the equation (2) in Victor J. W. Guo, Bijective proofs of Gould-Mohanty's and Raney-Mohanty's identities, arXiv:1005.4258v1 is supposed to be (I say "supposed" because equation (2) as it appears in Guo's preprint is false).

Let me derive Theorem 2 from an even better known identity, namely the Abel identity (appearing as equation (1) in the above-cited paper by Victor J. W. Guo):

Theorem 3. Let $n$ be a nonnegative integer. In the polynomial ring $\mathbb{Z}\left[ x,y,z\right] $, we have $$ \sum\limits_{k=0}^{n}\dbinom{n}{k}x\left( x-kz\right) ^{k-1}\left( y+kz\right) ^{n-k}=\left( x+y\right) ^{n}. $$

As before, both sides of the equality in Theorem 3 are well-defined polynomials in $\mathbb{Z}\left[ x,y,z\right] $.

The most well-known particular case of Theorem 3 is probably the one obtained by substituting $-1$ for $z$:

Theorem 4. Let $n$ be a nonnegative integer. In the polynomial ring $\mathbb{Z}\left[ x,y\right] $, we have $$ \sum\limits_{k=0}^{n}\dbinom{n}{k}x\left( x+k\right) ^{k-1}\left( y-k\right) ^{n-k}=\left( x+y\right) ^{n}. $$

Theorem 4 appears in many places, e.g. (with a boring proof) in my solution to Problem 4 on the 6th QEDMO 2009 (scroll down to Theorem 4). Yes, I am that lazy at reference hunting. $\square$

I am going to reverse the cart and derive Theorem 1 back from Theorem 4. The first step is getting Theorem 3:

Proof of Theorem 3. Work in the field $\mathbb{Q}\left( x,y,z\right) $ of rational functions in $x,y,z$. Substitute $\dfrac{x}{z}$ and $\dfrac{y}{z}$ for $x$ and $y$ in Theorem 4. The result is $$ \sum\limits_{k=0}^{n}\dbinom{n}{k}\dfrac{x}{z}\left( \dfrac{x}{z}-k\right) ^{k-1}\left( \dfrac{y}{z}+k\right) ^{n-k}=\left( \dfrac{x}{z}+\dfrac{y} {z}\right) ^{n}. $$ Multiplying this equality by $z^{n}$ and clearing denominators results in $$ \sum\limits_{k=0}^{n}\dbinom{n}{k}x\left( x-kz\right) ^{k-1}\left( y+kz\right) ^{n-k}=\left( x+y\right) ^{n}. $$ Thus, Theorem 3 is proven. $\square$

Next, I shall derive Theorem 2 from Theorem 3:

Proof of Theorem 2. Substituting $y-nz$ for $y$ in Theorem 3 yields $$ \sum\limits_{k=0}^{n}\dbinom{n}{k}x\left( x-kz\right) ^{k-1}\left( y-nz+kz\right) ^{n-k}=\left( x+y-nz\right) ^{n}. $$ Thus, \begin{align} \left( x+y-nz\right) ^{n} & =\sum\limits_{k=0}^{n}\dbinom{n}{k}x\left( x-kz\right) ^{k-1}\left( \underbrace{y-nz+kz}_{=y-\left( n-k\right) z}\right) ^{n-k}\nonumber\\ \tag{1} & =\sum\limits_{k=0}^{n}\dbinom{n}{k}x\left( x-kz\right) ^{k-1}\left( y-\left( n-k\right) z\right) ^{n-k}. \label{pf.t2.1} \end{align} Multiplying this equality by $y$, we find \begin{align} y\left( x+y-nz\right) ^{n} & =y\sum\limits_{k=0}^{n}\dbinom{n}{k}x\left( x-kz\right) ^{k-1}\left( y-\left( n-k\right) z\right) ^{n-k}\nonumber\\ & =\sum\limits_{k=0}^{n}\dbinom{n}{k}xy\left( x-kz\right) ^{k-1}\underbrace{\left( y-\left( n-k\right) z\right) ^{n-k}}_{=\left( y-\left( n-k\right) z\right) \left( y-\left( n-k\right) z\right) ^{n-k-1}}\nonumber\\ & =\sum\limits_{k=0}^{n}\dbinom{n}{k}xy\left( x-kz\right) ^{k-1}\left( y-\left( n-k\right) z\right) \left( y-\left( n-k\right) z\right) ^{n-k-1} \nonumber\\ \tag{2} & =\sum\limits_{k=0}^{n}\left( y-\left( n-k\right) z\right) \dbinom{n} {k}xy\left( x-kz\right) ^{k-1}\left( y-\left( n-k\right) z\right) ^{n-k-1}. \label{pf.t2.2} \end{align}

On the other hand, substituting $y$ and $x$ for $x$ and $y$ in \eqref{pf.t2.1}, we obtain \begin{align*} \left( y+x-nz\right) ^{n} & =\sum\limits_{k=0}^{n}\dbinom{n}{k}y\left( y-kz\right) ^{k-1}\left( x-\left( n-k\right) z\right) ^{n-k}\\ & =\sum\limits_{k=0}^{n}\dbinom{n}{n-k}y\left( y-\left( n-k\right) z\right) ^{n-k-1}\left( x-\left( n-\left( n-k\right) \right) z\right) ^{n-\left( n-k\right) } \end{align*} (here, we have substituted $n-k$ for $k$ in the sum). Since $y+x=x+y$, this rewrites as \begin{align*} & \left( x+y-nz\right) ^{n}\\ & =\sum\limits_{k=0}^{n}\underbrace{\dbinom{n}{n-k}}_{=\dbinom{n}{k}}y\left( y-\left( n-k\right) z\right) ^{n-k-1}\underbrace{\left( x-\left( n-\left( n-k\right) \right) z\right) ^{n-\left( n-k\right) } }_{\substack{=\left( x-kz\right) ^{k}\\=\left( x-kz\right) \left( x-kz\right) ^{k-1}}}\\ & =\sum\limits_{k=0}^{n}\dbinom{n}{k}y\left( y-\left( n-k\right) z\right) ^{n-k-1}\left( x-kz\right) \left( x-kz\right) ^{k-1}\\ & =\sum\limits_{k=0}^{n}\dbinom{n}{k}y\left( x-kz\right) \left( x-kz\right) ^{k-1}\left( y-\left( n-k\right) z\right) ^{n-k-1}. \end{align*} Multiplying this equality by $x$, we obtain \begin{align*} x\left( x+y-nz\right) ^{n} & =x\sum\limits_{k=0}^{n}\dbinom{n}{k}y\left( x-kz\right) \left( x-kz\right) ^{k-1}\left( y-\left( n-k\right) z\right) ^{n-k-1}\\ & =\sum\limits_{k=0}^{n}\dbinom{n}{k}xy\left( x-kz\right) \left( x-kz\right) ^{k-1}\left( y-\left( n-k\right) z\right) ^{n-k-1}\\ & =\sum\limits_{k=0}^{n}\left( x-kz\right) \dbinom{n}{k}xy\left( x-kz\right) ^{k-1}\left( y-\left( n-k\right) z\right) ^{n-k-1}. \end{align*} Adding this equality to \eqref{pf.t2.2}, we find \begin{align*} & y\left( x+y-nz\right) ^{n}+x\left( x+y-nz\right) ^{n}\\ & =\sum\limits_{k=0}^{n}\left( y-\left( n-k\right) z\right) \dbinom{n} {k}xy\left( x-kz\right) ^{k-1}\left( y-\left( n-k\right) z\right) ^{n-k-1}\\ & \ \ \ \ \ \ \ \ \ \ +\sum\limits_{k=0}^{n}\left( x-kz\right) \dbinom{n} {k}xy\left( x-kz\right) ^{k-1}\left( y-\left( n-k\right) z\right) ^{n-k-1}\\ & =\sum\limits_{k=0}^{n}\underbrace{\left( \left( y-\left( n-k\right) z\right) +\left( x-kz\right) \right) }_{=x+y-nz}\dbinom{n}{k}xy\left( x-kz\right) ^{k-1}\left( y-\left( n-k\right) z\right) ^{n-k-1}\\ & =\sum\limits_{k=0}^{n}\left( x+y-nz\right) \dbinom{n}{k}xy\left( x-kz\right) ^{k-1}\left( y-\left( n-k\right) z\right) ^{n-k-1}\\ & =\left( x+y-nz\right) \sum\limits_{k=0}^{n}\dbinom{n}{k}xy\left( x-kz\right) ^{k-1}\left( y-\left( n-k\right) z\right) ^{n-k-1}. \end{align*} Thus, \begin{align*} & \left( x+y-nz\right) \sum\limits_{k=0}^{n}\dbinom{n}{k}xy\left( x-kz\right) ^{k-1}\left( y-\left( n-k\right) z\right) ^{n-k-1}\\ & =y\left( x+y-nz\right) ^{n}+x\left( x+y-nz\right) ^{n}=\left( y+x\right) \left( x+y-nz\right) ^{n}\\ & =\left( x+y\right) \left( x+y-nz\right) ^{n}. \end{align*} Dividing this equality by $x+y-nz$, we obtain $$ \sum\limits_{k=0}^{n}\dbinom{n}{k}xy\left( x-kz\right) ^{k-1}\left( y-\left( n-k\right) z\right) ^{n-k-1}=\left( x+y\right) \left( x+y-nz\right) ^{n-1}. $$ This proves Theorem 2. $\square$

Finally, we can get Theorem 1:

First proof of Theorem 1. Theorem 2 (applied to $n-2$ instead of $n$) shows that in the polynomial ring $\mathbb{Z}\left[ x,y,z\right] $, we have \begin{align*} & \sum\limits_{k=0}^{n-2}\dbinom{n-2}{k}xy\left( x-kz\right) ^{k-1}\left( y-\left( \left( n-2\right) -k\right) z\right) ^{\left( n-2\right) -k-1}\\ & =\left( x+y\right) \left( x+y-\left( n-2\right) z\right) ^{n-3}. \end{align*} Substituting $1$, $1$ and $-1$ for $x$, $y$ and $z$ in this equality (and making the obvious simplifications), we find \begin{align*} & \sum\limits_{k=0}^{n-2}\dbinom{n-2}{k}\left( 1+k\right) ^{k-1}\left( 1+\left( \left( n-2\right) -k\right) \right) ^{\left( n-2\right) -k-1}\\ & =2\left( 2+\left( n-2\right) \right) ^{n-3}=2n^{n-3}. \end{align*} Hence, \begin{align*} 2n^{n-3} & =\sum\limits_{k=0}^{n-2}\dbinom{n-2}{k}\left( 1+k\right) ^{k-1}\left( 1+\left( \left( n-2\right) -k\right) \right) ^{\left( n-2\right) -k-1}\\ & =\sum\limits_{i=1}^{n-1}\dbinom{n-2}{i-1}\left( 1+\left( i-1\right) \right) ^{\left( i-1\right) -1}\left( 1+\left( \left( n-2\right) -\left( i-1\right) \right) \right) ^{\left( n-2\right) -\left( i-1\right) -1} \end{align*} (here, we have substituted $i-1$ for $k$ in the sum). After some trivial simplifications, this becomes $$ 2n^{n-3}=\sum\limits_{i=1}^{n-1}\dbinom{n-2}{i-1}i^{i-2}\left( n-i\right) ^{n-i-2}. $$ Dividing this equality by $2$, we obtain the claim of Theorem 1. $\square$

Second proof: Cayley's formula and the symmetry of trees

Let me say right away that the above first proof of Theorem 1 is my favorite, since it shows various rather general combinatorial identities in cascade. In contrast, the following second proof is cute and memorable.

A tree shall here mean a simple undirected graph (i.e., a pair $\left( V,E\right) $ in which $V$ is a finite set and $E$ is a set of $2$-element subsets of $V$) that is connected and has no cycles. Of course, various other equivalent characterizations of trees exist. If $n\in\mathbb{N}$, then an $n$-tree means a tree whose vertex set is $\left\{ 1,2,\ldots,n\right\} $. Notice that there exist no $0$-trees, since a graph with no vertices is not connected. If $G=\left( V,E\right) $ is a simple undirected graph, then the edge set $E$ is denoted by $\operatorname*{E}\left( G\right) $.

The following theorem is one of the famous results of 19th century combinatorics -- the Cayley formula (actually discovered by Borchardt in 1860):

Theorem 5. Let $n$ be a positive integer. Then, the number of all $n$-trees is $n^{n-2}$.

The similarity of the $n^{n-2}$ term here with the powers in Theorem 1 suggests a relation, and such indeed exists. First, let me derive a corollary of Theorem 5:

Corollary 6. Let $n\geq2$ be an integer. Let $f$ be a $2$-element subset of $\left\{ 1,2,\ldots,n\right\} $. Then, the number of all $n$-trees $T$ such that $f\in\operatorname*{E}\left( T\right) $ is $2n^{n-3}$.

Proof of Corollary 6. It is well-known that the number of edges in a tree is always its number of vertices minus $1$. Thus, a tree with $n$ vertices must have exactly $n-1$ edges. In other words, any $n$-tree must have exactly $n-1$ edges.

Let $F$ be the set of all $2$-element subsets of $\left\{ 1,2,\ldots ,n\right\} $. Then, for each $n$-tree $T$, we have $\operatorname*{E}\left( T\right) \subseteq F$ (that is, the edges of $T$ are elements of $F$). Also, $f$ is a $2$-element subset of $\left\{ 1,2,\ldots,n\right\} $ and thus belongs to $F$. Also, clearly, $\left\vert F\right\vert =\dbinom{n}{2} =\dfrac{n\left( n-1\right) }{2}$.

Now, we claim that any $e\in F$ satisfies \begin{align} \left( \text{the number of all }n\text{-trees }T\text{ such that }\left\{ 1,2\right\} \in\operatorname*{E}\left( T\right) \right) \nonumber\\ \tag{3} =\left( \text{the number of all }n\text{-trees }T\text{ such that } e\in\operatorname*{E}\left( T\right) \right) . \label{pf.c6.1} \end{align}

[Proof of \eqref{pf.c6.1}: Let $e\in F$. Thus, $e$ is a $2$-element subset of $\left\{ 1,2,\ldots,n\right\} $. In other words, $e=\left\{ x,y\right\} $ for two distinct elements $x$ and $y$ of $\left\{ 1,2,\ldots,n\right\} $. Consider these $x$ and $y$.

The elements $x$ and $y$ of $\left\{ 1,2,\ldots,n\right\} $ are distinct. Thus, there exists some permutation $\sigma$ of $\left\{ 1,2,\ldots ,n\right\} $ such that $\sigma\left( 1\right) =x$ and $\sigma\left( 2\right) =y$. (For example, one can find such a permutation $\sigma$ by setting its first two values $\sigma\left( 1\right) $ and $\sigma\left( 2\right) $ to be $x$ and $y$, and setting all its remaining $n-2$ values to be the remaining $n-2$ elements of $\left\{ 1,2,\ldots,n\right\} $ in any order.) Consider such a $\sigma$.

Recall that any permutation $\omega$ of $\left\{ 1,2,\ldots,n\right\} $ also induces a permutation of the set $F$ of all $2$-element subsets of $\left\{ 1,2,\ldots,n\right\} $ (namely, it sends each $g\in F$ to $\omega\left( g \right) =\left\{ \omega\left( u\right) \ \mid\ u\in g \right\} $). In particular, $\sigma$ induces a permutation of the set $F$. This permutation satisfies $\sigma\left( \left\{ 1,2\right\} \right) =\left\{ \underbrace{\sigma\left( 1\right) }_{=x},\underbrace{\sigma\left( 2\right) }_{=y}\right\} =\left\{ x,y\right\} =e$.

If $T$ is an $n$-tree, and if $\omega$ is a permutation of $\left\{ 1,2,\ldots,n\right\} $, then $\omega\left( T\right) $ shall denote the $n$-tree whose edges are the images of the edges of $T$ under $\omega$ (that is, $\operatorname*{E}\left( \omega\left( T\right) \right) =\left\{ \omega\left( e\right) \ \mid\ e\in\operatorname*{E}\left( T\right) \right\} $). It is easy to see that this $\omega\left( T\right) $ is indeed an $n$-tree (indeed, it is just the $n$-tree $T$ with its vertices relabelled by the map $\omega$). Hence, the map $$ \left\{ n\text{-trees}\right\} \rightarrow\left\{ n\text{-trees}\right\} ,\ T\mapsto\sigma\left( T\right) $$ is well-defined. Moreover, this map is a bijection (indeed, the map $\left\{ n\text{-trees}\right\} \rightarrow\left\{ n\text{-trees}\right\} ,\ T\mapsto\sigma^{-1}\left( T\right) $ is easily seen to be inverse to it). This bijection restricts to a bijection \begin{align*} \left\{ n\text{-trees }T\text{ such that }\left\{ 1,2\right\} \in\operatorname*{E}\left( T\right) \right\} & \rightarrow\left\{ n\text{-trees }T\text{ such that }e\in\operatorname*{E}\left( T\right) \right\} ,\\ T & \mapsto\sigma\left( T\right) \end{align*} (since $\sigma\left( \left\{ 1,2\right\} \right) =e$). Hence, the sets $\left\{ n\text{-trees }T\text{ such that }\left\{ 1,2\right\} \in\operatorname*{E}\left( T\right) \right\} $ and $\left\{ n\text{-trees }T\text{ such that }e\in\operatorname*{E}\left( T\right) \right\} $ are in bijection. Thus, these two sets have the same size. In other words, \eqref{pf.c6.1} holds.]

Now, \begin{align*} & \left( \text{the number of all pairs }\left( T,e\right) \text{ where }T\text{ is an }n\text{-tree and }e\in\operatorname*{E}\left( T\right) \right) \\ & =\sum\limits_{T\text{ is an }n\text{-tree}}\underbrace{\left( \text{the number of all }e\in\operatorname*{E}\left( T\right) \right) }_{\substack{=\left\vert \operatorname*{E}\left( T\right) \right\vert =\left( \text{the number of all edges of }T\right) =n-1\\\text{(since any }n\text{-tree must have exactly }n-1\text{ edges)}}}\\ & =\sum\limits_{T\text{ is an }n\text{-tree}}\left( n-1\right) =\left( n-1\right) \cdot\underbrace{\left( \text{the number of all }n\text{-trees}\right) }_{\substack{=n^{n-2}\\\text{(by Theorem 5)}}}\\ & =\left( n-1\right) \cdot n^{n-2}. \end{align*} Hence, \begin{align*} & \left( n-1\right) \cdot n^{n-2}\\ & =\left( \text{the number of all pairs }\left( T,e\right) \text{ where }T\text{ is an }n\text{-tree and }e\in\operatorname*{E}\left( T\right) \right) \\ & =\sum\limits_{e\in F}\underbrace{\left( \text{the number of all }n\text{-trees }T\text{ such that }e\in\operatorname*{E}\left( T\right) \right) }_{\substack{=\left( \text{the number of all }n\text{-trees }T\text{ such that }\left\{ 1,2\right\} \in\operatorname*{E}\left( T\right) \right) \\\text{(by \eqref{pf.c6.1})}}}\\ & \ \ \ \ \ \ \ \ \ \ \left( \text{since }\operatorname*{E}\left( T\right) \subseteq F\text{ for each }n\text{-tree }T\right) \\ & =\sum\limits_{e\in F}\left( \text{the number of all }n\text{-trees }T\text{ such that }\left\{ 1,2\right\} \in\operatorname*{E}\left( T\right) \right) \\ & =\underbrace{\left\vert F\right\vert }_{=\dfrac{n\left( n-1\right) }{2} } \cdot \underbrace{\left( \text{the number of all }n\text{-trees }T\text{ such that }\left\{ 1,2\right\} \in \operatorname*{E}\left( T\right) \right) }_{\substack{=\left( \text{the number of all }n\text{-trees }T\text{ such that }f\in\operatorname*{E}\left( T\right) \right) \\\text{(by \eqref{pf.c6.1}, applied to }e=f\text{)}}}\\ & =\dfrac{n\left( n-1\right) }{2}\cdot\left( \text{the number of all }n\text{-trees }T\text{ such that }f\in\operatorname*{E}\left( T\right) \right) . \end{align*} Solving this equality for $\left( \text{the number of all }n\text{-trees }T\text{ such that }f\in\operatorname*{E}\left( T\right) \right) $, we obtain \begin{align*} \left( \text{the number of all }n\text{-trees }T\text{ such that } f\in\operatorname*{E}\left( T\right) \right) & =\left( n-1\right) \cdot n^{n-2}/\dfrac{n\left( n-1\right) }{2}\\ & =2n^{n-3}. \end{align*} This proves Corollary 6. $\square$

Here is another trivial corollary of Theorem 5:

Corollary 7. Let $S$ be a finite nonempty set. Then, the number of all trees with vertex set $S$ is $\left\vert S\right\vert ^{\left\vert S\right\vert -2}$.

Proof of Corollary 7. Let $n=\left\vert S\right\vert $. Then, there exists a bijection $\left\{ 1,2,\ldots,n\right\} \rightarrow S$. We can use this bijection to transform any $n$-tree into a tree with vertex set $S$ (by relabelling its vertices) and vice versa. Hence, the number of all trees with vertex set $S$ equals the number of all $n$-trees. But the latter number is $n^{n-2}$ (by Theorem 5). Hence, the former number is also $n^{n-2}$. In other words, the number of all trees with vertex set $S$ is $n^{n-2}=\left\vert S\right\vert ^{\left\vert S\right\vert -2}$ (since $n=\left\vert S\right\vert $). Corollary 7 is proven. $\square$

Now, we can finally reprove Theorem 1:

Second proof of Theorem 1. Corollary 6 (applied to $f=\left\{ 1,2\right\} $) shows that the number of all $n$-trees $T$ satisfying $\left\{ 1,2\right\} \in\operatorname*{E}\left( T\right) $ is $2n^{n-3}$.

Now, let me show a different way to compute this number.

Indeed, if we remove the edge $\left\{ 1,2\right\} $ from an $n$-tree $T$ satisfying $\left\{ 1,2\right\} \in\operatorname*{E}\left( T\right) $, then the remaining graph splits into two connected components, one of which contains the vertex $1$ while the other contains the vertex $2$. Both connected components are trees; we denote them by $A_{T}$ and $B_{T}$, respectively (so that $1$ is a vertex of $A_{T}$ and $2$ is a vertex of $B_{T}$). Let $\mathcal{A}_{T}$ be the vertex set of the tree $A_{T}$, and let $\mathcal{B}_{T}$ be the vertex set of the tree $B_{T}$. Then, $\mathcal{A} _{T}$ and $\mathcal{B}_{T}$ are two disjoint subsets of $\left\{ 1,2,\ldots,n\right\} $ whose union is $\left\{ 1,2,\ldots,n\right\} $; thus, $\mathcal{B}_{T}=\left\{ 1,2,\ldots,n\right\} \setminus\mathcal{A} _{T}$. Note that $1\in\mathcal{A}_{T}$ (since $1$ is a vertex of $A_{T}$) and $2\in\mathcal{B}_{T}$ (since $2$ is a vertex of $B_{T}$), thus $2\in \mathcal{B}_{T}=\left\{ 1,2,\ldots,n\right\} \setminus\mathcal{A}_{T}$, thus $2\notin\mathcal{A}_{T}$.

Obviously, an $n$-tree $T$ satisfying $\left\{ 1,2\right\} \in \operatorname*{E}\left( T\right) $ is uniquely determined by the two trees $A_{T}$ and $B_{T}$. Thus, any $n$-tree $T$ satisfying $\left\{ 1,2\right\} \in\operatorname*{E}\left( T\right) $ can be constructed by the following procedure:

  1. First, we decide how many elements the set $\mathcal{A}_{T}$ will have (i.e., how many vertices $A_{T}$ will have). The number of elements of $\mathcal{A}_{T}$ has to be an integer from $1$ to $n-1$ (in fact, it cannot be $0$ (since we must have $1\in\mathcal{A}_{T}$); but it cannot be $n$ either (since we must have $2\notin\mathcal{A}_{T}$)). We choose one such integer, and denote it by $i$. We thus want the set $\mathcal{A}_{T}$ to have $i$ elements.

  2. Then, we choose the set $\mathcal{A}_{T}$ itself (i.e., we decide which vertices $A_{T}$ will have). We already know that this set will have $i$ elements, and we know that $1$ will be one of them (since $1\in\mathcal{A} _{T}$) but $2$ will be not (since $2\notin\mathcal{A}_{T}$); thus, we are left to choose the remaining $i-1$ elements of $\mathcal{A}_{T}$ freely among the $n-2$ numbers $3,4,\ldots,n$. There are $\dbinom{n-2}{i-1}$ ways to make this choice.

  3. Having chosen the set $\mathcal{A}_{T}$, we immediately know the set $\mathcal{B}_{T}$: namely, $\mathcal{B}_{T}=\left\{ 1,2,\ldots,n\right\} \setminus\mathcal{A}_{T}$ (there are no choices to make here). Notice that $\left\vert \mathcal{A}_{T}\right\vert =i$ (since the set $\mathcal{A}_{T}$ has $i$ elements), and from $\mathcal{B}_{T}=\left\{ 1,2,\ldots,n\right\} \setminus\mathcal{A}_{T}$ we obtain $\left\vert \mathcal{B}_{T}\right\vert =\left\vert \left\{ 1,2,\ldots,n\right\} \setminus\mathcal{A}_{T}\right\vert =\underbrace{\left\vert \left\{ 1,2,\ldots,n\right\} \right\vert } _{=n}-\underbrace{\left\vert \mathcal{A}_{T}\right\vert }_{=i}=n-i$. Note that both sets $\mathcal{A}_{T}$ and $\mathcal{B}_{T}$ are nonempty (since $1\in\mathcal{A}_{T}$ but $2\in\mathcal{B}_{T}$ (since $2\notin\mathcal{A} _{T}$)).

  4. Now, we choose the tree $A_{T}$. This tree has to be a tree with vertex set $\mathcal{A}_{T}$; the number of all such trees is $\left\vert \mathcal{A} _{T}\right\vert ^{\left\vert \mathcal{A}_{T}\right\vert -2}$ (by Corollary 7, applied to $S=\mathcal{A}_{T}$). In other words, the number of all such trees is $i^{i-2}$ (since $\left\vert \mathcal{A}_{T}\right\vert =i$). Thus, there are $i^{i-2}$ ways to choose $A_{T}$.

  5. Now, we choose the tree $B_{T}$. This tree has to be a tree with vertex set $\mathcal{B}_{T}$; the number of all such trees is $\left\vert \mathcal{B} _{T}\right\vert ^{\left\vert \mathcal{B}_{T}\right\vert -2}$ (by Corollary 7, applied to $S=\mathcal{B}_{T}$). In other words, the number of all such trees is $\left( n-i\right) ^{n-i-2}$ (since $\left\vert \mathcal{B} _{T}\right\vert =n-i$). Thus, there are $\left( n-i\right) ^{n-i-2}$ ways to choose $B_{T}$.

  6. Finally, we assemble the $n$-tree $T$ from $A_{T}$ and $B_{T}$ by adding the edge $\left\{ 1,2\right\} $.

This procedure clearly yields any $n$-tree $T$ satisfying $\left\{ 1,2\right\} \in\operatorname*{E}\left( T\right) $ in a unique way. Thus, the number of all $n$-trees $T$ satisfying $\left\{ 1,2\right\} \in\operatorname*{E}\left( T\right) $ is $\sum\limits_{i=1}^{n-1}\dbinom{n-2} {i-1}i^{i-2}\left( n-i\right) ^{n-i-2}$ (because this is how many ways we have to make choices in the above procedure). Comparing this with the fact that this number is $2n^{n-3}$ (as shown above), we conclude that $$ 2n^{n-3}=\sum\limits_{i=1}^{n-1}\dbinom{n-2}{i-1}i^{i-2}\left( n-i\right) ^{n-i-2}. $$ Dividing this equality by $2$, we obtain the claim of Theorem 1. $\square$

$\endgroup$
1
  • $\begingroup$ Thank you for the detailed answer! The combinatorial proof is very nice, and I have some hope that Abel's identity will solve my bigger question (I added a link in the original post), once I have time to think about it. $\endgroup$
    – Drew
    Jul 3 '17 at 15:14
2
$\begingroup$

In my (first research) paper, A note on evaluation of Abel's sums, (that appeared second, in 1979) I described another way to evaluate Abel's sum of the form $$A_n(x,y;p,q)=\sum_{k=0}^n {{n} \choose {k}}(k+x)^{k+p}(n-k+y)^{n-k+q},$$ via (simpler) auxiliary sums defined by $$F_n(x,y;p,q)=\sum_{k=0}^n {{n} \choose {k}}(-1)^k (k+x)^{p}(n-k+y)^{q}.$$ The $F_n$ functions have simple evaluations in terms of difference operators. I was inspired by Riordan's book Combinatorial Identities and later corresponded with Riordan, and met him in 78.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.