Pick Up Sticks
By
Larry Shepp, Doron Zeilberger, and CunHui 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.
Pictures

Here are all the 14 throwing scenarios of a
fiveinch stick .

Here are all the 14 Binary Search Trees with
4 records .

Here are all the 42 throwing scenarios of a
sixinch stick .

Here are all the 42 Binary Search Trees with
5 records .

Here are 10 throwing scenarios out of the 4862 throwing scenarios of a
teninch stick .

Here is the Binary Search Tree corresponding to the permutation
[4,3,9,1,5, 6, 2,11, 7,8, 10,12] .
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 ninch 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
"weightenumerator 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 nth term is the polynomial whose coeff. of t^i is the probability of needing i throws to
completely break an ninch ruler).
the
input file
would yield the
output file
Personal Journal of Shalosh B. Ekhad and Doron Zeilberger
Doron Zeilberger's Home Page