The Distribution of Degrees in a Large Random Tree.

摘要

For labeled trees, Renyi showed that the probability that an arbitrary point of a random tree has degree k approaches 1/e(k-1)prime. For unlabeled trees, the answer is different because the number of ways to label a given tree depends on the order of its automorphism group. Using arguments involving combinatorial enumeration and asymptotics, the corresponding probabilities for large unlabeled trees is evaluated.