# zbMATH — the first resource for mathematics

The number of plane trees. (English) Zbl 0126.19002
Two plane trees are called map-isomorphic if there exists an orientation-preserving homeomorphism of the plane onto itself which maps one onto the other. Using the well-known enumeration method of G. Pólya [Acta Math. 68, 145–254 (1937; Zbl 0017.23202)], there are found for each positive integer $$n$$, the number of non-map-isomorphic plane trees with $$n$$ vertices. The number of planted plane trees, i. e. plane trees which are rooted at an end vertex, for each integer $$n$$, are the coefficients of the series
\begin{aligned} P(x) = x^2 Z(I_\infty, x^{-1} P(x) &= \tfrac12 x(1-(1-4x)^{1/2}) = \\ &= x^2+x^3+2x^4+5x^5+14x^6+42x^7+\ldots \end{aligned}
The number of unrooted plane trees are obtained by applying Otter’s method as coefficients of the series
\begin{aligned} t(x) &= x Z(C_\infty, x^{-1} P(x)) - (1/2 x^2) (P^2(x)-P(x^2))= \\ &=x+x^2+x^3+2x^4+3x^5+6x^6+14x^7+\ldots \end{aligned}
In the second part of the paper there are discussed trees in the plane closed by adjoining a point $$v_\infty$$. Especially there are discussed trivalent trees, i.e. trees in which each vertex is either monovalent (an end vertex) or trivalent.
Reviewer: D. Dobrev
Show Scanned Page ##### MSC:
 05C05 Trees 05C30 Enumeration in graph theory