Hostname: page-component-586b7cd67f-g8jcs Total loading time: 0 Render date: 2024-11-26T08:51:53.706Z Has data issue: false hasContentIssue false
  • English
  • Français

The number of plane trees with a given partition

Published online by Cambridge University Press:  26 February 2010

F. Harary  and
W. T. Tutte
F. Harary
Affiliation:
University of Michigan.
W. T. Tutte
Affiliation:
University of Waterloo.
Get access

Extract

This note is a continuation of the articles [6] and [2]. In [1], trees with a given partition α = (a1; a2, …), where ai is the number of vertices (points) of valency (degree) i were enumerated. After the determination of the number of plane trees in [2], the number of planted plane trees with a given partition α was found explicitly in [6]. In the present note, the number of plane trees with a given partition is expressed as a function of the number of planted trees with a given partition. The method, which is not new, consists of an application of the enumeration techniques of Otter [3] and Pólya [4]; it was used in [1] and also by Riordan [5].

Type
Research Article
Information
Mathematika , Volume 11 , Issue 2 , December 1964 , pp. 99 - 101
Copyright
Copyright © University College London 1964

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. Harary, F. and Prins, G., “The number of homeomorphically irreducible trees, and other species”, Acta Math., 101 (1959), 141–162.CrossRefGoogle Scholar
2. Harary, F. and Prins, G., and Tutte, W. T., “The number of plane trees”, Nederl. Wetensch. Proc. Ser. A,67 = Indag, Math., 26 (1964), 319–329.Google Scholar
3. Otter, R., “The number of trees”, Annals of Math., 49 (1948), 583–599.CrossRefGoogle Scholar
4. Pólya, G., “Kombinatorische Anzahlbestimmungen für Gruppen, Graphen und chemische Verbindungen”, Acta Math., 68 (1937), 145–254.CrossRefGoogle Scholar
5. Riordan, J.. “The numbers of labeled colored and chromatic trees”, Acta Math., 97 (1957), 211–225.CrossRefGoogle Scholar
6. Tutte, W. T., “The number of planted plane trees with a given partition”, American Math. Monthly, 71 (1964), 272–277.CrossRefGoogle Scholar
7. Read, R. C., “A note on the number of functional digraphs”, Math. Annalen, 143 (1961), 109–110.CrossRefGoogle Scholar