The Number of Trees

Abstract

The mathematical theory of trees was first discussed by Cayley in 1857 (1). He was successful in finding recursion formulas for counting the number of trees or rooted trees having a finite number of vertices, where the number of branches at a vertex was not limited. Cayley also recognized the possibility of studying the chemical problem of isomers by making use of the notion of a tree, although a restriction on the number of branches that may occur at a vertex is necessary for the solution of this problem. In 1931 Henze and Blair (2) developed recursion formulas for counting the number of trees or rooted trees having the same finite number of vertices, where the number of branches at a vertex was allowed to be at most four, except for a root vertex, which was allowed to have at most three branches. This was the first solution to a problem of isomers in chemistry. The number of such trees with n vertices is precisely the same as the number of structurally isomeric, aliphatic hydrocarbons, i.e. the compounds of the molecular formula CnH2n+2. The number of such rooted trees with n vertices is precisely the same as the number of structurally isomeric, mono-substituted, aliphatic hydrocarbons, i.e. the compounds of the molecular formula CnH2+1XX where X represents any chemical radical or atom different from hydrogen. In his classic publication in 1937 G. Polya (3) developed a powerful method for treating the symmetries of certain types of geometrical configurations under a given permutation group. Using as generating functions, power series whose coefficients represent the number of different possible configurations with respect to this permutation group, methods were developed which yield functional equations for these generating functions. These functional equations contain implicitly recursion formulas for determining the coefficients and his analysis of the functional equations resulted in asymptotic expressions for the coefficients. In particular, Polya studied many problems of interest to chemists, obtaining the recursion formulas of Henze and Blair, and Cayley; but he also solved a wealth of other problems connected with chemical isomers. Although, in his publication Polya restricts himself to counting those trees and rooted trees which are of foremost interest to chemists, it is clear that his methods permit generalization to the counting of trees and rooted trees in the cases we have covered. But it is not apparent that his methods of analysis of the generating functions can be generalized to yield asymptotic values. It seems, however, that although the machinery he has set up is powerful for the solution of some very general problems in symmetries of geometrical configurations, much of it is superfluous for the treatment of trees or of rooted trees