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.
Pictures
-
Here are all the 14 throwing scenarios of a
five-inch stick .
-
Here are all the 14 Binary Search Trees with
4 records .
-
Here are all the 42 throwing scenarios of a
six-inch 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
ten-inch 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 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
Doron Zeilberger's Home Page