×

Reductions of binary trees and lattice paths induced by the register function. (English) Zbl 1380.68305

Summary: The register function (or Horton-Strahler number) of a binary tree is a well-known combinatorial parameter. We study a reduction procedure for binary trees which offers a new interpretation for the register function as the maximal number of reductions that can be applied to a given tree. In particular, the precise asymptotic behavior of the number of certain substructures (“branches”) that occur when reducing a tree repeatedly is determined.
In the same manner we introduce a reduction for simple two-dimensional lattice paths from which a complexity measure similar to the register function can be derived. We analyze this quantity, as well as the (cumulative) size of an (iteratively) reduced lattice path asymptotically.

MSC:

68R05 Combinatorics in computer science
05A10 Factorials, binomial coefficients, combinatorial functions
05A15 Exact enumeration problems, generating functions
05A16 Asymptotic enumeration

Software:

OEIS; SageMath
PDFBibTeX XMLCite
Full Text: DOI arXiv

References:

[1] The SageMath Developers, SageMath Mathematics Software (Version 7.4) (2016)
[2] (Olver, Frank W. J.; Olde Daalhuis, Adri B.; Lozier, Daniel W.; Schneider, Barry I.; Boisvert, Ronald F.; Clark, Charles W.; Miller, Bruce R.; Saunders, Bonita V., NIST Digital Library of Mathematical Functions (2016)), Release 1.0.13, 2016-09-16
[3] Drmota, Michael, Random Trees (2009), Springer: Springer Wien, New York · Zbl 1170.05022
[4] Drmota, Michael; Prodinger, Helmut, The register function for \(t\)-ary trees, ACM Trans. Algorithms, 2, 3, 318-334 (2006) · Zbl 1321.68221
[5] Finch, Steven R., Mathematical constants, Encyclopedia of Mathematics and Its Applications, vol. 94 (2003), Cambridge University Press: Cambridge University Press Cambridge · Zbl 1054.00001
[6] Flajolet, Philippe, Analyse d’algorithmes de manipulation d’arbres et de fichiers, Cahiers du Bureau Universitaire de Recherche Opérationnelle, vols. 34/35, 1-209 (1981)
[7] Flajolet, Philippe; Odlyzko, Andrew, Singularity analysis of generating functions, SIAM J. Discrete Math., 3, 216-240 (1990) · Zbl 0712.05004
[8] Flajolet, Philippe; Prodinger, Helmut, Register allocation for unary-binary trees, SIAM J. Comput., 15, 3, 629-640 (1986) · Zbl 0612.68065
[9] Flajolet, Philippe; Raoult, Jean-Claude; Vuillemin, Jean, The number of registers required for evaluating arithmetic expressions, Theoret. Comput. Sci., 9, 1, 99-125 (1979) · Zbl 0407.68057
[10] Flajolet, Philippe; Sedgewick, Robert, Analytic Combinatorics (2009), Cambridge University Press: Cambridge University Press Cambridge · Zbl 1165.05001
[11] Graham, Ronald L.; Knuth, Donald E.; Patashnik, Oren, Concrete Mathematics. A Foundation for Computer Science (1994), Addison-Wesley · Zbl 0836.00001
[12] Hackl, Benjamin; Heuberger, Clemens; Prodinger, Helmut, The register function and reductions of binary trees and lattice paths, (Proceedings of the 27th International Conference on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms (2016)) · Zbl 1380.68305
[13] Heuberger, Clemens; Kropf, Sara, Higher dimensional quasi-power theorem and Berry-Esseen inequality (2016) · Zbl 1412.60044
[14] Horton, Robert E., Erosioned development of systems and their drainage basins, Geol. Soc. Am. Bull., 56, 275-370 (1945)
[15] Hwang, Hsien-Kuei, On convergence rates in the central limit theorems for combinatorial structures, European J. Combin., 19, 329-343 (1998) · Zbl 0906.60024
[16] Kemp, Rainer, The average number of registers needed to evaluate a binary tree optimally, Acta Inform., 11, 4, 363-372 (1978/79) · Zbl 0395.68059
[17] Louchard, Guy; Prodinger, Helmut, The register function for lattice paths, (Fifth Colloquium on Mathematics and Computer Science. Discrete Math. Theor. Comput. Sci. Proc., AI (2008)), 135-148 · Zbl 1355.05085
[18] Moon, John W., On Horton’s law for random channel networks, Combinatorics 79 (Proc. Colloq., Univ. Montréal, Montreal, Que., 1979), Part I. Combinatorics 79 (Proc. Colloq., Univ. Montréal, Montreal, Que., 1979), Part I, Ann. Discrete Math., 8, 117-121 (1980) · Zbl 0443.05035
[19] Nebel, Markus E., A unified approach to the analysis of Horton-Strahler parameters of binary tree structures, Random Struct. Algorithms, 21, 3-4, 252-277 (2002), Random structures and algorithms (Poznan, 2001) · Zbl 1027.68102
[20] The On-Line Encyclopedia of Integer Sequences (2016)
[21] Prodinger, Helmut, On a problem of Yekutieli and Mandelbrot about the bifurcation ratio of binary trees, Theoret. Comput. Sci., 181, 1, 181-194 (1997) · Zbl 0901.68147
[22] Prodinger, Helmut, Analytic methods, (Bóna, Miklós, Handbook of Enumerative Combinatorics. Handbook of Enumerative Combinatorics, CRC Press Series on Discrete Mathematics and Its Applications (2015), Chapman & Hall/CRC: Chapman & Hall/CRC Boca Raton, FL), 173-252 · Zbl 1326.05011
[23] Helmut Prodinger, Introduction to Philippe Flajolet’s work on the register function and related topics, Mark Daniel Ward, ed., Philippe Flajolet’s Collected Papers, vol. V, to appear.; Helmut Prodinger, Introduction to Philippe Flajolet’s work on the register function and related topics, Mark Daniel Ward, ed., Philippe Flajolet’s Collected Papers, vol. V, to appear.
[24] Shapiro, Louis W., A short proof of an identity of Touchard’s concerning Catalan numbers, J. Combin. Theory Ser. A, 20, 3, 375-376 (1976) · Zbl 0337.05012
[25] Spanier, Jerome; Oldham, Keith, An Atlas of Functions (1987), Taylor & Francis/Hemisphere: Taylor & Francis/Hemisphere Bristol, PA, USA · Zbl 0618.65007
[26] Strahler, Arthur N., Hypsomic analysis of erosional topography, Geol. Soc. Am. Bull., 63, 1117-1142 (1952)
[27] Touchard, Jacques, Sur certaines équations fonctionnelles, (Proc. Internat. Math. Congress I. Proc. Internat. Math. Congress I, 1924 (1928)), 465-472 · JFM 54.0440.03
[28] Gérard Viennot, Xavier, A Strahler bijection between Dyck paths and planar trees, Discrete Math.. Discrete Math., Formal Power Series and Algebraic Combinatorics, 246, 1-3, 317-329 (1999) · Zbl 0997.05026
[29] Wagner, Stephan, Central limit theorems for additive tree parameters with small toll functions, Combin. Probab. Comput., 24, 329-353 (2015) · Zbl 1371.60033
[30] Wang, Stanley Xi; Waymire, Edward C., A large deviation rate and central limit theorem for Horton ratios, SIAM J. Discrete Math., 4, 4, 575-588 (1991) · Zbl 0739.60023
[31] Whittaker, Edmund T.; Watson, George N., A Course of Modern Analysis (1996), Cambridge University Press: Cambridge University Press Cambridge, Reprint of the fourth (1927) edition · Zbl 0951.30002
[32] Yamamoto, Ken; Yamazaki, Yoshihiro, Central limit theorem for the bifurcation ratio of a random binary tree, J. Phys. A, 42, 41, Article 415002 pp. (2009) · Zbl 1182.60012
[33] Yamamoto, Ken; Yamazaki, Yoshihiro, Topological self-similarity on the random binary-tree model, J. Stat. Phys., 139, 1, 62-71 (2010) · Zbl 1193.05148
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.