Counting Clean Words According to the Number of Their Clean Neighbors
By Shalosh B. Ekhad and Doron Zeilberger
.pdf
.tex
Written: April 21, 2023
Dedicated to the memory of Marko Petkovsek (1955-2023)
We extract brilliant ideas of Sandi Klavzar, Michel Mollard, and Marko Petkovsek who used them to solve one very specific enumeration problem, namely
counting the number of words in the alphabet {0,1} of length n avoiding two consecutive ones, and having exactly k such neighbors, to a much more
general setting where one has any (finite) alphabet, and any (finite) set of forbidden words. More important, we fully
implement it in Maple.
Also appeared in Vol. 57, No. 1, Issue 223, March 2023, of ACM Communication in Computer Algebra,
Maple package
Sample Input and Output for Marko.txt
If you want to see bivariate generating function in x,y, such that coeff. of xn ym is the
number of words of length n in the alphabet {0,1} avoiding the pattern [1,...1] (1 repeated i time) and
having exactly m neighbors (i.e. Hamming distance 1) with that property, for i=2 to i=6
the input gives the
output.
If you want to see bivariate generating function in x,y, such that coeff. of xn ym is the
number of BINARY words of length n in the alphabet {0,1} avoiding the patterns {[1,...1],[0,...0]} (1 and 0 repeated i times, respectively) and
having exactly m neighbors (i.e. Hamming distance 1) with that property, for i=2 to i=6
the input gives the
output.
If you want to see all such generating functions (still with BINARY words) for all possible SINGLE patterns of length 3,4,5 (up to symmetry)
the input gives the
output.
If you want to see all such generating functions for all possible DOUBLE patterns of length 3,4,5 (
up to symmetry), still with BINARY words
the input gives the
output.
If you want to see all such generating functions for all possible TRIPLE patterns of length 3,4 (up to symmetry), still with BINARY words
the input gives the
output.
If you want to see all such generating functions (now with TERNARY words) for all possible SINGLE patterns of lengths 2, 3,4 (up to symmetry)
the input gives the
output.
If you want to see all such generating functions (now with TERNARY words) for all possible DOUBLE patterns of lengths 2, 3 (up to symmetry)
the input gives the
output.
Personal Journal of Shalosh B. Ekhad and Doron Zeilberger
Doron Zeilberger's Home Page