Hostname: page-component-cd9895bd7-dk4vv Total loading time: 0 Render date: 2024-12-28T17:40:12.124Z Has data issue: false hasContentIssue false
  • English
  • Français

Another Enumeration of Trees

Published online by Cambridge University Press:  20 November 2018

Donald E. Knuth
Donald E. Knuth*
Affiliation:
California Institute of Technology, Pasadena, California
Rights & Permissions [Opens in a new window]

Extract

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.

Given a set of vertices which have each been assigned one of the colours C1, C2, …, Cm, with nj vertices Cj, a formula is derived for the number of oriented trees on these vertices, having a designated root, and subject to any number of restrictions of the form “no arc goes from a vertex of colour Ci to a vertex of colour Cj”. The formula is based on a combinatorial construction which defines a correspondence between such trees and certain sequences.

Type
Research Article
Information
Canadian Journal of Mathematics , Volume 20 , 1968 , pp. 1077 - 1086
Copyright
Copyright © Canadian Mathematical Society 1968

Footnotes

This research was partially supported by NSF Grant GP 3909.

References

1. Austin, T. L., The enumeration of point labelled chromatic graphs and trees, Can. J. Math. 12 (1960), 535–545.Google Scholar
2. Cayley, A., A theorem on trees, Collected mathematical papers, Volume 13, 26–28.Google Scholar
3. Good, I. J., The generalization of Lagrange's expansion and the enumeration of trees, Proc. Cambridge Philos. Soc. 61 (1965), 499–517.Google Scholar
4. Gould, H. W., Note on problems 4960 and 4984, Amer. Math. Monthly 69 (1962), 572.Google Scholar
5. Knuth, D., Oriented subtrees of an arc digraph, J. Combinatorial Theory 3 (1967), 309–314.Google Scholar
6. Moon, J. W., Various proofs of Cayley's formula for counting trees, A Seminar on Graph Theory, Harary, F., ed. (Holt, Rinehart, and Winston, 1967, pp. 70–78).Google Scholar
7. Prufer, H., Neuer Beweis eines Satzes iiber Permutationen, Arch. Math, und Phys. 27 1918), 142–144.Google Scholar
8. Raney, G., A formal solution of Yf*Li Ai exp(BiX) = X, Can. J. Math. 16 (1964), 755–762.Google Scholar
9. Riordan, J., The enumeration of labeled trees by degrees, Bull. Amer. Math. Soc. 72 (1966), 110–112.Google Scholar
10. Scoins, H. I., The number of trees with nodes of alternate parity, Proc. Cambridge Philos. Soc. 58 (1962), 12–16.Google Scholar
11. Tutte, W., The dissection of equilateral triangles into equilateral triangles, Proc. Cambridge Philos. Soc. 15 (1948), 463–482.Google Scholar