| The Umbral Transfer-Matrix Method. V. The Goulden-Jackson Cluster Method for Infinitely Many Mistakes, this article (2009) | |||||||||||||||
Abstract | |||||||||||||||
| This is the fifth, and last, installment of the saga on the Umbral Transfer-Matrix method, based on Gian-Carlo Rota’s seminal notion of the umbra. Here we extend the powerful Goulden-Jackson Cluster method, that enables one to compute generating functions enumerating words that avoid, as factors, any given finite set of “mistakes”, to the case where there are infinitely many mistakes. This infinite set of mistakes should be a union of finitely many finite-parameter families, given symbolically in frequency notation. We illustrate the method by introducing a new ‘toy model ’ for self-avoiding walks, that is much more interesting and complex than finite-memory approximations, yet much simpler than the (probably intractable) “real thing”. Required Reading The reader is expected to be familiar with [Z1], and the classical Goulden-Jackson Cluster Method ([GJ1],[GJ2]), lucidly described in [NZ]. How Likely is a Monkey to Type YHVH? It is a sin to utter the name of the Lord in vain, or even to have it written down, or printed, except in a holy text. Ignoring spaces, it is also bad luck to have the letters Yod, Heh, Vav, Heh consecutively. The classical Goulden-Jackson Cluster Method answers the following question. What is the probability that a random word will not contain, consecutively, the word YHVH?. | |||||||||||||||
Publication details | |||||||||||||||
| |||||||||||||||