%&latex
\documentclass[11pt]{article}
\marginparwidth 0pt
\oddsidemargin 0pt
\evensidemargin 0pt
\marginparsep 0pt
\topmargin 0pt
\textwidth 6.3in
\textheight 8.5in
\parskip = 3mm
\usepackage{amsmath,amsthm}
\usepackage{amssymb}
\usepackage{color}
\usepackage{xspace}
% load hyperref last
\usepackage[colorlinks=true,
linkcolor=green,
filecolor=brown,
citecolor=green]{hyperref}
\def\red{\textcolor{red} }
\renewcommand{\baselinestretch}{1.2}
\begin{document}
\mbox{ }
\vspace*{-20mm}
\begin{center}
{\Large
The Joyal Approach to Counting Edge-Labeled Trees \\
}
\vspace{10mm}
DAVID CALLAN \\
Department of Statistics \\
\vspace*{-2mm}
University of Wisconsin-Madison \\
\vspace*{-2mm}
1300 University Ave \\
\vspace*{-2mm}
Madison, WI \ 53706-1532 \\
{\bf callan@stat.wisc.edu} \\
\vspace{5mm}
Dec 22, 2005
\end{center}
\vspace{5mm}
Many authors have offered proofs of Cayley's classic result that that there are
$n^{n-2}$ vertex-labeled trees on $n$ vertices, including Pr\"{u}fer
(1918) and Joyal (1981) \cite[p.\,174]{thebook}.
Oleg Pikhurko \cite{Pikhurko} gives an ``algorithmic'' proof in the style
of Pr\"{u}fer that there are
$n^{n-3}$ \emph{edge-labeled} trees on $n$ vertices. Here we show that Joyal's ``conceptual''
approach also yields the edge-labeled result.
Recall Joyal
\cite[p.\,174]{thebook} uses a
canonical correspondence between permutations and lists to
identify the functional digraph of $f:[n]\to [n]$ with a marked
rooted tree on $[n]$ as follows. The functional digraph has vertex set $[n]$ and
an edge from $i$ to $j$ iff $f(i)=j$. The path from any vertex must
eventually feed into a cycle and so this graph consists of trees
rooted at the vertices of one or more cycles. The cycles form a
permutation on a subset of $[n]$, say $(7,5,4,9)(2)(6,8,10)$.
There is a canonical form for such a permutation: smallest element
first in each cycle, cycles arranged
in decreasing order of their first elements: $(6,8,10)(4,9,7,5)(2)$.
The point is that erasing the parentheses now gives a bijection to the set
of \emph{lists} on the same elements, because the first elements of the
cycles can be recovered as the left-to-right minima of the list.
Joyal uses this bijection to ``open out'' the cycles into a list, an
edge joining each list element (except the last) to its successor. Designate the first
list element the root and the last list element the mark.
Then, ignoring edge directions, we get a marked
rooted tree on $[n]$ that represents $f:[n]\to [n]$.
Erasing the mark and root---$n^{2}$
possibilities---yields Cayley's $n^{n-2}$ formula.
Now Joyal, as just described, identifies a
function $f:[n]\to [n]$ whose fixed points include $1,n-1$ and $n$ (there
are $n^{n-3}$ such) with a tree on $[n]$ (rooted at $n$, marked at 1)
in which $n-1$ is the
first interior vertex on the (unique) path from $n$ to 1. This is
because each of $n,n-1$ and 1 forms a one-element cycle and so
$n,n-1,1$ are necessarily the first, second and last element of the
associated list.
Redirect all edges \emph{away} from the root $n$ and give each the label of its
terminal vertex to produce an edge-labeled tree. The root can be
recaptured as a terminal vertex of the unique path in the
edge-labeled tree with
terminal edges 1 and $n-1$, and the $n^{n-3}$ formula follows.
\begin{thebibliography}{99}
\bibitem{Pikhurko}Oleg Pikhurko,
Generating edge-labeled trees, {\em Amer. Math. Monthly} \textbf{112},
2005, 919--921.
\bibitem{thebook} Martin Aigner, G\"{u}nter M. Ziegler,
{\em Proofs from \sc{the book}} 3rd ed., Springer, 2003.
\end{thebibliography}
\end{document}