{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,5,14]],"date-time":"2025-05-14T22:27:48Z","timestamp":1747261668224},"reference-count":55,"publisher":"Cambridge University Press (CUP)","issue":"3","license":[{"start":{"date-parts":[[2018,10,31]],"date-time":"2018-10-31T00:00:00Z","timestamp":1540944000000},"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,5]]},"abstract":"<jats:p>We study<jats:italic>I<\/jats:italic>(<jats:italic>T<\/jats:italic>), the number of inversions in a tree<jats:italic>T<\/jats:italic>with its vertices labelled uniformly at random, which is a generalization of inversions in permutations. We first show that the cumulants of<jats:italic>I<\/jats:italic>(<jats:italic>T<\/jats:italic>) have explicit formulas involving the<jats:italic>k<\/jats:italic>-total common ancestors of<jats:italic>T<\/jats:italic>(an extension of the total path length). Then we consider<jats:italic>X<\/jats:italic><jats:sub><jats:italic>n<\/jats:italic><\/jats:sub>, the normalized version of<jats:italic>I<\/jats:italic>(<jats:italic>T<\/jats:italic><jats:sub><jats:italic>n<\/jats:italic><\/jats:sub>), for a sequence of trees<jats:italic>T<\/jats:italic><jats:sub><jats:italic>n<\/jats:italic><\/jats:sub>. For fixed<jats:italic>T<\/jats:italic><jats:sub><jats:italic>n<\/jats:italic><\/jats:sub>'s, we prove a sufficient condition for<jats:italic>X<\/jats:italic><jats:sub><jats:italic>n<\/jats:italic><\/jats:sub>to converge in distribution. As an application, we identify the limit of<jats:italic>X<\/jats:italic><jats:sub><jats:italic>n<\/jats:italic><\/jats:sub>for complete<jats:italic>b<\/jats:italic>-ary trees. For<jats:italic>T<\/jats:italic><jats:sub><jats:italic>n<\/jats:italic><\/jats:sub>being split trees [16], we show that<jats:italic>X<\/jats:italic><jats:sub><jats:italic>n<\/jats:italic><\/jats:sub>converges to the unique solution of a distributional equation. Finally, when<jats:italic>T<\/jats:italic><jats:sub><jats:italic>n<\/jats:italic><\/jats:sub>'s are conditional Galton\u2013Watson trees, we show that<jats:italic>X<\/jats:italic><jats:sub><jats:italic>n<\/jats:italic><\/jats:sub>converges to a random variable defined in terms of Brownian excursions. By exploiting the connection between inversions and the total path length, we are able to give results that significantly strengthen and broaden previous work by Panholzer and Seitz [46].<\/jats:p>","DOI":"10.1017\/s0963548318000512","type":"journal-article","created":{"date-parts":[[2018,10,31]],"date-time":"2018-10-31T08:52:02Z","timestamp":1540975922000},"page":"335-364","source":"Crossref","is-referenced-by-count":5,"title":["Inversions in Split Trees and Conditional Galton\u2013Watson Trees"],"prefix":"10.1017","volume":"28","author":[{"given":"XING SHI","family":"CAI","sequence":"first","affiliation":[]},{"given":"CECILIA","family":"HOLMGREN","sequence":"additional","affiliation":[]},{"given":"SVANTE","family":"JANSON","sequence":"additional","affiliation":[]},{"given":"TONY","family":"JOHANSSON","sequence":"additional","affiliation":[]},{"given":"FIONA","family":"SKERMAN","sequence":"additional","affiliation":[]}],"member":"56","published-online":{"date-parts":[[2018,10,31]]},"reference":[{"key":"S0963548318000512_ref49","doi-asserted-by":"publisher","DOI":"10.1051\/ita\/1991250100851"},{"key":"S0963548318000512_ref53","doi-asserted-by":"crossref","first-page":"217","DOI":"10.1080\/00031305.1995.10476146","article-title":"A recursive formulation of the old problem of obtaining moments from cumulants and vice versa","volume":"49","author":"Smith","year":"1995","journal-title":"Amer. Statist"},{"key":"S0963548318000512_ref46","doi-asserted-by":"publisher","DOI":"10.1007\/s00026-012-0164-3"},{"key":"S0963548318000512_ref44","doi-asserted-by":"publisher","DOI":"10.1002\/(SICI)1098-2418(199908)15:1<25::AID-RSA2>3.0.CO;2-R"},{"key":"S0963548318000512_ref41","doi-asserted-by":"publisher","DOI":"10.1090\/S0002-9904-1968-11888-9"},{"key":"S0963548318000512_ref38","doi-asserted-by":"publisher","DOI":"10.1007\/s00440-016-0704-6"},{"key":"S0963548318000512_ref37","volume-title":"The Art of Computer Programming","author":"Knuth","year":"1998"},{"key":"S0963548318000512_ref55","doi-asserted-by":"publisher","DOI":"10.2307\/2841222"},{"key":"S0963548318000512_ref31","doi-asserted-by":"publisher","DOI":"10.1002\/rsa.10074"},{"key":"S0963548318000512_ref29","doi-asserted-by":"publisher","DOI":"10.1080\/01621459.1963.10500830"},{"key":"S0963548318000512_ref28","doi-asserted-by":"publisher","DOI":"10.1093\/comjnl\/5.1.10"},{"key":"S0963548318000512_ref26","doi-asserted-by":"publisher","DOI":"10.1023\/B:JOTP.0000012006.91251.e8"},{"key":"S0963548318000512_ref25","doi-asserted-by":"publisher","DOI":"10.1002\/jgt.3190190402"},{"key":"S0963548318000512_ref22","doi-asserted-by":"publisher","DOI":"10.1007\/BF00288933"},{"key":"S0963548318000512_ref20","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9780511779398"},{"key":"S0963548318000512_ref19","doi-asserted-by":"publisher","DOI":"10.1002\/rsa.20233"},{"key":"S0963548318000512_ref18","unstructured":"DLMF (2017) NIST Digital Library of Mathematical Functions ( F. W. J. Olver et al., eds), Release 1.0.15 of 2017-06-01. http:\/\/dlmf.nist.gov\/"},{"key":"S0963548318000512_ref17","unstructured":"Devroye L. , Holmgren C. and Sulzbach H. (2017) The heavy path approach to Galton\u2013Watson trees with an application to Apollonian networks. arXiv:1701.02527"},{"key":"S0963548318000512_ref16","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539795283954"},{"key":"S0963548318000512_ref15","doi-asserted-by":"publisher","DOI":"10.1007\/BF01210596"},{"key":"S0963548318000512_ref14","unstructured":"Cramer G. (1750) Introduction \u00e0 l'Analyse des Lignes Courbes Alg\u00e9briques, Fr\u00e8res Cramer et Claude Philibert."},{"key":"S0963548318000512_ref12","first-page":"427","article-title":"File structures using hashing functions","volume":"13","author":"Coffman","year":"1970","journal-title":"Commun. Assoc. Comput. Mach."},{"key":"S0963548318000512_ref11","doi-asserted-by":"publisher","DOI":"10.1002\/rsa.10108"},{"key":"S0963548318000512_ref6","doi-asserted-by":"publisher","DOI":"10.1016\/0020-0190(87)90215-8"},{"key":"S0963548318000512_ref5","doi-asserted-by":"publisher","DOI":"10.1214\/aop\/1176989404"},{"key":"S0963548318000512_ref32","doi-asserted-by":"publisher","DOI":"10.1214\/11-PS188"},{"key":"S0963548318000512_ref4","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9780511662980.003"},{"key":"S0963548318000512_ref30","doi-asserted-by":"publisher","DOI":"10.1214\/EJP.v17-1723"},{"key":"S0963548318000512_ref3","doi-asserted-by":"publisher","DOI":"10.1214\/aop\/1176990534"},{"key":"S0963548318000512_ref2","unstructured":"Albert M. , Holmgren C. , Johansson T. and Skerman F. (2018) Permutations in binary trees and split trees. In 29th International Conference on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms (AofA 2018), Vol. 110 of Leibniz International Proceedings in Informatics (LIPIcs), Schloss Dagstuhl\u2013Leibniz-Zentrum f\u00fcr Informatik."},{"key":"S0963548318000512_ref10","doi-asserted-by":"crossref","first-page":"579","DOI":"10.30757\/ALEA.v14-29","article-title":"A study of large fringe and non-fringe subtrees in conditional Galton\u2013Watson trees.","volume":"XIV","author":"Cai","year":"2017","journal-title":"Latin American Journal of Probability and Mathematical Statistics"},{"key":"S0963548318000512_ref34","unstructured":"Janson S. (2017) Random recursive trees and preferential attachment trees are random split trees. arXiv:1706.05487"},{"key":"S0963548318000512_ref8","first-page":"225","article-title":"De la loi de multiplication et de la dur\u00e9e des familles.","volume":"7","author":"Bienaym\u00e9","year":"1845","journal-title":"Bull. London Math. Soc."},{"key":"S0963548318000512_ref52","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9780511666193"},{"key":"S0963548318000512_ref24","doi-asserted-by":"crossref","unstructured":"Flajolet P. , Roux M. and Vall\u00e9e B. (2010) Digital trees and memoryless sources: From arithmetics to analysis. In 21st International Meeting on Probabilistic, Combinatorial, and Asymptotic Methods in the Analysis of Algorithms (AofA'10), DMTCS Proc. AM, pp. 233\u2013260.","DOI":"10.46298\/dmtcs.2799"},{"key":"S0963548318000512_ref7","doi-asserted-by":"publisher","DOI":"10.1016\/0097-3165(73)90038-1"},{"key":"S0963548318000512_ref42","article-title":"Permutations with inversions","volume":"4","author":"Margolius","year":"2001","journal-title":"J. Integer Seq."},{"key":"S0963548318000512_ref50","doi-asserted-by":"publisher","DOI":"10.1007\/BF02679621"},{"key":"S0963548318000512_ref40","doi-asserted-by":"publisher","DOI":"10.1016\/0196-6774(89)90023-0"},{"key":"S0963548318000512_ref9","doi-asserted-by":"publisher","DOI":"10.1214\/11-AAP812"},{"key":"S0963548318000512_ref43","doi-asserted-by":"publisher","DOI":"10.1002\/rsa.10010"},{"key":"S0963548318000512_ref23","doi-asserted-by":"publisher","DOI":"10.1007\/PL00009236"},{"key":"S0963548318000512_ref54","doi-asserted-by":"publisher","DOI":"10.1093\/comjnl\/19.4.322"},{"key":"S0963548318000512_ref33","doi-asserted-by":"publisher","DOI":"10.1002\/rsa.20568"},{"key":"S0963548318000512_ref13","unstructured":"Conrad K. Probability distributions and maximum entropy. http:\/\/www.math.uconn.edu\/~kconrad\/blurbs\/analysis\/entropypost.pdf"},{"key":"S0963548318000512_ref1","doi-asserted-by":"publisher","DOI":"10.1214\/12-AOP758"},{"key":"S0963548318000512_ref45","doi-asserted-by":"crossref","first-page":"378","DOI":"10.1214\/aoap\/1075828056","article-title":"A general limit theorem for recursive algorithms and combinatorial structures","volume":"14","author":"Neininger","year":"2004","journal-title":"Ann. Appl. Probab"},{"key":"S0963548318000512_ref35","doi-asserted-by":"publisher","DOI":"10.1214\/ECP.v9-1088"},{"key":"S0963548318000512_ref39","article-title":"The number of inversions in permutations: A saddle point approach","volume":"6","author":"Louchard","year":"2003","journal-title":"J. Integer Seq."},{"key":"S0963548318000512_ref51","doi-asserted-by":"publisher","DOI":"10.1007\/BF02679611"},{"key":"S0963548318000512_ref47","doi-asserted-by":"crossref","first-page":"395","DOI":"10.1111\/j.2517-6161.1965.tb00602.x","article-title":"Spacings (with discussion)","volume":"27","author":"Pyke","year":"1965","journal-title":"J. Roy. Statist. Soc. Ser. B"},{"key":"S0963548318000512_ref48","doi-asserted-by":"publisher","DOI":"10.1109\/18.42197"},{"key":"S0963548318000512_ref27","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4614-4708-5"},{"key":"S0963548318000512_ref36","doi-asserted-by":"publisher","DOI":"10.1007\/s10959-005-7252-9"},{"key":"S0963548318000512_ref21","volume-title":"An Introduction to Probability Theory and its Applications","author":"Feller","year":"1968"}],"container-title":["Combinatorics, Probability and Computing"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.cambridge.org\/core\/services\/aop-cambridge-core\/content\/view\/S0963548318000512","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,7,11]],"date-time":"2024-07-11T22:41:25Z","timestamp":1720737685000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.cambridge.org\/core\/product\/identifier\/S0963548318000512\/type\/journal_article"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2018,10,31]]},"references-count":55,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2019,5]]}},"alternative-id":["S0963548318000512"],"URL":"https:\/\/doi.org\/10.1017\/s0963548318000512","relation":{},"ISSN":["0963-5483","1469-2163"],"issn-type":[{"value":"0963-5483","type":"print"},{"value":"1469-2163","type":"electronic"}],"subject":[],"published":{"date-parts":[[2018,10,31]]}}}