Automatic Solution of Richard Stanley's Amer. Math. Monthly Problem #11610
and ANY Problem of That Type
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)
Written: Dec. 28, 2012.
Richard Stanely proposed, in a recent Amer. Math. Monthly Problem (Dec. 2011) to prove a nice
explicit formula for the generating function for the number of n-letter words in {H,T} that
have as many occurrences of HT as HH. In this article, we show how to prove this
problem automatically, and ANY problem of that type, regardless of the size of the alphabet
and the length of the two chosen strings.
Maple Packages
-
RPS
A Maple package for solving any problems of the type: "number of n-letter words using an m-letter alphabet
that contain exactly the same number of occurrences as factors of w1 and w2 for
any two different words w1, w2, of the same length.
-
RPSplus
A Maple package for solving any problems of the more general type: "number of n-letter words using an m-letter alphabet
such that a1#w1- a2#w2=r for any positive integers a1
and a2 and r (the former case, dealt by RPS does the special case a1=1, a2=1, r=0)
for any two different words w1, w2 of the same length.
Web-books
-
If you want to see the quadratic equation satisfies by the
ordinary generating function of the sequence enumerating
n-letter words in the two-letter alphabet {1,2} that
contain as many occurrences, as (consecutive) substrings,
of w1 and w2 FOR all pairs of words {w1,w2} of length 2,
as well as linear recurrences and asymptotic formulas for
the enumerating sequence itself,
the
input file
would yield the
output file
-
If you want to see the quadratic equation satisfies by the
ordinary generating function of the sequence enumerating
n-letter words in the two-letter alphabet {1,2} that
contain as many occurrences, as (consecutive) substrings,
of w1 and w2 FOR all pairs of words {w1,w2} of length 3,
as well as linear recurrences and asymptotic formulas for
the enumerating sequence itself,
the
input file
would yield the
output file
-
If you want to see the quadratic equation satisfies by the
ordinary generating function of the sequence enumerating
n-letter words in the two-letter alphabet {1,2} that
contain as many occurrences, as (consecutive) substrings,
of w1 and w2 FOR all pairs of words {w1,w2} of length 4,
as well as linear recurrences and asymptotic formulas for
the enumerating sequence itself,
the
input file
would yield the
output file
-
If you want to see the quadratic equation satisfies by the
ordinary generating function of the sequence enumerating
n-letter words in the two-letter alphabet {1,2} that
contain as many occurrences, as (consecutive) substrings,
of w1 and w2 FOR all pairs of words {w1,w2} of length 5,
as well as linear recurrences and asymptotic formulas for
the enumerating sequence itself,
the
input file
would yield the
output file
-
If you want to see the quadratic equation satisfies by the
ordinary generating function of the sequence enumerating
n-letter words in the three-letter alphabet {1,2,3} that
contain as many occurrences, as (consecutive) substrings,
of w1 and w2 FOR all pairs of words {w1,w2} of length 2,
as well as linear recurrences and asymptotic formulas for
the enumerating sequence itself,
the
input file
would yield the
output file
-
If you want to see the quadratic equation satisfies by the
ordinary generating function of the sequence enumerating
n-letter words in the three-letter alphabet {1,2,3} that
contain as many occurrences, as (consecutive) substrings,
of w1 and w2 FOR all pairs of words {w1,w2} of length 3,
as well as linear recurrences and asymptotic formulas for
the enumerating sequence itself,
the
input file
would yield the
output file
-
If you want to see the quadratic equation satisfies by the
ordinary generating function of the sequence enumerating
n-letter words in the four-letter alphabet {1,2,3,4} that
contain as many occurrences, as (consecutive) substrings,
of w1 and w2 FOR all pairs of words {w1,w2} of length 2,
as well as linear recurrences and asymptotic formulas for
the enumerating sequence itself,
the
input file
would yield the
output file
-
If you want to see the quadratic equation satisfies by the
ordinary generating function of the sequence enumerating
n-letter words in the four-letter alphabet {1,2,3,4} that
contain as many occurrences, as (consecutive) substrings,
of w1 and w2 FOR all pairs of words {w1,w2} of length 3,
as well as linear recurrences and asymptotic formulas for
the enumerating sequence itself,
the
input file
would yield the
output file
-
If you want to see the quadratic equation satisfies by the
ordinary generating function of the sequence enumerating
n-letter words in the four-letter alphabet {1,2,3,4,5} that
contain as many occurrences, as (consecutive) substrings,
of w1 and w2 FOR all pairs of words {w1,w2} of length 2,
as well as linear recurrences and asymptotic formulas for
the enumerating sequence itself,
the
input file
would yield the
output file
-
If you want to see the quadratic equation satisfies by the
ordinary generating function of the sequence enumerating
n-letter words in the five-letter alphabet {1,2,3,4,5} that
contain as many occurrences, as (consecutive) substrings,
of w1 and w2 FOR all pairs of words {w1,w2} of length 3,
as well as linear recurrences and asymptotic formulas for
the enumerating sequence itself,
the
input file
would yield the
output file
-
If you want to see the quadratic equation satisfies by the
ordinary generating function of the sequence enumerating
n-letter words in the six-letter alphabet {1,2,3,4,5,6} that
contain as many occurrences, as (consecutive) substrings,
of w1 and w2 FOR all pairs of words {w1,w2} of length 2,
as well as linear recurrences and asymptotic formulas for
the enumerating sequence itself,
the
input file
would yield the
output file
-
If you want to see the quadratic equation satisfies by the
ordinary generating function of the sequence enumerating
n-letter words in the six-letter alphabet {1,2,3,4,5,6} that
contain as many occurrences, as (consecutive) substrings,
of w1 and w2 FOR all pairs of words {w1,w2} of length 3,
as well as linear recurrences and asymptotic formulas for
the enumerating sequence itself,
the
input file
would yield the
output file
Personal Journal of Shalosh B. Ekhad and Doron Zeilberger
Doron Zeilberger's Home Page