论文标题
具有程度限制的标记树木的自动计数和统计分析
Automated Counting and Statistical Analysis of Labeled Trees with Degree Restrictions
论文作者
论文摘要
亚瑟·卡利（Arthur Cayley）著名地证明了n个顶点上有N-2标记的树木的n。在这里，我们走得更远，展示了如何自动自动列举标记的树木，以使每个顶点都有许多属于指定有限集的邻居，并且还计算不允许邻居数量的树木数量。我们还提供了详细的统计分析，并表明，在具有N顶点的标记树的样本空间中，“与D邻居的顶点的数量”随机变化是渐近正常的，并且对于任何不同程度，在任何不同的程度上是渐近地正常的，但当然是不独立的（即（1,3），即剩下的（1,3），剩下的数量和数量是剩下的数量。我们还为Amram Meir和John Noon的表达式提供了新的证据，以限制这些期望和差异，并为协方差提供明确的表达。
Arthur Cayley famously proved that there are n to the power n-2 labeled trees on n vertices. Here we go much further and show how to enumerate, fully automatically, labeled trees such that every vertex has a number of neighbors that belongs to a specified finite set, and also count trees where the number of neighbors is not allowed to be in a given finite set. We also give detailed statistical analysis, and show that in the sample space of labeled trees with n vertices, the random variable "number of vertices with d neighbors" is asymptotically normal, and for any different degrees, are jointly asymptotically normal, but of course, not independently so (except for the pair (1,3), i.e. the number of leaves and the number of degree-3 vertices, where there are asymptotically independent). We also give new proofs to Amram Meir and John Noon's expressions for the limiting expectation and variance for these, and derive an explicit expression for the covariance.
