The asymptotic number of different rooted trees of a tree

Original · EN

Let Tₙ be the set of trees with n vertices. Suppose that each tree in Tₙ is equally likely. We show that the number of different rooted trees of a tree equals (μᵣ+o(1))n for almost every tree of Tₙ, where μᵣ is a constant. As an application, we show that the number of any given pattern in Tₙ is also asymptotically normally distributed with mean μₘ n and variance σₘ n, where μₘ, σₘ are some constants related to the given pattern. This solves an open question claimed in Kok's thesis.