\documentclass[12pt,twoside,notitlepage]{article}
%% On the Analytical Forms Called Trees
%% Professor Cayley
%% American Journal of Mathematics, Volume 4, Tome 1/4 (1881), 266-268
%% http://links.jstor.org/sici?sici=0002-9327(1881)4:14<266:OTAFCT>2.0.CO;2-2
%% LaTeX version 05 Sep 2003 Michael Somos
\usepackage{fancyhdr}
%%
\setlength{\evensidemargin}{.45in}
\setlength{\oddsidemargin}{.45in}
\setlength{\textwidth}{5.6in}
\setlength{\textheight}{7.5in}
%% a few needed macros
\newcommand{\sfrac}[2]{{\scriptstyle\frac{#1}{#2}}}
\newcommand{\half}{\frac{1}{2}}
\newcommand{\shalf}{\sfrac{1}{2}}
\newcommand{\bksp}{\!\!\!\!}
%%
\pagestyle{empty}
\frenchspacing
\begin{document}
%% --[ page 267 ]--
\begin{center}
{\large\bfseries\itshape On the Analytical Forms called Trees.} \\
\vskip 2em
{\small B\textsc{y} P\textsc{rofessor} C\textsc{ayley}.} \\
\vskip 1.5em
\rule{1.4in}{.1pt}
\end{center}
\vskip .5em
\par
In a tree of $N$ knots, selecting any knot at pleasure as a root, the tree may
be regarded as springing from this root, and it is then called a root-tree. The
same tree thus presents itself in various forms as a root-tree; and if we
consider the different root-trees with $N$ knots, these are not all of them
distinct trees. We have thus the two questions, to find the number of
root-trees with $N$ knots; and, to find the number of distinct trees with $N$
knots.
\par
I have in my paper, ``On the Theory of the Analytical Forms called Trees,''
\textit{Phil. Mag.},t. 13 (1857), pp. 172--176, given the solution of the
first question; viz. if $\phi_N$ denotes the number of the root-trees with $N$
knots, then the successive number $\phi_1,\phi_2,\phi_3$, etc., are given by
the formula
$$ \phi_1+x\phi_2+x^2\phi_3+\dots=(1-x)^{-\phi_1}(1-x^2)^{-\phi_2}
(1-x^3)^{-\phi_3}\dots $$
viz. we thus find
\\[.3cm]
\begin{tabular}{@{}rlccccccccccccc@{}}
suffix of&$\bksp\phi$&1& 2& 3& 4& 5& 6& 7& 8& 9& 10& 11& 12& 13 \\
\hline
&$\bksp\phi=\bksp$& 1& 1& 2& 4& 9& 20& 48& 115& 286& 719& 1842& 4766& 12486 \\
\end{tabular}
\\
\par
And I have, in the paper ``On the Analytical Forms called Trees, with
Appli\-cations to the Theory of Chemical Combinations,'' \textit{Brit. Assoc.
Report,} 1875, pp. 257--305, also shown how by the consideration of the centre
or bicentre ``of length'' we can obtain formulae for the number of central and
bicentral trees, that is for the number of distinct trees, with $N$ knots : the
numerical result obtained for the the total number of distinct trees with $N$
knots is given as follows:
\\[.3cm]
\begin{tabular}{@{}clccccccccccccc@{}}
No. of$\bksp$&Knots &1& 2& 3& 4& 5& 6& 7& 8& 9& 10& 11& 12& 13 \\
\hline
No. of$\bksp$&Central Trees&1& 0& 1& 1& 2& 3& 7& 12& 27& 55& 127& 284& 682 \\
'' $\bksp$&Bicentral ''&0& 1& 0& 1& 1& 3& 4& 11& 20& 51& 108& 267& 619 \\
\hline
Total& &1& 1& 1& 2& 3& 6& 11& 23& 47& 106& 235& 551&1301 \\
\end{tabular}
\newpage
%%
\pagestyle{fancy}
\addtolength{\headheight}{2.5pt}
\addtolength{\headsep}{-10pt}
\renewcommand{\sectionmark}[1]{\markright{#1}}
\renewcommand{\headrulewidth}{0pt}
\fancyhf{}
\fancyhead[LE,RO]{\thepage}
\fancyhead[CO]{\rightmark}
\fancyhead[CE]{\rightmark}
%%
\setcounter{page}{267}
\sectionmark%
{\textrm{C}\textsc{ayley}: \textit{On the Analytical Forms called Trees.}}
%% --[ page 267 ]--
\par
But a more simple solution is obtained by the consideration of the centre
or bicentre ``of number.'' A tree of an odd number $N$ of knots has a centre
of number, and a tree of an even number $N$ of knots has a centre or else a
bicentre of number. To explain this notion (due to M. Camille Jordan) we
consider the branches which proceed from any knot, and (excluding always this
knot itself) we count the number of the knots upon the several branches; say
these numbers are $\alpha, \beta, \gamma, \delta, \epsilon$, etc., where of
course $\alpha+\beta+\gamma+\delta+\epsilon+$ etc. $=N-1$. If $N$ is even we
may have, say $\alpha=\half N$; and then $\beta+\gamma+\delta+\epsilon+$ etc.
$=\half N-1$, viz. $\alpha$ is larger by unity than the sum of the
remaining numbers: the branch with $\alpha$ knots, or the number $\alpha$, is
said to be ``merely dominant.'' If $N$ be odd, we cannot of course have $\alpha
=\half N$, but we may have $\alpha>\half N$; here $\alpha$ exceeds
by 2 at least the sum of the other numbers; and the branch with $\alpha$
knots, or the number $\alpha$, is said to be ``predominant.'' In every other
case, viz. in the case where each number $\alpha$ is less than $\half N$,
(and where consequently the largest number $\alpha$ does not exceed the sum
of the remaining numbers), the several branches, or the numbers $\alpha,\beta,
\gamma$, etc., are said to be subequal. And we have the theorem: first when
$N$ is odd, there is always one knot (and only one knot) for which the branches
are subequal: such knot is called the centre of number. Secondly when N is
even; either there is one knot (and only one knot) for which the branches are
subequal; and such knot is then called the centre of number; or else there is
no such knot, but there are two adjacent knots (and no other knot) each having
a merely-dominant branch; such two knots are called the bicentre of number,
and each of them separately is a half-centre.
\par
Considering now the trees with $N$ knots as springing from a centre or a
bicentre of number, and writing $\psi_N$ for the whole number of distinct
trees with $N$ knots, we readily obtain these in terms of the foregoing
numbers $\phi_1,\phi_2,\phi_3$, etc., viz. we have
\begin{eqnarray*}
\psi_1 & = & 1, \\
\psi_2 & = & \shalf\phi_1(\phi_1+1), \\
\psi_3 & = & \textrm{coeff.}\ x^2 \ \textrm{in}\ (1-x)^{-\phi_1}, \\
\psi_4 & = & \shalf\phi_2(\phi_2+1) + \textrm{coeff.}\ x^3 \ \textrm{in}\
(1-x)^{-\phi_1}, \\
\psi_5 & = & \textrm{coeff.}\ x^4 \ \textrm{in}\
(1-x)^{-\phi_1}(1-x^2)^{-\phi_2}, \\
\psi_6 & = & \shalf\phi_3(\phi_3+1) + \textrm{coeff.}\ x^5 \ \textrm{in}\
(1-x)^{-\phi_1}(1-x^2)^{-\phi_2}, \\
\psi_7 &=& \textrm{coeff.}\ x^6 \ \textrm{in}\
(1-x)^{-\phi_1}(1-x^2)^{-\phi_2}(1-x^3)^{-\phi_3}, \\
\end{eqnarray*}
%% \newpage
%% --[ page 268 ]--
and so on, the law being obvious. And the formulae are at once seen to be
true. Thus for $N=6$, the formula is
\begin{eqnarray*}
\psi_6 = \shalf\phi_3(\phi_3+1) +\shalf\phi_2(\phi_2+1).\phi_1
+\phi_2.\sfrac{1}{6}\phi_1(\phi_1+1)(\phi_1+2) \\
+\sfrac{1}{120}\phi_1(\phi_1+1)(\phi_1+2)(\phi_1+3)(\phi_1+4).
\end{eqnarray*}
\par
We have $\phi_3$ root-trees with 3 knots, and by simply joining together
any two of them, treating the two roots as a bicentre, we have all the
bicentral trees with 6 knots: this accounts for the term $\half\phi_3
(\phi_3+1)$. Again we have $\phi_1$ root-trees with 1 knot, $\phi_2$ root-trees
with 2 knots; and with a given knot as centre, and the partitions $(2,2,1),
(2,1,1,1), (1,1,1,1,1)$ successively, we build up the central trees of 6 knots,
viz. $1^{\circ}$ we take as branches any two $\phi_2$'s and any one $\phi_1$;
$2^{\circ}$ any one $\phi_2$ and any three $\phi_1$'s; $3^{\circ}$ any five
$\phi_1$'s; the partitions in question being all the partitions of 5 with no
part greater than 2, that is all the partitions with subequal parts. We easily
obtain
\\[.3cm]
\begin{tabular}{@{}rlccccccccccccc@{}}
suffix of&$\psi$ &1& 2& 3& 4& 5& 6& 7& 8& 9& 10& 11& 12 & 13 \\
\hline
&$\psi=$&1& 1& 1& 2& 3& 6& 11& 23& 47& 106& 235& 551& 1301 \\
\end{tabular}
\\[.3cm]
agreeing with the results obtained by the much more complicated formulae of
the paper of 1875.
\end{document}