Wallner, Michael A bijection of plane increasing trees with relaxed binary trees of right height at most one. (English) Zbl 1441.05051 Theor. Comput. Sci. 755, 1-12 (2019). Summary: Plane increasing trees are rooted labeled trees embedded into the plane such that the sequence of labels is increasing on any branch starting at the root. Relaxed binary trees are a subclass of unlabeled directed acyclic graphs. We construct a bijection between these two combinatorial objects and study the therefrom arising connections of certain parameters. Furthermore, we show central limit theorems for two statistics on leaves. We end the study by considering more than 20 subclasses and their bijective counterparts. Many of these subclasses are enumerated by known counting sequences, and thus enrich their combinatorial interpretation. Cited in 3 Documents MSC: 05C05 Trees 05C10 Planar graphs; geometric and topological aspects of graph theory 05C78 Graph labelling (graceful graphs, bandwidth, etc.) 05C30 Enumeration in graph theory 11B39 Fibonacci and Lucas numbers and polynomials and generalizations Keywords:bijection; directed acyclic graphs; increasing trees; Fibonacci numbers; analytic combinatorics; limit laws; random generation Software:OEIS PDFBibTeX XMLCite \textit{M. Wallner}, Theor. Comput. Sci. 755, 1--12 (2019; Zbl 1441.05051) Full Text: DOI arXiv Online Encyclopedia of Integer Sequences: Double factorial of odd numbers: a(n) = (2*n-1)!! = 1*3*5*...*(2*n-1). a(n) = (2*n + 3)!!/3 = A001147(n+2)/3. Expansion of e.g.f.: (x/(1-x))*exp(x/(1-x)). Number of deterministic completely defined initially connected acyclic automata with 2 inputs and n transient unlabeled states (and a unique absorbing state). a(n) = (n-1)*a(n-2), a(0)=1, a(1)=0. E.g.f.: exp(x^2 / 2) / (1 - x). a(n) = (n+1)*(a(n-1) +a(n-2)) n>1, a(0)=1,a(1)=0 Expansion of e.g.f. arcsin(x). Alternating row sums of triangle A201201: first associated monic Laguerre-Sonin(e) polynomials with parameter alpha=1 evaluated at x=-1. E.g.f.: exp( Sum_{n>=1} Fibonacci(n+1)*x^n/n ), where Fibonacci(n) = A000045(n). Number of relaxed compacted binary trees of right height at most one with empty initial and final sequence on level 0. Number of relaxed compacted binary trees of right height at most one with empty sequences between branch nodes on level 0. Number of relaxed compacted binary trees of right height at most one with minimal sequences between branch nodes except after the last branch node on level 0. Number of relaxed compacted binary trees of right height at most one with minimal sequences between branch nodes except before the first and after the last branch node on level 0. Number of simple relaxed compacted binary trees of right height at most one with no sequences on level 1 and no final sequences on level 0. References: [1] Albert, R.; Barabási, A.-L., Statistical mechanics of complex networks, Rev. Modern Phys., 74, 1, 47-97 (Jan. 2002) [2] Bergeron, F.; Flajolet, P.; Salvy, B., Varieties of increasing trees, (CAAP ’92. CAAP ’92, Rennes, 1992. CAAP ’92. CAAP ’92, Rennes, 1992, Lecture Notes in Computer Science, vol. 581 (1992), Springer: Springer Berlin Heidelberg), 24-48 [3] 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 [4] Broutin, N.; Devroye, L.; McLeish, E.; de la Salle, M., The height of increasing trees, Random Structures Algorithms, 32, 4, 494-518 (2008) · Zbl 1148.05024 [5] Callan, D., A combinatorial survey of identities for the double factorial (2009), ArXiv preprint [6] Drmota, M., The height of increasing trees, Ann. Comb., 12, 4, 373-402 (Mar 2009) [7] Drmota, M., Random Trees: An Interplay Between Combinatorics and Probability (2009), Springer Science & Business Media · Zbl 1170.05022 [8] Flajolet, P.; Sedgewick, R., Analytic Combinatorics (2009), Cambridge University Press · Zbl 1165.05001 [9] Flajolet, P.; Sipala, P.; Steyaert, J.-M., Analytic variations on the common subexpression problem, (Automata, Languages and Programming. Automata, Languages and Programming, Lecture Notes in Computer Science, vol. 443 (1990), Springer), 220-234 · Zbl 0765.68048 [10] Genitrini, A.; Gittenberger, B.; Kauers, M.; Wallner, M., Asymptotic enumeration of compacted binary trees of bounded right height (2017), ArXiv preprint · Zbl 1433.05154 [11] Janson, S., Plane recursive trees, Stirling permutations and an urn model, (Fifth Colloquium on Mathematics and Computer Science. Fifth Colloquium on Mathematics and Computer Science, Nancy. Fifth Colloquium on Mathematics and Computer Science. Fifth Colloquium on Mathematics and Computer Science, Nancy, Discrete Math. Theor. Comput. Sci. Proc., AI (2008), Assoc. Discrete Math. Theor. Comput. Sci.), 541-547 · Zbl 1358.60015 [12] Janson, S.; Kuba, M.; Panholzer, A., Generalized Stirling permutations, families of increasing trees and urn models, J. Combin. Theory Ser. A, 118, 1, 94-114 (Jan. 2011) [13] Kuba, M.; Panholzer, A., On the degree distribution of the nodes in increasing trees, J. Combin. Theory Ser. A, 114, 4, 597-618 (May 2007) [14] Mahmoud, H. M., Distances in random plane-oriented recursive trees, Asymptotic Methods in Analysis and Combinatorics. Asymptotic Methods in Analysis and Combinatorics, J. Comput. Appl. Math., 41, 1-2, 237-245 (aug 1992) [15] Mahmoud, H. M.; Smythe, R. T.; Szymański, J., On the structure of random plane-oriented recursive trees and their branches, Random Structures Algorithms, 4, 2, 151-176 (1993) · Zbl 0773.05040 [16] Pittel, B., Note on the heights of random recursive trees and random \(m\)-ary search trees, Random Structures Algorithms, 5, 2, 337-347 (1994) · Zbl 0790.05077 [17] Sachkov, V. N., Probabilistic Methods in Combinatorial Analysis, Encyclopedia of Mathematics and its Applications, vol. 56 (1997), Cambridge University Press: Cambridge University Press Cambridge, Translated from the Russian, Revised by the author · Zbl 0874.60020 [18] Sloane, N. J.A., The on-line encyclopedia of integer sequences (OEIS) · Zbl 1044.11108 [19] Smythe, R. T.; Mahmoud, H. M., A survey of recursive trees, Theory Probab. Math. Statist., 51, 1-27 (1994) · Zbl 0933.05038 [20] Wallner, M., A half-normal distribution scheme for generating functions (2016), ArXiv preprint · Zbl 1409.05020 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.