The Goulden–Jackson Cluster Method, and its extensions

The Goulden–Jackson cluster method is a way of using generating functions to enumerate words on an alphabet without certain (specified) forbidden subwords, that was introduced by I. P. Goulden and D. M. Jackson in 1979. For example, if our alphabet is the numbers {0,1}, and our forbidden subwords are {000, 111}, we are interested in the number of 0–1 strings of a specified length that avoid three 0's in a row and three 1's in a row.

For a good introduction, see this paper by Noonan and Zeilberger. In addition to how the process works, this paper covers some of the ways to generalize the method for more complicated weight enumerators, or ways of counting these words that give us more information about the individual letters they contain.

Debbie Yuster and I have expanded the method to look at even more complicated weight enumerators, that give information about the ordered letter pairs and ordered letter triples that these words contain. Our paper is available on the arXiv. In addition, we have implemented our algorithms in a Maple Package called GeneralizedGouldenJackson.

Here is some additional material:

Some basic examples of Goulden–Jackson: .mw, .pdf Some examples using Goulden–Jackson to make a (simplistic) model of the English language as a Markov Chain: .mw .pdf The wordlist we used, to get the input for the English language example. This came from the spell-check dictionary of a Linux system. Extra code used for the English Language examples, for analyzing the word list and creating the matrix of transition probabilites: