The Distribution of Patterns in Random Trees

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~$\mu n$ and~$\sigma^2n$, respectively, where the constants $\mu>0$ and~$\sigma\ge 0$ are computable.
Complete list of metadatas

Cited literature [14 references]  Display  Hide  Download

https://hal.inria.fr/inria-00001281
Contributor : Frédéric Chyzak <>
Submitted on : Friday, May 5, 2006 - 11:25:55 AM
Last modification on : Saturday, October 6, 2018 - 6:58:01 PM
Long-term archiving on : Saturday, April 3, 2010 - 9:19:22 PM

Identifiers

Collections

Citation

Frédéric Chyzak, Michael Drmota, Thomas Klausner, Gerard Kok. The Distribution of Patterns in Random Trees. 2006. ⟨inria-00001281⟩

Share

Metrics

Record views

192

Files downloads

239