 
%-----begin plain TeX file of cayley.tex: outputs 1 page 
 
%begin macros
\def\mod{\mathop{\rm mod} \nolimits}
\baselineskip=14pt
\parskip=10pt
\def\qed{\hbox{\vrule height0.15cm width0.01cm\vbox{\hrule height
 0.01cm width0.2cm \vskip0.15cm \hrule height 0.01cm width0.2cm}\vrule
 height0.15cm width 0.01cm}}
\font\eightrm=cmr8 \font\sixrm=cmr6 
\font\eighttt=cmtt8
\magnification=\magstephalf
\def\lheading#1{\bigbreak \noindent {\bf#1} 
}
\parindent=0pt
\overfullrule=0in
%end macros
\bf
\centerline
{ Yet Another Proof for the Enumeration of Labelled Trees}
\rm
\bigskip
\centerline{ {\it 
Based on a comment of Herb Wilf (spelled out by D. Zeilberger)}}
[Exclusive for DZ's mailing list, and his ftp and www forum.]
 
In [1], a very short and elementary proof of Abel's identity was given,
using the methods introduced in [2]. For the sake of completeness
we reproduce the statement and proof.
 
{\bf Theorem:} For $n\ge0$:
$$
\sum_{k=0}^n {{n}\choose {k}}(r+k)^{k-1}(s-k)^{n-k}= { {(r+s)^n} \over {r}} \,
\eqno(1)
$$
 
{\bf Proof ([1]):}  Let $F_{n,k}(r,s)$ and $a_n(r,s)$ denote, respectively, 
the summand and sum on the LHS of (1), and let 
$G_{n,k}:=(s-n){{n-1}\choose {k-1}}(r+k)^{k-1}(s-k)^{n-k-1}$. Since
$$
F_{n,k}(r,s)-sF_{n-1,k}(r,s)-(n+r)F_{n-1,k}(r+1,s-1)
        +(n-1)(r+s)F_{n-2,k}(r+1,s-1)=G_{n,k}-G_{n,k+1} \,,
$$
(check!), we have by summing from $k=0$ to $k=n$, thanks to the telescoping
on the right:
$$
 a_n(r,s)-sa_{n-1}(r,s)-(n+r) a_{n-1}(r+1,s-1)+
        (n-1)(r+s) a_{n-2}(r+1,s-1)=0.
$$
Since $(r+s)^n\cdot r^{-1}$ also satisfies 
this recurrence (check!) with the same initial 
conditions $a_0(r,s)=r^{-1}$ and 
$a_1(r,s)=(r+s)\cdot r^{-1}$, $(1)$ follows.\qed  
 
Now, letting $n \rightarrow n-2$, $r:=1$, and $s:=n-1$, and
setting $b_n:=n^{n-2}$, one obtains the recurrence:
$$
b_n=\sum_{k=0}^{n-2}{{n-2}\choose{k}} b_{k+1}[(n-k-1)b_{n-k-1}] .
\eqno(2)
$$
Let $t_n$ be the number of labelled trees on $n$ vertices, then:
$$
t_n=\sum_{k=0}^{n-2}{{n-2}\choose{k}} t_{k+1}[(n-k-1) t_{n-k-1}] .
\eqno(3)
$$
Indeed every labelled tree $T$ on $\{1,2, \dots , n \}$ gives rise
to a unique triple $(T',T'',S)$, where $T''$ is the rooted tree
to which the vertex $2$ belongs, in the forest resulting from
deleting $1$ (rooted at the vertex connected to $1$), $T'$ is
the tree obtained from $T$ by deleting $T''$, and $S$ is the set
of labels (in addition to $1$) participating in $T'$.
Now sum over all possible $k:=\vert S\vert$, to get $(3)$.
 
Since $b_1=t_1$, and $b_n$ and $t_n$ satisfy the same recurrence,
it follows that we have the $(n^{n-2})$th proof of Cayley's theorem.
 
{\bf References}
 
1. S. B. Ekhad and J. Majewicz
{\it A short WZ-style proof of Abel's identity}, preprint.
(available via anonymous ftp to ftp.math.temple.edu in directory pub/jmaj )
 
2. J. Majewicz
{\it WZ-type certification procedures and Sister Celine's technique for
         Abel-type sums}, 
preprint (available via anonymous ftp to
         ftp.math.temple.edu in directory pub/jmaj ).
 
\end
 
 
