Otter's Tree Enumeration Constants

A graph of order n consists of a set of n vertices (points) together with a set of edges (unordered pairs of distinct points). Note that loops and multiple parallel edges are automatically disallowed. Two points joined by an edge are called adjacent.

A tree is a graph which is

  • connected, i.e., for any two distinct vertices u and w, there is a sequence of vertices v(0), v(1), ... , v(m) such that v(0)=u, v(m)=w and v(k) is adjacent to v(k+1), for all k<m

  • acyclic, i.e., there is no sequence of adjacent vertices v(0), v(1), ... , v(m), with v(i), v(j) distinct for each i<j<m, such that v(0)=v(m).
Two trees S and T are isomorphic if there is a one-to-one map from the vertices of S to the vertices of T which preserves adjacency. Here, for example, are all three non-isomorphic trees of order 5:



Harary [1] gave diagrams for all non-isomorphic trees of order < 11.

What can be said about the asymptotics of t(n), the number of non-isomorphic trees of order n? Building on the work of Cayley and Pólya, Otter [2-4] determined that


where is the unique positive root of the equation



involving a certain function f, and


where denotes the derivative of f. The function f used above is specified by the analytic power series

whose coefficients satisfy





In fact, f is the generating function for what are known as rooted trees [3] and is its radius of convergence.

There exist many species of trees and the elaborate details of enumerating them are best left to [2,3]. We give, however, one example of special interest.

First, a rooted tree is a tree in which precisely one vertex, called the root, is distinguished from the others. We agree to draw the root as a tree's leftmost vertex. A weakly binary tree is a rooted tree for which the root is adjacent to at most 2 vertices and all non-root vertices are adjacent to at most 3 vertices. Here, for example, are all six non-isomorphic weakly binary trees of order 5:



The asymptotics of b(n), the number of non-isomorphic weakly binary trees of order n, were also obtained by Otter [2,4,5]:


where is the unique positive root of the equation



involving a certain function g, and by a formula analogous to that for earlier. (Knuth [4] corrected a mistaken value for in Otter [2].) The function g used above is specified by the analytic power series

whose coefficients satisfy






Otter showed, in this special example, that the following interesting formula holds:

where the sequence {} obeys the quadratic recurrence




and consequently



Here is a slight variation on the above. Define a strongly binary tree to be a rooted tree for which the root is adjacent to either 0 or 2 vertices, and all non-root vertices are adjacent to either 1 or 3 vertices. These trees, also called binary trees or strictly binary trees, are discussed further in my notes on Random Binary Trees Grown via the Galton-Watson Branching Process. For example, there are two non-isomorphic strongly binary trees of order 7:



What is known about the number of non-isomorphic strongly binary trees of order 2n+1? This turns out to be exactly b(n). The one-to-one correspondence is obtained, in the forward direction, by deleting all the leaves of a strongly binary tree. To go in reverse, starting with a "stripped-down" weakly binary tree, add two leaves to any vertex of degree 1 (or to the root if it has degree 0), and one leaf to any vertex of degree 2 (or to the root if it has degree 1). This always works, so the above asymptotics also apply here.

Applications of this material include chemistry (enumerating isometric hydrocarbons), abstract algebra (enumerating interpretations of in commutative non-associative algebras) and much more [5].

Relevant Mathcad files will be included as time permits.

Postscript
We didn't mention Otter's corresponding result for rooted trees (as opposed to free trees):



Although these constants can be calculated efficiently to great accuracy, we do not know whether they are algebraic or transcendental [10,11]. Plouffe gave an accurate approximation, due to Broadhurst [15,16], of both constants in the Inverse Symbolic Calculator web pages.

Let G be a graph and let A(G) be the automorphism group of G. A vertex v of G is a fixed point if h(v)=v for every h in A(G). Harary and Palmer 18] proved that the limiting probability of a fixed point in a large random tree, whether rooted or not, is 0.69953887.... Broadhurst [16,17] has computed this constant to high precision.

Labeled graphs are easier to enumerate than unlabeled graphs [1,3]. We mention one example: the number a(n) of labeled graphs of order n, in which every vertex has degree two, satisfies [19]







See Robinson [20,21] for an interesting geometric connection.

Elsewhere, we mention the average height of strictly binary trees and the asymptotic number of non-isomorphic identity trees.

References

  1. F. Harary, Graph Theory, Addison-Wesley, 1969; MR 41 #1566.
  2. R. Otter, The number of trees, Annals of Math. 49 (1948) 583-599; MR 10,53c.
  3. F. Harary and E. M. Palmer, Graphical Enumeration, Academic Press, 1973; MR 50 #9682.
  4. D. E. Knuth, The Art of Computer Programming, v. 1, Fundamental Algorithms, Addison-Wesley, 1997; MR 51 #14624.
  5. Solution to problem 4277, Genetic algebra, Amer. Math. Monthly 56 (1949) 697-699.
  6. L. Comtet, Advanced Combinatorics: The Art of Finite and Infinite Expansions, Reidel, 1974; MR 57 #124.
  7. E. A. Bender, Asymptotic methods in enumeration, SIAM Review 16 (1974) 485-515, errata 18 (1976) 292; MR 51 #12545 and MR 55 #10276.
  8. N. J. A. Sloane, On-Line Encyclopedia of Integer Sequences, AT&T; Research, A000055, A000081, A001190.
  9. C. Domb, Graph theory and embeddings, Phase Transitions and Critical Phenomena, v. 3, ed. C. Domb and M. S. Green, Academic Press, 1974; MR 50 #6393.
  10. A. M. Odlyzko, Asymptotic enumeration methods, Handbook of Combinatorics, R. L. Graham, M. Groetschel, L. Lovasz, eds., North Holland, 1995, pp. 1063-1229; preprint; MR 97b:05012.
  11. A. M. Odlyzko, Some new methods and results in tree enumeration, Congr. Numer. 42 (1984) 27-52; preprint; MR 85g:05061.
  12. F. Bergeron, G. Labelle and P. Leroux, Combinatorial Species and Tree-Like Structures, Cambridge Univ. Press, 1998; MR 2000a:05008.
  13. J. W. Moon, Counting Labelled Trees, Canad. Math. Monographs, 1970; MR 43 #98.
  14. V. F. Kolchin, Random Mappings, Optimization Software Inc., 1986; MR 88a:60022.
  15. D. J. Broadhurst and D. Kreimer, Renormalization automated by Hopf algebra, J. Symbolic Comput. 27 (1999) 581-600; hep-th/9810087.
  16. D. J. Broadhurst, private communication (1999).
  17. N. J. A. Sloane, On-Line Encyclopedia of Integer Sequences, AT&T; Research, A005200, A005201.
  18. F. Harary and E. M. Palmer, The probability that a point of a tree is fixed, Math. Proc. Cambridge Philos. Soc. 85 (1979) 407-415; MR 80f:05020.
  19. H. S. Wilf, generatingfunctionology, Academic Press, 1990; reprint; MR 95a:05002.
  20. R. Robinson, A new absolute geometric constant, Amer. Math. Monthly 58 (1951) 462-469; addendum 59 (1952) 296-297; MR 13,200b.
  21. N. J. A. Sloane, On-Line Encyclopedia of Integer Sequences, AT&T; Research, A001205.
  22. A. Meir and J. W. Moon, Packing and covering constants for certain families of trees, II, Trans. Amer. Math. Soc. 233 (1977) 167-178; MR 57 #157.
  23. R. Sedgewick and P. Flajolet, Introduction to the Analysis of Algorithms, Addison-Wesley, 1996, pp. 280-282.
  24. G. Pólya and R. C. Read, Combinatorial Enumeration of Groups, Graphs, and Chemical Compounds, Springer-Verlag, 1987, pp. 130-134; MR 89f:05013.
  25. R. W. Robinson, Counting labeled acyclic digraphs, New Directions in the Theory of Graphs, Proc. 1971 Ann Arbor conf., ed. F. Harary, Academic Press, 1973, pp. 239-273; MR 51 #249.
  26. R. W. Robinson, Counting unlabeled acyclic digraphs, Combinatorial Mathematics V, Proc. 1976 Melbourne conf., ed. C. H. C. Little, Lecture Notes in Math. 622, Springer-Verlag, 1977, pp. 28-43; MR 57 #16129.
  27. R. P. Stanley, Acyclic orientations of graphs, Discrete Math. 5 (1973) 171-178; MR 47 #6537.
  28. V. A. Liskovec, The number of maximal vertices of a random acyclic digraph, Teoriya Veroyatnostei i ee Primeneniya 20 (1975) 412-421; Engl. transl. in Theory of Probability and its Applications 20 (1975) 401-421; MR 52 #1822.
  29. E. A. Bender, L. B. Richmond, R. W. Robinson and N. C. Wormald, The asymptotic number of acyclic digraphs, I, Combinatorica 6 (1986) 15-22; MR 87m:05102.
  30. V. I. Rodionov, On the number of labeled acyclic digraphs, Discrete Math. 105 (1992) 319-321; MR 93h:05094.
  31. K. Mahler, On a special functional equation, J. London Math. Soc. 15 (1940) 115-123; MR 2,133e.
  32. N. J. A. Sloane, On-Line Encyclopedia of Integer Sequences, AT&T; Research, A003024, A003087.

Return to the Favorite Mathematical Constants page.
Return to the Unsolved Mathematics Problems page.
Return to the MathSoft home page.

Copyright © 1995-2001 Steven Finch
MathSoft Engineering & Education, Inc.
All rights reserved.