On the enumeration of leaf-labeled increasing trees with arbitrary node-degree

DOI10.26493/2590-9770.1589.7E1MaRDI QIDQ6065318zbMATH OpenFDO

Authors Johannes Wirtz

Publication date 11 December 2023

Published in The Art of Discrete and Applied Mathematics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/2211.03632

zbMATH Keywords

coefficient asymptoticsdifferential equationsgenealogical treesmerger histories

Mathematics Subject Classification ID

Exact enumeration problems, generating functions (05A15) Trees (05C05) Graph labelling (graceful graphs, bandwidth, etc.) (05C78)

Abstract: We consider the counting problem of the number of extit{leaf-labeled increasing trees}, where internal nodes may have an arbitrary number of descendants. The set of all such trees is a discrete representation of the genealogies obtained under certain population-genetical models such as multiple-merger coalescents. While the combinatorics of the binary trees among those are well understood, for the number of all trees only an approximate asymptotic formula is known. In this work, we validate this formula up to constant terms and compare the asymptotic behavior of the number of all leaf-labelled increasing trees to that of binary, ternary and quaternary trees.

Recommendations

• On the number of increasing trees with label repetitions
• On the degree distribution of the nodes in increasing trees
• Descendants in increasing trees
• Generating functions for multi-labeled trees
• Enumerating phylogenetic trees with multiple labels

Cites work

• Analytic combinatorics
• Beta-coalescents and continuous stable random trees
• Coalescent theory. An introduction
• Coalescents with multiple collisions
• Counting dendrograms: A survey
• Demographic inference under the coalescent in a spatial continuum
• scientific article; zbMATH DE number 3817476 (Why is no real title available?)
• scientific article; zbMATH DE number 2024859 (Why is no real title available?)
• scientific article; zbMATH DE number 1865935 (Why is no real title available?)
• Measuring the external branches of a Kingman tree: a discrete approach
• Mixing Time for a Markov Chain on Cladograms
• On probability distributions of single-linkage dendrograms
• Rate of coalescence of lineage pairs in the spatial \(\varLambda\)-Fleming-Viot process
• Stochastic models and descriptive statistics for phylogenetic trees, from Yule to today.
• Strict monotonic trees arising from evolutionary processes: combinatorial and probabilistic study
• The evolving Moran genealogy
• The general coalescent with asynchronous mergers of ancestral lines
• The impact of genetic diversity statistics on model selection between coalescents
• The latent roots of certain Markov chains arising in genetics: A new approach, II. Further haploid models
• Topological linkage disequilibrium calculated from coalescent genealogies
• Yule-generated trees constrained by node imbalance

Cited in

(1)

• Labeled histories and maximally probable labeled topologies with multifurcation

This page was built for publication: On the enumeration of leaf-labeled increasing trees with arbitrary node-degree

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6065318)