By Shalosh B. Ekhad and Doron Zeilberger
First Written: 15 in Shevat, 5782 (alias Jan. 17, 2022).
This version: Feb. 1, 2022.
Arthur Cayley famously proved that there are n^{n-2} labeled trees on n vertices. This important sequence A272 is of course in the OEIS. But what about the number of labeled trees where the degree of each vertex must belong to a given finite set? Or where none of the vertex-degrees belong to a given finite set? Except for sequence A5512 that counts the number of labeled trees where none of the vertex-degrees can be 2, and sequence A3603 that counts the number of labeled trees where each vertex has degree at most 2, none of these sequences are (yet) in the OEIS.
We show how to compute these sequences efficiently, and actually compute many terms for many choices for the allowed (or forbidden) set, as well, as fully automatically, give linear recurrence equations and asymptotics (in the positive case).
In the second part of the paper, we do `statistical analysis', deriving (automatically, of course!) explicit formulas for the expectation, variance, and covariance of the random variables `number of vertices with degree d', for any positive integer d, and show asymptotic normality, thereby reproving results of A. Rény and Amram Meir and John W. Moon. More interestingly, we prove joint asymptotic normality for any two prescribed degrees.
The input file generates the output file
The input file generates the output file
The input file generates the output file
The input file generates the output file