Exploring Werner Krandick's Binary Tree Jump Statistics

By Shalosh B. Ekhad and Doron Zeilberger

.pdf    .tex   


First Written: July 16, 2024

This version: Aug. 23. 2024.

Twenty years ago, Werner Krandick defined two statistics on binary trees. The first one determines the number of jumps, when traversing the tree in depth-first-search, from a vertex to one closer to the root, and the second keeps tracks of the sum of the jump-distances. He used clever but ad hoc human-generated arguments to find explicit expressions for their expectations. In this methodological note, we illustrate the power of experimental mathematics and symbolic computation to do much more. We derive closed-form expressions for the actual weight-enumerators according to these statistics (from which not only the expectations, but also the variances, and as many higher moments as desired, can be obtained). We also actually give the first eight moments, and conjecture that the first statistic (number of jumps) is asymptotically normal, and prove that the second one (sum of jump distances) is definitely not. In this revised version we are happy to announce that Stephen Melczer and Tia Ruza fully proved the asymptotic normality, and we provide a link to their writeup.

Added July 27, 2024: Stephen Melczer and Tia Ruza kindly pointed out that the asymptotic normality of the Jump statistics, conjectured in the paper, follows from a theorem of Ed Bender and Bruce Richmond

Maple package

Sample Input and Output for Krandick.txt

  • If you want to see a fully rigorous proof for the grand generating function of the weight enumerators of full binary trees according to the statistics "number of jumps" (and "number of internal nodes") and explicit expressions for the first 10 moments.

    then the input gives the output.

  • If you want to see a fully rigorous proof for the grand generating function of the weight enumerators of full binary trees according to the statistics "sum of jump distances" (and "number of internal nodes") and explicit expressions for the first 10 moments.

    then the input gives the output.

    Doron Zeilberger's Home Page