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