pith. sign in

arxiv: 1207.3915 · v2 · pith:CQKLUYM6new · submitted 2012-07-17 · 🧮 math.CO

The asymptotic number of different rooted trees of a tree

classification 🧮 math.CO
keywords mathcaltreenumbertreesdifferentgivenpatternrooted
0
0 comments X
read the original 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.

This paper has not been read by Pith yet.

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.