The height of multiple edge plane trees. (English) Zbl 1337.05055
Summary: Multi-edge trees as introduced in a recent paper of M. Dziemiańczuk [Discrete Math. 337, 9–24 (2014; Zbl 1301.05178)] 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.
MSC:
| 05C30 | Enumeration in graph theory |
| 05A16 | Asymptotic enumeration |
| 05A15 | Exact enumeration problems, generating functions |
| 05C05 | Trees |
| 05C10 | Planar graphs; geometric and topological aspects of graph theory |
| 60C05 | Combinatorial probability |
Citations:
Zbl 1301.05178Software:
OEISReferences:
| [1] | de Bruijn, N.G.: Asymptotic methods in analysis. In: Bibliotheca Mathematica, vol. 4. North-Holland Publishing Co., Amsterdam (1958) · Zbl 0082.04202 |
| [2] | 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) · Zbl 0247.05106 |
| [3] | Drmota, M.: Random Trees. Springer, NewYork (2009). doi:10.1007/978-3-211-75357-6 · Zbl 1170.05022 |
| [4] | 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 · Zbl 1301.05178 |
| [5] | 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 · Zbl 0795.05042 |
| [6] | 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 · Zbl 0869.68057 |
| [7] | 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 · Zbl 0499.68027 |
| [8] | Flajolet, P., Odlyzko, A.: Singularity analysis of generating functions. SIAM J. Discret. Math. 3, 216-240 (1990). doi:10.1137/0403019 · Zbl 0712.05004 |
| [9] | Flajolet, P., Prodinger, H.: Register allocation for unary-binary trees. SIAM J. Comput. 15(3), 629-640 (1986). doi:10.1137/0215046 · Zbl 0612.68065 |
| [10] | Flajolet, P., Sedgewick, R.: Analytic Combinatorics. Cambridge University Press, Cambridge (2009). doi:10.1017/CBO9780511801655 · Zbl 1165.05001 |
| [11] | 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 · Zbl 0824.68043 |
| [12] | 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 · Zbl 0906.60024 |
| [13] | Kemp, R.: The average height of r-tuply rooted planted plane trees. Computing 25(3), 209-232 (1980). doi:10.1007/BF02242000 · Zbl 0433.05024 |
| [14] | 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 · Zbl 0516.05020 |
| [15] | The on-line encyclopedia of integer sequences (2015). http://oeis.org |
| [16] | 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) · Zbl 1294.05191 |
| [17] | 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 · Zbl 0476.05033 |
| [18] | Prodinger, H.: The height of planted plane trees revisited. Ars Comb. 16(B), 51-55 (1983) · Zbl 0533.05023 |
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.
