On the number of increasing trees with label repetitions
| dc.contributor.author | Bodini, Olivier | en_ZA |
| dc.contributor.author | Genitrini, Antoine | en_ZA |
| dc.contributor.author | Gittenberger, Bernhard | en_ZA |
| dc.contributor.author | Wagner, Stephan | en_ZA |
| dc.date.accessioned | 2022-07-01T07:30:06Z | |
| dc.date.available | 2022-07-01T07:30:06Z | |
| dc.date.issued | 2019 | |
| dc.description | CITATION: Bodini, O. et al. 2020. On the number of increasing trees with label repetitions. Discrete Mathematics, 343(8). doi:10.1016/j.disc.2019.111722 | |
| dc.description | The original publication is available at https://www.sciencedirect.com/journal/discrete-mathematics | |
| dc.description.abstract | We study the asymptotic number of certain monotonically labeled increasing trees arising from a generalized evolution process. The main difference between the presented model and the classical model of binary increasing trees is that the same label can appear in distinct branches of the tree. In the course of the analysis we develop a method to extract asymptotic information on the coefficients of purely formal power series. The method is based on an approximate Borel transform (or, more generally, Mittag-Leffler transform) which enables us to quickly guess the exponential growth rate. With this guess the sequence is then rescaled and a singularity analysis of the generating function of the scaled counting sequence yields accurate asymptotics. The actual analysis is based on differential equations and a Tauberian argument. The counting problem for trees of size n exhibits interesting asymptotics involving powers of n with irrational exponents. | en_ZA |
| dc.description.uri | https://www.sciencedirect.com/science/article/pii/S0012365X19304005 | |
| dc.description.version | Publishers version | |
| dc.format.extent | 12 pages | |
| dc.identifier.citation | Bodini, O. et al. 2020. On the number of increasing trees with label repetitions. Discrete Mathematics, 343(8). doi:10.1016/j.disc.2019.111722 | |
| dc.identifier.issn | 0012-365X (print) | |
| dc.identifier.other | doi:10.1016/j.disc.2019.111722 | |
| dc.identifier.uri | http://hdl.handle.net/10019.1/125445 | |
| dc.language.iso | en_ZA | en_ZA |
| dc.publisher | Elsevier | |
| dc.subject | Increasing tree | en_ZA |
| dc.subject | Borel transform | en_ZA |
| dc.subject | Evolution process | en_ZA |
| dc.subject | Ordinary differential equation | en_ZA |
| dc.subject | Asymptotic enumeration | en_ZA |
| dc.subject | Trees -- Labeling | en_ZA |
| dc.subject | Trees -- Growth -- Mathematical models | en_ZA |
| dc.subject | Evolution equations -- Asymptotic theory | en_ZA |
| dc.title | On the number of increasing trees with label repetitions | en_ZA |
| dc.type | Article | en_ZA |