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.

Puzzle Book

• 40 Circuit Board puzzles by Shalosh B. Ekhad,

Maple packages

• ETSIM.txt, a Maple package to count and generate trees (and spanning trees) with degree restrictions

• CircuitBoard.txt, a Maple package for creating circuit board puzzles
  [It requires the data set CircuitBoardPre.txt]

Sample Input and Output for ETSIM.txt

• If you want to see the first 30 terms of the enumerating sequences for labeled trees whose vertex-degrees are confined to a given finite set S (containing 1, of course) for all subsets (containing 1) of {1,2,3,4,5} with at least three elements, as well as linear recurrences, asymptotics, and limiting distribution of the average occurrences of each vertex-degrees

  The input file generates the output file  

• If you want to see the first 30 terms of the enumerating sequences for labeled trees whose vertex-degrees are confined to a given finite set S (containing 1, of course) for all subsets (containing 1) of {1,2,3,4,5,6,7} with at least three elements, as well as linear recurrences, asymptotics, but NO limiting distribution of the average occurrences of each vertex-degrees (as in the above file, this takes much longer)

  The input file generates the output file  

• If you want to see the first 100 terms of the enumerating sequences for labeled trees whose vertex-degrees are FORBIDDEN to belongs to a given finite set S (that does not contain 1, of course) for all subsets of {2,3,4,5,6,7} with up to four elements, as well as (estimated, non-rigorous) asymptotics

  The input file generates the output file  

• If you want to see detailed statistical analysis of the random variable "number of vertices with d neighbors" in the sample space of all labeled trees on n vertices, with explicit expressions for the moments, mixed moments, and limiting behavior (all done automatically!)

  The input file generates the output file  

Doron Zeilberger's Home Page