Pick Up Sticks
By
Larry Shepp, Doron Zeilberger, and Cun-Hui Zhang

.pdf   .ps   .tex

(Exclusively published in the Personal Journal of Shalosh B. Ekhad and Doron Zeilberger and arxiv.org)

Written: Oct. 16, 2012.

We apply a classic result in Theoretical Computer Science to solve a sticky problem, and give a neat and slick quick proof of half of it.

Maple Programs

• BinaryTrees, to study, empirically and symbolically, the stick (alias random binary search trees) as well the probability generating function of the random variable "maximal height of a full binary tree with n leaves" beautifully study by P. Flajolet and A. Odlyzko

• EtzBinary, to draw binary trees and throwing scenarios.

• ArbresBinaires, an alternative, preliminary, package, covering the same ground as BinaryTrees.

Sample Input and Output for the Maple package BinaryTrees

• If you want to see the first 100 terms of the sequence "average height of a full binary tree with n leaves", under the uniform distribution

the input file would yield the output file

• If you want to see the first 100 terms of the sequence "average number of throws it takes to break an n-inch ruler", (alias one plus the average height of a random Binary Search Tree)

the input file would yield the output file

• If you want to see the first 100 terms of the sequence of polynomials "weight-enumerator of a full binary tree with n leaves according to the weight t^(height)",

the input file would yield the output file

• If you want to see the first 100 terms of the sequence "probability generating functions for the stick problem" (the n-th term is the polynomial whose coeff. of t^i is the probability of needing i throws to completely break an n-inch ruler).

the input file would yield the output file

Personal Journal of Shalosh B. Ekhad and Doron Zeilberger