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, 2n-1 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