Hostname: page-component-78c5997874-94fs2 Total loading time: 0 Render date: 2024-11-16T17:06:27.529Z Has data issue: false hasContentIssue false
  • English
  • Français

Valency enumeration of rooted plane trees

Published online by Cambridge University Press:  09 April 2009

C. L. Mallows  and
K. W. Wachter
C. L. Mallows
Affiliation:
Bell Telephone Laboratories, Incorporated Murray Hill, New Jersey
K. W. Wachter
Affiliation:
Bell Telephone Laboratories, Incorporated Murray Hill, New Jersey
Rights & Permissions [Opens in a new window]

Abstract

Core share and HTML view are not available for this content. However, as you have access to this content, a full PDF is available via the ‘Save PDF’ action button.

We obtain the enumerator by node-valencies of planted plane trees, whose square gives the enumerator of rooted plane trees. We also study the enumeration by number of nodes and black-node-valencies of bichromatic rooted plane trees, encountering a remarkably simple inversion formula. Finally, we remark that these bichromatic trees are in 1–1 correspondence with solutions to the weak lead ballot problem.

Type
Research Article
Information
Journal of the Australian Mathematical Society , Volume 13 , Issue 4 , June 1972 , pp. 472 - 476
Copyright
Copyright © Australian Mathematical Society 1972

References

[1]David, F. N., Kendall, M. G. and Barton, D. E., Symmetric Functions and Allied Tables (Cambridge University Press, 1966.)Google Scholar
[2]Mallows, C. L. and Wachter, K. W., ‘The asymptotic configuration of Wishart eigenvalues’, in preparation.Google Scholar
[3]Riordan, J., ‘Ballots and trees’, J. Comb. Theory 6 (1969), 408–411.CrossRefGoogle Scholar
[4]Riordan, J., ‘Ballots and plane trees’, unpublished manuscript.Google Scholar
[5]Tutte, W. T., ‘The number of planted plane trees with a given partition’. Amer. Math. Monthly 71 (1964), 272–277.CrossRefGoogle Scholar
[6]Whittaker, E. T. and Watson, G. N., Modern Analysis (4th ed.) (Cambridge University Press, 1940).Google Scholar