×

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

MSC:
05C05 Trees
05C30 Enumeration in graph theory
PDF BibTeX XML Cite