Pattern distribution in various types of random trees
Gerard Kok
Abstract
Let Tn denote the set of unrooted unlabeled trees of size n and let Mk be a particular (finite) tree. Assuming that every tree of Tn is equally likely, it is shown that the number of occurrences Xn of Mk as an induced sub-tree satisfies E Xn ∼µn and Var Xn ∼σ2 n for some (computable) constants µ> 0 and σ≥0. Furthermore, if σ>0 then (Xn - E Xn)/√Var Xn converges to a limiting distribution with density (A+Bt2)e-Ct2 for some constants A,B,C. However, in all cases in which we were able to calculate these constants, we obtained B=0 and thus a normal distribution. Further, if we consider planted or rooted trees instead of Tn then the limiting distribution is always normal. Similar results can be proved for planar, labeled and simply generated trees.
Full Text: GZIP Compressed PostScript PostScript PDF original HTML abstract page