Hostname: page-component-cd9895bd7-8ctnn Total loading time: 0 Render date: 2024-12-23T18:45:02.029Z Has data issue: false hasContentIssue false

The number of plane trees

Published online by Cambridge University Press:  26 February 2010

David W. Walkup
Affiliation:
Department of Applied Mathematics and Computer Science, Washington University, St. Louis, Missouri, U.S.A.
Get access

Extract

By a plane tree or rooted plane tree is meant a realization of a tree or rooted tree by points and arcs in the plane. By an isomorphism between two plane trees or rooted plane trees is meant an isomorphism in the usual sense for such trees which preserves the clockwise cyclic order of the edges about each node. In [2] Harary, Prins, and Tutte demonstrate how Polya's Theorem may be used to obtain formal expressions for the enumerating functions for unrooted, rooted, and other species of plane trees. In the process they obtain the explicit formula

for the number of nonisomorphic planted plane trees with n ≥ 1 edges. (A planted tree is a rooted tree with root at a node of degree one.)

MSC classification

Secondary: 05C05: Trees
Type
Research Article
Copyright
Copyright © University College London 1972

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

References

1.de Bruijn, N. G. and Morselt, B. J. M., “A Note on Plane Trees”, J. Combinatorial Theory, 2 (1967), 2734.CrossRefGoogle Scholar
2.Harary, F., Prins, G. and Tutte, W. T., “The Number of Plane Trees”, Proc. Kon. Ned. Akad. v. Wetensch. (A), 67 (≈ Indag. Math. 26) (1963), 319329.CrossRefGoogle Scholar
3.Knuth, D. E., The Art of Computer Programming, Vol. 1 (Addison-Wesley, 1968).Google Scholar
4.Riordan, J., An Introduction to combinatorial Analysis (Wiley, 1958).Google Scholar