{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,7,15]],"date-time":"2024-07-15T16:10:09Z","timestamp":1721059809038},"reference-count":17,"publisher":"Cambridge University Press (CUP)","issue":"4","license":[{"start":{"date-parts":[[2019,3,8]],"date-time":"2019-03-08T00:00:00Z","timestamp":1552003200000},"content-version":"unspecified","delay-in-days":0,"URL":"https:\/\/www.cambridge.org\/core\/terms"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Combinator. Probab. Comp."],"published-print":{"date-parts":[[2019,7]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>A tree functional is called additive if it satisfies a recursion of the form<jats:inline-formula><jats:alternatives><jats:inline-graphic xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" mime-subtype=\"gif\" xlink:type=\"simple\" xlink:href=\"S0963548318000585_inline1\"\/><jats:tex-math>$F(T) = \\sum_{j=1}^k F(B_j) + f(T)$<\/jats:tex-math><\/jats:alternatives><\/jats:inline-formula>, where<jats:italic>B<\/jats:italic><jats:sub>1<\/jats:sub>, \u2026,<jats:italic>B<jats:sub>k<\/jats:sub><\/jats:italic>are the branches of the tree<jats:italic>T<\/jats:italic>and<jats:italic>f<\/jats:italic>(<jats:italic>T<\/jats:italic>) is a toll function. We prove a general central limit theorem for additive functionals of<jats:italic>d<\/jats:italic>-ary increasing trees under suitable assumptions on the toll function. The same method also applies to generalized plane-oriented increasing trees (GPORTs). One of our main applications is a log-normal law that we prove for the size of the automorphism group of<jats:italic>d<\/jats:italic>-ary increasing trees, but other examples (old and new) are covered as well.<\/jats:p>","DOI":"10.1017\/s0963548318000585","type":"journal-article","created":{"date-parts":[[2019,3,8]],"date-time":"2019-03-08T11:16:35Z","timestamp":1552043795000},"page":"618-637","source":"Crossref","is-referenced-by-count":6,"title":["A central limit theorem for additive functionals of increasing trees"],"prefix":"10.1017","volume":"28","author":[{"given":"Dimbinaina","family":"Ralaivaosaona","sequence":"first","affiliation":[]},{"given":"Stephan","family":"Wagner","sequence":"additional","affiliation":[]}],"member":"56","published-online":{"date-parts":[[2019,3,8]]},"reference":[{"key":"S0963548318000585_ref16","doi-asserted-by":"crossref","DOI":"10.1093\/oso\/9780198509424.001.0001","volume-title":"Phylogenetics","author":"Semple","year":"2003"},{"key":"S0963548318000585_ref12","doi-asserted-by":"publisher","DOI":"10.1002\/rsa.20568"},{"key":"S0963548318000585_ref11","doi-asserted-by":"crossref","first-page":"1687","DOI":"10.1137\/S009753970138390X","article-title":"Phase change of limit laws in the quicksort recurrence under varying toll functions","volume":"31","author":"Hwang","year":"2002","journal-title":"SIAM J. Comput"},{"key":"S0963548318000585_ref10","doi-asserted-by":"crossref","first-page":"P2.51","DOI":"10.37236\/6374","article-title":"Multivariate normal limit laws for the numbers of fringe subtrees in m-ary search trees and preferential attachment trees","volume":"24","author":"Holmgren","year":"2017","journal-title":"Electron. J. Combin"},{"key":"S0963548318000585_ref9","doi-asserted-by":"publisher","DOI":"10.1214\/EJP.v20-3627"},{"key":"S0963548318000585_ref8","doi-asserted-by":"publisher","DOI":"10.1017\/S096354831100071X"},{"key":"S0963548318000585_ref7","doi-asserted-by":"crossref","DOI":"10.1017\/CBO9780511801655","volume-title":"Analytic Combinatorics","author":"Flajolet","year":"2009"},{"key":"S0963548318000585_ref5","doi-asserted-by":"crossref","first-page":"271","DOI":"10.1016\/j.cam.2004.04.014","article-title":"Singularity analysis, Hadamard products, and tree recurrences","volume":"174","author":"Fill","year":"2005","journal-title":"J. Comput. Appl. Math."},{"key":"S0963548318000585_ref4","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-211-75357-6"},{"key":"S0963548318000585_ref1","doi-asserted-by":"publisher","DOI":"10.1007\/3-540-55251-0_2"},{"key":"S0963548318000585_ref17","doi-asserted-by":"publisher","DOI":"10.1017\/S0963548314000443"},{"key":"S0963548318000585_ref3","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539701383923"},{"key":"S0963548318000585_ref15","unstructured":"15. Ralaivaosaona, D. and Wagner, S. (2016) Additive functionals of d-ary increasing trees. In Proceedings of the 27th International Conference on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms. arXiv:1605.03918"},{"key":"S0963548318000585_ref2","doi-asserted-by":"crossref","first-page":"1005","DOI":"10.1239\/jap\/1261670685","article-title":"Isomorphism and symmetries in random phylogenetic trees","volume":"46","author":"B\u00f3na","year":"2009","journal-title":"J. Appl. Probab."},{"key":"S0963548318000585_ref13","doi-asserted-by":"publisher","DOI":"10.1002\/(SICI)1098-2418(199803)12:2<197::AID-RSA3>3.0.CO;2-S"},{"key":"S0963548318000585_ref6","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2004.05.010"},{"key":"S0963548318000585_ref14","doi-asserted-by":"publisher","DOI":"10.1002\/rsa.20161"}],"container-title":["Combinatorics, Probability and Computing"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.cambridge.org\/core\/services\/aop-cambridge-core\/content\/view\/S0963548318000585","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,7,15]],"date-time":"2024-07-15T15:25:59Z","timestamp":1721057159000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.cambridge.org\/core\/product\/identifier\/S0963548318000585\/type\/journal_article"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2019,3,8]]},"references-count":17,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2019,7]]}},"alternative-id":["S0963548318000585"],"URL":"https:\/\/doi.org\/10.1017\/s0963548318000585","relation":{},"ISSN":["0963-5483","1469-2163"],"issn-type":[{"value":"0963-5483","type":"print"},{"value":"1469-2163","type":"electronic"}],"subject":[],"published":{"date-parts":[[2019,3,8]]}}}