The asymptotic number of different rooted trees of a tree

Abstract

Let ${\mathcal{T}}_n$ be the set of trees with $n$ vertices. Suppose that each tree in ${\mathcal{T}}_n$ is equally likely. We show that the number of different rooted trees of a tree equals $({\mu }_r+o(1))n$ for almost every tree of ${\mathcal{T}}_n$, where ${\mu }_r$ is a constant. As an application, we show that the number of any given pattern in ${\mathcal{T}}_n$ is also asymptotically normally distributed with mean $\sim {\mu }_{M}n$ and variance $\sim {\sigma }_{M}n$, where ${\mu }_M,{\sigma }_M$ are some constants related to the given pattern. This solves an open question claimed in Kok's thesis.

arXiv comment12 pages