SymUGJ: A Maple package that finds Umbral Schemes
for enumerating words that avoid as factors
an infinite family of parametrized "mistakes"
where the set of mistakes is symmetric w.r.t. permuting letters
It is one of the packages that accompany Doron Zeilberger's article:
The Umbral Transfer Matrix Method. V. The Goulden-Jackson
Cluster Method for Infinitely Many Mistakes
Please report bugs to zeilberg@math.temple.edu
``
Created: May 2001
This version: May 2001
``
Written by Doron Zeilberger, zeilberg@math.temple.edu
``
Please report bugs to zeilberg@math.temple.edu
``
The most current version of this package and paper
are available from
http://www.math.temple.edu/~zeilberg/
For a list of the procedures type ezra(), for help with
a specific procedure, type ezra(procedure_name)
This is a sample example for SymUGJ
This is a simple example of an Umbral Scheme for
for generating functions for enumerating words in {1,2,3}
that avoid any factor of the form
1^(a+1)2^(a+1)3^(a+1) , for all a>=0
and its five permutations, in other words you can't
have 3 consecutive blocks of all 3 letters of the same length
The Umbral Scheme is
3 2
t 2 F[1](1) t
[F[1](x[1]) = - ------------ - --------------------------- - F[1](t x[1]) t
3 3 2
-t x[1] + 1 (t x[1] - 1) (t x[1] - 1)
2 4
2 F[1](t x[1]) t x[1]
+ ---------------------------], [6]
3 2
(t x[1] - 1) (t x[1] - 1)
Using this Umbral Scheme, the first 30 terms of the
generating function are
[1, 3, 9, 21, 51, 123, 291, 681, 1599, 3753, 8799, 20631, 48363, 113373, 265791,
623103, 1460769, 3424569, 8028393, 18821415, 44124129, 103442697, 242506653,
568522251, 1332819249, 3124604547, 7325189409, 17172861033, 40259321709,
94382233551, 221265675429]
The whole thing took, 0.355, minutes of CPU time