The Symbolic Goulden Jackson Cluster Method

Xiangdong Wen

1. Introduction

Let V and B be a finite alphabet and a finite set of bad words respectively. Suppose a(n) is the total number of words with length n that avoid the bad words in B as factors. The aim is to find the generating function

f(s) = ∑_{n=0}^{∞} a(n)s^{n}  (1)

in an efficient way.

The Goulden-Jackson cluster method[GoJ1,GoJ2] has been beautifully explained, extended, and implemented by J. Noonan and D. Zeilberger([?]). The Goulden-Jackson cluster method needs to solve a system of |B| linear equations and it is much more efficient than the Naive approach which needs to solve a system of ∑ |d|^{|v|−1}, v ∈ B, linear equations. However, their Maple packages require that the cardinality of the alphabet is a numeric argument, rather than symbolic. In this paper, I extend the method into the latter case, thereby initiating the Symbolic Goulden-Jackson Method.

2. Review of the Goulden Jackson Cluster method

Recall that a factor of a word w_{1}w_{2} ⋯ w_{n} is any of the words w_{i}w_{i+1} ⋯ w_{j−1}w_{j}, for 1 ≤ i ≤ j ≤ n. Such a factor is represented by [i, j]. Two factors [i, j] and [i′, j′] overlap if they have at least one common letter, i.e. i < i′ ≤ j.

Define the weight of a word w as weight(w) = s^{|w|}, where |w| is the length of w. Obviously, the generating function (1) becomes

f(s) = ∑_{w∈L(B)} weight(w),

where L(B) is the set of all words that avoid the members of B as factors.

A word with some factors marked is called a marked word. Here we only consider the case where the marked factors are the words in B. A marked word could be written in the following form:

(w; [i_{1}, j_{1}], [i_{2}, j_{2}], ⋯, [i_{l}, j_{l}]), where [i_{r}, j_{r}] 1 ≤ r ≤ l, are the marked factors.

For example, let V = {1, 2, 3}, B = {123, 231, 312} and w = 12312. There are 2^{3} marked words for w:

\begin{matrix}(12312; ), & (12312; [1, 3]), & (12312; [2, 4]), & (12312; [3, 5]), \\ (12312; [1, 3], [2, 4]), & (12312; [1, 3], [3, 5]), & (12312, [2, 4], [3, 5]), & (12312; [1, 3], [2, 4], [3, 5]). \end{matrix}

Define the \overline{weight} of a marked word w with marked factors S, where S ⊂ B, as:

\overline{weight}(w, S) = (−1)^{|S|}s^{|w|},

where |S| is the cardinality of S and |w| the length of w.

Let V^{∗} be the set of all words generated by V, and Bad(w) be the set of bad factors in w. We have Theorem 1 :

f(s) = ∑_{w∈L(B)} weight(w) = ∑_{w∈V^{∗}} ∑_{S⊂Bad(w)} \overline{weight}(w, S).  (3)

Proof: The basic idea in the proof is to use the inclusion-exclusion principle. Let N_{B}(w) denote the number of marked factors, that belong to B, of w. Then,

f(s) = ∑_{w∈L(B)} weight(w)
= ∑_{w∈V^{∗}} weight(w)0^{N_{B}(w)}
= ∑_{w∈V^{∗}} s^{|w|}[1 + (−1)]^{N_{B}(w)}
= ∑_{w∈V^{∗}} s^{|w|} ∑_{S⊂Bad(w)}(−1)^{|S|}
= ∑_{w∈V^{∗}} ∑_{S⊂Bad(w)}(−1)^{|S|}s^{|w|}
= ∑_{w∈V^{∗}} ∑_{S⊂Bad(w)} \overline{weight}(w, S)

By the theorem, the calculation of the generating function (1) is then transfered to finding the generating function for the weighted marked words (3), and it is much easier to weight-count by the Goulden-Jackson cluster method.

A cluster is a marked word

(w_{1}w_{2} ⋯ w_{n}; [i_{1}(= 1), j_{1}], [i_{2}, j_{2}], ⋯, [i_{l}, j_{l}(= n)]),

where [i_{k}, j_{k}] overlaps with [i_{k+1}, j_{k+1}], for all k = 1...l − 1.

A marked word is either an empty word, or ends with a letter that is not part of a cluster, or ends with a cluster. Peeling-off the maximal cluster, we get a smaller marked word. So we have the following decomposition:

M = {empty word} ∪ MV ∪ MC.

Taking weight on both sides and solve for \overline{weight}(M) we have,

f(s) = \overline{weight}(M) = \frac{1}{1 − ds − \overline{weight}(C)} .  (4)

The only step left is to find \overline{weight}(C).

For a given word w = w_{1}w_{2} ⋯ w_{n}, let HEAD(w) be the set of all proper prefixes:

HEAD(w) := {w_{1}w_{2} ⋯ w_{k}|k = 1, 2, ⋯, n − 1},

and T AIL(w) be the set of all proper suffixes

T AIL(w) := {w_{k}w_{k+1} ⋯ w_{n}|k = 2, 3, ⋯, n},

and let

OV ERLAP (u, v) := T AIL(u) ∩ HEAD(v).

Let u/v denote the operation of the word u chopping off its head v. For example: 12321/12 = 321. Let

u : v = ∑_{x∈OV ERLAP (u,v)} \overline{weight}(v/x).

The set of clusters C, can be partitioned into

C = ⋃_{v∈B} C[v] ,

where C[v] (v ∈ B), is the set of clusters whose last entry is v.

Given a cluster in C[v], v ∈ B, it either consists of just v, or chopping v results in a smaller cluster in C[u], u ∈ B if OV ERLAP (u, v) is not empty. On the other hand, given a cluster in C[u], we could always reconstitute the bigger cluster in C[v] by adding some words in OV ERLAP (u, v). Hence there exists a bijection:

C(v) ↔ {(v; [1, |v|])} ⋃_{u∈B} C[u]OV ERLAP (u, v).

Taking weights on both sides, we have:

\overline{weight}(C[v]) = (−1) \overline{weight}(v) − ∑_{u∈B} (u : v) \overline{weight}(C[u]).  (5)

This is a system of |B| linear equations with |B| unknowns \overline{weight}(C[v]), v ∈ B.

After solving these equations we could simply obtain \overline{weight}(C) by: \overline{weight}(C) = ∑_{v∈B} \overline{weight}(C[v])

Notice that \overline{weight}(C) is independent of the cardinality of the alphabet, we can see from equation (4) that the symbolic Goulden Jackson could be easily implemented.

3 Symmetric Cases

Given an alphabet V = {1, 2, 3}, let us find the generating function for the number of words which do not have three consecutive different letters as factors, i.e. B = {123, 132, 213, 231, 321}.

By the Goulden-Jackson cluster method, we need set up and solve a system of |B| = 6 linear equations with six unknowns \overline{weight}(C[v]), v ∈ B :

\{ \begin{matrix}\overline{weight}(C[123]) & = & −s^{3} − s^{2} \overline{weight}(C[312]) − s^{2} \overline{weight}(C[321]) − s \overline{weight}(C[231]) \\ \overline{weight}(C[132]) & = & −s^{3} − s^{2} \overline{weight}(C[231]) − s^{2} \overline{weight}(C[213]) − s \overline{weight}(C[321]) \\ \overline{weight}(C[213]) & = & −s^{3} − s^{2} \overline{weight}(C[312]) − s^{2} \overline{weight}(C[321]) − s \overline{weight}(C[132]) \\ \overline{weight}(C[231]) & = & −s^{3} − s^{2} \overline{weight}(C[123]) − s^{2} \overline{weight}(C[132]) − s \overline{weight}(C[312]) \\ \overline{weight}(C[312]) & = & −s^{3} − s^{2} \overline{weight}(C[213]) − s^{2} \overline{weight}(C[231]) − s \overline{weight}(C[123]) \\ \overline{weight}(C[321]) & = & −s^{3} − s^{2} \overline{weight}(C[123]) − s^{2} \overline{weight}(C[132]) − s \overline{weight}(C[213]) \end{matrix} .

By the symmetry of B, all the clusters C[v] have the same generating function \overline{weight}(C). Thus we can reduce these six equations to one equation:

\overline{weight}(C[123]) = −s^{3} − 2s^{2} \overline{weight}(C[123]) − s \overline{weight}(C[123]).

After solving it we have

\overline{weight}(C) = 6 \overline{weight}(C[123]) = \frac{−6s^{3}}{1 + 2s^{2} + s},

and

f(s) = \frac{1}{1 − 3s − \frac{−6s^{3}}{1+2s^{2}+s}} = −\frac{2s^{2} + s + 1}{s^{2} + 2s − 1}.

Assuming the cardinality of the alphabet V changed, V = {1, 2, 3, ⋯ d}, let us find the generating function for the number of words which do not have three consecutive different letters as factors, i.e.

B = {123, 124, 125, ⋯, d(d − 1)(d − 3), d(d − 1)(d − 2)}.

By the original Goulden-Jackson cluster method, we need set up and solve a system of |B| = d(d−1)(d−2) linear equations. Notice the symmetry of B, we only need set up and solve one equation:

\overline{weight}(C[123]) = −s^{3} − (d − 1)(d − 2)s^{2} \overline{weight}(C[123]) − (d − 2)s \overline{weight}(C[123]).

Thus,

\overline{weight}(C) = d(d − 1)(d − 2) \overline{weight}(C[123]) = \frac{−d(d − 1)(d − 2)s^{3}}{1 + (d − 1)(d − 2)s^{2} + (d − 2)s},

and

f(s) = \frac{1}{1 − ds − \frac{−d(d−1)(d−2)s^{3}}{1+(d−1)(d−2)s^{2}+(d−2)s}} = \frac{(−d^{2} + 3d − 2)s^{2} + (−d + 2)s − 1}{(d − 2)s^{2} + 2s − 1}.

In general, if the set of bad words B is invariant under the action of the symmetric group, we could take advantage of the symmetry of B.

Two words u,v are equivalent, u ≡ v, if there exists a permutation λ such that λ(u) = v. By symmetry, all the elements in the equivalence class of v have the same cluster generating function \overline{weight}(C[v]) .

Define the dimension of a letter v, dim(v), as the number of different letters appeared in v. Then the equivalence class of v has \binom{d}{dim(v)} different words.

Suppose the bad words set B is partitioned into different equivalent classes B_{1}, B_{2}, B_{3}, ⋯, B_{k}, and b_{1}, b_{2}, b_{3}, ⋯, b_{k} are the representives respectively. Define (b_{i} : B_{j}) := ∑_{b∈B_{j}}(b_{i} : b), then the system (5) becomes

\overline{weight}(C[b_{i}]) = −\overline{weight}(b_{i}) − ∑_{j=1}^{k}(b_{i} : B_{j})\overline{weight}(b_{j}), i = 1, ⋯, k.  (7)

It is a system of k linear equations with k unknowns \overline{weight}(C[b_{i}]), i = 1, ⋯, k. Remember that k is the number of different equivalent classes in B. Now there are many fewer equations and many fewer unknowns than in the original Goulden-Jackson cluster method, and thus everything is much more efficient. After solving the system, we could obtain \overline{weight}(C) by

\overline{weight}(C) = ∑_{i=1}^{k} \binom{d}{dim(b_{i})}\overline{weight}(C[b_{i}]).  (8)

Given u = u_{1}u_{2}u_{3} ⋯ u_{n}, let H_{i}(u) be the HEAD of u with length i, i.e. H_{i}(u) := u_{1}u_{2} ⋯ u_{i}. Let T_{i}(u) be the TAIL of u with length i, i.e. T_{i}(u) := u_{n−i+1}u_{n−i+2} ⋯ u_{n−1}u_{n}. We have

b_{i} : B_{j} = ∑_{m=1}^{min(|b_{i}|,|b_{j}|)−1} I(T_{m}(b_{i}) ≡ H_{m}(b_{j}))\binom{d}{dim(b_{j}) − dim(H_{m}(b_{j}))}s^{|v|−m},

where

I(T_{m}(b_{i}) ≡ H_{m}(b_{j})) = \{ \begin{matrix}1, & ifT_{m}(b_{i}) and H_{m}(b_{j}) are equivalent , \\ 0, & otherwise. \end{matrix}

In the two examples below, the first can still be done with the unextended Goulden-Jackson, since the number of letters is numeric, 3, but the second one requires the new extension, since the number of letters is d, i.e. a symbol.

Example 1: Let V = {1, 2, 3}. Find the generating function for the number of words which do not have three consecutive different letters or three consecutive same letters as factors, i.e.

B = {123, 132, 213, 231, 312, 321, 111, 222, 333}.

By the symmetry of B we have,

\overline{weight}(C[123]) = \overline{weight}(C[132]) = ⋯ = \overline{weight}(C[321]),

and

\overline{weight}(C[111]) = \overline{weight}(C[222]) = \overline{weight}(C[333]).

Thus by system (5) and equation (8), we have

\{ \begin{matrix}\overline{weight}(C[123]) & = & −s^{3} − 2s^{2} \overline{weight}(C[123]) − s \overline{weight}(C[123]) − s^{2} \overline{weight}(C[111]) \\ \overline{weight}(C[111]) & = & −s^{3} − 2s^{2} \overline{weight}(C[123]) − s^{2} \overline{weight}(C[111]) − s \overline{weight}(C[111]) \end{matrix} ,

and

\overline{weight}(C) = 6 \overline{weight}(C[321]) + 3 \overline{weight}(C[111].

Solving the system, finally we have

f(s) = \frac{1}{1 − 3s − \overline{weight}(C)} = \frac{1}{1 − 3s − [6 \overline{weight}(C[321]) + 3 \overline{weight}(C[111])]} = −\frac{3s^{2} + s + 1}{2s − 1}

Example 2: Let V = {1, 2, 3, ⋯, d}. Find the generating function for the number of words which do not have three consecutive different letters or three consecutive same letters as factors.

By (5) and (8), we have

\{ \begin{matrix}\overline{weight}(C[123]) & = & −s^{3} − (d − 1)(d − 2)s^{2} \overline{weight}(C[123]) − (d − 2)s \overline{weight}(C[123]) − s^{2} \overline{weight}(C[111]) \\ \overline{weight}(C[111]) & = & −s^{3} − (d − 1)(d − 2)s^{2} \overline{weight}(C[123]) − s^{2} \overline{weight}(C[111]) − s \overline{weight}(C[111]) \end{matrix} ,

and

\overline{weight}(C) = d(d − 1)(d − 2) \overline{weight}(C[321]) + d \overline{weight}(C[111]).

Finally, we could obtain

f(s) = \frac{1}{1 − ds − \overline{weight}(C)} = \frac{(−d^{2} + 2d)s^{3} + (−d^{2} + 2d − 1)s^{2} + (1 − d)s − 1}{(d − 1)s^{2} + s − 1}

4 Finite Memory Self-Avoiding Walks

The set of s-called self-avoiding walks could be regarded as a the set of words in the alphabet V = {1, −1, 2, −2, ⋯ }, that avoid, as factors, words with as many i’s as −i’s for each i between 1 and d. In other words, words avoiding the ‘bad words’ in B = {[1, −1], [1, 2, −1, −2] ⋯ } and all their images under the action of group of signed permutations. J. Noonan ([3]) has a detailed discussion about the finite memory self-avoiding walks for the memory up to 8. We have implemented the procedures for symmetric cases under signed permutations too. Using our maple package we could automatically get the formula for the generating functions for 2-step, 4-step and 6-step memory self-avoiding walks. For 8-step memory selfavoiding walk, the package set up a system of 112 linear equations but our own computer was not big enough to solve it.

5. The Maple package

All the procedures are included in the package “SYMBOLIC GJ”, downloadable from the web address: http://www.math.temple.edu/˜ wen/gj/gj/SYMBOLIC GJ . The program takes the cardinality of the alphabet as symbolic input. Moreover it could compute generating functions for the symmetric cases and for the finite memory self avoiding walks.

6. Acknowledgment

This work will be a part of the author’s Ph.D. dissertation, written under the direction of Professor Doron Zeilberger (Rutgers University). I wish to thank Dr. Zeilberger for his generous support and encouragement.

References

[1] [Brinkhuis] J.Brinkhuis, “Non-repetitive sequences on three symbols”, Quart. J. Math, Oxford(2), 145-149, 34(1983).

[2] [Zeilberger] John Noonan and Doron Zeilberger, “ The Goulden-Jackson Cluster Method: Extensions, Applications, and Implementations”, J. Difference Eq. Appl., 355-377. 5(1999),

[3] [Noonan] John Noonan, “ New Upper Bounds for The Connective Constants of Self-Avoiding Walks”, J. Stat. Phys., 871-888. 91(1998),

[4] [CoGuy] J.H. Conway and R.K. Guy, “The book of numbers”, Copernicus, Springer, New York. (1996).

[5] [MS] N. Madras,and G. Slade, “The Self avoiding Walk”, Birkhauser, Boston (1993).

[6] [GoJ1] I. Goulden and D.M. Jackson, An inversion theorem for cluster decompositions of sequences with distinguished subsequences, J. London Math. Soc.(2)20 (1979), 567-576.

[7] [GoJ2] I. Goulden and D.M. Jackson, ”Combinatorial Enumeration”, John Wiley, 1983, New York.

Department of Mathematics, Temple University, Philadelphia, PA 19122. wen@math.temple.edu