The Distribution of Patterns in Random Trees

2006/05/05 by Frédéric Chyzak, Michael Drmota, Chyzak, Frédéric +5
Computer Science · Mathematics · #Combinatorics (math.CO) #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #FOS: Mathematics #Markov Chains and Monte Carlo Methods #Stochastic processes and statistical mechanics #Topological and Geometric Data Analysis

paper · pdf · doi:10.48550/arxiv.cs/0605019

openalex publication_date 2006/05/05 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

Let T_n denote the set of unrooted labeled trees of size n and let T_n be a particular (finite, unlabeled) tree. Assuming that every tree of T_n is equally likely, it is shown that the limiting distribution as n goes to infinity of the number of occurrences of M as an induced subtree is asymptotically normal with mean value and variance asymptotically equivalent to μn and σ²n, respectively, where the constants μ>0 and σ≥ 0 are computable.

Related

• The number of occurrences of patterns in a random tree or forest permutation
• The asymptotic number of different rooted trees of a tree
• Subtrees of a random tree
• Random enriched trees with applications to random graphs
• Fluctuations for the number of records on subtrees of the Continuum Random Tree