Abstract
Multi-edge trees as introduced in a recent paper of Dziemiańczuk are plane trees where multiple edges are allowed. We first show that d-ary multi-edge trees where the out-degrees are bounded by d are in bijection with classical d-ary trees. This allows us to analyse parameters such as the height. The main part of this paper is concerned with multi-edge trees counted by their number of edges. The distribution of the number of vertices as well as the height are analysed asymptotically.
Article PDF
Similar content being viewed by others
Avoid common mistakes on your manuscript.
References
de Bruijn, N.G.: Asymptotic methods in analysis. In: Bibliotheca Mathematica, vol. 4. North-Holland Publishing Co., Amsterdam (1958)
de Bruijn, N.G., Knuth, D.E., Rice, S.O.: The average height of planted plane trees. In: Graph Theory and Computing, pp. 15–22. Academic Press, New York (1972)
Drmota, M.: Random Trees. Springer, NewYork (2009). doi:10.1007/978-3-211-75357-6
Dziemiańczuk, M.: Enumerations of plane trees with multiple edges and Raney lattice paths. Discret. Math. 337, 9–24 (2014). doi:10.1016/j.disc.2014.07.024
Flajolet, P., Gao, Z., Odlyzko, A., Richmond, B.: The distribution of heights of binary trees and other simple trees. Comb. Probab. Comput. 2(2), 145–156 (1993). doi:10.1017/S0963548300000560
Flajolet, P., Gourdon, X., Dumas, P.: Mellin transforms and asymptotics: Harmonic sums. Theor. Comput. Sci. 144, 3–58 (1995). doi:10.1016/0304-3975(95)00002-E
Flajolet, P., Odlyzko, A.: The average height of binary trees and other simple trees. J. Comput. Syst. Sci. 25(2), 171–213 (1982). doi:10.1016/0022-0000(82)90004-6
Flajolet, P., Odlyzko, A.: Singularity analysis of generating functions. SIAM J. Discret. Math. 3, 216–240 (1990). doi:10.1137/0403019
Flajolet, P., Prodinger, H.: Register allocation for unary-binary trees. SIAM J. Comput. 15(3), 629–640 (1986). doi:10.1137/0215046
Flajolet, P., Sedgewick, R.: Analytic Combinatorics. Cambridge University Press, Cambridge (2009). doi:10.1017/CBO9780511801655
Greene, D.H., Knuth, D.E.: Mathematics for the analysis of algorithms. In: Progress in Computer Science and Applied Logic, 3rd edn., vol. 1. Birkhäuser Boston, Inc., Boston (1990). doi:10.1007/978-0-8176-4729-2
Hwang, H.-K.: On convergence rates in the central limit theorems for combinatorial structures. Eur. J. Comb. 19, 329–343 (1998). doi:10.1006/eujc.1997.0179
Kemp, R.: The average height of r-tuply rooted planted plane trees. Computing 25(3), 209–232 (1980). doi:10.1007/BF02242000
Kemp, R.: The average height of planted plane trees with M leaves. J. Comb. Theory Ser. B 34(2), 191–208 (1983). doi:10.1016/0095-8956(83)90019-9
The on-line encyclopedia of integer sequences (2015). http://oeis.org
Priez, J.-B.: Lattice of combinatorial Hopf algebras: binary trees with multiplicities. In: 25th International Conference on Formal Power Series and Algebraic Combinatorics (FPSAC 2013), DMTCS Proceedings, pp. 1137–1148 (2013)
Prodinger, H.: A note on a result of R. Kemp on r-tuply rooted planted plane trees. Computing 28(4), 363–366 (1982). doi:10.1007/BF02279818
Prodinger, H.: The height of planted plane trees revisited. Ars Comb. 16(B), 51–55 (1983)
Author information
Authors and Affiliations
Corresponding author
Additional information
C. Heuberger is supported by the Austrian Science Fund (FWF): P 24644-N26. This paper has been written while he was a visitor at Stellenbosch University.
H. Prodinger is supported by an incentive grant of the National Research Foundation of South Africa.
S. Wagner is supported by the National Research Foundation of South Africa, grant number 96236.
Rights and permissions
Open Access This article is distributed under the terms of the Creative Commons Attribution 4.0 International License (http://creativecommons.org/licenses/by/4.0/), which permits unrestricted use, distribution, and reproduction in any medium, provided you give appropriate credit to the original author(s) and the source, provide a link to the Creative Commons license, and indicate if changes were made.
About this article
Cite this article
Heuberger, C., Prodinger, H. & Wagner, S. The height of multiple edge plane trees. Aequat. Math. 90, 625–645 (2016). https://doi.org/10.1007/s00010-015-0380-0
Received:
Revised:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s00010-015-0380-0