Automated Counting and Statistical Analysis of Labeled Trees with Degree Restrictions

Shalosh B. Ekhad, Doron Zeilberger

Published 2022-01-18Version 1

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 explicit expressions for the limiting expectation, variance, and covariance.