244 
ON THE THEORY OF THE ANALYTICAL FORMS CALLED TREES. 
[203 
first of which contains only four, while the latter contains six trees, viz. the first tree, 
the second, third and fourth trees, the fifth tree and the sixth tree of fig. 3 (bis) 
correspond respectively to the first tree, the second tree, the third tree, and the fourth 
tree of fig. 3. To derive fig. 3 (bis) from fig. 3, we must fill up the trees of fig. 3 
with U at the root and R, Q, P at the other knots in every possible manner, 
subject only to the restriction, that, reckoning up from the extremity of a free branch 
to the root, there must not be any transposition in the order of the symbols RQP, 
and taking care to admit only distinct trees. Thus the first tree of fig. 3 might be 
filled up in six ways; but the trees so obtained are considered as one and the same 
tree, and we have only the first tree of fig. 3 (bis). Again, on account of the 
restriction, the fourth tree of fig. 3 can be filled up in one way only, and we have 
thus the sixth tree of fig. 3 (bis). And thus, in general, each figure of the second 
set can be formed at once from the corresponding figure of the first set; or when 
the first set of figures is given, the expression for YX...QPU can be formed directly 
without the assistance of the expression for the preceding symbol X...QPU; the 
number of terms for the nth figure of the second set is obviously 1.2.3...», and 
consequently it is only necessary to count the terms in order to ascertain that no 
admissible mode of filling up has been omitted. 
The number of parts in any one of the figures of the first set is much smaller 
than the number of parts in the corresponding figure of the second set; and the 
law for the number of parts, i.e. for the number A n of the trees with n branches, 
is a very singular one. To obtain this law, we must consider how the trees with n 
branches can be formed by means of those of a smaller number of branches. A tree 
with n branches has either a single main branch, or else two main branches, three 
main branches, &c....to n main branches. If the tree has one main branch, it can 
only be formed by adding on to this main branch a tree with (n — 1) branches, 
i.e. A n contains a part A n _ x . If the tree has two main branches, then p + q being 
a partition of n — 2, the tree can be formed by adding on to one main branch a 
tree of p branches, and to the other main branch a tree of q branches; the number 
of trees so obtained is A p A q : this, however, assumes that the parts p and q are 
unequal; if they are equal, it is easy to see that the number of trees is only 
%A p (A p + l). Hence p + q being any partition of »-2, A n contains the part A p A q 
if p and q are unequal, and the part %A p (A p +1) if p and q are equal. In like 
manner, considering the trees with three main branches, then if p + q + r is any 
partition of n — 3, A n contains the part A p A q A r if p, q, r are unequal; but if two 
of these numbers, e.g. p and q, are equal, then the part \A P (A p +1) A r \ and if 
p, q, r are all equal, then the part ±A P (A p +1) (A p + 2); and so on, until lastly we 
have a single tree with n main branches, or A n contains the part unity. A little 
consideration will show that the preceding rule for the formation of the number A n 
is completely expressed by the equation 
(1 — #) _1 (1 — x 2 )~+ (1 — o?)~+ (1 — o?)~+. .. = 1 + Ape + Ap? + Ap? + Ap? + &c., 
and consequently that we may, by means of this equation, calculate successively for 
the different values of n the number A n of the trees with n branches. The calculation