\problemdata                                                             
        {counting-21} % latex-friendly label for the prob.
        {Counting; Numbered Trees } % The topic(s) of the problem content.  
        {?} % Source (if known)                                          
        {S02 cp7M; F99 TUT9} % Usage (list ones you are aware of). 
        {Tina Wang, S02} % Last revision info (author, date).   
                                                                         
                                                                         
\begin{problem}           
\textbf{Counting Numbered Trees.}  

A \emph{numbered tree} is a tree whose vertex set is
$\set{1,2,\dots,n}$ for some $n \geq 2$.  We define the \emph{code} of
the numbered tree to be a sequence of $n-2$ integers from 1 to $n$
obtained by the following recursive process:
\begin{quotation}\noindent
If $n=2$, stop---the code is the empty sequence.  Otherwise, write down
the \emph{father} of the largest leaf, delete this \emph{leaf}, and
continue the process on the resulting smaller tree.
\end{quotation}
For example, the codes of a couple of numbered trees are shown in 

Figure~(\ref{fig:n-2}).
\begin{figure}[htb]
\begin{center}
\includegraphics[width=4in]{figures/n-2}
\end{center}
\caption{Coding Numbered Trees}
\label{fig:n-2}
\end{figure}

\begin{problemparts}

\problempart Describe a procedure for reconstructing a numbered tree from its
code.

\solution{
The key observation is that, given a code of length $n-2$, the numbers
between 1 and $n$ which \emph{do not appear} in the code must be leaves of
the tree.  Hence, the largest missing number is a leaf attached to the
first number of the code.  The rest of the tree can now be reconstructed
by deleting the first number in the code, henceforth ignoring the largest
leaf, and proceeding recursively on the rest of the code.  (We're using
the obvious fact that what's left after deleting a leaf from a tree is
another tree.)

More precisely, the reconstruction procedure applies to any finite tree
whose vertex set is totally ordered.  The procedure takes \emph{two}
parameters: the vertex set, $V$, and a length $\card{V}-2$ ``code''
sequence, $S$, of elements in $V$.  If $l$ is the largest element in $V$
which does not appear in $S$, and $f$ is the first element of $S$, then
the reconstructed tree is obtained by adding edge $(l,f)$ to the tree
reconstructed by calling the procedure recursively with first argument
$V-\set{l}$ and second argument equal to the code obtained by erasing the
initial $f$ from $S$.  The procedure terminates when $\card{V}=2$,
returning the edge between the two numbers in $V$.

To justify the key observation, note that any vertex that gets deleted by
the process and was not a leaf to begin with, must have been the father of
a previously deleted leaf, which means it would appear in the code.  So
the missing integers must have been leaves to begin with or must be one of
the two undeleted vertices left when the coding process terminates.  But
by the end of the process the two remaining vertices are leaves, and if
they weren't leaves to begin with, they must have become leaves by having
their sons deleted, which means they would not have been missing from the
code.  So the two vertices remaining at the end must also have been leaves
of the original tree.
}

\problempart How many numbered trees with $n$ vertices are there?

\solution{There are exactly as many $n$-vertex numbered trees a there
are length $n-2$ sequences of numbers between 1 and $n$.  So there are
$n^{n-2}$ numbered trees.
  
The reason there are the same number is that the tree reconstruction
procedure takes any such length $n-2$ sequence and returns an $n$-vertex
numbered tree whose code it is.  But the explanation above of why the
recursive reconstruction procedure is correct actually shows more: the
reconstructed tree is the \emph{unique} one with that code.

Now since every such length $n-2$ sequence is the code of some $n$-vertex
numbered tree, the coding procedure defines a surjection.  Since the tree
with that code is unique, the coding coding procedure also defines an
injection.  So the tree-coding function is a bijection.  Therefore the
number of numbered trees with $n$ vertices is the same as the number of
length $n-2$ sequences of integers between 1 and $n$.}

\end{problemparts}
\end{problem} 
                                 