Séminaire du 9 décembre 2002, Thomas Klausner, Technical Mathematics, TUW, Vienna, Austria.

Patterns in Trees

Let \ensuremath{{\mathcal T}_n} denote the set of unrooted labeled trees of size $n$ and let \ensuremath{{\mathcal M}_k} be a particular tree with $k$ edges. Assuming that every tree of \ensuremath{{\mathcal T}_n} is equally likely it is shown that the limiting distribution of the number of occurrences of \ensuremath{{\mathcal M}_k} as an induced sub-tree is asymptotically normal with mean value $\sim\mu n$ and variance $\sim\sigma^2 n$ with constants $\mu$ and $\sigma$ that can be computed for any given \ensuremath{{\mathcal M}_k}.