%From:Doron Zeilberger, <zeilberg@math.temple.edu>
%TO:E-friends
%Re:Hopefully the  last unsolicited e-paper to be distributed
 
%I have asked our system administrator to establish an anonymous ftp
%for people who are intereseted to "get" my papers. When he does that,
%I will only send a short ad when new papers become available. Until he gets
%around to it, here is a new paper, that would not take too much
%of your precious disk-space. If anybody has seen this proof
%before please let me know as soon as possible.
 
%-------begin plain TeX file of distributed preprint-----------
\font\eightrm=cmr8 \font\sixrm=cmr6 
\font\eighttt=cmtt8
\magnification=\magstephalf
\def\lheading#1{\bigbreak \noindent {\bf#1} \medskip}
\parindent=0pt
\overfullrule=0in
 
\bf
\noindent
The ${n^{n-2}}^{th}$ Proof Of The Formula For The Number Of Labelled Trees
\medskip
\noindent
\it
Doron Zeilberger\footnote{$^1$}
{\eightrm 
Department of Mathematics, Temple University,
Philadelphia, PA 19122, USA. 
\break
{\eighttt zeilberg@euclid.math.temple.edu .}
Supported in part by the NSF.
}
\medskip
\noindent
\rm
There are probably already more than $4^2$ different proofs of the 
Cayley-Borchardt
formula, $n^{n-2}$, for the number of labelled trees on $n$ vertices([K],[M].)
The one I present here is not the prettiest,this honor goes to Joyal's[J]
(see also [L]), and not the ugliest,
but it is {\it mine} (although it has some similarities with 
Clarke's proof[C].)
\smallskip
Let $R(e,b)$ be the number of ways of organizing $e$ employees and $b$
bosses, such that every employee has exactly one immediate supervisor
(who may be another employee or a boss), in such a way that no employee
is her own (immediate or non-immediate) superior. The ways of deciding
the organization  can be split into four independent decisions:
\smallskip
(i) How many employees, $s$, $1 \leq s \leq e$,
will report directly to bosses? Let's call them {\it little  bosses}.
\smallskip
(ii) Which $s$ of the $e$ employees will be named {\it little bosses}:
${ {e} \choose {s}}$ ways.
\smallskip
(iii)How to organize the $s$ little bosses and remaining $e-s$ employees
amongst themselves: $R(e-s,s)$ ways.
\smallskip
(iv) For each of the $s$ little bosses, which big boss should she report to?:
$b^s$ ways.
\smallskip
Hence:
 
$$
R(e,b)= \sum_{s=1}^{e} {{e} \choose {s}} b^s R(e-s,s) \quad,
\eqno(*)
$$
 
which together with the trivial initial condition $R(0,b)=1$, uniquely
determines $R$. Since the recurrence (*), and the initial condition,
are also satisfied by $b(b+e)^{e-1}$, by the binomial theorem,
it follows that $R(e,b)=b(b+e)^{e-1}$. In particular, $R(n-1,1)$, the
number of labelled trees on $n$ vertices, equals $n^{n-2}$. 
\medskip
\noindent
{\bf References}
\medskip
\noindent
 
[C] L.E. Clarke, {\it On Cayley's formula for counting trees},
J. London Math. Soc. {\bf 33}(1958), 471-475.
 
[J] A. Joyal, {\it Une th\'eorie combinatoire des s\'eries formelles},
Adv. in Math. {\bf 42}(1981), 1-82.
 
[K] D.E. Knuth, {\it ``The Art Of Computing Programming'', v.1:
``Fundamental Algorithms''}, 2nd edition, Addison-Wesley, Reading, 1973.
(p. 406).
 
[L] G. Labelle, {\it Une nouvelle d\'emonstration combinatoire des formules
d'inversion de Lagrange}, Adv. in Math. {\bf 42}(1981), 217-247.
 
[M] J.W. Moon, {\it ``Counting Labelled Trees''}, Canad. Math. Congress,
Montreal, 1970.
 
 
\bye
 
-----end distributed preprint------------------------------------