×

Asymptotic enumeration of compacted binary trees of bounded right height. (English) Zbl 1433.05154

Summary: A compacted binary tree is a graph created from a binary tree such that repeatedly occurring subtrees in the original tree are represented by pointers to existing ones, and hence every subtree is unique. Such representations form a special class of directed acyclic graphs. We are interested in the asymptotic number of compacted trees of given size, where the size of a compacted tree is given by the number of its internal nodes. Due to its superexponential growth this problem poses many difficulties. Therefore we restrict our investigations to compacted trees of bounded right height, which is the maximal number of edges going to the right on any path from the root to a leaf.
We solve the asymptotic counting problem for this class as well as a closely related, further simplified class.
For this purpose, we develop a calculus on exponential generating functions for compacted trees of bounded right height and for relaxed trees of bounded right height, which differ from compacted trees by dropping the above described uniqueness condition. This enables us to derive a recursively defined sequence of differential equations for the exponential generating functions. The coefficients can then be determined by performing a singularity analysis of the solutions of these differential equations. Our main results are the computation of the asymptotic numbers of relaxed as well as compacted trees of bounded right height and given size, when the size tends to infinity.

MSC:

05C30 Enumeration in graph theory
05C05 Trees
05C20 Directed graphs (digraphs), tournaments
05A16 Asymptotic enumeration

Software:

DLMF
PDFBibTeX XMLCite
Full Text: DOI arXiv Link

References:

[1] Abramowitz, M.; Stegun, I. A., Handbook of Mathematical Functions With Formulas, Graphs, and Mathematical Tables, National Bureau of Standards Applied Mathematics Series, vol. 55 (1964), U.S. Government Printing Office: U.S. Government Printing Office Washington, DC, For sale by the Superintendent of Documents · Zbl 0171.38503
[2] Aho, A. V.; Sethi, R.; Ullman, J. D., Compilers, Principles, Techniques (1986), Addison-Wesley: Addison-Wesley Boston
[3] Akkan, C.; Drexl, A.; Kimms, A., Generating two-terminal directed acyclic graphs with a given complexity index by constraint logic programming, J. Log. Algebraic Program., 62, 1, 1-39 (2005) · Zbl 1101.68711
[4] Bender, E. A.; Richmond, L. B.; Robinson, R. W.; Wormald, N. C., The asymptotic number of acyclic digraphs. I, Combinatorica, 6, 1, 15-22 (1986) · Zbl 0601.05025
[5] Bender, E. A.; Robinson, R. W., The asymptotic number of acyclic digraphs. II, J. Comb. Theory, Ser. B, 44, 3, 363-369 (1988) · Zbl 0654.05035
[6] Bodini, O.; Dien, M.; Genitrini, A.; Peschanski, F., The ordered and colored products in analytic combinatorics: application to the quantitative study of synchronizations in concurrent processes, (Proceedings of the Meeting on Analytic Algorithmics and Combinatorics. Proceedings of the Meeting on Analytic Algorithmics and Combinatorics, ANALCO’17 (2017)) · Zbl 1429.68145
[7] Bodini, O.; Gardy, D.; Gittenberger, B., Lambda terms of bounded unary height, (Proceedings of the Meeting on Analytic Algorithmics and Combinatorics. Proceedings of the Meeting on Analytic Algorithmics and Combinatorics, ANALCO ’11 (2011), Society for Industrial and Applied Mathematics: Society for Industrial and Applied Mathematics Philadelphia, PA, USA), 23-32 · Zbl 1429.68155
[8] Bodini, O.; Gardy, D.; Gittenberger, B.; Gołębiewski, Z., On the number of unary-binary tree-like structures with restrictions on the unary height, Ann. Comb., 22, 1, 45-91 (2018) · Zbl 1384.05034
[9] Bodini, O.; Gardy, D.; Gittenberger, B.; Jacquot, A., Enumeration of generalized BCI lambda-terms, Electron. J. Comb., 20, 4, P30 (2013) · Zbl 1295.05040
[10] Bousquet-Mélou, M.; Lohrey, M.; Maneth, S.; Noeth, E., XML compression via directed acyclic graphs, Theory Comput. Syst., 57, 4, 1322-1371 (2015) · Zbl 1352.68079
[11] Carnino, V.; De Felice, S., Sampling different kinds of acyclic automata using Markov chains, Theor. Comput. Sci., 450, 31-42 (2012) · Zbl 1276.68090
[12] F.W.J. Olver, A.B. Olde Daalhuis, D.W. Lozier, B.I. Schneider, R.F. Boisvert, C.W. Clark, B.R. Miller, B.V. Saunders (Eds.), NIST Digital Library of Mathematical Functions, http://dlmf.nist.gov/, release 1.0.13 of 2016-09-16.
[13] Downey, P. J.; Sethi, R.; Tarjan, R. E., Variations on the common subexpression problem, J. Assoc. Comput. Mach., 27, 4, 758-771 (1980) · Zbl 0458.68026
[14] Flajolet, P.; Sedgewick, R., Analytic Combinatorics (2009), Cambridge University Press · Zbl 1165.05001
[15] Flajolet, P.; Sipala, P.; Steyaert, J.-M., Analytic variations on the common subexpression problem, (Automata, Languages and Programming. Automata, Languages and Programming, Coventry, 1990. Automata, Languages and Programming. Automata, Languages and Programming, Coventry, 1990, Lecture Notes in Comput. Sci., vol. 443 (1990), Springer: Springer New York), 220-234 · Zbl 0765.68048
[16] Grabner, P. J.; Steinsky, B., Asymptotic behaviour of the poles of a special generating function for acyclic digraphs, Aequ. Math., 70, 3, 268-278 (2005) · Zbl 1081.05011
[17] Henrici, P., Applied and Computational Complex Analysis, vol. 2 (1991), John Wiley & Sons, Inc.: John Wiley & Sons, Inc. New York, Special functions—integral transforms—asymptotics—continued fractions, Reprint of the 1977 original, a Wiley-Interscience Publication · Zbl 0925.30003
[18] Ince, E. L., Ordinary Differential Equations (1944), Dover Publications: Dover Publications New York · Zbl 0063.02971
[19] Kauers, M.; Paule, P., The Concrete Tetrahedron: Symbolic Sums, Recurrence Equations, Generating Functions, Asymptotic Estimates, Texts and Monographs in Symbolic Computation (2011), SpringerWien NewYork: SpringerWien NewYork Vienna · Zbl 1225.00001
[20] Liskovets, V. A., Exact enumeration of acyclic deterministic automata, Discrete Appl. Math., 154, 3, 537-551 (2006) · Zbl 1090.68060
[21] McDiarmid, C.; Semple, C.; Welsh, D., Counting phylogenetic networks, Ann. Comb., 19, 1, 205-224 (2015) · Zbl 1310.05120
[22] McKay, B. D., On the shape of a random acyclic digraph, Math. Proc. Camb. Philos. Soc., 106, 3, 459-465 (1989) · Zbl 0702.05040
[23] Melançon, G.; Dutour, I.; Bousquet-Mélou, M., Random generation of directed acyclic graphs, (Comb01—Euroconference on Combinatorics, Graph Theory and Applications. Comb01—Euroconference on Combinatorics, Graph Theory and Applications, Electron. Notes Discrete Math., vol. 10 (2001), Elsevier: Elsevier Amsterdam), 6 pp. (electronic) · Zbl 1171.05339
[24] Melançon, G.; Philippe, F., Generating connected acyclic digraphs uniformly at random, Inf. Process. Lett., 90, 4, 209-213 (2004) · Zbl 1177.68155
[25] Mezzarobba, M., Autour de l’évaluation numérique des fonctions D-finies (November 2011), École polytechnique: École polytechnique France, Palaiseau, PhD thesis
[26] Pólya, G., Kombinatorische Anzahlbestimmungen für Gruppen, Graphen und chemische Verbindungen, Acta Math., 68, 1, 145-254 (1937) · JFM 63.0547.04
[27] Ralaivaosaona, D.; Wagner, S., Repeated fringe subtrees in random rooted trees, (2015 Proceedings of the Twelfth Workshop on Analytic Algorithmics and Combinatorics. 2015 Proceedings of the Twelfth Workshop on Analytic Algorithmics and Combinatorics, ANALCO (2015), SIAM: SIAM Philadelphia, PA), 78-88 · Zbl 1430.05114
[28] Robinson, R. W., Enumeration of acyclic digraphs, (Proc. Second Chapel Hill Conf. on Combinatorial Mathematics and Its Applications. Proc. Second Chapel Hill Conf. on Combinatorial Mathematics and Its Applications, Univ. North Carolina, Chapel Hill, N.C., 1970 (1970), Univ. North Carolina: Univ. North Carolina Chapel Hill, NC), 391-399 · Zbl 0219.05065
[29] Robinson, R. W., Counting labeled acyclic digraphs, (New Directions in the Theory of Graphs, Proc. Third Ann Arbor Conf.. New Directions in the Theory of Graphs, Proc. Third Ann Arbor Conf., Univ. Michigan, Ann Arbor, Mich., 1971 (1973), Academic Press: Academic Press New York), 239-273
[30] Robinson, R. W., Counting unlabeled acyclic digraphs, (Combinatorial Mathematics, V, Proc. Fifth Austral. Conf., Roy.. Combinatorial Mathematics, V, Proc. Fifth Austral. Conf., Roy., Melbourne Inst. Tech., Melbourne, 1976. Combinatorial Mathematics, V, Proc. Fifth Austral. Conf., Roy.. Combinatorial Mathematics, V, Proc. Fifth Austral. Conf., Roy., Melbourne Inst. Tech., Melbourne, 1976, Lecture Notes in Math., vol. 622 (1977), Springer: Springer Berlin), 28-43
[31] Schlesinger, L., Handbuch der Theorie der linearen Differentialgleichungen: In zwei Bänden, Band I, Bibliotheca Mathematica Teubneriana, Band 30 (1968), Johnson Reprint Corp.: Johnson Reprint Corp. New York-London, Reprint · JFM 26.0329.01
[32] Stanley, R. P., Enumerative Combinatorics, vol. 2, Cambridge Studies in Advanced Mathematics, vol. 62 (1999), Cambridge University Press: Cambridge University Press Cambridge, with a foreword by Gian-Carlo Rota and appendix 1 by Sergey Fomin · Zbl 0928.05001
[33] Steinsky, B., Enumeration of labelled chain graphs and labelled essential directed acyclic graphs, Discrete Math., 270, 1-3, 267-278 (2003) · Zbl 1060.05047
[34] Steinsky, B., Asymptotic behaviour of the number of labelled essential acyclic digraphs and labelled chain graphs, Graphs Comb., 20, 3, 399-411 (2004) · Zbl 1055.05081
[35] Wagner, S., Asymptotic enumeration of extensional acyclic digraphs, Algorithmica, 66, 4, 829-847 (2013) · Zbl 1275.05029
[36] Wallner, M., A bijection of plane increasing trees with relaxed binary trees of right height at most one, Theor. Comput. Sci., 755, 1-12 (2019) · Zbl 1441.05051
[37] Wasow, W., Asymptotic Expansions for Ordinary Differential Equations (1987), Dover Publications, Inc.: Dover Publications, Inc. New York, Reprint of the 1976 edition · Zbl 0169.10903
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.