The ``Monkey Typing Shakespeare" Problem for Compositions
By Shalosh B. Ekhad and Doron Zeilberger
.pdf
.ps
.tex
(Exclusively published in the Personal Journal of Shalosh B. Ekhad and Doron Zeilberger and arxiv.org )
Posted: Jan. 12, 2019
Suppose that your mother gave you n candies. You have to eat at least one candy each day.
One possibility is to eat all n of them the first day. Another extreme is to make them last
n days, and only eat one candy a day. Altogether, you have, famously, 2^{n1} choices.
If each such choice is equally likely, what is the probability that you never have
three consecutive days, where in the first day you ate at least 2 candies, in the second day you ate
at least 5 candies, and in the third day you ate at least 3 candies? This article develops
an algorithm, fully implemented in two Maple packages, to answer such important questions, and more general ones, of this kind.
Maple packages

Compositions.txt,
a Maple package to count compositions that avoid (by containment) any finite set of fixed compositions of the same length.

CompositionsPlus.txt,
a Maple package that in addition to including the former procedures,
includes many additional ones. t also enumerates
compositions that contain specified numbers of occurrences, from a finite set of compositions all of the same
length, and performs (symbolic) statistical analysis of the random variables "number of occurrences of the subcomposition C"
in a random composition of n, for the members C of the offending set.
Sample Input and Output Files for the Maple package
Compositions.txt,

If you want to see generating functions and growth constants for the
enumerating sequences for compositions avoiding a single pattern, for all compositions up to length 10
the input file generates the
output file.

If you want to see generating functions and growth constants for the
enumerating sequences for compositions avoiding all subsets of compositions of ≤ 6 with the same number of parts
the input file generates the
output file.

If you want to see the generating functions for compositions of depth < r, for r from 1 to 10, using Prop. 1 in the
"The Depth of Compositions" by A. Blecher, C. Brennan, A. Knopfmacher and T. Mansour
(to appear in "Mathematics in Computer Science"), who used a different approach,
the input file generates the
output file.

If you want to see the growth constants arranged in ascending order for all compositions whose sum is ≤ 11
the input file generates the
output file.
Sample Input and Output Files for the Maple package
CompositionsPlus.txt,

If you want to see generating functions and growth constants for the
enumerating sequences for compositions avoiding a single pattern, as well as the more general generating
functions keeping track of the number of occurrences, and statistical analysis for the random variable
"number of occurrences (as containment) of a given composition C", for
for all compositions up to length 10
the input file generates the
output file.

If you want to see generating functions and growth constants for the
enumerating sequences for compositions avoiding a pair of patterns of the same length and same sum,
the sum being from 3 to 6, as well as the more general generating functions keeping
track of the number of occurrences of the offenders
and statistical analysis for the random variables in question
the input file generates the
output file.

If you want to see generating functions and growth constants for the
enumerating sequences for compositions avoiding pairs of compositions one of 7, the other 8, of the same length
(both 2 and both 3) and statistical analysis for the random variables in question
the input file generates the
output file.
Personal Journal of Shalosh B. Ekhad and Doron Zeilberger
Doron Zeilberger's Home Page