The asymptotic number of non-isomorphic rooted trees obtained by rooting a tree

JOURNAL OF MATHEMATICAL ANALYSIS AND APPLICATIONS

卷:434

Article

Li, Xueliang¹ 

[1] Nankai Univ, Ctr Combinator, Tianjin 300071, Peoples R China

关键词: Tree;    Rooted tree;    Pattern;    Counting, generating function;    Limiting distribution;    Automorphism;   

DOI  :  10.1016/j.jmaa.2015.09.007

来源: Elsevier

【 摘 要 】

Let T-n denote the set of trees with n vertices. Suppose that each tree in T-n is equally likely. We show that the number of non-isomorphic rooted trees obtained by rooting a tree equals (mu(r) + o(1))n for almost every tree of T-n where mu(r) is a constant. As an application, we show that in T-n the number of any given pattern, which is a fixed small tree with internal vertices specified, is asymptotically normally distributed with mean similar to mu(M)n and variance similar to sigma(M)n, where mu(M) and sigma(M) are some constants related to the given pattern. This solves an open question claimed in Kok's thesis. (C) 2015 Elsevier Inc. All rights reserved.

【 授权许可】

Free